Algorytm trwałych małżeństwa - błąd w implementacji [Pascal]

0

Witam. Na podstawie Wrighta postanowiłem zaimplementować algorytm trwałych małżeństw. Program się normalnie kompiluje ale po wpisaniu danych zamyka bez wyświetlenia wyników więc ciężko mi powiedzieć czy te są poprawne. Prosiłbym o pomoc w rozwikłaniu problemu.

program malzensta(input,output);

uses

	crt;

const 

	n=8;

type

	mezczyzna=1..n; 
	kobieta=1..n; 
	pozycja=1..n;
	
var

	m:mezczyzna;
	k:kobieta;
	p:pozycja;
	kmp: array[mezczyzna,pozycja] of kobieta;
	licznik:integer;
	mkp: array[kobieta,pozycja] of mezczyzna;
	pmk: array[mezczyzna,kobieta] of pozycja;
	pkm: array[kobieta, mezczyzna] of pozycja;
	x: array[mezczyzna] of kobieta;
	y: array[kobieta] of mezczyzna;
	panna: array[kobieta] of boolean;

procedure drukuj;

var
	m:mezczyzna;
	pm,pk:integer;
	begin
		pm:=0;
		pk:=0;
			for m:=1 to n do
				begin
					write(x[m]:4);
					pm:=pm+pmk[m,x[m]];
					pk:=pk+pkm[x[m],m];
				end;
		writeln(pm:8, pk:4);
		readln;
	end;
	
procedure probuj(m:mezczyzna);

var
	p:pozycja;
	k:kobieta;

function trwale:boolean;

var
	t:boolean;
	i,lim:pozycja;
	pm:mezczyzna;
	pk:kobieta;
	
begin
	t:=true;
	i:=1;
	while (i<p) or t do 
		begin
		pk:=kmp[m,i];
		i:=i+1;
		if panna[pk] then
			t:=pkm[pk,m]<pkm[pk,y[pk]];
		end;
	i:=1;
	lim:=pkm[k,m];
	while (i<lim) or t do 
		begin
		pm:=mkp[k,i];
		i:=i+1;
		if pm<m then
			t:=pmk[pm,k]>pmk[pm,x[pm]];
		end;
	trwale:=t;
	end; //Trwale
	begin 
	for p:=1 to n do
		begin
		k:=kmp[m,p];
		if panna[k] then
			if trwale then
				begin
				x[m]:=k;
				y[k]:=m;
				panna[k]:=false;
			if m<n then probuj(succ(m))
			else
				drukuj;
				panna[k]:=true;
			end;
		end;
	end; //Probuj
	
begin //Program glowny

	for m:=1 to n do 
		for p:=1 to n do
		begin
		
			clrscr;
				writeln('Podaj ', p ,' preferencje ',m,' mezczyzny.');
			readln(kmp[m,p]);
			pmk[m,kmp[m,p]]:=p;
	
		end;
	for k:=1 to n do
		for p:=1 to n do
			begin
			clrscr;
			writeln('Podaj ', p ,' preferencje ',k,' kobiety.');
			readln(mkp[k,p]);
			pkm[k,mkp[k,p]]:=p;
		end;
	for k:=1 to n do 
		panna[k]:=true;
		probuj(1);
		readln;
end.
		
		

 

Dane wejściowe:

709cdebb7b.png

Dane wyjściowe:

07039b90ce.png

0

Wcięcia rób tak:

    for m:=1 to n do 
        for p:=1 to n do
        begin
            read(kmp[m,p]); //Pobieranie typow kobiet
            pmk[m,kmp[m,p]]:=p;
        end;
    while (i<lim) or t do 
    begin
        pm:=mkp[k,i];
        i:=i+1;
        if pm<m then
            t:=pmk[pm,k]>pmk[pm,x[pm]];
    end;

popraw wszędzie, bo teraz ciężko to czytać.

i podaj jakie jest przykładowe wejście programu i spodziewany wynik.

0

Zdaje się że ten problem jest opisany tutaj

http://edu.i-lo.tarnow.pl/inf/alg/001_search/0131a.php

0

@Azarien : Poprawiłem wcięcia oraz dodałem wyniki wejściowe i spodziewane wyjściowe (z książki z której jest algorytm).

@drorat1: Owszem ten problem jest tam opisany tylko głupio się przyznać ale nie rozumiem jego obsługi. Z tego co zrozumiałem to w tym miejscu:

read(n,m);             // Czytamy liczbę wierzchołków i krawędzi 

należy podać najpierw liczbę wierzchołków a następnie krawędzi. W moim przypadku wierzchołki to kobiety i mężczyźni a krawędzie ilość możliwych dopasowań. Jeśli mam 2 pary (4 wierzchołki) to kobiety mogą w sumie mieć 4 preferencje czyli 4 krawędzie. Podaję 4 za n i 4 za m. Później podaje:
Panna 1 Kawaler 2
Panna 1 Kawaler 1
Panna 2 Kawaler 1
Panna 2 Kawaler 2
jako preferencje kobiet.

Wyniki jakie otrzymuję to na przykład:

7281e0b528.png

i są to wyniki złe. Oczywiście bardzo możliwe, że źle rozumiem podany na tamtej stronie kod i jeśli tak jest to bardzo bym prosił jakąś dobrą duszę o wytłumaczenie co i jak należy podać aby otrzymać poprawny wynik. Z góry dziękuję i pozdrawiam.

1 użytkowników online, w tym zalogowanych: 0, gości: 1