Deklaratív programozás

1. SML kis házi feladat

V1.0, 2006. október 7.

A feladat

Monotonnak nevezünk egy (vezető nullákat nem tartalmazó) természetes számokból álló sorozatot, amelyben ha az első elem nem kisebb a másodiknál, akkor a második sem kisebb a harmadiknál, a harmadik sem a negyediknél s.í.t., ha pedig az első elem nem nagyobb a másodiknál, akkor a második sem nagyobb a harmadiknál, a harmadik sem a negyediknél s.í.t. Pontosítva: Természetes számok egy a₀, a₁, ..., a_n-1 sorozata monoton, ha a₀ > 0, és vagy a_i ≥ a_i+1, vagy a_i ≤ a_i+1, minden 0 ≤ i ≤ n-2-re. Példák monoton sorozatokra: 2 2; 7 4 3; 5 4 4 3 2 2; 4 3 2 2 2 1. Ellenpéldák: 1 5 4; 4 2 5 3 1; 1 2 4 3 1 0.

Írjon olyan SML-függvényt monoton néven, amely kielégíti az alábbi specifikációt:

(* monoton : int -> int
   monoton a = b, ahol 'b' >= 2 a legkisebb olyan természetes szám, amelyre a
   'b' alapú számrendszerben felírt 'a' szám monoton számsorozatot ad eredményül 
*)

Segédfüggvényeket definiálhat. A jobbrekurzív függvényekből generált számítási folyamatok kevesebb tárterületet használnak, mint a nemjobbrekurzív függvényekből generáltak, ezért ajánljuk, hogy jobbrekurzív függvényeket írjon, ám ez nem kötelező, a pontozásba nem számít bele.

Példák

monoton 4   = 2 (* mert 4₂ = 1 0 0 monoton *)

monoton 11  = 4 (* mert 11₄ = 2 3 monoton, de 11₃ = 1 0 2 és  11₂ = 1 0 1 1 nem azok *)

monoton 145 = 8 (* mert 145₈ = 2 2 1 monoton, de ... *)

monoton 293 = 7 (* mert 293₇ = 5 6 6 monoton, de ... *)

Megjegyzés: a példákban d_r a d decimális szám r számrendszerbeli megfelelőjét jelenti.

Tudnivalók a beadásról

A kis házi feladat beadását, jóllehet nem kötelező, a tárgy minden hallgatójának nagyon ajánljuk.

A programot az Elektronikus Tanársegéd segítségével Weben keresztül lehet beadni, a HF beadás menüpont alatt.
A beadási határidő 2006. október 24., kedd, 24:00.

A vizsgaosztályzat megállapításakor a határidőre beadott, helyesen megoldott kis házi feladatért plusz 1 pont jár.