Feladatgyűjtemény a Mesterséges intelligencia 1 című tantárgyhoz Kósa Márk 2003. június 27.
1. fejezet
Egyszemélyes problémák 1. Lucky 7. Adott egy 3×3-as játéktábla, rajta hét darab számozott lapocska, két üres hely és két darab mezőelválasztó elem, fal. A két üres hely egyikén, a tábla középső elemén sohasem állhat számozott lapocska. Bármelyik számozott lapocska áttolható egy vele vízszintesen vagy függőlegesen szomszédos üres mezőre, ha a két mezőt nem választja el fal, illetve áttolható függőleges irányban a tábla középső mezeje fölött is egy üres mezőre.
2
3
1
1
7
4
7
2
6
6
5
3
(a) Kiinduló állapot.
4
5
(b) Célállapot.
1.1. ábra. Lucky 7. Írj olyan programot, amely a 1.1(a) ábrán látható kezdőállapotból kiindulva előállítja a 1.1(b) ábrán látható célállapotba vezető megoldást! Az eredeti feladat elérhető a http://www.mazeworks.com/sliders/index.htm honlapról. 2. Nyolcas tilitoli. Adott egy 18×18-as játéktábla, rajta különböző alakú számjegyek 1-től 8ig. A feladat megoldásának szempontjából nagyon fontos a számjegyek alakja, különösen az egyesé, a négyesé és a hetesé! A számjegyek kiinduló helyzete az 1.2(a) ábrán látható.
(a) A kiinduló állapot.
(b) A célállapot.
1.2. ábra. Nyolcas tilitoli. Írj olyan programot, amely a számjegyek tologatásával felcseréli a hetes és a nyolcas számjegyet, és előállítja az 1.2(b) ábrán látható célállapotba vezető megoldást! A tologatások során a számjegyek nem fedhetik át egymást!
1
1. Egyszemélyes problémák
2
A nyolcas tilitoli játék a http://www.johnrausch.com/SlidingBlockPuzzles/digits.htm honlapon is megtekinthető és kipróbálható. 3. Huszárcsere. Adott egy 3×3-as sakktábla, melynek alsó sarkaiban sötét huszárok, felső sarkaiban világos huszárok állnak úgy, ahogy az az 1.3-as ábrán látható.
1.3. ábra. A futók kiinduló helyzete. Írj olyan programot, amely szabályos sakklépésekkel felcseréli a világos huszárokat a sötétekkel! 4. Futócsere. Adott egy 5×4-es sakktábla, melynek alsó sorában sötét futók, felső sorában világos futók állnak úgy, ahogy az az 1.4-es ábrán látható.
1.4. ábra. A futók kiinduló helyzete. Írj olyan programot, amely szabályos sakklépésekkel felcseréli a világos futókat a sötétekkel úgy, hogy a lépések során egyetlen futó sem léphet ellentétes színű futó(k) által támadott mezőre! 5. Négy királynő, négy huszár. Adott egy 8×8-as üres sakktábla. Írj olyan programot, amely egyesével elhelyez ezen a sakktáblán négy királynőt és négy huszárt úgy, hogy a bábuk ne álljanak egymás ütésében!
1.5. ábra. A négy királynő és a négy huszár egy lehetséges elrendezése. 6. Tilitoli öt elemmel. Adott egy 4×6-os játéktábla, rajta öt különböző alakú síkidom. Az egyes síkidomokat vízszintes és függőleges irányban lehet tologatni a szomszédos szabad helyekre, elforgatni egyik síkidomot sem szabad. A síkidomok a tologatások során nem fedhetik át egymást. Írj olyan programot, amely a 1.6(a) ábrán látható kezdőállapotból kiindulva előállítja a 1.6(b) ábrán látható célállapotba vezető megoldást!
3
1. Egyszemélyes problémák 1
2
1
2
5
4
3
5
4
(a) A kiinduló állapot.
3 (b) A célállapot.
1.6. ábra. Tilitoli öt elemmel. 7. Tilitoli kilenc elemmel. Adott egy 4×6-os játéktábla, rajta kilenc síkidom. Az egyes síkidomokat vízszintes és függőleges irányban lehet tologatni a szomszédos szabad helyekre, elforgatni egyik síkidomot sem szabad. A síkidomok a tologatások során nem fedhetik át egymást. 1
2 6
1
7 5
9 4
2
(a) A kiinduló állapot.
7
9
8
5
8 3
6
4
3 (b) A célállapot.
1.7. ábra. Tilitoli kilenc elemmel. Írj olyan programot, amely a 1.7(a) ábrán látható kezdőállapotból kiindulva előállítja a 1.7(b) ábrán látható célállapotba vezető megoldást! 8. Helycsere korongokkal. Adott az 1.8 ábrán látható játéktábla, rajta nyolc világos színű és nyolc sötét színű koronggal.
1.8. ábra. A korongok kiinduló helyzete. A világos színű korongok lefelé vagy jobbra, a sötétek felfelé vagy balra mozgathatók. Egy koronggal vagy a szomszédos mezőre lehet lépni, ha az üres, vagy pedig át lehet ugrani egy másik korongot, ha az ugró korong ily módon üres mezőre kerül. Írj olyan programot, amely felcseréli a korongokat kiinduló helyzetükhöz képest! 9. Rajzoljuk egyetlen vonallal! Adott az 1.9 ábrán látható néhány gráf. Írj olyan programot, amely a gráfok egy tetszőleges csúcsából kiindulva megpróbálja az adott gráf éleit bejárni úgy, hogy (a) minden élen pontosan egyszer halad végig, (b) minden élen pontosan egyszer halad végig és a kiinduló csúcsba érkezik vissza, (c) minden élen pontosan egyszer halad végig és egyetlen már bejárt élt sem keresztez,
4
1. Egyszemélyes problémák
(d) minden élen pontosan egyszer halad végig, egyetlen már bejárt élt sem keresztez és a kiinduló csúcsba érkezik vissza!
(j)
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(k)
(l)
1.9. ábra. Hogyan lehet megrajzolni ezeket az ábrákat egyetlen vonallal, anélkül, hogy a ceruzánkat felemelnénk a papírlapról? A feladat eredeti szövege a hasonló típusú feladatokra vonatkozó megjegyzésekkel együtt a [4] honlapon olvasható. 10. Dupla golyógörgetés. Adott egy 5×5-ös labirintustábla, benne a bal felső sarokban két golyó. A tábla előre, hátra, jobbra és balra történő megdöntésével a golyók vízszintesen és függőlegesen gurulnak mindaddig, míg valamilyen akadályba nem ütköznek. Ez az akadály lehet a labirintus fala, vagy a másik golyó. Írj olyan programot, amely az 1.10(a)–1.10(l) ábrákon látható kiindulóhelyzetekből a labirintustáblák jobb alsó pozícióiba görgeti a golyókat! Ez a 12 feladat és további 34 hasonló elérhető a [1] honlapról. 11. Csőtologatás. Adott az 1.11 ábrán látható játéktábla. A tábla felső és alsó sorának két-két eleme rögzített, a felső két elemben egy másfél egység hosszú csődarab található. A csődarab ketté nem törhető, de vízszintesen áttolható az ábrán zöldeskék színnel jelölt csőszállító elemekbe. A csőszállító elemek kivételével más elemekkel a cső nem szállítható, és szállítás közben a csőszállító elemekből sem lóghat ki.
5
1. Egyszemélyes problémák
(a) 9 görgetés.
(b) 10 görgetés.
(c) 15 görgetés.
(d) 12 görgetés.
(e) 20 görgetés.
(f) 7 görgetés.
(g) 21 görgetés.
(h) 25 görgetés.
(i) 19 görgetés.
(j) 26 görgetés.
(k) 20 görgetés.
(l) 22 görgetés.
1.10. ábra. Dupla golyógörgetés. Írj olyan programot, amely a csőszállító elemek segítségével eljuttatja a csövet a felső két rögzített elemből az alsó két rögzített elembe! A probléma megtalálható a http://home.wanadoo.nl/mike.henkes/index.html honlapon is. 12. Bűvös csiga. Adott az 1.12 ábrán látható 6×6-os tábla, rajta egy csigavonal és benne néhány szám. Írj olyan programot, amely 1-től 3-ig számokat helyez el az ábrában úgy, hogy a feladat végeztével minden sorban és oszlopban mindhárom szám pontosan egyszer szerepeljen, továbbá a bal felső sarokból elindulva, a csigavonalon haladva a számok mindig 1 − 2 − 3 − 1 − 2 − 3 − . . . sorrendben kövessék egymást! A probléma a Füles rejtvényújság 2002/02-es számában jelent meg. 13. UFO. Az 1.13(a) és 1.13(b) ábrákon minden korong egy űrhajót jelöl, amelyek vízszintesen vagy függőlegesen tudnak mozogni, de csak egy másik űrhajó irányába. Ha egy űrhajó mozogni kezd, el is megy egészen a másik űrhajó előtti mezőig, máshol – így például a játéktábla szélén – megállni nem tud. Egy lépés a fent leírt mozgások sorozatából áll. Például az 1.13(a) ábrán (1) a D hajó függőlegesen mozog az A-ig, (2) az X függőlegesen mozog C-ig, majd vízszintesen mozog D-ig, illetve az 1.13(b) ábrán (1) az X hajó vízszintesen mozog az E-ig, (2) az E függőlegesen mozog A-ig, (3) a C vízszintesen mozog E-ig, majd függőlegesen mozog D-ig.
6
1. Egyszemélyes problémák
1.11. ábra. A csőtologató játék kiinduló helyzete.
2
3
1 2 1
3
1.12. ábra. A bűvös csigavonal. Írj olyan programot, amely legfeljebb hat (6) lépésben juttatja el az X jelű űrhajót a tábla közepére! 14. Szerelvények. Van egy nevezetes vasútállomás Veremvárosban. A táj arrafelé hihetelenül dimbes-dombos. Az állomás még a XIX. században épült. Sajnos az anyagi eszközök rendkívül korlátozottak voltak abban az időben. Csak egy felszíni pálya kiépítésére volt lehetőség. Ráadásul kiderült, hogy az állomásnak csak vakvágánya lehet (lásd az 1.14. ábrát) és a lehetséges hely hiányának köszönhetően abból is csak egyetlen egy. A helyi hagyomány az, hogy minden A irányból érkező vonat a B irányban folytatja az útját a vasúti kocsik valamilyen módon történő átrendezésével. Tegyük fel, hogy az A irányból érkező vonatnak N ≤ 1000 számozott kocsija van, 1-től N -ig növekvő sorrendben. A vonatrendező főnöknek tudnia kell, hogy vajon lehetséges-e átrendezni a vasúti kocsikat űgy, hogy útjukat a B irányban folytatva a sorrendjük a1 , a2 , . . . , aN legyen. Segíts neki és írj egy programot, amely eldönti, hogy elő lehet-e állítani a vasúti kocsik megadott sorrendjét. Feltételezheted, hogy az egyes kocsik lekapcsolhatók a vonatról, mielőtt beérkeznek az állomásra, és hogy egyedül is képesek mozogni, amíg a B irányba menő vágányra nem állnak. Feltételezheted továbbá azt is, hogy bármikor annyi vasúti kocsit lehet tárolni az állomáson, amennyit csak szükséges. Azonban ha egy vasúti kocsi begördült az állomásra, nem tud visszatérni az A irányból érkező vágányra, és hasonlóan, ha egyszer elhagyta az állomást a B irányban, akkor nem tud visszatérni az állomásra. 15. Bűvös huszonhat. Írj olyan programot, amely a 1.15. ábrán látható kereszt alakú táblának a mezőibe elhelyezi 1-től 12-ig az egész számokat – minden cellába pontosan egy számot – úgy, hogy a tábla • nyilakkal megjelölt soraiban és oszlopaiban, valamint • a három különböző színű mezőcsoporton, amelyeket a, b és c betűkkel is megjelöltünk, az ott található számok összege a bűvös 26-ot adja eredményül! 16. Számpótlás. Adottak a 1.16. ábrán látható táblák, bennük néhány matematikai műveleti jel és néhány szám. Írj olyan programot, amely az összes lehetséges módon kitölti a táblákat a 0-tól 9-ig terjedő számokkal úgy, hogy soronként és oszloponként a műveleteket sorrendben elvégezve, az egyenlőségjel után álló számokat kapjuk eredményül! Egy szám egy táblában többször is előfordulhat.
7
1. Egyszemélyes problémák
A
B
C
A
B C
D D E
X
E
(a) Megoldás 6 lépésben.
X
(b) Megoldás 6 lépésben.
1.13. ábra. Kiinduló UFO-állások.
3, 5, 4, 2, 1
1, 2, 3, 4, 5
B
A
´ Allom´ as 1.14. ábra. Veremváros vasútvonalai. A feladatok a Füles rejtvényújság 1992/29-es, 1992/34-es, 1992/39-es, 1992/42-es, 1992/48-as, 1993/5-ös, 1993/15-ös és 1993/22-es számaiban jelentek meg. 17. Tripla golyógörgetés. Adott egy 5×5-ös labirintustábla, benne a bal felső sarokban három golyó. A tábla előre, hátra, jobbra és balra történő megdöntésével a golyók vízszintesen és függőlegesen gurulnak mindaddig, míg valamilyen akadályba nem ütköznek. Ez az akadály lehet a labirintus fala, vagy egy másik golyó. Írj olyan programot, amely az 1.17(a)–1.17(j) ábrákon látható kiindulóhelyzetekből a labirintustáblák jobb alsó pozícióiba görgeti a golyókat! Ez a 10 feladat elérhető a http://www.bekkoame.ne.jp/˜ishmnn/java/ballmaze3/ballmaze3.html honlapról. 18. Sakklogika. A futó úgynevezett vonalbáb, amely pillanatok alatt eljuthat a tábla egyik végéből a másikba. A 1.18. ábrán látható állásokban is egy lépésben eljuthatna a1-ről a tábla túlsó sarkába, h8-ra – ha nem állnák útját saját gyalogjai. Ráadásul tételezzük fel, hogy ezek a gyalogok nem is léphetnek, kizárólag a futó mozoghat. Ilyen feltételek mellett írj olyan programot, amely meghatározza azt a minimális számú lépést, amellyel a futó az egyes ábrák a1-es pozíciójáról a h8-as pozícióba jut! A feladat a Füles rejtvényújság 1992/33-as számában jelent meg. 19. Torpedó. A tengeren állomásozó flotta egy csatahajóból (hosszúsága négy egység), két cirkálóból (három egység), három rombolóból (két egység) és négy tengeralattjáróból (egy egység) áll (1.19(a) ábra). A hajók elhelyezkedése lehet vízszintes vagy függőleges, egymással azonban sem oldalukkal, sem sarkosan nem érintkezhetnek. Az 1.19(b) és 1.19(c) ábra szélén látható számok azt jelzik, hogy az adott sorban vagy oszlopban mennyi négyzetet foglal el egy hajó vagy egy hajórész. A hullámos vonallal jelölt területen hajórész nem lehet. Írj olyan programot, amely megadja a hajók pontos helyét! A feladat a Füles rejtvényújság 2000/51-es számában jelent meg. 20. Lidércfiókák. Ebben a lidérces feladatban a lidércfalót szimbolizáló sötét színű (sajt alakú) alakzattal úgy kell áthaladni a 12 lidércfiókán – amelyeket természetesen a lidércfaló azonnal felfal –, hogy a fiókákat csak egy irányból, a foguk felől támadhatja meg. Hogy még lidércesebb
8
1. Egyszemélyes problémák
b
b
a
c
c
a
a
c
c
a
b
b
1.15. ábra. Bűvös huszonhat.
+
3
: =
9
2
:
× =
×
+ +
2
+
+
− −
=
:
+ :
0
=
− ×
+
1
− −
− +
=
−
: +
8
+
×
×
=
+
− −
5
+
−
=
=
=
=
=
=
=
=
=
4
2
4
2
2
2
8
1
5
(a)
× + +
=
× +
−
(b)
1
1
×
=
6
+
5
=
5
+ 4
:
×
6
+
6
−
: −
=
=
=
=
=
=
=
=
4
9
1
1
9
1
5
3
8
−
5
×
3
×
=
2
:
3
=
9
=
−
2
8
+ +
−
=
=
=
=
=
=
=
=
4
3
2
1
4
2
9
9
7
: ×
4
−
:
−
=
+
=
7
=
2
×
5
=
−
:
=
7
=
7
× +
×
: +
+
4
+
:
+
9
=
6
=
9
=
9
=
9
=
5
+ −
3
=
9
=
1
+ + :
− :
+
=
=
=
=
=
=
=
=
=
2
1
7
1
8
2
9
1
1
(j)
=
(i)
+
− −
− :
+
9
+
× ×
(h)
+
6
+
=
(g)
=
×
+
× =
:
+ +
7
×
+
× :
:
−
6
(f)
+ ×
:
− −
+
4 +
=
−
+
×
= +
× ×
(e)
+
×
=
−
=
(d)
6
+
×
× =
−
+
− −
=
:
−
=
(c)
− ×
:
− +
−
− =
:
×
+
4
×
4
+
− +
2
= ×
(k)
(l)
1.16. ábra. Mik a hiányzó számok? legyen a játék, a lidércfaló ugyanazon a ponton kétszer nem haladhat át! Írj olyan programot, amely megadja, hogy merre kell haladnia a lidércfalónak, hogy teljesítse küldetését, s felfalja az összes lidércfiókát!
9
1. Egyszemélyes problémák
(a) 16 görgetés.
(b) 13 görgetés.
(c) 8 görgetés.
(d) 24 görgetés.
(e) 22 görgetés.
(f) 29 görgetés.
(g) 16 görgetés.
(h) 14 görgetés.
(i) 19 görgetés.
(j) 23 görgetés.
1.17. ábra. Tripla golyógörgetés. A feladat a Füles rejtvényújság 1992/42-es számában jelent meg. 21. Legyen pontos! Adott az 1.21(a) ábrán látható kilenc féldominó. Írj olyan programot, amely elhelyezi ezeket a féldominókat az 1.21(b) ábrában úgy, hogy minden sorban, oszlopban, illetve a két átlóban annyi pont legyen, amennyi a sorok, oszlopok, illetve az átlók végén olvasható számok értéke! Az egyes elemeket elforgatni nem szabad. A probléma a Füles rejtvényújság 2002/02-es számában jelent meg. 22. Matematikai négyzet. Adott a 1.22. ábrán látható táblázat, benne néhány matematikai műveleti jel és néhány szám. Írj olyan programot, amely kitölti az ábrát az 1-től 9-ig terjedő számokkal úgy, hogy soronként és oszloponként a műveleteket sorrendben elvégezve, az egyenlőségjel után álló számokat kapjuk eredményül! Minden szám csak egyszer fordulhat elő. A feladat a Füles rejtvényújság 2002/1-es számában jelent meg. 23. Mágikus csillag. Adott a 1.23. ábrán látható két mágikus csillag, bennük néhány előre beírt szám. Írj olyan programot, amely elhelyezi a csillagok üres köreiben 1-től 12-ig, illetve 1-től 16-ig a még be nem írt számokat úgy, hogy az egyenes vonalak mentén elhelyezkedő számok összege 26, illetve 34 legyen!
10
1. Egyszemélyes problémák 8
8
8
7
7
7
6
6
6
5
5
5
4
4
4
3
3
3
2
2
2
1
1 a
b
c
d
e
f
g
h
1 a
b
c
(a)
d
e
f
g
h
a
b
(b)
c
d
e
f
g
h
(c)
1.18. ábra. Merre szalad a futó?
(a) A flotta hajói.
4 0 ≈ 4 1 ≈ ≈ 1 2 1 3 4 0 1 3 1 2 1 5 2 2 2 1 (b) Hol rejtőzhetnek a hajók?
≈
≈ 2 0 3 1 3 3 2 2 2 2
2 1 2 4 1 1 5 1 2 1
(c) Hol rejtőzhetnek a hajók?
1.19. ábra. Torpedó. A feladatok a Füles rejtvényújság 1992/47-es és 2001/49-es számaiban jelentek meg. 24. Éjféli körjárat. Éjjelente a hatalmas üzem minden épületét őrzik. Az éjjeliőr tíz perc alatt óránként végigjárja az útvonalát, mégpedig úgy, hogy az egyik – számmal jelölt – ponttól a következőig fél perc alatt teszi meg a távolságot. Feladata, hogy valamennyi számmal jelölt bejáratot ellenőrizze, de nem okvetlenül szükséges, hogy minden összekötő úton végigmenjen. Az őr szokása, hogy mindig az 1-es kapunál kezd. Írj olyan programot, amely segít megtervezni az őr útvonalát! A feladat a Füles rejtvényújság 1992/40-es számában jelent meg. 25. Csillagvarázs. A 1.25. ábrán látható rajzokon a karikákban lévő számok azt jelzik, hogy az adott csúcspontban hány sötét árnyalatú háromszög találkozik (lásd a példaként adott 1.25(a) rajzot). Írj olyan programot, amely megadja, hogy az egyes rajzokon melyek a sötét és melyek a világos árnyalatú háromszögek! A feladat a Füles rejtvényújság 1993/2-es számában jelent meg. 26. Számolás nevekkel. A Mária, Lenke és Ilona nevekben az ábécé 10 különböző betűje szerepel. Ezeket a betűket számokká alakítva számtani műveletek végezhetők. Írj olyan programot, amely 0-tól 9-ig a megfelelő számokkal helyettesíti a betűket úgy, hogy a 1.26. ábrán látható műveletek elvégzése után a megadott eredmények helyesek legyenek! Azonos betűk mindig azonos számokat szimbolizálnak. A feladat a Füles rejtvényújság 1993/6-os számában jelent meg. 27. Hatot hat csapásra. A világos vezér rendkívül mozgékony, vonalon és átlón egy pillanat alatt végigszáguldhatja az egész táblát. Tegyük fel, hogy a 1.27. ábra állásaiban hatszor egymás után
11
1. Egyszemélyes problémák
1.20. ábra. A labirintus a lidércfiókákkal. 6 9 4 9 5 2 5 4 3 4 5 (a) A dominókészlet.
4
5
7
4
7
5
4
4
6
(b) Az üres táblázat.
1.21. ábra. Legyen pontos! mi vagyunk lépésen. Írj olyan programot, amely megadja, hogy a sarokban álló világos vezérrel milyen útvonalon haladva üthetjük ki mind a hat ellenfelünket! A feladat a Füles rejtvényújság 1993/6-os számában jelent meg. 28. Értékes mezők. A 1.28. ábrát tíz különböző méretű mezőre osztottuk fel, és minden mezőbe rajzoltunk egy kört. Írj olyan programot, amely elhelyezi a körökbe az 1-től 10-ig terjedő számokat úgy, hogy a mezőkben előre megadott számok az adott területtel szomszédos mezők köreibe írt számok összegeivel legyenek egyenlők! A feladat a Füles rejtvényújság 2001/51–52-es számában jelent meg. 29. Számok a szomszédban. Írj olyan programot, amely elhelyezi az 1-től 12-ig terjedő számokat a 1.29. ábrában úgy, hogy a körökkel szomszédos mezőkbe kerülő számok összege megegyezzen a körben lévő számmal! Könnyítésül két számot előre beírtunk. A feladat a Füles rejtvényújság 2001/51–52-es számában jelent meg. 30. Tengeri kígyó. Az 1.30. ábrában egy 45 méter hosszú kígyó rejtőzködik. A kígyó vízszintesen és függőlegesen tekereg, de sehol sem érinti saját magát, még sarkosan sem. A sorok és oszlopok végén látható számok azt jelzik, hogy a kígyó hány egységnyi – nem feltétlenül összefüggő – része található az adott sorban vagy oszlopban. A fekete mezők sziklákat jelképeznek, ahol
12
1. Egyszemélyes problémák
−
× +
:
= 19
+
×
− = 40
× :
× = 10
+
− =
=
=
1
6
24
1.22. ábra. Matematikai négyzet. 1
1 2 9
12
4 7 13
(a) A vonalmenti összeg 26.
(b) A vonalmenti összeg 34.
1.23. ábra. Mágikus csillagok. nem lehet része a kígyónak. Írj olyan programot, amely megadja a kígyó pontos helyét az ábrában! A feladatok a Füles rejtvényújság 2001/49-es és 2002/6-os számaiban jelentek meg. 31. Egyenlő és egyenlőtlen. Írj olyan programot, amely kitölti az 1.31. ábra mezőit az 1-től 6-ig terjedő egész számokkal úgy, hogy a jelzett egyenlőségek és egyenlőtlenségek teljesüljenek! (Az a > b azt jelenti, hogy a nagyobb, mint b, például: 5 > 2 vagy 1 < 4.) A feladat a Füles rejtvényújság 2002/7-es számában jelent meg. 32. Aknakereső. Az 1.32. ábrán látható rajzokon a számok az őket tartalmazó mezők körül – közvetlenül alatta, felette, mellette és átlós irányban – található aknák darabszámát jelzik. Írj olyan programot, amely feltérképezi a rajzokon látható aknamezőket, és minden rajzon megtalálja a bennük elrejtett 10-10 darab aknát! A számokat tartalmazó mezőkben akna nem lehet. A feladat a Füles rejtvényújság 2002/8-as számában jelent meg. 33. Töréspontok. Írj olyan programot, amely az 1.33. ábrába olyan zárt hurkot rajzol, amelynek nincs eleje és vége, önmagát sehol nem keresztezi és érinti az ábra összes mezejét! A hurok minden második töréspontját (amelyek olyan pontok, ahol a hurok 90◦ -ban megtörik) színes mezők jelzik az ábrában. A feladat a Füles rejtvényújság 2002/8-as számában jelent meg. 34. Varázsnégyzet. Írj olyan programot, amely kitölti az 1.34. ábra üres mezőit az 1-től 6ig terjedő egész számokkal úgy, hogy minden sorban és oszlopban, valamint a színnel jelölt átlókban minden szám csak egyszer szerepeljen! A feladat a Füles rejtvényújság 2002/8-as számában jelent meg. 35. Súlyos feladat. Adott n darab súly, egyenként 1, 2, 3, . . . , n egység nehezek. Az 1.35. ábrán látható esetekben a vízszintes rudak azt jelzik, hogy a forgatónyomatékok a rudak mindkét oldalán egyenlőek. Minden súlynak a forgatónyomatéka a saját súlyának és a felfüggesztési ponttól való távolságának a szorzata. Feltehetjük, hogy a felfüggesztéseknek és a rudaknak a súlyai elhanyagolhatóak.
13
1. Egyszemélyes problémák 17
9
8
10
16
18 7
2
11
3
1
4
6
12 5
15
14
13
20
19
1.24. ábra. A hatalmas ötszögletű telephely. Írj programot, amely meghatározza a súlyok lehetséges elrendezéseit az egyes felüggesztésekben! A feladat eredeti szövege, a példák megoldásai további feladványokkal együtt megtalálhatók a http://www.stetson.edu/˜efriedma/weight/ honlapon. 36. Csatahajók. Adott öt darab, 1-től 5-ig számozott 3×1-es méretű torpedóromboló, amelyet elrejtettünk egy 5×5-ös négyzetrácson. A négyzetrács oldalain, a sorok és oszlopok mellett található számok jelzik az adott sorban vagy oszlopban lévő hajók sorszámainak összegét. Íme egy példa:
2
4 3
5
1 9
0
7
3
6
Írj programot, amely az 1.36. ábra négyzetrácsaiba elhelyezi a torpedórombolókat! A feladat eredeti szövege, a példák megoldásai további feladványokkal együtt megtalálhatók a http://www.stetson.edu/˜efriedma/battle/ honlapon. 37. Ütésszámlálás. Hat világos sakkfigurát (egy királyt, egy királynőt, egy bástyát, egy futót, egy huszárt és egy gyalogot) kell elhelyezni a sakktáblán úgy, hogy a sakktábla néhány előre megjelölt mezejét pontosan annyi bábu támadja, amekkora értékeket a megjelölt mezőbe beleírtunk. A sakkjáték eredeti szabályaival ellentétben egy gyalogot akár az első, akár az utolsó sorbais elhelyezhetünk. Nem állhat két figura azonos mezőn, és nem állhat figura a számokkal megjelölt mezőkön sem. Íme egy példa: 8
1
6
7 6
2
5 4
0
3 2 1 a
b
c
d
e
f
g
h
14
1. Egyszemélyes problémák
2
1
3
2
2
2
2
2
1
3
3
2
3
2
2
(g) Mi a középső szám?
3
2
3
3
2
2
(f) Mi a megoldás?
3
2
2
2
2
3
3
2
(c) Van megoldás?
3
2
3
3
(e) És itt?
1
2
2
1
2
1
3
2
3
2
(d) És itt van megoldás?
2
1
(b) Mi a megoldás?
3
2
2
3
(a) A példa.
2
1
3
1
2
2
(h) Mi a hiányzó szám?
0
1
0
0
0
(i) Hány megoldás van?
1.25. ábra. Csillagvarázs. Írj olyan programot, amely az 1.37. ábra sakktábláin elhelyezi a hat sakkfigurát a fenti szabályok figyelembe vételével! A feladat eredeti szövege, a példák megoldásai további feladványokkal együtt megtalálhatók a http://www.stetson.edu/˜efriedma/chessnum/ honlapon. 38. Húzd ki a gyufát! Adott 24 darab gyufa a 1.38. ábrán látható elrendezésben. Ezek a gyufák 9 kisméretű, 4 közepes méretű és 1 nagy méretű négyzetet határolnak. Írj programot, amely eltávolít a 24 gyufából (a) 9-et úgy, hogy 2 négyzet maradjon;
15
1. Egyszemélyes problémák
+ + 1
M L I 7
Á E L 2
R N O 5
I K N 9
A E A 4
+ − 1
M L I 0
Á E L 3
R N O 3
I K N 7
A E A 0
M L I 9
Á E L 2
R N O 2
I K N 9
A E A 4
− +
1.26. ábra. Számolás nevekkel. 8
8
7
7
6
6
5
5
4
4
3
3
2
2
1
1 a
b
c
d
e
f
g
h
(a)
a
b
c
d
e
f
g
h
(b)
1.27. ábra. Merre haladjon a királynő? (b) 9-et úgy, hogy 4 négyzet maradjon!
A megmaradt gyufák mindegyikének valamelyik négyzetet kell határolnia, azaz nem maradhat olyan gyufa, amelyik nem tartozik egyetlen négyzet oldalához sem! 39. Átkelés a folyón. (a) Csónakázás. Egy révésznek egy káposztát, egy kecskét és egy farkast kell átszállítani egy folyó egyik partjáról a másikra. A csónakjában egyszerre csak egy dolgot tud magával vinni a túlpartra. A fuvarozás közben vigyáznia kell rá, hogy ne maradjon egy parton se a kecske a káposztával, se pedig a farkas a kecskével. Írj programot, amely megoldja a révész problémáját! (b) Kannibálok és misszionáriusok. Három hittérítő és három kannibál egy folyónak egyazon partján tartózkodik. Ugyanezen parton ki van kötve egy csónak, amely egy vagy két embert tud szállítani. Írj egy olyan programot, amely megkeres egy olyan átkelési módot a folyón, amely során soha sehol nem lesznek a kannibálok túlsülyban a hittérítők felett! (A probléma megtalálható [5]-ben is.) (c) Házaspárok. Három házaspár egy gyalogtúra során egy széles folyóhoz érkezik, amelynek a partján találnak egy kétszemélyes csónakot. A folyón történő átkelés rendkívül bonyolult, mert a férjek nagyon féltékenyek, és nem hagyják, hogy feleségeik nélkülük
16
1. Egyszemélyes problémák
24
19
25
27 36 10 18
1.28. ábra. Milyen értékek kerülnek a körökbe?
23
37
30
27
40
24
1
5
1.29. ábra. Milyen számok lesznek a szomszédok? legyenek egy olyan társaságban, ahol más férfi(ak) is van(nak). Írj egy olyan programot, amely megadja a házaspárok folyón történő átkelésének egy lehetséges sorrendjét! (A probléma megtalálható [2]-ban is.) (d) Majmok és emberek. Három ember, egy nagy majom és két kis majom szeretne átkelni a folyón egy csónak segítségével. Hogyan csinálják, ha (1) evezni csak az emberek és a nagy majom tudnak, (2) egy helyen egy időben nem lehet több majom, mint ember, mert akkor a majmok megeszik az embereket, és (3) a csónakban kettőnél többen nem férnek el? (e) Hadsereg a folyóparton. A törökök Thrákiából történő kivonulása alatt egy kisebb csapat megakadt egy mély és széles folyónál. Szerencsére megláttak két csónakázó gyereket a közelben. A csónak azonban olyan kicsi volt, hogy egyszerre csak a két gyerek, vagy egy felnőtt ember fért el benne. Írj programot, amely megadja, hogy hogyan tudott mégis a csapat kapitánya 357 katonájával együtt átjutni a folyón úgy, hogy végül a gyerekek is a találkozási pontnál maradhattak a csónakjukkal együtt! Hányszor kellett eközben a csónaknak átkelnie a folyón? 40. Tények és állványok. Az alábbi idézet [6]-ból származik. Csöngettek. A belépő asszony egy olyan ember magabiztosságával járt, mint aki tökéletesen ellenőrzése alatt tudja környezetét. Ha zavarta is a hőség, semmi jelét nem adta. – Melyikük dr. Ecco? – kérdezte. – Állok rendelkezésére, asszonyom – egyenesedett fel Ecco. – A nevem Decker – mondta az asszony tétovázás nélkül. – Ügyvéd vagyok, és egy rendkívül fontos ügyet kell röviden ismertetnem. Az eset tényanyaga meglehetősen bonyolult, így a bíró megengedte, hogy öt papírtartó állvány segítségével mutassam be azokat. Úgy szeretném előadni a beszédemet, hogy amikor egy új papírt mutatok be, azzal egyidőben másik állványon vagy állványokon láthatóak legyenek az azt alátámasztó kijelentések, bizonyítékok. Egy papír sem mutatható be kétszer. Továbbá minden tény vagy kijelentés bemutatásához egy papír szükségeltetik. Hadd mondjak egy egyszerű példát. Tételezzük fel, hogy az A és a B tények támasztják alá C-t, C állítás és D tény támasztják alá az E végkövetkeztetést. Ha ezeket a D, A, B, C, E sorrendben mutatom be, négy állványra lesz szükségem: amikor bemutatom C-t, akkor A-nak, B-nek és D-nek is láthatónak kell lennie. Ugyanakkor, ha A, B, C, D, E a sorrend, akkor csak három állványra van szüksé-
17
1. Egyszemélyes problémák 3
1
5
1
3
3
5
4
7
7
5
1
4
5 23
7
8
2
1
4
3
6
5
6
5
5
5
5 45
5
45 3
3
4
5
3
5
6 6
(a)
4
5
6
5
2
4
(b)
1.30. ábra. Merre kanyarog a kígyó?
< >
>
>
> >
<
> >
=
<
< =
=
> <
< <
> <
> <
=
<
>
= <
< <
<
<
< 6 >
>
<
<
> >
>
<
=
<
>
<
< >
> >
> > <
= >
>
=
> <
<
<
=
1.31. ábra. Egyenlő és egyenlőtlen. gem: miután C-t bemutattam, az állványokat, amelyeken az A és a B állításokat tartalmazó papír van, már használhatom másra. – Úgy hangzik, mint amikor az egyetemi előadónak azt kell megoldania, hogyan használja a táblát – nézett rám Ecco. – Pontosan – mondta az ügyvédnő. – Próbáltam már egy előadótermi tábla segítségével is, de ez a probléma túl összetett. Ezután megadta a tények és állítások közötti kapcsolatokat: A, B és C támasztják alá M -et, D és E támasztják alá N -et, G és H támasztják alá O-t, I és J támasztják alá P -t, K és L támasztják alá Q-t, M és N támasztják alá R-et, O, P és Q támasztják alá S-et, F és S támasztják alá T -t, R és T támasztják alá U -t. – Szeretném tudni, hogy végig lehet-e vezetni az esetet U -ig mindössze öt állvány segítségével, és ha igen, melyik papírnak melyik állványon kell lennie, és milyen sorrendben kell bemutatnom ezeket? Ne feledje, hogy valahányszor bemutatok egy állítást, az azt alátámasztó tényeknek és állításoknak is láthatónak kell lenniük. Azt se feledje, hogy minden tény vagy állítás egy papírt igényel. Írj olyan programot, amely megoldja az ügyvédnő problémáját, azaz megadja, hogy az egyes tényeket és állításokat milyen sorrendben kell az állványokra helyeznie, majd onnan eltávolítania!
18
1. Egyszemélyes problémák
3
0 2 2 2
3
2 4
3
0
3 2
1 3
0
2
3
1
0
0
4
4
3 2
0
3
4
0 2
1
3
0
(a)
(c)
(b)
1.32. ábra. Hol rejtőznek az aknák?
1.33. ábra. Vajon merre kanyarog a zárt hurok?
6 2
4 6
4
5
2
6 4
5
5 3
1.34. ábra. Varázsnégyzet.
0
19
1. Egyszemélyes problémák
3
5 1
2
4
(a) A példa mérleg.
(b) Mérleg öt súllyal.
(c) Mérleg hat súllyal.
(d) Mérleg hét súllyal.
(e) Mérleg nyolc súllyal.
1.35. ábra. Merre billen a mérleg nyelve?
1
3
5 7 6
3
7
6 2
3
4
2
5
6
9
7
(b)
(a)
2
7
(c) 8
5 7
9 4 3 7 10
11
(d)
5
3
4
5
6
(e)
1.36. ábra. Hol lehet a flotta?
4
4
(f)
5
5
20
1. Egyszemélyes problémák
8
8 7
6
6 5
0
0
1
4 b
c
d
(a)
e
f
g
h
3
0
6 0
0 0
0
5
0
4
3
2
8 7
4 0
a
1
0
5
4
4 3
1
7
4
5
3
2
0
1
0 a
b
c
d
e
f
2 1 g
h
(b)
1.37. ábra. Hol vannak a sakkfigurák?
1.38. ábra. A gyufák alaphelyzetben.
3
0
1 a
b
c
d
(c)
e
f
g
h
Irodalomjegyzék [1] Stones’s Home Page, 2BallMaze, http://www.bekkoame.ne.jp/˜ishmnn/java/ballmaze/ballmaze.html. [2] C. L. Liu, Elements of discrete mathematics, 2nd edition, McGraw-Hill Book Company, 1986. [3] Jurg Nievergelt, J. Craig Farrar, Edward M. Reingold, Matematikai problémák megoldásainak számítógépes módszerei, Műszaki Könyvkiadó, Budapest, 1977. [4] Puzzle Playground – Treasury of Classic and Modern Puzzles, The Unicursal Marathon, http://www.puzzles.com/PuzzlePlayground/UnicursalMarathon/UnicursalMarathon.html. [5] Stuart J. Russell, Peter Norvig, Mesterséges intelligencia modern megközelítésben, Panem Könyvkiadó – Prentice Hall, Budapest, 2000. [6] Dennis Shasha, Dr. Ecco talányos kalandjai, Typotex Kiadó – SHL Hungary Kft., Budapest, 2000.
21
