Programozás

[Valezius]

Originally Posted by Redback

2009/2010-es OKTV-ről két feladatra lennék kíváncsi :

1. Írj programot (jarda.pas, …), amely kiszámítja, hogy hány féleképpen lehet kikövezni egy 2*N egység méretű járdát 1*1 és 1*2 méretű lapokkal!

Nekem az jött ki, hogy ezt rekurzióval kell megcsinálni.

Ezután egy 2*N-es járdát úgy számolnék ki, hogy a vágósíkokat végigfuttatnám rajta.
Először felteszem, hogy 1+N-1 -re van szétvágva, aztán 2+N-2-re és így tovább.

A gond, hogy ezeket nem lehet összeadni, mert van közte átfedés.
De mindenképp úgy számolnék, hogy letenném a vágósíkokat minden lehetséges módon, aztán csak össze kell adogatni az eredményt.

Az egyes szétvágott daraboknak olyannak kell lennie, hogy belül már ne legyen vágósík. Ez akkor van, ha egy darab 1 széles (2elrendezés) vagy 2 széles (3 elrendezés) vagy 2x széles ekkor megint 2 elrendezés van.

Vagyis az N-et fel kell osztani minden lehetséges módon 1,2,4,6,8... összegére. A sorrend is számít.
De ezt leprogramozni nem tűnik vészesnek.

Például a 2x2-esnél ha nincs felosztva az 3 elrendezés, ha fel van, akkor még 2*2 és kijön a 7.

2x3-asnál 1+1+1 , 1+2, 2+1 a lehetséges sorrendek, szépek ki lehet számolni, hogy ez 2*2*2+2*3+3*2=20 lefedést jelent.