Quote:
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.