Коридор имеет размеры 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, асимптотически верное решение проще получить найдя предварительно наибольшее собстеввное число матрицы, ведь возводить его в степень п, куда удобней чем саму матрицу. И на лицо ассимптотика роста

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