en temat z pewno╢ci▒ spodoba siΩ matematykom, kt≤rzy chc▒ zaprz▒c komputer do matematycznych zada±. W praktyce, opisany algorytm jest te┐ przydatny po odpowiednim rozbudowaniu i zaadaptowaniu do generowania wszystkich mo┐liwych ci▒g≤w znak≤w - indeks≤w s│≤w itp.
Algorytm nasz bΩdzie mia│ za zadanie wczytaµ od u┐ytkownika pewien zbi≤r znak≤w ASCII i wygenerowaµ na jego podstawie wszystkie mo┐liwe wariacje z powt≤rzeniami o okre╢lonej d│ugo╢ci.
Na pocz▒tek przypomnijmy, czym tak w│a╢ciwie s▒ wariacje z powt≤rzeniami.
k-wyrazow▒ wariacj▒ z powt≤rzeniami utworzon▒ spo╢r≤d n element≤w nazywamy ka┐dy k-wyrazowy ci▒g o wyrazach niekoniecznie r≤┐nych utworzony spo╢r≤d tych n wyraz≤w (k,n - liczby naturalne).
Przyk│adowo, je╢li dane s▒ wyrazy a,b,c, to istniej▒ nastΩpuj▒ce 2-wyrazowe wariacje element≤w zbioru {a,b,c}:
(a,a); (a,b); (a,c); (b,a); (b,b); (b,c); (c,a); (c,b); (c,c)
Gdy wiemy ju┐, co ma robiµ nasz program, nale┐a│o by siΩ zastanowiµ nad postaci▒ wprowadzanych do niego danych. Wyrazy wej╢ciowe, kt≤rych wariacje bΩdziemy znajdowaµ, s▒ zbiorem, wydawa│oby siΩ wiΩc, ┐e najlepszym sposobem reprezentacji dla nich w pamiΩci komputera w przypadku programu pascalowego by│by typ mnogo╢ciowy, czyli w│a╢nie zbi≤r (set of...). Potrafi on bez problemu przechowywaµ znaki ASCII, na kt≤rych bΩdziemy chcieli operowaµ. Tu jednak jest ma│a pu│apka. W przypadku tego typu bowiem mo┐na sprawdziµ obecno╢µ danego elementu w zbiorze, ale nie jest zaimplementowane w jΩzyku odczytywanie po kolei wszystkich element≤w. Jest to normalne, gdy┐ zbi≤r z natury jest nieuporz▒dkowany, wiΩc dostΩp do wszystkich element≤w po kolei by│by niezgodny z zasadami matematyki. W naszym przypadku jednak │atwiej bΩdzie zrezygnowaµ z matematycznej poprawno╢ci, i zaimplementowaµ zbi≤r jako uporz▒dkowan▒ strukturΩ o wygodnym dostΩpie. Nasuwaj▒ siΩ tu dwie mo┐liwo╢ci: albo zadeklarowaµ zmienn▒ napisow▒ do przechowywania poszczeg≤lnych element≤w zbioru jako kolejnych liter napisu, albo po prostu stworzyµ tablicΩ o typie podstawowym char. To pierwsze rozwi▒zanie wydaje siΩ jednak w tej sytuacji bardziej sztuczne. Zrezygnujemy z niego na rzecz "rΩcznie zadeklarowanej" tablicy, zmiennej napisowej bΩdziemy natomiast u┐ywaµ ju┐ bezpo╢rednio w trakcie generowania wariacji do przechowywania wynik≤w poszczeg≤lnych wynik≤w dzia│ania algorytmu ze wzglΩdu na │atwo╢µ wyprowadzania danych (w przypadku, gdyby╢my chcieli operowaµ nie na znakach, ale na przyk│ad na liczbach czy napisach bΩd▒cych elementami zbioru, trzeba by nasz algorytm trochΩ uog≤lniµ).
W programie najpierw deklarujemy ca│kowite zmienne globalne k i n. Zmienna n bΩdzie zawieraµ ilo╢µ element≤w zbioru wej╢ciowego. Zmienna k bΩdzie z kolei przechowywaµ informacje o tym, iluelementowe wariacje generowaµ (jakiej d│ugo╢ci napisy). Deklarujemy te┐ tablicΩ zbior o typie podstawowym char, do kt≤rej nastΩpnie w programie wczytujemy n r≤┐nych element≤w (znak≤w ASCII). Tablica ta w naszym przypadku mo┐e przechowywaµ 100 element≤w (dobraµ w praktyce mo┐na dowoln▒ d│ugo╢µ tablicy, ale i tak nikt nie bΩdzie "wstukiwa│" 100 literek!).
My╢lΩ, ┐e dotychczas wszystko jest zrozumia│e. W naszym "zbiorze" nie mo┐emy jednak nic zmieniaµ w trakcie wykonywania algorytmu, gdy┐ doprowadzi│oby to do utraty informacji o tym, jakie elementy mamy wykorzystaµ przy generowaniu wariacji. Deklarujemy wiΩc dodatkow▒ zmienn▒ "robocz▒", na kt≤rej bΩdziemy operowaµ i kt≤r▒ bΩdziemy wy╢wietlaµ jako wynik. BΩdzie to tak┐e zmienna globalna, ale tym razem typu napisowego (wcze╢niej napisa│em, dlaczego akurat tego typu). Zmienn▒ tΩ nazwijmy napis.
Pocz▒tkowo (po wczytaniu zbioru wej╢ciowego) ustalamy d│ugo╢µ napisu napis na k. Trzeba to zrobiµ niestety trochΩ "na piechotΩ", pokazany poni┐ej przyk│ad nie zadzia│a na wszystkich kompilatorach. NastΩpnie wszystkie litery napisu ustawiamy na identyczn▒ warto╢µ, r≤wn▒ pierwszej literze naszego "zbioru" wej╢ciowego. Je╢li na przyk│ad w zbiorze wej╢ciowym mamy litery a, b, c, a chcemy generowaµ 4-wyrazowe wariacje, to pocz▒tkowo warto╢µ napisu napis musi wynosiµ 'aaaa'.
Teraz w programie g│≤wnym przystΩpujemy do sedna sprawy, czyli do wywo│ania procedury, kt≤ra wygeneruje (i jednocze╢nie bΩdzie pisaµ na ekranie) wszystkie mo┐liwe wariacje. ProcedurΩ tΩ nazwa│em w swoim przyk│adzie wariacje. Podaje siΩ jej dwa argumenty. Pierwszy z nich to zmienna napis. Ju┐ wyja╢ni│em, jak▒ warto╢µ ma mieµ ta zmienna podczas wywo│ania procedury wariacje w programie g│≤wnym. Drugim argumentem jest liczba ca│kowita, kt≤ra z kolei podczas wywo│ania naszej procedury z programu g│≤wnego ma zawsze warto╢µ 1. Zmienna ta ma s│u┐yµ wy│acznie do badania w kolejnych rekurencyjnych wywo│aniach procedury wariacje poziomu zag│ebienia rekurencji. Gdy poziom rekurencji osi▒gnie warto╢µ k, znaczy to ┐e w danym wywo│aniu procedury zosta│o zako±czone generowanie kolejnej wariacji i mo┐na j▒ ju┐ wypisaµ na ekranie, oraz porzuciµ dalsze zag│Ωbienia rekurencyjne i wr≤ciµ w hierarchii wywo│a± o jeden poziom "do g≤ry", czyli bli┐ej "pierwotnego" wywo│ania.
Kluczem do zrozumienia algorytmu jest zrozumienie istoty wywo│a± rekurencyjnych naszej procedury. W procedurze wykonuje siΩ n pΩtli, w ka┐dej z nich przypisuj▒c odpowiedniej literze zmiennej napis kolejne warto╢ci ze zbioru zbior. To, kt≤rej literze przypisaµ odpowiedni▒ zmienn▒, poznaje siΩ po warto╢ci zmienne poz w danym wywo│aniu rekurencyjnym. W kolejnych poziomach rekurencji zmienna ta jest zwiΩkszana o 1. Wynika z tego, ┐e najwy┐szy w hierarchii wywo│a± "egzemplarz" procedury wariacje zmienia po kolei warto╢µ pierwszej litery, potem ka┐dy z n egzemplarzy podrzΩdnych zmienia drug▒ literΩ itd. Musisz postaraµ siΩ zrozumieµ to samemu. Najlepiej, je╢li postarasz siΩ rozrysowaµ to na jakim╢ schemacie. W ten spos≤b, po doj╢ciu do k-tego poziomu rekurencji, pisze siΩ kolejn▒ wariacjΩ. W zasadzie powinna ona byµ zapisana w poprawnej, matematycznej notacji, ale u nas jest to po prostu napis (wiΩcej wariacji zmie╢ci siΩ na ekranie).
Mam nadziejΩ, ┐e zrozumia│e╢, na czym polega przedstawiony przeze mnie algorytm. Je╢li nie, spr≤buj jeszcze raz dok│adnie i ze zrozumieniem przeanalizowaµ zasady rekurencyjnych wywo│a± procedury wariacje.
uses crt;
var
n: integer;
i: integer;
k: integer;
zbior: array[1..100] of char;
napis: string;
procedure wariacje(s:string; poz: integer);
var
i: integer;
begin
for i:=1 to n do begin
s[poz]:=zbior[i];
if poz=k then write(s,' ');
if poz<k then wariacje(s,poz+1);
end;
end;
begin
clrscr;
writeln('Ile element≤w permutowaµ?');
readln(n);
for i:=1 to n do begin
writeln('Podaj kolejny element:');
readln(zbior[i]);
end;
writeln('Iluelementowe wariacje znale╝µ?');
readln(k);
napis[0]:=char(k);
for i:=1 to k do napis[i]:=zbior[1];
wariacje(napis,1);
writeln('Zrobione!!!');
readln;
end.
Mo┐esz pobraµ kod ╝r≤d│owy w pliku oraz skompilowany program.
