Полигони

[Bibi]

Според мен този начин е ясен и трябва само да се изброи по-внимателно. Но също е ясно, че не е ефективен.
Май е по-добре да се замислим за съвсем различни подходи.

[MitkoS]

Докато мислим за различния подход, да питам какво точно е условието според вас на тази задача по-долу ?
Знам официалния отговор и той по никакъв начин не съвпада с решението на това което си превеждам като условие.

How many ways are there to cover a 2 x n rectangular grid with 2 x 1 tiles?

[Bibi]

По колко начина можеш да покриеш правоъгълника с плочки за домино. Така го разбрах аз.

[MitkoS]

И аз така го разбрах.

Само че, официалния отговор е редицата на Фибоначи без първата единица
n=1,2,3,4,5,6
брой=1,2,3,5,8,13,...

А за това което аз и ти сме разбрали, бройката е друга (ако не бъркам нещо)

[Bibi]

А според мен е вярно. За първите 5 случая го проверих. Следва индукция.
Ако знаем всички решения за n, можем да ги разделим на две групи - такива, които започват с една изправена, и такива, които започват с две легнали.
Броят на решенията от първия вид е f(n-1), а вторите - f(n-2).
Значи f(n) = f(n-1) + f(n-2)