Uolevi saapui neliön muotoiseen puistoon ja päätti kulkea koko puiston läpi. Puiston sisäänkäynti on vasemman yläkulman ruudussa ja uloskäynti on vasemman alakulman ruudussa. Uolevi voi liikkua kerrallaan askeleen vasemmalle, oikealle, alaspäin tai ylöspäin. Montako mahdollisuutta Uolevilla on käydä tasan kerran jokaisessa ruudussa?
Esimerkiksi jos puiston koko on 5x5, yksi mahdollinen reitti on seuraava:
Ensimmäiset tulokset tehtävään ovat:
| ruudukon koko | reittien määrä |
|---|---|
| 1x1 | 1 |
| 2x2 | 1 |
| 3x3 | 2 |
| 4x4 | 8 |
| 5x5 | 86 |
Tehtäväsi on laatia ohjelma, joka laskee reittien määriä suuremmille ruudukoille. Saat kurssille TMC-pisteitä lisää n–3, jossa n on suurimman laskemasi ruudukon koko (ja vähintään 6). Esimerkiksi jos pystyt laskemaan tapauksen 8x8 reittien määrän, saat 5 TMC-pistettä lisää.
Palauta ratkaisusi viimeistään su 26.10. lähettämällä sähköpostiviesti osoitteeseen ahslaaks@cs.helsinki.fi. Kirjoita viestiin nimesi, opiskelijanumerosi, suurin laskemasi ruudukon koko ja tätä vastaava reittien määrä. Liitä lisäksi käyttämäsi koodi viestin liitteeksi.
Huom! Toisin kuin kurssin TMC-tehtävissä, tässä tehtävässä ei ole tiukkaa aikarajaa, vaan kysymys on siitä, kuinka suuren tuloksen pystyt laskemaan deadlinen puitteissa... Mutta tehokas algoritmi on silti suositeltava, koska reittien määrä kasvaa nopeasti ruudukon koon suurentuessa.
Voit käyttää tehtävän ratkomiseen mitä tahansa ohjelmointikieltä, eli Java ei ole pakollinen.