Problem Z Rekurencja

[Shakell]

Witam, mam problem ze znalezieniem błędu w moim programie w Pascalu, pisanym zreszta w ramach nauki stosowania rekursji. Program ma spełniać nastepujące zadanie:

 

 

Napisz program, który wygeneruje wszystkie podzbiory zbioru -elementowego. Zauważmy, że każdy taki podzbiór można utożsamiać z ciągiem zer i jedynek - jeden na -tej pozycji oznacza, że -ty element zbioru znajduje się w tym podzbiorze, zaś 0 - że się nie znajduje. Na przykład ciąg 01101 można utożsamiać z podzbiorem {2,3,5}.

Zadanie

 

Napisz program, który:

wczyta ze standardowego wejścia rozmiar zbioru,

znajdzie wszystkie podzbiory tego zbioru,

wypisze wynik na standardowe wyjście.

Wejście

 

W pierwszym i jedynym wierszu wejścia znajduje się jedna liczba całkowita 1<n<15 oznaczająca liczność zbioru.

Wyjście

 

Na wyjściu powinny być wypisane wszystkie podzbiory zbioru -elementowego, w postaci ciągów zerojedynkowych, po jednym w wierszu (patrz przykład). Kolejność, w jakiej wypiszesz te podzbiory, nie ma znaczenia.

Przykład

Dla danych wejściowych:

3

poprawną odpowiedzią jest:

000

001

010

011

100

101

110

111

 

 

 

Mój kod wygląda w sposób następujący:

 

program podzbiory;var		n : byte;		tab : array[1.15] of integer;////////////////////////////////////////////procedure rek(poz : byte;znak : byte); {przekazujemy miejsce w tablicy na które wstawiamy znak - 0 lub 1}var i : byte;begin		if poz > n then begin		{jesli wywolalismy procedure n razy i wypelnilismy tyle pol ile trzeba, wypisujemy}				for i:=1 to n do write(tab[i]);				writeln;		end		else begin									 {jesli nie, podstawiamy znak i wywolujemy funkcje rekurencyjnie}				tab[poz]:=znak;				rek(poz+1,1);				rek(poz+1,0);		end;end;begin		readln(n);		rek(1,1);								{wywolujemy funkcje zaczynajac od 1 i od 0}		rek(1,0);end.

problemem jest zdublowanie sie wyników, które zamiast tak jak w podanym przykladzie, są podwojne:

 

100

100

101

101

110

110

111

111

000

000

001

001

010

010

011

011

 

 

Staram sie nauczyc rekurencji :) ale zdarzaja mi sie takie przypadki jak teraz, kiedy siedze godzine i szukam błędu.

Nie jest to wina tablicy globalnej, bo próbowalem tez przekazywac tablice tab przez nazwe - ten sam defekt. Ma ktos pomysl który fragment programu powoduje dublowanie wyswietlanych elementów?

[ULLISSES]

Po co wywołujesz 2 razy?

rek(1,1);rek(1,0);

Skoro w kodzie już masz obie wartości wpisywane...?

rek(poz+1,1);rek(poz+1,0);

Ostrzegam, że Pascala w czystej postaci używałem jakieś 10 lat temu. ;]

[Shakell]

wywoluje 2 razy zeby ustawic na 1 miejscu w raz 0 i raz 1, a nastepnie juz wewnatrz funkcji wywoluje znowuz zeby wstawic na miejscie poz+1 równiez 1 lub 0

[p3dzi0r]

A bierzesz pod uwagę dalszy ciąg kodu przy powrocie z wywołania rekurencyjnego ? , bo to może tak wyglądać, ja także nie używałem pascala z 10 lat ;p. Najlepiej byłoby użyć debuggera

[ULLISSES]

A jeśli usuniesz jedno z wywołań rek() ? Czy wtedy nie działa prawidłowo?