Gyakorlat, 1. hét: adatmodellezés, algoritmusok

Czirkos Zoltán · 2019.09.07.

Bevezető a programozás, az adatmodellezés és az algoritmusok világába.

1. Mi és hogyan?

Rajzolnunk kell egy háromszöget, amelynek oldalai 5, 3 és 4 egység hosszúak.

A feladatot kétféleképpen közelíthetjük meg. Az egyik az alábbi. Adott egy háromszög, és ellenőrizni kell, hogy ez pont olyan-e, mint amilyet a feladat kért. A rajz egyébként pont ilyet mutat; az oldalhosszak vonalzóval ellenőrizhetőek is.

Háromszög, 5, 3 és 4 hosszúságú oldalakkal

A másik megoldás pedig az alábbi. Ez egy szerkesztési utasítás: ha követjük, akkor meg tudjuk rajzolni azt a háromszöget, amit a feladat kért.

Háromszög szerkesztése
  1. Felveszünk egy félegyenest, amelynek a kezdőpontja A.
  2. Körívet szerkesztünk r=5 sugárral az A pontból. A félegyenest ez B pontban metszi, így egy szakaszt kaptunk.
  3. Körívet szerkesztünk r=3 sugárral, szintén az A pontból.
  4. Körívet szerkesztünk r=4 sugárral a B pontból. A kapott metszéspontot C-nek nevezzük (ha nincs, akkor nem szerkeszthető a háromszög).
  5. Összekötjük A és C pontokat.
  6. Összekötjük B és C pontokat – a háromszög kész.

A két megoldás nagyon eltérő szemléletű. Az első puszta tényközlés: „így néz ki a háromszög”. A második viszont egy módszert ad: azt írja le, hogyan szerkesztjük meg a semmiből.

Az alábbi feladatoknál mindig a hogyan lesz a kérdésünk. A feladatoknál ne az eredményt közöljük, hanem módszert, algoritmust adjunk a feladat megoldására! Eközben pedig arra is figyelünk, hogy milyen adatokra van szükségünk, és hogyan használjuk fel azokat. Például megkérdezhetjük valakitől, hogy hány éves, de adhatunk az életkor meghatározására egy módszert is: ki kell vonni a jelenlegi évszámból a születési évszámot. Megkérdezhetjük, hány kilométerre van egymástól Budapest és Szeged. A válasz 175, de most az a lényeg, hogy ezt hogyan határozzuk meg: össze kell adni azoknak az útszakaszoknak a hosszát, amin végigutazunk.

2. Futóverseny

Az itt látható táblázat egy futóverseny eredményeit tartalmazza.

RajtszámNévSzületésnapIdő
1Break Elek1982. 09. 30.13:10
2Am Erika1984. 05. 06.12:35
3Kasza Blanka1979. 06. 10.13:37
4Dil Emma1988. 08. 25.12:37
5Koax K. Ábel1991. 03. 19.nem jött el
6Lin Yutang1987. 03. 30.12:51
7Reset Elek1992. 04. 05.13:37
8Andrea Rossi1986. 07. 08.13:05

Adjuk meg, hogyan kell megválaszolni az alábbi kérdéseket!

  1. Ki nyerte meg a versenyt?
  2. ... Mi kellene ahhoz, hogy gyorsan meg lehessen válaszolni ezt a kérdést?
  3. Milyen gyors volt a legfiatalabb nevező?
  4. ... Mikor tudnánk gyorsabban megválaszolni ezt a kérdést?
  5. Hányan vettek részt a versenyen?
  6. Mi a nemek aránya a nevezők közt?
  7. Volt-e holtverseny?
  8. ... Mikor lenne könnyebb megválaszolni ezt a kérdést?
Megoldás
  1. Meg kell keresni a legrövidebb időt. A válasz az ahhoz a sorhoz tartozó név.
  2. ... A táblázat jelenleg a rajtszámok (nevezések sorrendje) alapján van rendezve. Ezért az idők össze-vissza vannak. Ha a táblázatot a mért idő alapján rendeznénk sorba, az előző kérdést könnyebb lenne megválaszolni: a táblázat első sorában található név. Lásd a lenti első táblázatot és a kiemelést.
  3. A fentihez hasonlóan végig kell néznünk a táblázatot, keresve a legnagyobb év–hónap–napot. A válasz a megtalált sorban találhatő idő (de előfordulhat, hogy nem indult).
  4. ... A dátum szerinti rendezéssel. A legalsó sor lenne a válasz. Lásd a lenti második táblázatot és a kiemelést.
  5. Meg kell számolni, hány sorban szerepel idő megadva. Ki kell hagyni azokat, akiknél „nem jött el” jelölést látunk.
  6. Első körben erre azt válaszoljuk, hogy meg kell számolni a nőket és a férfiakat; nők / összes nevező, és férfiak / összes nevező a válasz. Valójában nem ilyen egyszerű a dolog: a külföldi neveket nem ismerjük, vagy esetleg azt sem tudjuk, melyik a vezetéknév és melyik a keresztnév. Andrea a magyartól eltérően olaszul férfinév, és ott a keresztnevet veszik előre.
  7. Azt kell megvizsgálnunk, találunk-e két egyforma időt. Ha legalább egy ilyen párt találunk, akkor volt.
  8. ... Jelenleg minden sort mindegyik másikkal össze kell hasonlítani. Ha a versenyen mért idő alapján lenne rendezve a táblázat, a holtversenyben befutó versenyzők egymás alatt lennének. Vagyis elég lenne az egymás alatti számokat összehasonlítani. Lásd a lenti első táblázatot.
RajtszámNévSzületésnapIdő
2Am Erika1984. 05. 06.12:35
4Dil Emma1988. 08. 25.12:37
6Lin Yutang1987. 03. 30.12:51
8Andrea Rossi1986. 07. 08.13:05
1Break Elek1982. 09. 30.13:10
7Reset Elek1992. 04. 05.13:37
3Kasza Blanka1979. 06. 10.13:37
5Koaksz K. Ábel1991. 03. 19.nem jött el
Elért idő szerint rendezve
RajtszámNévSzületésnapIdő
3Kasza Blanka1979. 06. 10.13:37
1Break Elek1982. 09. 30.13:10
2Am Erika1984. 05. 06.12:35
8Andrea Rossi1986. 07. 08.13:05
6Lin Yutang1987. 03. 30.12:51
4Dil Emma1988. 08. 25.12:37
5Koaksz K. Ábel1991. 03. 19.nem jött el
7Reset Elek1992. 04. 05.13:37
Születési idő szerint rendezve

3. Dolgozatok

Egy évfolyam dolgozatot írt. A dolgozatok maximum 10 pontosak lehetnek. Az alábbi pontszámok születtek:

9, 8, 9, 6, 10, 3, 5, 1, 3, 9, 3, 7, 10, 5, 7, 4, 7, 4, 3, 9, 4, 2, 9, 9, 10, 5, 2, 7, 7, 7, 6, 9, 7, 7, 10, 10, 9, 7, 7, 2, 3, 6, 7, 7, 7, 5, 8, 8, 5, 5, 9, 8, 7, 7, 4, 7, 6, 7, 10, 10, 7, 8, 3, 10, 6, 7, 10, 9, 2, 10, 8, 2, 10, 3, 6, 10, 10, 6, 6, 7, 10, 7, 4, 1, 7, 9, 9, 4, 5, 10, 8, 0, 7, 10, 6, 2, 10, 9, 7, 2, 7, 10, 3, 7, 7, 5, 7, 7, 10, 10, 9, 10, 9, 10, 3, 10, 7, 6, 2, 9, 3, 2, 6, 8, 6, 7, 2, 7, 10, 5, 8, 9, 1, 9, 3, 7, 7, 4, 4, 5, 10, 10, 7, 8, 10, 5, 5, 10, 7, 7, 6, 4, 7, 7, 8, 10, 7, 6, 7

Adjunk módszert az alábbi feladatok megoldására!

  1. Lett hibátlan dolgozat? Lett nulla pontos dolgozat?
  2. Hány 7 pontos dolgozat született?
  3. Az előző feladatra adott megoldást felhasználva, hogyan készítünk táblázatot arról, hogy milyen pontszámból, hány darab lett?
  4. Képzeljük el azt, hogy csak egyszer szaladhatunk végig a pontszámok listáján. Sőt: meg sem kapjuk papíron, hanem valaki lediktálja nekünk, egyetlen egyszer. Hogyan tudunk ilyenkor táblázatot készíteni arról, hogy milyen pontszámból, hány darab lett?
  5. Ha megvan a pontszámok eloszlása, akkor hogyan válaszoljuk meg az első kérdést: lett-e hibátlan dolgozat?
  6. Melyik volt a leggyakoribb pontszám?
Megoldás
  1. (Tegyük fel, hogy a hibátlan 10 pontosat jelent.) Elindulunk a lista elejéről. Amint találunk egy 10 pontost, azt mondhatjuk, hogy igen, lett ilyen. Ha végignéztük a számsort, és sehol nem találtunk, akkor viszont nincs. Vegyük észre, hogy a szemünk nagyon könnyen megtalálja a 10 pontosokat, de a 0-sakat nem. 0-sból amúgy egyetlen egy darab van. Ha szisztematikus módszert akarunk adni, az viszont a 0 és a 10 pontosok keresésére is ugyanaz: egyesével végigmegyünk a számsoron.
  2. Végig kell nézni a teljes számsort, és az ujjunkon / strigulákkal / bárhogy máshogy számlálni a 7-eseket.
  3. Felírjuk a pontokat 0-tól 10-ig. Mindegyik számra alkalmazzuk az előző módszert: megszámláljuk a 0-kat, az 1-eket, és így tovább.
     0 pont:  1 db
     1 pont:  3 db
     2 pont: 10 db
     3 pont: 11 db
     4 pont:  9 db
     5 pont: 12 db
     6 pont: 14 db
     7 pont: 41 db
     8 pont: 11 db
     9 pont: 18 db
    10 pont: 29 db
    
  4. Felírjuk a pontokat 0-tól 10-ig. Hallgatjuk a diktált számsort; amilyen számot hallunk, amellé húzzuk a strigulát. Ahány pontról van szó, a táblázatnak annyiadik soráról beszélünk. Mire végzünk, előállt a táblázat, amit szerettünk volna.
     0 pont:  1 db, |
     1 pont:  3 db, |||
     2 pont: 10 db, ||||| ||||| 
     3 pont: 11 db, ||||| ||||| |
     4 pont:  9 db, ||||| ||||
     5 pont: 12 db, ||||| ||||| ||
     6 pont: 14 db, ||||| ||||| ||||
     7 pont: 41 db, ||||| ||||| ||||| ||||| ||||| ||||| ||||| ||||| |
     8 pont: 11 db, ||||| ||||| |
     9 pont: 18 db, ||||| ||||| ||||| |||
    10 pont: 29 db, ||||| ||||| ||||| ||||| ||||| ||||
    
  5. Csak meg kell nézni a táblázat legalsó sorát. Az eredeti pontszámokra már nincs is szükségünk.
  6. Az előző táblázatban keressük azt a sort, ahol a legnagyobb szám van. Ne feledjük: grafikusan ez könnyű, de ha számokról van szó, akkor meg kell keresnünk a legnagyobbat. Lásd a futóversenyes feladatot.

4. Fogadó

Ez a feladat a 2017-es informatika érettségi adaptációja.

Egy fogadó az alábbi adatokról vezet nyilvántartást:

  • Szobák a fogadóban (sorszám, név, ágyak száma, pótágyak száma)
  • Vendégek (azonosító, név, irányítószám)
  • Foglalások (foglalás sorszáma, vendég sorszáma, szoba sorszáma, érkezés, távozás, személyek száma).
SorszámNévÁgyPótágy
1Szende43
2Szundi42
...
Szobák
AzonosítóNévIrsz
1Gulyás Klaudia2074
2Barta Andrea8943
...
Vendégek
FoglalásVendégSzobaÉrkezésTávozásSzemélyek
1132016-01-042016-01-074
2242016-01-042016-01-063
...
Foglalások

Válaszoljuk meg a kérdéseket, illetve adjunk módszert az alábbi kérdések megválaszolására!

  1. Minden táblázat sorait beszámoztuk. Szükséges ez, vagy van, ahol elhagyható lenne a sorszám?
  2. Hány fő szállásolható el a fogadóban?
  3. Hány vendég érkezett Borsod-Abaúj-Zemplén megyéből? (Az irányítószámok: 3400–3999.)
  4. Hány foglalás található a Szende nevű szobához?
  5. Szabad-e a Szende nevű szoba 2020.12.30-tól 2021.01.02-ig?
  6. Melyik a legnépszerűbb szoba, vagyis ahova a legtöbbször foglaltak a vendégek?
  7. Kik a visszatérő vendégek?
  8. Van-e szabad szoba 3 fő részére, 2020.12.30-tól 2021.01.02-ig?
  9. A fogadó adatvédelmi nyilatkozata szerint a vendégek adatait 1 évig őrzik meg. Soroljuk fel azokat a foglalásokat és vendégeket, amiket / akiket törölni kell az adatbázisból!
  10. Van-e olyan foglalás az adatbázisban, ahol véletlenül túl kicsi szobát adtak?
  11. Vannak-e ütköző foglalások az adatbázisban, amikor ugyanarra az időszakra két vendégnek kiadták ugyanazt a szobát?
  12. Javítható-e a hiba, azaz van-e üres szoba nekik?
Megoldás
  1. A szobákat nem feltétlenül kellene sorszámozni, ha figyelünk rá, hogy mindegyik szoba neve eltérő legyen. A vendégeknél viszont ez feltétlenül szükséges, mert lehetnek ugyanolyan nevű vendégek.
  2. Ehhez össze kell adnunk az összes szoba ágyainak és pótágyainak számát.
  3. A vendégek táblázatát kell csak nézni, szűrni irányítószámok szerint.
  4. Meg kell keresni a szoba sorszámát. Utána a foglalások közül azokat kell megszámolni, amikhez ez a sorszám tartozik.
  5. Megkeressük a szoba sorszámát. Ezután pedig végignézzük a foglalások közül azokat, ahol ezt a sorszámot látjuk. Ha a megadott időintervallum nem fed át semelyik foglalással, akkor igen. (A régi vendég távozása, és az új vendég érkezése eshet egy napra. Ha az előbbi reggel elutazik, akkor az utóbbi délután már megkaphatja a szobát.)
  6. Érdemes egy segédtáblázatot készíteni: szoba sorszáma, foglalások száma. A foglalások táblázatát vizsgálva ezt ki tudjuk tölteni (lásd a fenti, dolgozatos feladatot). Ha megvan, megkeressük a maximumot: a szoba sorszáma alapján pedig a neve meghatározható a szobák táblázatából.
  7. Ehhez is segédtáblázatot készítünk: vendég sorszáma, foglalások száma. Ha elkészült, akkor azokat válogatjuk ki, akiknél a foglalások száma ≥ 2. Így kapunk néhány vendégazonosítót, amikhez kikeressük a neveket.
  8. Segédtáblázatot készítünk a szobákból. Kihúzzuk azokat, amik 3 fősnél kisebbek. Végignézzük a foglalásokat, csak azokat figyelembe véve, amik átfednek a megadott időintervallummal. Amik igen, az ahhoz tartozó szobákat is kihúzzuk. A megmaradt szobákat adhatjuk ki; ha legalább egyet találtunk, a válaszunk: van szabad szoba. Sokat segítene a megoldásban, ha naptárszerűen látnánk a foglalásokat. Tehát megoldási módszer lehet az is, hogy az összes foglalást felvezetjük egy naptárba, amiben utána már könnyű az adott időszakot vizsgálni.
  9. Töröljük az egy évnél régebbi foglalásokat. Utána pedig töröljük azokat a vendégeket, akikhez nincs foglalás rögzítve (vagy épp most lett törölve). Vigyázat: egy foglalás törlése nem jelenti azt, hogy a vendéget is törölni kell; lehetett egy évnél frissebb foglalása is.
  10. Végignézzük a foglalásokat. Mindegyiknél a szoba sorszáma alapján megkeressük a szobát is. Ha ágyak + pótágyak < személyek száma, akkor hibát találtunk.
  11. Minden foglalást megvizsgálunk, hogy van-e olyan másik foglalás, amelyik ugyanarra a szobára, átfedő időszakra vonatkozik.
  12. Ha találunk ütközést, akkor valamelyik foglaláshoz másik szobát kell keresni (lásd a fenti feladatot). Vigyázat: ha A foglalás ütközik B-vel, akkor előfordulhat, hogy csak A-t, vagy csak B-t tudjuk máshova költöztetni (mert eltérő időszak, eltérő vendégszám lehet.) És vigyázat: lehet, hogy kettőnél több foglalás ütközik!

5. Térkép

Az alábbi elnagyolt térkép néhány várost és azok GPS koordinátáit mutatja. Jelöli a köztük vezető utakat is, azok neveivel és hosszaival együtt:

térkép

A térkép adatait a gépi feldolgozáshoz táblázatban rögzítjük. Kézenfekvő megoldás a városoknak és az utaknak két külön táblázatot csinálni, hiszen

  • A számuk különböző (egymástól függetlenül változhat).
  • A városokhoz (név, gps) és az utakhoz (név, hossz) eltérő adatokat rögzítünk.

Építsük fel a táblázatokat, feltüntetve az összes várost és utat!

SorszámNévGPS
1Budapest47.49, 19.04
2Székesfehérvár47.19, 18.41
...
Városok
HonnanHovaNévHossz
12M765
...
Utak

Az adatmodell

Válaszoljuk meg az alábbi kérdéseket!

  1. Miért kellett beszámozni a városokat? Azonosíthatna egy várost a neve is?
  2. Az utakhoz nem rendeltünk hasraütésszerű sorszámokat. Be kellene számozni ezeket is?
  3. A táblázatban szereplő első út Budapestről Székesfehérvárra megy a sorszámok szerint. Nem Székesfehérvárról megy Budapestre? Miért? Lenne értelme ennek a megkülönböztetésnek?
Megoldás
  1. A várost nem tudja a neve azonosítani. Különböző országokban (esetleg egyes országokban különböző tartományokban) lehet ugyanolyan nevű város.
  2. Nem szükséges. Lehetnek ugyan párhuzamosan futó utak (pl. Budapest–Székesfehérvár között nem csak az M7-esen, hanem a 7-esen is mehetünk). Ugyan egy útnak lehetnek különböző szakaszai (pl. a térképen az M5 és az M6), de ha két város közt két út is van, azok eltérő nevet kapnak.
  3. Ebben a példában nincs értelme a megkülönböztetésnek. Ha tárolnánk egyirányú utcákat, akkor lehetne.

Keresések

Hogyan lehet a táblázatok alapján válaszolni az alábbi kérdésekre?

  1. Mi Veszprém sorszáma? Mi Debrecen sorszáma?
  2. ... Mit tehetünk annak érdekében, hogy erre a kérdésre gyorsabban lehessen válaszolni?
  3. Megy közvetlen út Kecskemétről Pécsre?
  4. ... Mit tehetünk annak érdekében, hogy erre a kérdésre könnyebben (kevesebb keresgéléssel) legyen válaszolni?
  5. Milyen hosszú a közvetlen út Bátaszék és Szeged között?
  6. Mennyi idő alatt lehet a Kecskemétről Dunaújvárosra tartó úton végigautózni?
  7. Milyen hosszú az M6-os út?
  8. ... Mit tehetünk annak érdekében, hogy erre a kérdésre könnyebb legyen válaszolni?
  9. ... Biztosan tudunk válaszolni erre a kérdésre?
  10. Mely városokat érinti az M5-ös?
  11. Soroljuk fel útirány szerint, mely városokat érinti az M5-ös!
  12. Vegyük sorra az eddigi megoldásainkat! Képzeljük el, hogy a városok táblázata 1) sorszám szerint, 2) ábécé rendbe van rendezve! Képzeljük el, hogy az utak táblázata 1) név szerint, 2) város sorszámok szerint, 3) hossz szerint van rendezve. Melyik eset, melyik feladat megoldását gyorsítja vagy lassítja?
  13. Igaz-e, hogy minden út Rómába vezet?
Megoldás
  1. Ezekhez végig kell néznünk a városok táblázatát. Ha megvan a város, a sorszám kiolvaható.
  2. ... Ha ábécébe rendezzük a városokat, akkor könnyebb megtalálni valamelyiket.
  3. Kikeressük Kecskemét sorszámát és Pécs sorszámát, mint az előző feladatban. Ha megvan mindkettő (pl. 3 és 5 a sorszámok), akkor megnézzük, hogy szerepel-e ilyen út a második táblázatban. Vigyázat: lehet, hogy 3→5, de az is lehet, hogy 5→3 formában találjuk meg.
  4. ... Ha a városok ábécében vannak, akkor könnyebb a sorszámokat megtalálni. Az utaknál figyelhetünk arra, hogy a „honnan” sorszám mindig a kisebb, a „hova” mindig a nagyobb legyen; tehát pl. 3→5-öt nem visszük fel a táblázatba 5→3 formában. Ezen felül, rendezhetjük az utakat is, a „honnan” város sorszáma, azon belül pedig a „hova” város sorszáma alapján, ezzel is segítve a keresést.
  5. Hasonlóan, mint az előző feladat, de egy másik oszlopban van a válasz.
  6. Nem tudjuk megmondani. Nem ismerjük a táblázatból a sebességkorlátozásokat.
  7. Ehhez végig kell néznünk az utak táblázatát, hogy hol szerepel „M6” a névnél. A kapott sorokban található hosszakat kell összegezni.
  8. ... Ha az utak táblázata rendezve van az út neve szerint, könnyebben megtaláljuk a keresett utat. A felette és az alatta lévő sorokat kell vizsgálni.
  9. ... Valójban nem. Az M7-es például továbbmegy a Balaton felé, de a térkép csak az első szakaszát jelöli, és ezáltal a táblázat is.
  10. Ehhez előbb meg kell keresnünk az M5-ös szakaszait az utak táblázatából, „honnan–hova” párokat kapva. A kapott számok közül kiválogatjuk a különbözőeket. (Lesznek egyformák, pl. Kecskemét→Budapest és Kecskemét→Szeged miatt.) A kapott sorszámokhoz tartozó városokat pedig kikeressük a városok táblázatából.
  11. A fentihez hasonlóan megkeressük az M5 szakaszait. De utána sorba is kell rakni azokat. Ezért keresünk ezek közül egy olyan sorszámot, amelyik csak egyszer szerepel – mert ez az út eleje vagy vége. (Elméletben pontosan kettő ilyen kell legyen, különben nem ismerjük az út összes szakaszát, vagy körbe-körbe megy az út.) Ettől kiindulva fel tudjuk sorolni az útvonalba eső városokat, mintha dominókként tennénk egymás után a számpárokat, pl. 5–8, 8–7, 7–11. Ezekből a kiinduló sorszámokra van szükségünk, és az utolsó párból az érkezőre is, pl. 5, 8, 7, 11. A sorszámok alapján pedig megkeressük a városokat, hogy a nevük is meglegyen.
  12. Mindig azt figyeljük, hogy amikor keresnünk kell valamit, akkor a táblázat aszerint van-e rendezve! Például ha fel kell sorolnunk azokat az utakat, amelyek egy bizonyos városból kiindulnak, akkor 1) jó, ha a városok táblázata ábécében van, mert akkor a várost hamar meg fogjuk találni, 2) jó, ha az utak táblázata sorszámok szerint, mert akkor az utakat hamar megtaláljuk, 3) ugyanakkor ez az utak megkeresésében nem segít, mert az a táblázat nem lehet egyszerre a „honnan” és a „hova” oszlop szerint is rendezve.
  13. A kérdés elég zavaros... De vegyük úgy, hogy azt kérdezi, van-e olyan város, ahonnan nem lehet eljutni Rómába. Valójában ezt könnyebb fordított irányba haladva megválaszolni. Keressük meg Róma sorszámát. Ezután keressük meg azokat az utakat, amik érintik ezt a várost („honnan” vagy „hova” sorszámuk megegyezik Rómáéval). Jegyezzük fel az így kapott városokat, jelöljük meg őket, hogy oda el lehet jutni. Keressük meg az ezekhez tartozó utakat is. Folytassuk addig, amíg találunk új várost – ha valamelyikben jártunk, azt hagyjuk figyelmen kívül. Amint végeztünk, már csak meg kell vizsgálni, van-e olyan város, amit nem jelöltünk be. Feltételezve, hogy az utak kétirányúak, ha Rómából nem lehet oda eljutni, akkor onnan sem lehet Rómába.

Módosítások

Hogyan kell módosítani a táblázatokat ezekkel az adatokkal? Mire kell figyelni?

  1. Új várost rögzítünk a táblázatban: Tatabánya. Mi a teendő?
  2. Szeretnénk felvinni az M1-es első szakaszát: Budapest–Tatabánya. Mi a teendő?
Megoldás
  1. Meg kell keresni, hogy szerepel-e már a város, mert nem lehet bent többször a táblázatban. Ha nincs, egyedi sorszámot hozzárendelve kell felvinni. Az egyedi sorszám lehet például a legnagyobb ismert sorszám + 1.
  2. Meg kell keresni a városok sorszámait. Amelyik város nem szerepel a táblázatban, fel kell vinni. Ha megvan mind a két sorszám, akkor már az utat is beírhatjuk a másik táblázatba – ha még nem szerepel.