4.1
ÉpítsÜnk fel egy olyan listaszerkezetet, amelyben az elemek
névsor szerint helyezkednek el egy vektorban! A lista
felépítésekor az alábbi mÜveleteket kell végrehajtani:
1. Beillesztés: KATI
2. Beillesztés: R•ZSI
3. Törlés: KATI
4. Beillesztés: MÁRIA
5. Beillesztés: BEA
6. Beillesztés: SACI
7. Törlés: MÁRIA !
Minden lépés után jegyezzük fel az adat- és a mutatóvektor
alakulását!
4.2
Listába fűzve tárolunk adatokat az LI$() nevű szöveges tömb-
ben, a MUT() nevű tömböt használva mutató tömbként. SF a sza-
badlistafej, MUT(0) a listafej. Néhány műveletet végrehajtva
adatszerkezetünk a következőképpen néz ki:
I LI$(I) MUT(I)
1 GÉZA 3
2 LAJOS 6
3 SANYI 0
4 ÉVA 2
5 ALAJOS
8
6 PISTA
10
7 SÁRI 9
8 BARNABÁS 4
9 PALI 1
10 ZOLI 0
MUT(0)=5 , SF=7
Végezzük el a következő műveleteket!
1. Beillesztés: ALBERT
2. Törlés: ZOLI
3. Beillesztés: DEMETER
Írjuk le minden művelet után, hogy néz ki az adatszerkezet!
Soroljuk fel, hogy a műveletek elvégzése után melyek a szabad
helyek!
4.3
Rendelkezésünkre áll a T$(), P() adat és mutatótömb. Ezekben
először kialakítottunk egy szabadlistát, majd a következő
sorrendben beillesztettünk hat adatot:
ABLAK, CINTULA, KALAP, FAL, ZAK•, BAB.
Írjuk ki a műveletek elvégzése után az adat és mutatótömb
elemeit! Végezzük el a következő teendőket!
1. Törlés: ZAK•
2. Beillesztés: MALAC
3. Törlés: CINTULA
4. Törlés: ABLAK
Hogyan néz ki most a két tömb?
4.4
Készítsünk algoritmust és programot, amely megvalósítja az
összes LISTA műveletet! Az elemek tárolására használjuk a
LI$(), a mutatók tárolására a MU() tömböt! Az elemek logikai
sorrendje olyan legyen, hogy bejáráskor növekedő sorrendben
kapjuk őket vissza!
4.5
Személyi számokat tárolunk az S$() tömbben. Ezek növekvő sor-
rendben listába vannak fűzve. Feltesszük, hogy csak 1900 után
született magyar állampolgárok szerepelnek a nyilvántartás-
ban. A FEJ változó legyen a fejmutató, az M() pedig a mutató
tömb. Írjunk algoritmust, amely a FEJF, FEJN változók és az
N() tömb segítségével szétválogatja a férfiakat és a nőket!
N() tömbben legyenek a két új lista mutatói!
4.6
Adott egy lista az E$() tömbben. A láncoláshoz szükséges mu-
tatókat a P() tömb tartalmazza. A P(0) mutat a lista első
elemére (a lista feje). Írjunk algoritmust, amely a lista
elemeinek sorrendjét megfordítja!
4.7
Készítsük el azt az algoritmust, amely két azonos típusú ele-
mekből álló rendezett listát úgy egyesít egy listává, hogy a
rendezettség továbbra is megmarad!
4.8
A kétirányú lista elemei mindkét irányban láncolva vannak.
Két fejmutató jelzi a láncolások kezdetét. Írjuk meg a kere-
sés, beszúrás, törlés és a mindkét irányú bejárás eljáráso-
kat!
4.9
Írjunk olyan programot, amely egy egyirányú listából kétirá-
nyú listát készít egy új mutatótömb segítségével!
4.10
Ha egy felépített listaszerkezetben kell elemeket keresni,
akkor nem célszerű mindig az elejéről indítani a keresést.
Ilyenkor szoktunk ciklikus listát használni. Ennél a szerke-
zetnél a fejmutató az utolsó műveletben utoljára megtalált
elemre mutat. Algoritmus megírása után készítsük el azt a
programot, amely bemutatja a ciklikus lista működését!
4.11
Készítsünk programot, amely listába fűzött számlálókat tud
csökkenteni 'párhuzamosan'! (Egy időegység alatt mindegyik
változó értéke 1-gyel csökkenjen!) Akármikor be lehessen
avatkozni és definiálni egy új számlálót (név, kezdőérték
megadásával). A számláló szűnjön meg, ha értéke elérte a 0-t!
Alkalmazzuk a ciklikus lista adatszerkezetét! —j számláló
létrehozását valamilyen billentyű leütésével lehessen jelez-
ni. A program futásakor legyen látható a képernyőn az összes
számláló neve és pillanatnyi értéke!
4.12
Készítsünk programot, amely számlálók értékét tudja lépésen-
ként 1-gyel változtatni! Induláskor lehessen ezek neveit, a
hozzájuk tartozó kezdőértékeket megadni; és mindegyikről meg
kelljen mondani, hogy növelni, vagy csökkenteni kell az érté-
két! A felhasználó futás közben tudjon új számlálót a láncba
illeszteni ((név, érték, nő-csökken) megadásával) és lehessen
már létező számláló változásának irányát megfordítani! Egy
számláló szűnjön meg, ha értéke 0-nál kisebbre változik!
4.13
Algoritmust és programot kell készíteni, amelyikkel kétirá-
nyú, ciklikus lista műveleteit tudjuk megvalósítani!
4.14
Nyilvántartást szeretnénk vezetni egy vállalat dolgozóiról.
Minden személyről tároljuk a nevét, személyi számát, címét,
foglalkozását. Különböző szempontok szerint kívánunk a majda-
ni adathalmazban keresni. A gyors elemelérés érdekében minden
szempont szerint listába fűzzük az adatokat. Ha két különböző
adatnak valamelyik mezője megegyezik, akkor ezek a személyi
számok szerint legyenek egymás között rendezve. Írjunk prog-
ramot, amely felépíti a listákat, majd különböző szempontok
szerint keressünk az adatállományban!
4.15
Egy osztály tanulóinak ismerjük a nevét és személyi számát.
Külön-külön listába fűzve, személyi szám szerint növekvő sor-
rendben adott a fiúk, illetve a lányok listája. Fűzzük egybe
a két listát személyi szám szerint növekvő sorrendbe!
4.16
Egy iskolanyilvántartásban adottak az osztályok tanulóinak
listái. Fűzzük őket egymás után!
4.17
Az olimpiára jelentkezett sportolókat egy listába fűzve tá-
roljuk ország-, azon belül pedig névsor szerinti sorrendben.
Megkapjuk egy újabb jelentkező ország sportolóit névsor sze-
rint egy másik listába fűzve, illesszük be őket a megfelelő
helyre!
4.18 *
Ismerjük egy osztály tanulóinak nevét és személyi számát,
személyi számok sorrendjében listába fűzve. Készítsünk hozzá
egy újabb listát, amelyben az elemek névsor szerint követik
egymást!
4.19
Egyetemi hallgatók adatait névsor szerint növekvő sorrendben
tároljuk, listaszerkezetben. Az egyik lány férjhezment, s
emiatt megváltozott a neve. Helyezzük át őt a névsor szerint
megfelelő helyre!
4.20
Ismerjük egy osztály tanulóinak nevét és személyi számát,
személyi számok sorrendjében listába fűzve. Válogassuk ki
újabb listákba a fiúkat, a lányokat, az olyan fiúkat az
aktuális évben betöltik 18. életévüket!
4.21
Egy iskola tanulóit a következőképpen tároljuk: az osztályo-
kat listába fűzzük, s ezen a listán belül egy-egy osztály egy
újabb allista, névsor szerint rendezve. Készítsük el ehhez az
adatszerkezethez a következő eljárásokat:
1. egy tanuló törlése,
2. új tanuló felvétele valamelyik osztályba,
3. egy tanuló áthelyezése másik osztályba,
4. tanév végén a 4.-esek megszüntetése, mindenki egy osz-
tállyal feljebb lép, majd az új elsősök felvétele.
4.22
Megvalósítottunk egy veremként működő adatszerkezetet.
Ábrázoljuk hogyan alakul a verem állapota a következő
műveletek elvégzése közben!
1. Tetejére:ALMA,
2. Tetejére:FA,
3. Tetejéről,
4. Tetejére:VEREM,
5. Tetejéről,
6. Tetejéről.
Megoldás:
1. művelet után: ALMA
2. művelet után: ALMA FA
3. művelet után: ALMA
4. művelet után: ALMA VEREM
5. művelet után: ALMA
6. művelet után: <üres>
4.23
Rendelkezésünkre áll egy N elemű vektor. Írjunk algoritmust
és programot a VEREM műveleteinek megvalósítására!
4.24
Egy N elemű vektort tudunk csak használni, de két vermet is
meg kell valósítani, amelyek együttes helyfoglalása elérheti
a tömb méretét. Készítsük el a VEREMműveleteket megvalósító
programot!
4.25
Egy 20 elemű tömbben tárolunk öt vermet is. —gy oldottuk meg
az elhelyezésüket, hogy listába fűztük az azonos veremhez
tartozó értékeket egy másik tömb és öt fejmutató segítségé-
vel. A maximális helykihasználás végett az éppen szabad he-
lyek szabadlistába vannak fűzve.
A veremmutatók : V1=14, V2=10, V3=18, V4=3, V5=0.
A szabadlistafej: SF=12.
Az adatok :
SORSZÁM ELEMEK MUTAT•
1. 4532 6
2. Alap 19
3. Fakír 4
4. Jóska 8
5. Sanyi 0
6. Data 0
7. 35288 16
8. Tegnap 2
9. Lapos 13
10. Vége 15
11. 24356 9
12. Lajos 7
13. 34455 20
14. Csaba 11
15. 57646 1
16. 87432 17
17. Goto 0
18. Print 0
19. If 5
20. Eleje 0
Az adott veremnek akkor van vége, ha az aktuális elem mutató-
ja 0. Soroljuk fel a vermek elemeit elérési sorrendben! Írjuk
le a szabad helyek számát!
4.26
Egy vektort tudunk három VEREM számára lefoglalni. Sajnos nem
biztos, hogy a vektorban van hely minden elemnek. Oldjuk meg,
hogy amíg a vektorban akár egy hely is van szabadon, akárme-
lyik VEREMbe tudjunk elemet berakni! Futásidő ne legyen szem-
pont, ha kell, akkor mozgassuk az elemeket nyugodtan!
4.27
Három VEREM szöveg tipusú adatai számára egy tömböt tudunk
lefoglalni. Sajnos nem biztos, hogy a vektorban van hely min-
den elemnek. Oldjuk meg, hogy amíg a vektorban akár egy hely
is van szabadon, akármelyik VEREMbe tudjunk elemet berakni! A
programot úgy tervezzük meg, hogy a berakott adatokat ne
kelljen mozgatni a memóriában! (Numerikus tömböt, a mutatók
számára létrehozhatsz!)
4.28
Írjuk le a verem állapotát lépésről-lépésre a következő LOGO
program végrehajtása közben, ha bemenő adat a SZALMA szó volt
és feltesszük, hogy a gép a szükséges paramétereket tárolja a
veremben!
TO ABETU :SZO
IF EMPTY :SZO THEN OUTPUT "FALSE
IF FIRST :SZO = "A THEN OUTPUT "TRUE
ELSE OUTPUT ABETU BUTFIRST :SZO
END
4.29
Hozzuk lengyel formára a következő kifejezést és ábrázoljuk
lépésenként a verem állapotát!
3*(4-5*(3-15)/4)+100
4.30
Végezzük el az alább adott lengyel formára hozott kifejezés
kiértékelését!
100 15 3 - 4 5 / * 4 - 3 * +
4.31
Készítsünk programot, amely lengyel formára hoz konstansokat
és alapműveleteket tartalmazó numerikus kifejezést!
4.32
Lengyel formára hozott kifejezést kiértékelő algoritmust és
programot kell írni! A kifejezésben csak konstansok, műveleti
jelek (esetleg függvények) szerepelnek.
4.33
Van három vermünk. Az egyikben, a tetejétől lefelé növekedően
felsoroltuk 1-től 5-ig a számokat. A másik kettő üres. Rakjuk
át az elemeket -csak veremműveletek használatával- az egyik
üres verembe, ugyanilyen sorrendben úgy, hogy ne rakjunk soha
kisebb számra nagyobbat! (Hanoi tornyai)
Az alfejezet további feladatai a FORTH nyelvhez kapcsolód-
nak. A nyelv lelkivilága miatt tartottuk indokoltnak ezen
feladatok leírását éppen a verem adatszerkezettel foglakozó
problémák között. Vannak olyan feladatok, ahol maga a szöveg
nem emeli ki a paraméter- és vezérlésiverem vizsgálatát, de
természetesen ezek sem oldhatók meg a VEREM ismerete nélkül.
Ezen feladatok nagy része szerepel a könyv más fejezete-
iben is, itt csak azért ismételjük meg őket, mert a FORTH
nyelv egészen más megoldást követel.
4.34
Határozzuk meg két szám legnagyobb közös osztóját! Eredményül
írjuk ki a két számot, valamint a legnagyobb közös osztót! A
program lefutása után a verem legyen üres!
4.35
FORTH nyelven írjunk olyan programot, amely meghatározza két
szám legkisebb közös többszörösét! Ábrázoljuk a verem álla-
potát egy-egy utasítás elvégzése után, ha a két szám: 6, 8!
4.36
A K számról kell eldönteni, hogy Fibonacci-szám-e! Készítsünk
FORTH programot ennek elvégzésére! Kövessük végig a paramé-
terverem alakulását, ha K=34!
4.37
Adott egy pozitív egész szám. Határozzuk meg az első, nála
nem kisebb négyzetszámot! A verem legyen üres a program vé-
gén!
4.38
Határozzuk meg egy pozitív számhoz legközelebbi négyzetszá-
mot! A program lefutása után a verem legyen üres!
4.39
Számold meg FORTH program segítségével, hogy hány olyan elem
van a veremben, amelyik 10-nél nagyobb és 100-nál kisebb.
4.40
A veremben van egy X elemű vektor és egy B szám. (A verem te-
tején a B szám, alatta a vektor elemszáma, ez alatt a legna-
gyobb indexű elem.) Számoljuk meg, hogy a vektornak hány
B-nél kisebb eleme van!
4.41
Mondjuk meg, hány osztója van a veremben levő számnak!
4.42
Határozzuk meg N különböző prímosztóinak a számát! (N a verem
tetején van. )
4.43
Egy természetes szám nem prím osztóinak számát számítsuk ki!
(A számot a verem tetején találjuk.)
4.44
Határozzuk meg a verem tetején levő természetes szám legna-
gyobb multiplicitású prímosztóját!
4.45
Írjuk ki a P természetes számhoz legközelebb álló kettőhat-
ványt! (P a verem tetején van.)
4.46
Számítsuk ki a verem tetején lévő természetes számhoz legkö-
zelebbi páratlan négyzetszámot!
4.47
Határozzuk meg a növekvően rendezett X vektornak azt a K in-
dexét, amelyre:
ABS(X(K)-X(K-1))+ABS(X(K+1)-X(K))
maximális! (Az X vektor a veremben van, a verem tetején a da-
rabszáma, alatta a legnagyobb indexű elem, ez a legnagyobb!)
4.48
Adott az X vektor és egy P szám. (A verem tetején a P van,
alatta a vektor elemeinek száma, ez alatt a legnagyobb indexű
vektorelem.) Írjuk ki a vektorban levő P-nél kisebb, P-vel
egyenlő, illetve P-nél nagyobb elemek számát!
4.49
Döntsük el, hogy a P természetes számnak (P a verem tetején
van) van-e páratlan valódi osztója!
4.50
Adjunk meg egy olyan számot, amely relatív prím a verembeli
számhoz!
4.51
Írjunk programot, amely kiszámítja a verem tetején található
szám legkisebb páratlan, valódi osztóját!
4.52
Határozzuk meg a P természetes szám legkisebb egyszeres
osztóját!
4.53
Egy vektor [P,Q] intervallumba eső elemeinek a számát és azok
összegét kell meghatározni! (A veremben először az X vektor
elemszáma, azután az elemek, majd P és Q van.)
4.54
Keressük meg az X vektorban a maximális összegű szomszédos
elempárt! A verem tetején a vektor elemszáma, majd alatta az
elemek vannak.
4.55
Adjuk meg az X vektornak azt az elemét, amelyiknek a szom-
szédjai átlagától vett eltérése a legnagyobb!
4.56
Adott a P és a Q szám (a verem tetején van a Q, alatta a P).
Határozzuk meg azt a P-nél nem nagyobb számot, amelynek Q-val
vett osztási maradéka 1!
4.57
Adott egy N elemű vektor. Készítsünk programot, amely a beér-
kező adatot a SOR végére teszi és egy jelre a legrégebben
bentlevőt kiírja képernyőre!
4.58
Olyan programot írjunk, amely a kívánt elemeket SORba illesz-
ti! Oldjuk meg azt is, hogy ha a felhasznált tömbnek a végére
értünk, akkor lehessen az elején felszabadult helyeken foly-
tatni a beillesztést! (Ezzel CIKLIKUS SORt hozunk létre.)
4.59
Kezeljen a programunk két SORt egy vektoron belül! Az egyes
sorok maximális helykihasználását nem tudjuk előre megbecsül-
ni, ezért dinamikusan kellene a rendelkezésre álló szabad he-
lyet megosztani az adathalmazok között.
4.60 *
Szimuláljuk egy benzinkút forgalmát program segítségével!
Mérjenek a kútnál 3 különféle benzint különböző kiszolgálási
sebességgel és érkezzenek a kutakhoz más-más gyakorisággal,
véletlenszerűen autók! A paraméterek módosításával figyeljük
meg, hogy mikor torlódnak fel a kocsik benzinre várva és mi-
kor nem kell sorba állniuk!
4.61 **
Szimuláljuk egy benzinkút forgalmát program segítségével!
Mérjenek a kútnál 3 különféle benzint különböző kiszolgálási
sebességgel és érkezzenek a kutakhoz más-más gyakorisággal,
véletlenszerűen autók! Mindegyik sor maximum K autóból áll-
hat, s ha valamelyik megtelt, akkor az összes újabb autó egy
közös sorba állhat, a benzinkút előtt. A paraméterek módosí-
tásával figyeljük meg, hogy mikor torlódnak fel a kocsik ben-
zinre várva és mikor nem kell sorba állniuk!
4.62 **
Szimuláljuk egy benzinkút forgalmát program segítségével!
Mérjenek a kútnál 3 különféle benzint különböző kiszolgálási
sebességgel. Van olyan benzinfajta, amelyet egyetlen helyen
adnak, s van olyan, amelyet két helyen. Érkezzenek a kutakhoz
más-más gyakorisággal, véletlenszerűen autók! Minden autóval
a szükséges benzinfajtákhoz álló sorok közül a rövidebbe áll-
nak be! A paraméterek módosításával figyeljük meg, hogy mikor
torlódnak fel a kocsik benzinre várva és mikor nem kell sorba
állniuk!
4.63 *
Szimuláljuk egy benzinkút forgalmát program segítségével!
Mérjenek a kútnál 3 különféle benzint különböző kiszolgálási
sebességgel és érkezzenek a kutakhoz más-más gyakorisággal,
véletlenszerűen autók! Ha a megfelelő fajtájú benzinért túl-
ságosan hosszú sor áll, akkor az autós adott valószínűséggel
dönthessen úgy, hogy nem áll be a sorba! A paraméterek módo-
sításával figyeljük meg, hogy mikor torlódnak fel a kocsik
benzinre várva és mikor nem kell sorba állniuk!
4.64 *
Egy kis közértben csupán egyetlen eladó dolgozik. § áll a hú-
sospultnál, s szükség esetén átmegy a pénztárhoz, illetve
vissza. (Az átmenés is valamennyi időbe kerül.) Érkezzenek a
közértbe vásárlók, s kövessük nyomon a sorok alakulását az
eladó különböző stratégiái szerint!
4.65 **
Tegyük fel, hogy egy áruházban nincs önkiszolgáló rész, min-
denhol pultok vannak, egy eladóval. A pultok meg vannak szá-
mozva. (Legyen N db pult!) Fizetni a vásárlás végén egyben
lehet a K db pénztár valamelyikénél. Modellezzük ennek az
áruháznak a működését úgy, hogy egy vevő érkezésekor meg kell
mondani a vásárló nevét és azoknak a pultoknak a sorszámát,
amelyeknél vásárolni kíván! Kíváncsiak vagyunk, hogy az egyes
vásárlók mennyi időegységet töltöttek az üzletben. Egy idő-
egység alatt minden sorból, a legrégebben beállt ember menjen
a következő állomáshelyre! Ezt úgy válassza meg, hogy minél
kevesebben legyenek előtte! —j ember érkezését billentyű le-
nyomásával kell jelezni!
4.66 **
Módosítsuk az előző feladatot úgy, hogy van M tartalék eladó,
akik beállhatnak olyan pultokhoz dolgozni, ahol túlságosan
hosszú sorok állnak! Ettől ezekben a sorokban kétszer olyan
gyorsan szolgálják ki a vevőket. Ha a sor elég rövid lett,
akkor a második eladó elmehet a pult mögül.
4.67 **
Módosítsuk az előző feladatot úgy, hogy a nyitva tartó pénz-
tárak számát is a forgalomhoz igazítjuk! Ha túl hosszúak a
sorok, akkor új pénztárt nyitunk; ha pedig rövidek, akkor
egyes pénztárakat lezárunk, azaz a még sorban állókat kiszol-
gáljuk, de újabb vevők már nem állhatnak be abba a sorba.
4.68 *
Egy áruházban a liftet csak úgy lehet használni, ha legalább
N ember akar vele a földszintről felmenni valamelyik emelet-
re, s ekkor K időegység múlva tér vissza a földszintre. Ké-
szítsünk programot, amely rendszertelenül érkező emberek ese-
tén szimulálja a lift működését!
4.69 *
Gépkocsikkal üzletelő cégnek kell programot írnunk! N típusú
autót árusít. Az igénylők érkezési sorrendben várakoznak a
kocsikra. Egyszerre egyféle autóból jön, de bármelyik típus-
ból is érkezzen, egyszerre mindig K db-ot hoznak. A program
legyen képes az igényeket sorba állítani és a kiértesítendő
vevőket kiírni! Tároljuk a vevők nevét, címüket és tipusigé-
nyüket!
4.70 *
Egy rendezőpályaudvaron szerelvényeket állítanak össze külön-
böző úti céllal. A szerelvényt akkor tekintjük késznek, ha a
mozdony teherbírásának megfelelő számú kocsit összekapcsoltuk
és van mozdony, amely elviheti. Készítsünk programot, amely-
lyel szimulálni lehet a rendező forgalmát.
4.71
Egy metróállomás mozgólépcsőjének működését kell szimulál-
nunk. A mozgólépcsőt jelképező sorba rendszertelenül lépnek
be emberek (egyszerre 0, 1 vagy 2), s mindegyiknek K időegy-
ségig kell a sorban tartózkodnia (ennyi idő alatt lehet a
lépcsőn végigérni, ha állva utazik rajta).
4.72 *
Egy OTP-fiókban különböző helyen lehet pénzt befizetni, köl-
csönt felvenni, valutát váltani stb. Bármelyik helyen is van
dolgunk, utána a pénztárnál kapjuk meg a pénzt, illetve kell
nekünk fizetni. Minden helyen sorba kell állni, s a forgalom-
tól függően mindenhol 1, 2 vagy 3 OTP-ügyintéző foglalkozik
az ügyfelekkel. Kövessük végig program segítségével az OTP
forgalmát!
4.73 *
Egy automata szerszámgép úgy dolgozik, hogy egy előtte levő
sorból elvesz egy munkadarabot, azzal elvégzi a teendőit (ez
fajtánként más-más időbe telik), majd kirakja egy másik sor-
ba. Egy dolgozó tölti fel a szerszámgép előtti sort úgy, hogy
egyszerre K db munkadarabot hoz bele. Ugyanez a dolgozó a
szerszámgép utáni sorból egyszerre szintén K darabot tud el-
vinni. Mindkét sorba N munkadarabot lehet elhelyezni. Köves-
sük nyomon a sorok alakulását a dolgozó különböző stratégiái
szerint!
4.74
Egy orvos várószobájába egyenként érkeznek a betegek, érkezé-
si sorrendben mennek be az orvoshoz, aki különböző ideig fog-
lalkozhat velük. Időnként érkezhetnek olyan betegek is, akik-
kel azonnal kell foglalkozni, s így soron kívül bejuthatnak
az orvoshoz. Vizsgáljuk meg, hogyan függ a sűrgős esetek szá-
mától, az egyes betegekre fordított időtől a sor átlagos
hossza, a sorban töltött átlagos idő!
4.75 *
Egy N vonalas munkahelyi telefonközpont úgy működik, hogy ha
van szabad vonal, akkor a telefonáló azonnal kap vonalat, s
hívhatja azt, akivel beszélgetni akar; ha pedig nincs, akkor
az igényeket sorbaállítja, s ha egy vonal szabadul, akkor a
legrégebbi igénylőnek adja. Megengedünk egy olyan műveletet
is, amely a sorra általában nem jellemző: hosszú várakozás
esetén egyes telefonálni akarók letehetik a telefonkagylót, s
ekkor el kell őket távolítani a sorból. Kövessük nyomon a vá-
rakozási idő alakulását!
4.76 **
Mivel csak egyetlen lemezegységünk, illetve nyomtatónk van,
ezért számítógépeinket összekapcsoltuk. A hálózat használata
a következőképpen történik: a gép lehetőséget kér az eszköz
használatára, s ha az szabad, akkor a vezérlő leköti számára,
s ezt tudatja vele. Ezután küldhet adatokat a lemezre (nyom-
tatóra) amíg egy speciális végjelet nem küld. Ha közben más
is szeretné ezeket az eszközöket használni, akkor a kéréseket
sorbaállítja, s olyan üzenetet küld vissza, hogy várjanak. Ha
az eszköz felszabadult, akkor a legrégebben várakozónak üzen,
hogy kezdheti a használatát. Írjuk meg a hálózatot vezérlő
programot!
4.77 *
A számítógép megszakításosan kezeli a billentyűzetet. Ha egy
billentyűt leütünk, akkor az aktuális programfutás megszakad,
s a megszakításkezelő szubrutin elhelyezi a leütött billen-
tyűhöz tartozó karaktert egy sorba. Amikor a program INPUT
utasítást hajt végre, akkor az adatokat a sorból kell venni,
illetve ha az kiürült, akkor várni kell addig, amíg a megsza-
kításkezelő szubrutin nem vesz egy végjelet. Írjuk meg a meg-
szakításkezelő szubrutin, illetve az INPUT utasítást végre-
hajtó szubrutin algoritmusát!
4.78
Amikor a számítógéppel lemezműveletet hajtunk végre (írás
vagy olvasás), akkor nem történik mindig fizikai lemezműve-
let. Például írásnál a kiírandókat a számítógép egy pufferba
gyűjti (ez egy sor, aminek csak a végére lehet írni), s ha
megtelt, akkor az egészet kiviszi lemezre (ez a lemezen éppen
egy blokk), majd csak ezután fogadja a következő írnivalót.
Készítsünk eljárásokat mind a beolvasás, mind a kiírás blok-
kosított megoldására!
4.79
Adjunk össze program segitségével, két egyforma méretű mát-
rixot!
4.80
Készítsünk programot, mely két mátrixot öszead és megvizsgál-
ja, hogy eredményül a csupa nulla elemeket tartalmazó mát-
rixot kaptuk-e!
4.81
Két mátrix összeadása után a program ellenőrizze, hogy az
egységmátrixot kaptuk-e végeredményként!
4.82
Adjuk meg egy N*N-es mátrix transzponáltját!
4.83
Írjunk programot, amely egy N*M és egy M*K méretű mátrixot
összeszoroz!
4.84
Síkbeli transzformációkat kell szemléltetni számítógépes gra-
fika segítségével. Írjunk olyan eljárást, amely a (Px,Py)
koordinátákkal adott pontnak kiszámítja a transzformáció utá-
ni helyét! Legyen a transzfomáció az ALFA szögű elforgatás!
Ennek a leképezésmátrixa:
cos(ALFA) -sin(ALFA)
sin(ALFA) cos(ALFA)
alakú. Ha ezzel a mátrixszal szorozzuk a (Px,Py) vektort,
akkor megkapjuk a pont elforgatottját!
4.85
Síkbeli transzformációkat kell szemléltetni számítógépes gra-
fika segítségével. Írjunk olyan eljárást, amely a (Px,Py)
koordinátákkal adott pontnak kiszámítja a transzformáció utá-
ni helyét! Legyen a transzfomáció az Sx-, Sy-szoros nagyítás
az egyes tengelyek irányába! Ennek a leképezésmátrixa:
Sx 0
0 Sy
alakú.
4.86
Síkbeli transzformációkat kell szemléltetni számítógépes gra-
fika segítségével. Írjunk olyan eljárást, amely a (Px,Py)
koordinátákkal adott pontnak kiszámítja a transzformáció utá-
ni helyét! Legyen a transzfomáció az Lx, Ly-nyira eltolás az
egyes tengelyek irányába! Ennek nem létezik a leképezésmát-
rixa, ezért a következűképpen járunk el: kiegészítjük a (Px,
Py) pontot egy harmadik koordinátával: (Px,Py,1). Így már tu-
dunk adni egy leképezésmátrixot:
1 0 0
0 1 0
Lx Ly 0 .
4.87 *
Síkbeli transzformációkat kell szemléltetni számítógépes gra-
fika segítségével. Írjunk olyan eljárást, amely a (Px,Py)
koordinátákkal adott pontnak kiszámítja a transzformáció utá-
ni helyét! Tetszőleges sorrendben végezhessünk különböző na-
gyításokat, forgatásokat, eltolásokat, majd az ezek utáni he-
lyet számoljuk ki!
4.88
Eljárást kell készítenünk a térbeli nagyítás, illetve kicsi-
nyítés szemléltetésére írandó programba! Az eljárás paramé-
terként a PONT() nevű vektort kapja, ezen kell tehát a megfe-
lelő műveletet elvégezni. A leképezésmátrix alakja:
Sx 0 0
0 Sy 0
0 0 Sz .
4.89
Számítsuk ki egy kétdimenziós mátrixnak a determinánsát!
4.90
Olyan függvényeljárást kell készítenünk, amely 3x3-as mátrix
determinánsát tudja kiszámítani.
4.91 *
Készítsünk eljárást, amely NxN-es mátrix determinánsát tudja
kiszámítani!
4.92 **
Egy négyzetes mátrix inverzét szeretnénk számítógép használa-
tával kiszámítani. Olyan mátrix lesz ez, mellyel az eredetit
megszorozva az egységmátrixot kapjuk eredményül. Készítsünk
eljárást, amely előállítja az inverzmátrixot!
4.93 **
Adott egy N egyenletből és N ismeretlenből álló, homogén li-
neáris egyenletrendszer. (Homogén, ha csak 0 szerepel kons-
tansként; lineáris, ha a változók nincsenek 1-nél magasabb
hatványon.) Program segítségével döntsük el, hogy van-e ennek
az egyenletrendszernek nem triviális megoldása! (Triviális
megoldásról akkor beszélünk, ha minden ismeretlen értéke nul-
la. Ilyen akkor nincs, ha az együtthatókból képzett determi-
náns nem nulla.)
4.94 **
Egy A(N,N) mátrixról döntsük el, hogy a transzponáltja azo-
nos-e az inverzével!
4.95
Egy A(N,N) mátrixról döntsük el, hogy önmagával szorozva a
0-mátrixot kapjuk-e!
4.96
Egy A(N,N) mátrixról döntsük el, hogy valahányadik hatványa
0-mátrix-e!
4.97
Egy A(N,N) mátrixról döntsük el, hogy a transzponáltjával
balról, illetve jobbról szorozva azonos eredményt kapunk-e!
4.98
Egy N sorú, K oszlopú mátrixot kell sorfolytonosan, vektorban
tárolni. (A sorfolytonosság azt jelenti, hogy soronként tá-
roljuk az adatokat és az L. sor utolsó eleme után az L+1. sor
első eleme következik.) Adjuk meg azt a címfÜggvényt, amely
az eredeti mátrix I. sorának, J. oszlopában található elemnek
a helyét határozza meg ebben a vektorban! (Legkisebb tömbin-
dex legyen 1!)
4.99
Egy N sorú, K oszlopú mátrixot sorfolytonosan tárolunk. Ala-
kítsuk át az ábrázolást oszlopfolytonossá!
4.100
Azonos hosszúságú (12 byte-nyi) adatokból álló N*K-s mátrixot
kell a memóriában elhelyezni, mondjuk az 1000-es címtől kezd-
ve! Írjunk olyan címfüggvényt, mely megmondja az (I,J) mát-
rixelem kezdetét a memóriában! (Legkisebb tömbindex legyen az
1!)
4.101
Az alábbi speciális N*N-es felső háromszög mátrixot gazdasá-
gos módon ábrázoljuk. Csak a nem nulla elemeket - az ábrán az
X-ek jelölik ezeknek a helyét - tároljuk, sorfolytonosan egy
vektorban. Adjuk meg azt a címfÜggvényt, amely az eredeti
mátrix (I,J) elemének a helyét határozza meg ebben a vektor-
ban!
X X X ... X
O X X ... X
O O X ... X
.
.
0 0 0 ... X
4.102 *
Egy NxN-es tridiagonális mátrixot szeretnénk a memóriában úgy
tárolni, hogy először a főátló fölötti átlót, azután a főát-
lót, majd a főátló alatti átlót tároljuk. Készítsük el a tá-
rolásnak megfelelő címfüggvényt! (X-ek a nem nulla elemek he-
lyét jelölik.)
X X 0 0 .. 0 0 0
X X X 0 .. 0 0 0
0 X X X .. 0 0 0
.
.
.
0 0 0 0 .. X X 0
0 0 0 0 .. X X X
0 0 0 0 .. 0 X X
4.103
Helyezzünk el egy NxN-es tridiagonális, valós típusú mátrixot
a memóriában a 2000-es címtől kezdve úgy, hogy a nem nulla
elemek sorfolytonosan követik egymást! Adjuk meg azt a cím-
függvényt, mely megmondja az (I,J) mátrixelem memóriabeli
kezdőcímét!
4.104 *
Adjuk meg az alábbi négyzetes mátrix címfüggvényét, ha tud-
juk, hogy oszlopfolytonosan tároltuk az elemeket! (N párat-
lan. Az X-ek jelölik a tárolt nem nulla elemek helyét.)
0 0 ... 0 0 ... 0 X
.
.
0 0 ... 0 X ... X X
0 0 ... X X ... X X
0 0 ... 0 X ... X X
.
.
0 0 ... 0 0 ... 0 X
4.105 *
Adjuk meg az alábbi négyzetes mátrix címfüggvényét! (N párat-
lan. Az X-ek jelölik a tárolt nem 0 elemek elhelyezkedését.)
0 ... 0 0 0 ... 0
.
.
0 ... 0 0 0 ... 0
0 ... 0 X 0 ... 0
0 ... X X X ... 0
.
.
X ... X X X ... X
4.106
Milyen elemeket érdemes tárolni az ún. N*N-es Toeplitz mát-
rixból és milyen alakú lesz a címfüggvény, amely megadja az
(I,J) mátrixelem helyét a tömörített tárolásban? A Toeplitz
mátrix felépítése olyan, hogy a főátlóval párhuzamos átlókban
az elemek azonos értékűek.
a b c ........
d a b c .....
e d a b c ...
.
.
4.107
Adott egy N*N-es Hankel mátrix. Hogyan lehetne a lehető leg-
kevesebb elmet tárolni úgy, hogy egy címfüggvény segítségével
minden mátrixműveletet el lehessen végezni? Adjuk meg a cím-
függvényt is! A Hankel mátrix felépítése olyan, hogy a mel-
lékátlóval párhuzamos irányokban az értékek megegyeznek.
....... c b a
.... c b a d
a d e
.
.
a d .........
4.108 *
Olyan mátrix tárolásáról kell gondoskodnunk, amelyben az ele-
mek nagyrésze 0. Ilyenkor nem célszerű a nulla elemekkel is
foglalni a helyet. Tároljuk szekvenciálisan a nem zérus ele-
meket úgy, hogy az elemek mellé két mutatót illesztünk! Az
egyik az elem sorindexe, a másik az oszlopindexe legyen. A
három mező - az érték a harmadik - alkot egy adatrekordot és
ezek ismeretében a mátrixot fel tudjuk építeni. Írjunk prog-
ramot, amely egy hézagosan kitöltött mátrixból felépíti a tá-
rolandó rekordokat!
4.109
Az alább látható mátrix nem nulla elemeit kell tárolni úgy,
hogy az elem értéke mellett jegyezzük a mátrixbeli sor- és
oszlopszámát is.
------------------------------------------------
l sorindex l oszlopindex l érték l
------------------------------------------------
Hogyan néz ki az átalakítás után ez a mátrix, ha feltesszük,
hogy a legkisebb tömbindex 1?
7 0 0 2 0
3 0 0 0 4
0 1 0 5 1
0 0 5 0 0
4.110
Készítsük el azt a programot, amely az előző feladatban leír-
tak szerint elkészített szekvenciális adatállományból a kép-
ernyőre kiírja az eredeti mátrixot!
4.111 *
Adott két hézagosan kitöltött mátrix. Tárolásukat úgy oldot-
ták meg, hogy a nem nulla elemek mellé felvették plusz mező-
ként az elem sorának és oszlopának számát, majd az így kép-
zett rekordokat egymás után az M, illetve a K nevű N1x3-as,
illetve N2x3-as tömbökben helyezték el. (N1, N2 a nem nulla
elemek száma.) Olyan eljárást készítsünk, amely ezt a két
mátrixot összeadja és az eredményt hasonló módon tárolja!
4.112 *
Adott két hézagosan kitöltött mátrix. Helytakarékosság miatt
egy értékes elemet az alábbi négyessel adunk meg:
---------------------------------------
I sor I oszlop I érték I mutató az I
I index I index I I oszlop köv.I
I I I I elemére I
---------------------------------------
Szorozzuk össze őket úgy, hogy az eredmény is a fenti formá-
ban adódjon!
4.113
Szénhidrogének szerkezeti felépítését mátrix segítségével tá-
roljuk. Az I. sor J. oszlopában szereplő szám megmutatja,
hogy az I. molekula a J. molekulával hány vegyértékű kötésben
áll. Ezt a táblázatot úgy tároltuk, hogy csak a nem nulla
elemeket vettük fel egy Nx3-as tömbbe. (N a molekula atomjai-
nak száma. Tároljuk a tömbben az értéket és az elem sor-, il-
letve oszlopszámát.) Határozzuk meg, hogy jól töltötték-e ki
az eredeti mátrixot!
4.114 **
Generáljunk labirintust! Egy NxK-s mátrixot töltsünk fel
egyesekkel és nullákkal aszerint, hogy az aktuális pozíción
fal van-e, vagy nincs! Vigyázzunk, hogy ne legyen olyan fal-
rész, amit körbe lehet járni!
4.115 **
Készítsünk olyan labirintust, amelyben nem lehet falrészt
körbe járni és írjunk olyan algoritmust, amellyel a bejárat-
tól eljuthatunk a kijáratig!
4.116 *
Ha egy hézagosan kitöltött mátrix nem nulla elemeit úgy tá-
roljuk oszlopfolytonosan, hogy az elem mellé az oszlop- és
sorindexét is felvesszük, akkor a mátrixot ugyan helyre is
tudjuk állítani és a szükséges műveleteket is el tudjuk vé-
gezni, de mindez túl sok időbe kerül. Ez azért van, mert nem
tudjuk pontosan, hogy az éppen kellő elem hányadik adat a tö-
mörített sorban. A keresési időt le lehet rövidíteni, ha az
azonos sorban levő elemeket felfűzzük egy listára és megje-
gyezzük valamilyen változóban, hogy az egyes sorokhoz tartozó
listák hol kezdődnek a nem nulla elemek felsorolásában. A
listára fűzéshez természetesen szükség van egy mutatóra, amit
szintén tárolni kell minden egyes elemhez. Írjunk olyan algo-
ritmust, mely az M(N,K) hézagosan kitöltött mátrix nem nulla
elemeit helytakarékosan tárolja az azonos sorokban levő ele-
mek listába fűzésével!
4.117 *
Az előző feladat meggondolását folytatva eljuthatunk odáig,
hogy ha az oszlopok és a sorok szerint is felfűzzük a nem
nulla elemeket, akkor még gyorsabban el tudjuk végezni a
szükséges műveleteket.
4.118
Egy mértani sorozat első 100 elemét kiszámolásuk után növekvő
sorrendben az S() nevű tömbbe raktuk. Logaritmikus keresés
algoritmusával keressük meg azt az elemet, mely a legközelebb
van egy, az A változóban adott értékhez!
4.119
Egy iskola tanulóinak névsora és személyi száma, a NEVS() ne-
vű Nx2-es, szöveges tömbben található a személyi számok sze-
rint rendezve növekvő sorrendben. Adjuk meg az első leány ta-
nuló nevét és születési évét!
4.120 *
'Sok' adatot kell a memóriában tárolni, illetve ezekből visz-
szakeresni. ('Sok' jelentse azt, hogy már érdemes olyan adat-
szerkezeten gondolkodni, amelynél az elemek eléréséhez minél
kevesebb idő kell.) Annak érdekében, hogy minél gyorsabban
megtaláljuk őket, indextáblás módszerrel külön altáblákba
szedjük az adatokat a kezdőbetűjük szerint. Az altáblákon be-
lül az adatok legyenek érkezési sorrendben felsorolva. Ké-
szítsük el annak a programnak az algoritmusát, amely a beér-
kező elemeket a megfelelő altáblának a végére rakja!
4.121 *
Készítsünk programot, amely segítségével az ismerőseink tele-
fonszámait tartjuk nyilván! A nevük kezdőbetűi alapján cso-
portosítsuk őket, mindegyikhez adjuk meg, hogy hol található
az első olyan kezdőbetűs, majd egy kezdőbetűn belül fűzzük
őket listába! A program tudjon az így tárolt adatok között
keresni, új nevet felvenni, telefonszámot módosítani!
4.122 *
Nagy mennyiségű adat elhelyezéséről kell gondoskodnunk úgy,
hogy minél gyorsabban megtaláljuk bármelyiket. Alkalmazzuk az
indextáblás módszert, azaz az adathalmazt 26 kisebb altáb-
lára osztjuk a kezdőbetűknek megfelelően! Az egyes altáblába
tartozó, - azonos kezdőbetűjű - szavakat fűzzük növekvő sor-
rendben listába! Készítsük el azt az eljárást, amely a
'nyers' adathalmazból felépíti az altábla rendszert! Az al-
táblákon belül legyenek az elemek növekvő sorrendben listába
fűzve!
4.123
Sok adatunk van és szeretnénk úgy tárolni ezeket, hogy az
elemekhez minél gyorsabban, de lehetőség szerint körülbelül
azonos idő alatt férjünk hozzá. Válasszuk az altáblákra bon-
tás módszerét, amely az adathalmazt több, egymástól különálló
részhalmazra osztja valamilyen megfontolás alapján! Egyik le-
hetőség a kezdőbetűk szerinti osztályozás. Ez most azért nem
a legcélszerűbb, mert például q betűvel sokkal kevesebb ma-
gyar szó kezdődik, mint k-val, ez pedig azt jelenti, hogy az
egyik halmazban jóval több az elem mint a másikban. Ekkor
természetesen nem tudjuk biztosítani az azonos elérési időt.
Egy másik módszert kell tehát alkalmazni. Egy ún. leképezési
függvény segítségével 10 altáblára bontjuk az alaphalmazun-
kat. Készítsük el azt a programot, amely képes egy érkező
elemet a megfelelő altábla végére illeszteni és képes adott
értékről eldönteni, hogy az eddig felvett adatok között
van-e! Legyen a leképező függvény a következőképpen adva: Ad-
juk össze az adatunk jeleinek ASCII kódját, majd vegyük a 10-
zel vett osztás maradékát! Ha így osztjuk szét az elemeket,
akkor minden elemet egyértelműen tudunk osztályba sorolni és
a tapasztalat szerint az altáblákban körülbelül egyforma sok
elem lesz.
4.124 **
Válasszuk ki a megfelelő gráf tárolási módot, ha a feladatul
két gráf 'egyformaságának' vizsgálatát kapjuk! (Két gráfot
egyformának mondunk, ha egyenlő számú csúcsuk van és két-két
azonos számú csúcs között van mindkét gráfban él.)
4.125 *
Adott egy N csúcsú irányított körmentes gráf. Adjuk meg a
csúcsoknak egy olyan új sorszámozását, amelyben az I. csúcs-
ból nem vezet él J-be, ha I>J!
4.126 **
Adott egy N csúcsú összefüggő gráf. Döntsük el,hogy a csúcsok
két osztályba sorolhatók-e úgy, hogy él egy osztály két csú-
csa között ne legyen, csak különböző osztálybeli csúcsok kö-
zött! (A gráf un. páros gráf-e?)
4.127
Adott egy gráf és annak két részgráfja. Határozzuk meg a
részgráfok közös éleit!
4.128 **
Határozzuk meg egy gráf minimális feszítőfáját!
4.129 *
Keressük meg egy gráf két kitüntetett csúcsa között a legke-
vesebb élt tartalmazó utat!
4.130 *
Adott egy N csúcsú irányított körmentes gráf és abban egy ki-
tüntetett csúcs. Adjuk meg a csúcsból kiinduló összes utat,
amelyben minden csúcs csak egyszer szerepelhet!
4.131 *
Bontsunk összefüggő komponenseire egy gráfot!
4.132 *
Adott egy összefüggő irányítatlan gráf. Keressünk benne olyan
élt, amit ha elhagynánk, a gráf már nem lenne összefüggő!
4.133 *
Határozzuk meg, hogy egy gráf két csúcsa között hány különbö-
ző út van!
4.134 *
Adott egy gráf és abban három csúcs: A, B, X. Keressünk egy
olyan utat az A és B csúcsok között, ami áthalad az X csú-
cson!
4.135 *
Adott a síkon hat pont. Rajzoljuk meg azt a fát, amely össze-
köti a pontokat és az élei hosszának összege a lehető legki-
sebb!
4.136 *
Adott egy fagráf, amelynek minden éléhez és minden leveléhez
értékeket rendeltünk. A gráfnak van egy kitüntetett pontja: a
gyökérelem. Adjunk meg minden utat, ami a gyökérelemtől va-
lamelyik levélig vezet, s az utakhoz adjuk meg az éleken levő
értékek összegét is!
4.137 **
Adott egy fagráf és abban egy kitüntetett levél. Adjuk meg a
gráf összes olyan csúcsát, amelyből K hosszúságú út vezet a
kitüntetett levélig!
4.138 **
Adott egy irányított körmentes gráf és benne két kitüntetett
pont, egy kezdő- és egy végpont. Adjuk meg a kezdőpontból a
végpontba vezető utakat úgy, hogy azoknak ne legyen közös
pontja (csak a két szélső pont) és még egy a kezdőpontból a
végpontba vezető utat felvéve már mindenképpen megsértenénk
az előző feltételt!
4.139 *
Megadtuk egy gyűrűs szénhidrogén szerkezetét úgy, hogy minden
szénatomhoz meghatároztuk a kapcsolódó szénatomokat. Hagyjuk
el belőle az olyan szénatomokat, amelyek nem tartoznak
egyetlen gyűrűhöz sem, illetve nem kötnek össze gyűrűt!
4.140 *
Egy munkafolyamat több részből áll, amelyek mindegyike külön-
böző időt igényel. Ismerjük azt is, hogy melyik megkezdése
előtt melyiket kell elvégezni. Számítsuk ki, hogy mennyi idő
alatt lehet végezni az egész munkával!
4.141 **
Módosítsuk az előző feladatot! Minden munkafolyamatot 1 ember
végez, de van M tartalék munkás is, akiket bárhova be lehet
állítani. Adjuk meg, hogy hova állítsuk be őket, s így meny-
nyi lesz az elkészüléshez szükséges idő!
4.142 **
Adott a síkon N darab piros és ugyanannyi kék pont.
Párosítsuk össze a pontokat úgy, hogy egy párban egy piros és
egy kék pont legyen és a párokban levő pontok távolságainak
összege a lehető legkisebb legyen!
4.143 **
Egy az A(1),...,A(N) városokat összekötő úthálózatot kell
építenünk, aminek olyannak kell lennie, hogy az úton bármely
városból bármely város elérhető legyen. Ismerjük a K(I,J)
költségeket: az út megépítésének költségét az I és J városok
között. Adjuk meg azt, hogy melyik városok között kell megé-
píteni a közvetlen utakat, hogy az építés a legolcsóbb le-
gyen!
4.144 **
Ismerjük az Árpádházi királyok családfáját, amelyben csak a
fiúutódok szerepelnek, illetve az, hogy mettől meddig uralko-
dott, ha király volt. Adjuk meg, hogy
1. mettől meddig tartott a leghosszabb egyenesági öröklés
(amikor az apát a fia követte a trónon),
2. kik voltak testvérkirályok (amikor valakit a testvére
követett),
3. volt-e olyan, hogy valakit az unokája követett a tró-
non,
4. kik azok, akiknek ősei az előző 3 nemzedékben nem vol-
tak királyok!
4.145 **
Módosítsuk úgy az előbbi feladatot, hogy a lányutódok is sze-
repeljenek a családfában, s a házasságokat is jelöljük! Adjuk
meg, hogy volt-e házassággal trónt szerzett király!
4.146 **
Ismerjük Budapest autóbuszjáratait: tudjuk hol vannak megál-
lók, valamint, hogy melyik busz, mely megállókban áll meg.
Két adott megálló esetén állapítsuk meg, hogy:
1. el lehet-e jutni az egyikről a másikra átszállás nél-
kül,
2. el lehet-e jutni az egyikről a másikra átszállással,
3. adjuk meg a két megálló között a legrövidebb utat, ha
tudjuk, hogy mennyi időbe telik egy busszal eljutni a
következő megállóba, valamint azt, hogy mennyi idő egy
átszállás,
4. melyik a legkevesebb átszállást igénylő út!
4.147
Egy gráfot ábrázolhatunk csúcsmátrixszal, illetve élmátrix-
szal. Írjunk eljárásokat, amelyek az egyik fajta ábrázolású
gráfot átalakítják a másik fajtává!
4.148 *
Ismerjük Magyarország városokat összekötő úthálózatát (melyik
út milyen hosszú). Adjuk meg az összes várospárra, hány kilo-
méter autóútra vannak egymástól!
4.149 **
Határozzunk meg az előző feladatban adott úthálózathoz egy
olyan kört, amelyben Budapestről indulunk, minden városban
járunk, de mindegyikben csak egyszer! (Hamilton kör)
4.150 **
Módosítsuk az előző feladatot úgy, hogy ez a kör a lehető
legrövidebb legyen!
4.151
Győr úthálózatát egy irányított gráffal ábrázoljuk.Az egyirá-
nyú utcáknál ez két csomópont között egy élt jelent, kétirá-
nyúaknál pedig kettőt.
1. Döntsük el, hogy az A pontról el lehet-e jutni a B
pontra!
2. Adjunk meg egy utat, amellyel A-ról B-re eljuthatunk!
3. Adjunk meg egy zsákutcát!
4. Adjuk meg azokat az utcákat, amelyek lezárásával az út-
hálózat már nem lesz összefüggő!
4.152 *
Az A(N,N) mátrix N darab város közti telefonhálózat leírását
tartalmazza: A(I,J)=1, ha az I. és a J. város között közvet-
len telefonösszeköttetés van, különben A(I,J)=0. Állapítsuk
meg, hogy két kijelölt város között létesíthetó-e (akár köz-
vetett) kapcsolat!
4.153 *
Adott N személyről az A(N,N) mátrix. A(I,J)=1, ha I és J is-
merik egymást, A(I,J)=0 különben. Döntsük el, hogy összeál-
lítható-e a társaságban olyan négyfős csoport, amelyiknek
tagjai (páronként) nem ismerik egymást?
4.154 *
Egy programban bizonyos eljárások más eljárásokat hívnak. Ha
egy V eljárást hívja egy W eljárás, azt így írjuk: V