ACM RTK - 2. skupina

Potenciranje

Predstavljajmo si zelo preprost, zbirniku podoben programski jezik. Program je sestavljen iz zaporedja ukazov; pred vsakim ukazom je lahko še oznaka (labela), na katero se lahko sklicujemo pri pogojnih skokih. Dovoljeni ukazi so naslednji:

• ADD x, y - izračuna vsoto x+y in jo shrani v x;
• SUB x, y - izračuna razliko x-y in jo shrani v x;
• MUL x, y - izračuna zmnožek x*y in ga shrani v x;
• DIV x, y - izračuna celi del količnika x/y in ga shrani v x;
• MOD x, y - izračuna ostanek po deljenju x z y in ga shrani v x;

Opomba: pri gornjih ukazih mora biti x spremenljivka, y pa je lahko spremenljivka ali celoštevilska konstanta.

• JL x, y, z - pogojni skok: če je x < y, skoči na ukaz z oznako (labelo) z. Pri tem sta x in y lahko spremenljivki in/ali celoštevilski konstanti. Če pogoj x < y ni izpolnjen, se izvajanje nadaljuje z naslednjim ukazom.

Program lahko uporablja poljubno mnogo spremenljivk. Vse spremenljivke so celoštevilske (kot tip int oz. integer, le da lahko za razliko od teh tipov hranijo poljubno velika cela števila) in jih pred uporabo ni treba posebej deklarirati. Ukazi se izvajajo po vrsti, razen če pride do pogojnega skoka (ukaz JL).

V tem programskem jeziku napiši program, ki izračuna vrednost a^b in jo shrani v spremenljivko c. Pri tem je b naravno število. Primer: če je pred začetkom izvajanja tvojega zaporedja ukazov v spremenljivki a vrednost 2, v spremenljivki b pa vrednost 3, mora biti na koncu izvajanja tvojega programa v spremenljivki c vrednost 8. Tvoj program naj pri tem izvede čim manj ukazov za velika števila a in b.

Svojo rešitev tudi dobro utemelji in komentiraj, kako in zakaj deluje.

Spomnimo se, da je b-ta potenca števila a definirana takole:

a^b = a * a * ... * a  ,

kjer je število pomnoženih a-jev b (b členov) in da za potence med drugim velja

a^b+c = a^b * a^c   .

Namig: najprej razmisli, kako bi učinkovito računal a², a⁴, a⁸, a¹⁶ itd., nato pa še o tem, kako bi s tem prišel do rešitve za poljuben b.

Za ilustracijo je tule primer programa, ki rešuje malo drugačen problem: v spremenljivki vsota izračuna vsoto števil od 1 do n (ob predpostavki, da je n večji od 0):

Pa še en primer: spodnji program računa isto vsoto, vendar namesto zanke uporabi formulo 1 + 2 + ... + n = n * (n + 1)/2.