A megoldás
Tárolás a memóriában
A folyókat tömbökben fogjuk tárolni úgy, hogy minden folyóra a tömb-indexével lehessen hivatkozni. A folyók nevei egy 1000 nagyságú tömbben lesznek, és felveszünk egy másik 1000 nagyságú tömböt is, amiben minden folyóhoz eltároljuk, hogy milyen sorszámú folyóba folyik bele. Tehát pl. fnev[] egy 1-től 1000-ig címezhető tömb, amiben szöveg típusú változók vannak, fkov[] pedig egy ugyanilyen, de egész számokat tartalmazó tömb. Így ha pl. a Tisza a Dunába folyik, és a Tisza a 6.-ik folyó, a Duna pedig a 17.-ik, akkor: fnev[6] = "Tisza", fnev[17] = "Duna" és fkov[6] = 17. (A sorszámokat majd a program fogja kiosztani betöltéskor.) Ha egy folyóról nem tudjuk, hogy mibe folyik, akkor annak 0-át teszünk az fkov[] tömbbe. A folyók nevének a hosszára nincs megkötés, de ha Dos-os rendszerben (pl. Turbo Pascal) az alapértelmezett (255-ös) STRING-eket használjuk, akkor a nev[] tömb mérete kb. 255 kilobyte lenne, így nekünk kell egy kisebb értéket keresnünk, amibe remélhetőleg belefér minden folyónév...
Betöltés
A betöltéshez készítünk egy olyan segédfüggvényt, ami egy folyónévhez megadja a folyó sorszámát az fnev[] tömbben. Ha még nem lenne benne az adott név, akkor előbb bele is teszi. Ehhez szükségünk lesz egy N0 számra, amiben a betöltött folyókat számolhatjuk. N0 kezdetben 0. Vigyázzunk, mert N0 nem feltétlenül lesz egyenlő N-el, azaz a folyó-kapcsolatok számával.
Eljárás FolyoNev(nev)
i:= 1;
Ciklus Amíg (i <= N0) és (fnev[i] <> nev)
i := i + 1;
Ciklus vége
Ha i > N0 Akkor
N0 := N0 + 1;
fnev[i] := nev;
fkov[i]:= 0;
Elágazás vége
FolyoNev := i;
Eljárás vége
Cilusunk akkor fog kilépni, ha megtalálta a nev nevű folyót, vagy ha a tömb végére ért. Ez utóbbi esetben viszont a ciklusváltozó (i) biztosan nagyobb lesz N0-nál. Tehát a betöltés:
Eljárás Betolt()
Beolvas(N);
Ciklus i := 1-től N-ig
Beolvas(nev1); Beolvas(nev2);
folyo1 := FolyoNev(nev1);
folyo2 := FolyoNev(nev2);
fkov[folyo1] := folyo2;
Ciklus Vége
Beolvas(nev1);
q:= FolyoNev(nev1);
Eljárás Vége
Az A.) részfeladat
A
q lesz a feladatban kérdezett folyó sorszáma. Itt is a
6.órán megismert útkereső algoritmust fogjuk használni, illetve annak egy módosításást. Jelöljük meg kezdetben a
q folyót, majd ismételgessük a következő lépést: vegyük sorra a folyókat, és ha olyat találunk, amelyik megjelölt folyóba folyik bele, akkor jelöljük meg azt. Mindezt addig kell ismételgetni, amíg le nem fut egy olyan lépés, amiben már nem jelöltünk meg új folyót. Ezzel megjelöltünk minden olyan folyót, amelyik belefolyt
q-ba. A megejlölésekhez felveszünk egy
fjel[], logikai értékeket tartalmazó tömböt, aminek kezdetben minden eleme
Hamis
fjel[q] := Igaz;
kesz := Hamis;
Ciklus Amíg (Nem kesz)
kesz := Igaz;
Ciklus i := 1-től N0-ig
Ha fjel[i] = Igaz Akkor
Ciklus j:= 1-től N0-ig
Ha (fkov[j] = i) és (fjel[j] = Hamis) Akkor
fjel[j] := Igaz;
kesz := Hamis;
Elágazás vége
Ciklus vége
Elágazás vége
Ciklus vége
Ciklus vége
(A Nem logikai tagadást jelöl.)
A megoldáshoz ki kell iratni a megjelölt folyók neveit, kivéve q nevét. Ki kell még írni a megjelölt folyók számát is, úgyhogy az előbbi algoritmusban már érdemes számolni a megjelöléseket.
A B.) részfeladat
Az elszennyeződő folyók kereséséhez elég csak végiglépkedni a q-ból induló, egymásba folyó folyók sorozatán. De mivel itt is előbb kell kiírni a talált folyók sorszámát, ezért először csak összeszámoljuk őket, és utána újból végigmegyünk rajtuk a kiíráshoz. Az összeszámolás:
i := fkov[q];
szamol := 0;
Ciklus Amíg i <> 0
szamol := szamol + 1;
i := fkov[i];
Ciklus Vége
Kiir(szamol);
A kiírás:
i := fkov[q];
Ciklus Amíg i <> 0
Kiir( fnev[i] );
i := fkov[i];
Ciklus Vége
Kiir(szamol);
Megoldások
