Deklaratív programozás

2. SML kis házi feladat

2005. április 10.

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

A feladat

Adott összegűnek nevezünk egy pozitív, azaz 0-nál nagyobb egészekből álló számsorozatot, ha elemeinek összege egy előre megadott értékkel egyenlő. Pontosítva: Adott összegű az a_i > 0 elemekből álló a₀, a₁, ..., a_n-1 számsorozat, ahol i <= 0 < n, ha adott s-re SUM_i=0^n-1a_i = s. Írjon olyan SML-függvényt adottOsszeguek néven, amely kielégíti az alábbi specifikációt:

(* adottOsszeguek : int * int list -> int list list
   adottOsszeguek(s, xs) = az xs szomszédos elemeiből álló, de egymást nem átfedő
        adott összegű sorozatokból képzett olyan listák listája, amelyek az elemek
        eredeti sorrendjét megőrzik, és amelyekben az elemek összege s.
*)

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

adottOsszeguek (9, [1, 2, 3, 4, 5, 4, 3, 2, 1]) =
  [[2, 3, 4], [5, 4]]; (* de [4, 3, 2] már nem, mert átfedésben lenne [5, 4]-gyel *)

adottOsszeguek (3, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) =
  [[1, 1, 1], [1, 1, 1], [1, 1, 1]]; (* de az utolsó két 1-essel már nem képezhető további sorozat *)

adottOsszeguek (1073741823, [1073741823, 73741822, 1, 1000000000]) =
  [[1073741823], [73741822, 1, 1000000000]]; (* a programnak még Int.maxInt-et is tudnia kell kezelni *) 

adottOsszeguek (1073741822, [1073741823, 73741822, 1, 1000000000]) =
  []; (* mert nem képezhető egyetlen s összegű sorozat sem *)

Tudnivalók a beadásról

A programot az Elektronikus Tanársegéd segítségével a weben keresztül lehet beadni, a HF beadás menüpont alatt. Ez a második SML kis házi feladat, ezért khf-ml2.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. április 18., hétfő 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 (a 100 pontból).