Deklaratív programozás

1. SML kis házi feladat

2005. október 22. Jav. 2004. nov. 1.

A kis házi feladat beadása nem kötelező.

A feladat

Párbafésültnek nevezünk egy számsorozatot, ha elemeinek száma páros, első eleme nem kisebb az utolsónál, harmadik eleme nem kisebb az utolsó előtti előttinél s.í.t. Pontosítva:

Egy a₁, a₂, ..., a_2n számsorozat párbafésült, ha minden 0≤i<n-re a_2i+1≥a_2n-2i.

Példák párbafésült sorozatokra: 1 1 és 4 1 3 2 5 4.

Írjon olyan SML-eljárást parbafesult néven, amely kielégíti az alábbi specifikációt:

(* parbafesult : int -> int
   parbafesult n = k, ahol k >= 2 az a legkisebb természetes szám,
            amelyre a k alapú számrendszerben felírt n decimális
            szám párbafésült számsorozatot ad eredményül
*)

Segédeljárást definiálhat.

A jobbrekurzív eljárásokból generált számítási folyamatok kevesebb tárterületet használnak, mint a nemjobbrekurzív eljárásokból generáltak, ezért ajánljuk, hogy jobbrekurzív eljárásokat írjon, ám ez nem kötelező, a pontozásba nem számít bele.

Példák

parbafesult 10 = 2        (* mert 10₂ = 1 0 1 0 párbafésült *)

parbafesult 4  = 3        (* mert 4₃ = 1 1 párbafésült, de
                             4₂ = 1 0 0 nem az, mert nem páros a hossza *)

parbafesult 29 = 7        (* mert 29₇ = 4 1 párbafésült, de ... *)

parbafesult 143 = 12      (* mert 143₁₂ = 11 11 párbafésült, de ... *)

parbafesult 293 = 18      (* mert 293₁₈ = 16 5 párbafésült, de ... *)

parbafesult 30302239 = 76 (* mert 30302239₇₆ = 69 2 17 51 párbafésült, de ... *)

Megjegyzés: n_k az n decimális szám k számrendszerben felírt alakját jelenti.

Tudnivalók a beadásról

A programot az Elektronikus Tanársegéd segítségével Weben keresztül lehet beadni, a HF beadás menüpont alatt. Ez az első SML kis házi feladat, ezért khf-ml1.sml néven kell beküldeni a megoldást. A névben meg kell különböztetni a kis- és nagybetűket. A beadási határidő 2005. november 2., szerda 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.