Коридор имеет размеры 3*N. Для любого заданного N, необходимо определить максимальное количество различных вариантов, которыми можно уложить паркет в этом коридоре плитками размером [1*2] или [2*2] (сами варианты укладки паркета определять не надо).
Например для N=2, ответом будет 5.

Это сообщение отредактировал(а) Jilian - 15.2.2006, 20:53

Посмотри тут
http://forum.vingrad.ru/index.php?showtopic=83500

А зачем мне числа Фибоначчи? О них и Вирте почитать можно -)

Не понял?
там числа фибоначи и рекурсия. А тут ищем кол-во.
Составить ф-ю и максимизировать её. Только вот с функцией проблемма.

Так ведь и ёжику понятно, что функцию надо составить. Только вот я никак не могу её составить. Ясно, что функция рекурсивная, но не все что рекурсия, есть числа Фибоначчи, с таким же успехом Вы могли дать мне ссылку на Ханойские башни.
Нет, в данной задачи Фибоначчи не поможет -)

Решим сначала задачу.

Нужно замостить 1*х метров с помощью досок длиной 1*2 и 1*8

Решается с помощью динамического программирования.


Обозначим черех Ф(Х) количество способов замостить доску размером 1*х


очевидно, что
Ф(х)=Ф(х-2)+Ф(х-8)

Ф(1)=0
Ф(2)=1
Ф(3)=0
...
Ф(8)=2

вот уравнение решая которое находим ответ.


Ваша задача решаеться аналогичной техникой. Подумайте как

Ты сказал "не могу разобраться с рекурсией" вот я тебе и дал ссылку. Видимо с рекурсией проблем у тебя нет. Так может в след. раз ты поумнее название темы придумаешь?

А так мысли такие:

Вроде даже без рекурсии...

А хотя нет, над правой стороной

надо еще подумать...
Может так:

Я все не могу посчитать в ручную сколько же комбинаций для N = 6...

Но еще думаю, что тут можно все таки без рекурсии...
Добавлено @ 23:08
А может и нельзя... Я в полной прострации...

Во, еще мысля… Первые три числа для N=2,4,6 это помоему 5, 30, 139… Думаю, что можно теперь рекурсивно искать результат и для N=8 будет что-нибудь типа
результат = результат(6)+результат(2)…

Интересно это имел в виду esperant0. Лично ему дам плюс если просветит меня в

во-первых, нужно свести ситуацию на n-м шаге к ситуации на n-1
раскладывать плитку будем по столбикам (3 ячейки)
будем считать, что все кроме последнего столбика полностью покрыты
а то, что творится в последнем, бывает 8-ми видов (каждая ячейка может быть покрыта или нет)
рисовать все 8 ситуаций тут не буду - условимся, что номер ситуации в двоичное представлении имеет 1 там, где ячейка покрыта, и 0 там, где - нет
0 соответствует полностью непокрытому столбику
7 - полностью покрытому
1 - в котором одна крайняя ячейка покрыта и все
2 - центральная
и т.д.
теперь введем функцию - f(n,m) - количество способов разложить плитку так, чтобы n-1 столбик был покрыт полностью, а код ситуации в n-м столбике был m
таким образом стоит задача найти f(N,7)
выразим f(n,m) через ее значения на n-1 м шаге:
f(n,0)=f(n-1,7)
f(n,1)=f(n-1,6)
f(n,2)=f(n-1,5)
f(n,3)=f(n-1,7)+f(n-1,4)+f(n-1,4)
f(n,4)=f(n,1) //из-за симметрии
f(n,5)=f(n-1,2)
f(n,6)=f(n,3) //из-за симметрии
f(n,7)=3*f(n-1,0)+2*f(n-1,3)

удобнее рассмотреть соотношения этой функции не между соседними шагами, а между шагами через один - оно и понятно, на нечетных N у нас ответ и так 0
если все это дело подставить и упростить, получатся такие соотношения:

f(n,7)=5*f(n-2,7)+4*f(n-2,1)
f(n,1)=1*f(n-2,7)+2*f(n-2,1)

которые и представляют решение задачи...
Добавлено @ 02:01
теперь о том, как убрать рекурсию и соптимизировать (а другой причины убирать рекурсию тут и нету)
в том виде, в котором сейчас записано решение, количество вычислений будет расти экспоненциально при увеличении n
это почти всегда неприемлимо (исключение составляют учебные задачи, да и то не все )
первая оптимизация - динамическое программирование
в данном контексте (да и во многих других) оно может быть описано так "не нужно по нескольку раз пересчитывать одни и те же значения"
в нашем случае пересчет получается потому, что например f(n-2,7) нужно вычислять и при вычислении f(n,7), и при вычислении f(n,1)
это - нехорошо, лучше завести переменную, вычислить один раз f(n-2,7) и записать его туда
выразить это можно, например, с помощью умножения матрицы на вектор:

тут все хорошо видно - 4 операции (неважно каких) на шаг от n-2 до n
общее количество таких операций растет линейно с увеличением n
такая скорость роста вполне приемлима в большинстве задач...

maxim1000, а для n=6 можно увидеть развертку рекурсии? (если честно я пока ничего не понял )

но это не означает, что дальше оптимизировать некуда
динамическое программирование - довольно общий метод, а у нас специфическая ситуация - на каждом шаге мы производим не просто операции, а линейные операции
если переписать все это в виде матричной арифметики, то получим:
x(n)=A*x(n-2)
где:
x(n)=стобец( f(n,7), f(n,1) )
A - матрица:
(5 4)
(1 2)
так что можно заменить это на
x(n)=A(n)*x(0)
здесь A(n) - A в n-ой степени
вся суть оптимизации состоит в том, что для вычисления n-ой степени матрицы достаточно не n операций, а log n...
делается это, как обычно рассказывают для вычисления целой степени числа:
если n четное - A(n)=sqr(A(n/2))
иначе - A(n)=A*sqr(A((n-1)/2))
ну и A(1)=A
на каждом шаге n уменьшается в 2 раза, количество операций - логарифмическое...

где-то тут я описывал подобные манипуляции с вычислением чисел Фибоначчи...
Добавлено @ 02:16

забыл начальные значения:
f(2,7)=5
f(2,1)=1
тогда получаем:
f(4,7)=5*5+4*1=29
f(4,1)=1*5+2*1=7

f(6,7)=5*29+4*7=173
f(6,1)=1*29+2*7=43

кстати, то, что оно не совпадает с

наводит на мысль, что там могла быть ошибка
если это так - она, скорее всего, в уравнениях, которые связывают n-1-й и n-й шаги
с несколько меньшей вероятностью - в процессе подстановки и упрощения выражений при сведении к связи n-2-го b n-го шагов...

в самом принципе, как мне кажется, ошибки нет - там все достаточно просто...

Если говорить о матричной арифметике, то для больших n, асимптотически верное решение проще получить найдя предварительно наибольшее собстеввное число матрицы, ведь возводить его в степень п, куда удобней чем саму матрицу. И на лицо ассимптотика роста

там это где? Я вручную пытался посчитать...

Да я вообще логоки не понял пока...

Дело в том, что эту задачу надо ОБЯЗАТЕЛЬНО решить рекурсивно. А с рекурсией я не могу разобраться конкретно в этой задаче. Так что не надо осуждать моё название, ОК? -)
Спасибо всем большое за посты. Сейчас со всем ознакомлюсь. Ясно, что при нечетных N решений не будет. Но уже при N=4, таких плиток много... Сегодня на лекциях сидела рисовала... Проверить правильность сложно...

2 cardinal
Не "сказал", а "сказала". -)
Добавлено @ 20:40


допустим 0 - ничего нету, 1 - это кусочек плитки 2Х1, а 2 - кусочек плитки 2Х2
2 0 1 0 1 0
2 2 1 1 0 0
0 2 0 1 0 1
(1) (2) (3) (4) (5) (6)

Вопросик:
зачем же нам 7-я и 8-я ситуации?
1
0
1 (7)
это невозможная ситуация, т.к. при её создании укладку нельзя завершить
а рассматриваение
0
0
0 (8)
на мой взгляд не имеет смысла

Это сообщение отредактировал(а) Jilian - 16.2.2006, 20:29

Пардон.

а какая разница, кусочек какой плитки покрывает ячейку
важно покрыта она или нет


да, нельзя, просто упомянул ее для полноты в начале рассуждения
а потом, когда выписывались выражения для интересующих нас ситуаций эти не участвовали...


опять же чисто для удобства, в конце она пропадает...

просто если ее не рассматривать, придется сразу выводить соотношения между n-2-м и n-м шагами... возможно, это даже и лучше, но тогда я рассуждал через сотношения между n-1-м и n-м шагами...

в конце концов, можно посмотреть на

не обращая внимания на промежуточный этап
может, так даже и проще получится
рассуждения не всегда получается сразу вести кратчайшим путем


логика простая - выделяем несколько последних операций так, чтобы количество способов ожно было легко посчитать (в данном случае я пошел по столбикам), а все остальное сводим к решению задачи для меньших n...

Но дело еще в том, что прога должна пройти по времени и сложности алгоритма... Т.к. прогу проверяет не препод, а система.

Вот правильное решение:

Интересно, а как оценить сверху чисто таких расстановок плиток?