?

Log in

 
 
15 March 2006 @ 04:58 pm
Кстати, о задаче.  
Вчера-с обещал выложить условие, выкладываю.
Ситуация какая.
Есть некое поле размером 5х3 клеток.
1,12,13,14,15,1
1,22,23,24,25,2
1,32,33,34,35,3

Каждая из этих 15 клеток может принимать значение от 0 до 5 (предположим пока так), назовём их "fruits".
У нас определено 15 кривых (назовём это множеством Lall), каждая из которых проходит только через 5 клеток игрового поля. Т.е. в общем виде координаты кривых выглядят как [(1, k), (2, k), (3, k), (4, k), (5, k)].

Дальше, у нас есть некая таблица, описывающая набор комбинаций из fruits. Например, комбинации (1, 1, 1), или (4, 4, 4, 4). Всего таких комбинаций 11.

Теперь, собственно, сама задача.
На входе есть набор комбинаций C. Так же есть некий набор линий L (подножество множества Lall ).
1<= sizeof(C) <= sizeof(L).
Проблема состоит в том, чтобы разместить все комбинации C на поле, при чём таким образом, чтобы комбинации располагались на линиях из множества L, на одной линии было бы не более одной комбинации, и комбинация идущая вдоль одной линии не прерывалась.

upd: в множестве C комбинации могут повторяться, т.е. он может иметь вид [(1, 1, 1), (4, 4, 4, 4), (1, 1, 1)]

Надеюсь, понятно объяснил. Если нет -- задавайте вопросы :D
 
 
 
Диггер, поверхностный.diggya on March 16th, 2006 08:58 am (UTC)
Re: Чую бесовщину...
В тридовом отображении работать проще.
Итак, базовое.
1. У нас есть например 2 комбинации из двойки и 9 комбинаций, срабатывающих с тройки (в сумме 11)
2. На каждой линии у нас может быть 13 комбинаций (11 базовых, и две которые могут еще влезть)
3. А вот здесь я как раз соврал вчера. Всего может быть 13^15 комбинаций (это максимум, который можно уменьшить может быть на порядок если выбрасывать невозможные к выпадению варианты, может быть на два)
4. Если мы учитываем что например мощность L=4 комбинаций в максимуме будет 13 * 13 * 13 * 13 = 28561 Гыгы, это очень немного. Правда таких комбинаций будет 15*14*13*12*11*10*9*8*7*6*5*4 = 217945728000.

Пока что мысли закончились. Теперь встречный вопрос. Можно ли использовать на вход множество L?
Кстати расстановка вариантов типичная переборная задача, если я правильно помню даже доказанно переборная. :(
Festerfester_ua on March 16th, 2006 09:42 am (UTC)
Re: Чую бесовщину...
Что значит "можно ли использовать на вход множесто L"?
Я пока склоняюсь к перебору, но мне это решение не нравится ни в какую. Даже если ограничивать условия перебора, то можно получить полную ж. при генерации комбинаций в реал-тайме.
Диггер, поверхностный.diggya on March 16th, 2006 10:18 am (UTC)
Не так уж и много.
28 килокомбинаций. Реалтайм всё равно секундами меряется.