FELADAT:

Írjunk egy olyan eljárást, melynek argumentumába egy N pozitív egész számot megadva egy olyan eljárást kapunk vissza, amely minden meghívásakor az N szám egy újabb particióját adja.

> restart;

Először kódoljuk le a KNUTH 4. kötetben (http://www-cs-faculty.stanford.edu/~knuth/news.html) található algoritmust úgy, ahogy le van írva, goto-val.

> partitions := proc(N::posint)

> local a, i, q, m, n, x;

> a:=array(0..N); m:=1; n:=N;

>

> 2: a[m]:=n; q:=m; if n=1 then q:=q-1 end if;

> 3: print( [seq(a[i], i=1..m)] );

> if a[q]<>2 then goto(5) end if;

> 4: a[q]:=1; q:=q-1; m:=m+1; a[m]:=1; goto(3);

> 5: if q=0 then goto(7) else

> x:=a[q]-1; a[q]:=x; n:=m-q+1; m:=q+1; end if;

> 6: while n>x do a[m]:=x; m:=m+1; n:=n-x end do; goto(2);

> 7: print("vege");

>

> end proc:

> partitions(5);

Következő lépésként írjuk át e kódot goto nélküli formába. Ehhez készítsük el a program blokkdiagramját (és értsük meg az algoritmust :-))

> restart;

> partitions:=proc(N::posint)
local a, i, q, m, x, n;

a:=array(0..N); m:=1; n:=N;

do
a[m]:=n; q:=m; if n=1 then q:=q-1 end if;

do
print( [seq(a[i],i=1..m)] );
if a[q]=2 then
a[q]:=1; q:=q-1; m:=m+1; a[m]:=1;
else
break
end if;
end do;

if q=0 then break end if;
x:=a[q]-1; a[q]:=x; n:=m-q+1; m:=q+1;
while n>x do a[m]:=x; m:=m+1; n:=n-x end do;
end do;

return "vége";

end proc:

> partitions(5);

Ezután keressünk e programrészlet átírására olyan megoldást, hogy minden meghívásakor csak egy partíciót adjon vissza, másrészt beépíthető legyen egy olyan eljárásba, amely ezt adja vissza:

> part:= proc(N::posint)
local a, q, m, n, x, p;

a := array(0..N,[1,0]); q:=1; m:=1; n:=N;

p := proc()
local i;
if a[q]>0 then
if a[q]=2 then
a[q]:=1; q:=q-1; m:=m+1; a[m]:=1; return [seq(a[i],i=1..m)];
elif q=0 then
q:=1; m:=1; n:=N; a[1]:=0; return FAIL;
else
x:=a[q]-1; a[q]:=x; n:=m-q+1; m:=q+1;
while n>x do
a[m]:=x; m:=m+1; n:=n-x
end do;
end if;
end if;
a[m]:=n; q:=m; if n=1 then q:=q-1 end if;
return [seq(a[i],i=1..m)];
end proc;

proc()
p()
end proc;

end proc:

> f:=part(5);

> to 10 do f() end do;

>

>