fejléc
Gyakori kérdések Belépés Új kérdés Véletlen kérdés
Keresés
Kezdőoldal » Számítástechnika » Programozás » Hogy érdemes megoldani ezt a...

Hogy érdemes megoldani ezt a feladatot?

Figyelt kérdés

Van egy játékunk, amiben 5 betűs szavakat lehet kirakni az angol ABC nagybetűiből. Megkapjuk a kiinduló szót, a nyerő szót és a tiltott szavak tömbjét. Egy lépésben megváltoztathatunk a kiinduló szóban egy betűt az ABC-ben azt megelőző vagy azt követő betűre (pl. A-ból lehet Z vagy B, B-ből lehet A vagy C stb.). Ha valamelyik lépésben olyan szót kapunk, ami szerepel a tiltott szavak listáján, akkor vesztettünk.


Az a kérdés, hogy mennyi a legkevesebb lépés, amivel nyerhetünk.


Pl:

"AAAAA" - kiinduló szó

"AACAA" - nyerő szó

["AABAA"] - tiltott szavak listája


A kézenfekvő megoldás ez lenne:

1. "AAAAA" -> "AABAA"

2. "AABAA" -> "AACAA"

2 lépés, de az "AABAA" tiltott szó miatt ez nem lehetséges.


A jó megoldás legkevesebb 4 lépés (több lehetséges megoldás is van):

1. "AAAAA" -> "ABAAA"

2. "ABAAA" -> "ABBAA"

3. "ABBAA" -> "ABCAA"

4. "ABCAA" -> "AACAA"



#programozás #feladat #C++ #Java #Python #C#
2021. szept. 28. 13:50
 1/8 anonim ***** válasza:
Az feltetelezhető, hogy a szavak hossza ugyanakkora?
2021. szept. 28. 14:02
Hasznos számodra ez a válasz?
 2/8 A kérdező kommentje:
Minden szó 5 betűs.
2021. szept. 28. 14:05
 3/8 anonim ***** válasza:
0%
Még mindig nem értem. Program tudja mi a tiltott szó? Ha nem akkor minden AAAAA inputra BAAAA-t is visszaadhatok.
2021. szept. 28. 14:28
Hasznos számodra ez a válasz?
 4/8 anonim ***** válasza:
0%
Mit jelent a "nyerő szó", hogy nyer, ha ezt adja ki?
2021. szept. 28. 14:28
Hasznos számodra ez a válasz?
 5/8 anonim ***** válasza:
40%
Pontosan erre való az állapotgép. Egész pontosan determinisztikus állapotgéppel megoldható a feladat.
2021. szept. 28. 14:37
Hasznos számodra ez a válasz?
 6/8 anonim ***** válasza:
83%
Sima BFS, de ez 26^5 lehetséges érték, a string másolgatásokkal együtt még 4 karakter esetén is viszonylag lassú lenne (bizonyos esetekben) és nincs jobb megoldás.
2021. szept. 28. 17:53
Hasznos számodra ez a válasz?
 7/8 anonim ***** válasza:

> Hogy érdemes megoldani ezt a feladatot?


Én így közelíteném meg:

Ha bele gondoltsz, ez egy sima gráfkeresés:

Az egyes szavak a gráf csúcsai.

Él akkor van a két csúcs közt, ha a szavak átalakíthatók egy lépésben egymásba, pl: AAAAA és AAAAB közt van él, viszont AAAAA és AAAAC közt nincs.

A tiltott szavak egyszerüen nem részei a gráfnak.


Meg kell találni a legrövidebb utat ebben a gráfban a kiinduló szó és a nyerö szó csúcsok közt.


Ez innen egy jól ismert probléma: [link]


Van még egy csavar a dologban: Ha nincsenek 'tiltott' szavak, akkor akkor két szó távolságát nagyon könnyen ki lehet számítani, csak összeadod a párban álló betük 'távolságát': AAA - BCD = |1-2| + |1-3| + |1-4| = 6


Ezt akár heurisztikának is használhatod a te problémádban: Sima gráfkeresö algoritmusok helyett használhatsz heurisztikus keresö algoritmusokat is.

Én a best-first search, vagy az A* algoritmusokat nézném meg a helyedben.

[link]

[link]

2021. szept. 28. 19:14
Hasznos számodra ez a válasz?
 8/8 A kérdező kommentje:
Már kaptam megoldást, köszönöm a válaszokat.
2021. szept. 28. 19:33

További kérdések:

Számítástechnika főkategória kérdései »
Számítástechnika - Programozás kategória kérdései »



Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!