Programiranje 1

Na kolesarski stezi na Večni poti so se te dni pojavile nove ovire.

Na Oddelek za gospodarstvo in motorni promet MOL smo vprašali, če niso tokrat morda vendarle pretiravali, saj je tole nemogoče zvoziti. Prejeli smo naslednji izgovor:

Skrb za varnost kolesarjev je prioriteta našega oddelka. (Pomembnejša nam je samo še čim večja pretočnost motornega prometa in zadostno število parkirišč.) Ovire na kolesarski poti pa niso namenjene zgolj varnosti kolesarjev, temveč tudi vevericam.

Te prikupne male živalice morajo nekako prečkati kolesarsko pot. Ker pa se bojijo hoditi po tleh, to počnejo tako, da skačejo iz ovire na oviro.

• Po vsaki oviri, na katero pride, steče na desno, čisto do konca ovire.
• Nato se ozre po primerni oviri, na katero lahko skoči. Veverice vedno skačejo na polja, ki so desno od trenutnega. Nikoli torej skočijo na polje, ki je nad ali pod trenutnim, ali celo na polje, ki je levo.
• Veverica lahko skoči eno enoto daleč. Pri tem lahko skoči iz vogala na vogal. Možni skoki so na sliki.
• Da prečka kolesarsko, mora priti do ovire, ki se dotika desnega roba kolesarske ali pa je od njega oddaljena eno polje, saj lahko veverica le-to preskoči.

Na MOL se zavzemamo za strpno sobivanje vseh soudeležencev v prometu, vključno z vevericami.

Obvezna naloga

Ovire so tokrat podane v preprostem seznamu trojk (y, x0, x1). Takšne oblike smo že vajeni.

Tokrat bomo izjemoma poenostavili argumente funkcij tako, da seznam ovir ne bo podan kot argument funkcije, temveč bo zapisan v globalnem seznamu z imenom ovire.

Napiši naslednje funkcije:

• mozen_skok(x, y, ovira) vrne True, če lahko veverica, ki je na polju x, y, skoči na podano oviro. Če skok ni možen, vrne False. (Ta funkcija naj ne uporablja seznama ovire - ker ga nima za kaj rabiti).

  Ta funkcija je sicer čisto kratka, a je lahko presenetljivo zoprna. Testi se jo trudijo temeljito pretestirati, vseeno pa je možno, da bodo spregledali kako napako, ki se bo lahko izkazala šele v prihodnjih funkcijah.

• mozne_ovire(x, y) prejme koordinate nekega polja, na katerem se nahaja veverica. Funkcija vrne vse ovire iz seznama ovire, na katere lahko skoči. (Ne vznemirjaj se, če to polje morda ni na nobeni oviri.)

• obstaja_pot(ovira) vrne True, če lahko veverica, ki se nahaja na podani oviri, prečka kolesarsko stezo. Če pot ni možna, naj vrne False. Polje bo morda na kaki oviri na levi strani, morda pa bo že sredi kolesarske. Ovira je podana kot terka (y, x0, x1).

Toplo priporočam, da zadnjo funkcijo napišete rekurzivno, saj bo tako veliko lažje, kot če poskušate kaj drugega. Prvi dve pa naj bosta "normalni".

Dodatna naloga

Veverica ima na koncu ovire pogosto izbiro, kam skočiti naprej.

Napiši funkcijo stevilo_poti(ovira), ki pove, na koliko načinov lahko veverica, ki stoji na podani oviri, doseže desno stran kolesarske, to je, na koliko načinov lahko pride do kake ovire, ki se bodisi drži desnega roba bodisi je od njega oddaljena za 1. Če pot ni možna, seveda vrne 0.

Nekaj primerov je na sliki. Upoštevaj, da obsega modra pot štiri načine (od kateri se dva končata na istem mestu).

Rjava pot pokriva 16 načinov:

• Do ovire (16, 17) lahko pride na 4 načine (tako da gre naravnost, naredi drugi ovinek, naredi prvi ovinek ali pa naredi oba ovinka).
• Tudi do ovire (15, 16) pride na štiri načine. Če gre odtod na modro pot, se vsak od teh nadaljuje na dva načina, kar bo torej naneslo, skupno, 8 načinov.
• Če pa že v začetku krene gor, na modro, se to konča s 4 možnimi načini.

Tale opis samo kaže, kako je treba razumeti število načinov. Pri programiranju najbrž ne bo potrebno ničesar množiti, temveč samo seštevati. Rešitev je skoraj enaka rešitvi obvezne naloge.

Testi