Matematické Fórum

Máme osít N záhonů. Na každém záhonu může být buď mrkev nebo petržel, avšak nikdy nesmí být žádné dva sousední záhony osety petrželí. Sestavte program, který ze standardního vstupu přečte počet záhonů N a na standardní výstup vypíše číslo P, kde P je počet různých přípustných osetí.

Snažte se o efektivní výpočet. Vstupní číslo N nesmí být větší než 44. Pro výpočty použijte typ longint.

Nemohu přijít na kombinatorické řešení tohoto problému, nemohli byste mě navést? Vždycky se nějak zacyklím. Naprogramování už tím pádem bude poměrně snadné, ale matematicky to nevyřeším, takže s tím nepohnu.

Pro N=1 jsou to 2 možnosti, pro N>1 je to 1 (samé mrkve) + N (jedna petržel) + nějaký wombo combo pro 2 až nějakej Z počet mrkví

předem díky.