Hogyan lehet megoldani a problémát a Kote Leopolde, az egér és az öt lyukakban
Kot Leopold nagyon éhes. Azt akarja fogni és enni az egér minden áron, de kívánatos, hogy gyorsan.
Egér mögött a fal, ez a rendszer öt nyérc elrendezve egymás mellett egy egyenes vonal. Mindegyik pár szomszédos nyérc (1. és 2., 2. és 3., 3. és 4., 4. és 5.) összekapcsolt hinta. Nyilvánvaló, hogy a lépések vannak elrejtve valahol a fal vastagsága.
Kot Leopold nem tudja pontosan, hol az egér, mivel nem látta. De tudja, hogy minden kísérlete előtt ő lenne valahol az öt lyukakban. Annak minden kísérlet, hogy a macska is kibír a mancsát az egyik nyérc (de csak valaki), és ellenőrizze a lyuk jelenlétét az egér. Ha a kísérlet sikeres volt, az egér fogott. Ha a kísérlet sikertelen volt, és az egeret a vizsgálatot nem ás, az egér, mielőtt a következő kísérletet macska feltétlenül megy át a szomszédos lyuk (ez a feltétele a probléma). Például mink № 3 meghibásodás esetén macska egér Lehet halad át, vagy mink № 2 vagy mink № 4. mink № 1 - csak № 2; re № 5 - № 4 jellegűek.
A kísérletek száma nem korlátozódik Leopold, de azt akarja elkapni az egeret, amennyire csak lehetséges, hogy a legkevesebb kísérlet.
Kérdés: lehet ilyen körülmények között Leopold még egy egeret elkapni, és ha igen, hány próbálkozás lesz szükség és milyen az algoritmus elkapni az egeret?
Nyilvánvaló, hogy először meg kell döntenie, hogy melyik lyuk lehet egér, majd ellenőrizze a változat a sorozatot. Tekintettel arra a tényre, hogy az egér után minden kísérlet macska megy át a szomszédos lyukba, egymás összefűzi az páros-páratlan lyukak. Tegyük fel, hogy ez a furcsa lyuk.
- Ellenőrizze 3 lyukat, ha nincs ott, az azt jelenti, 1 vagy 5 és halad át a 2-es vagy 4.
- Következő try furat 2, ismét üres, akkor a 4 lyuk, majd elrejtve a 3 vagy 5.
- Most a macska van szükség, hogy próbálja ki a 3 lyuk, amely kizárná a lehetőségét az egeret mozgatni a másik oldalon a nyérc, és az egér escape 5 lyuk.
- A következő lépés - 4 ellenőrző nyílások, amelyben az egér kell lennie a megfelelő kezdeti feltételezésünk. Ellenkező esetben, az egér menekült elején a játék még egy lyukat, és jelenleg a furcsa.
- Ellenőrizze ismét a 4 furat, így azt már az egyik még lyukak.
- Ha nem, akkor ő volt a lyuk szám alatt 2. Majd a macska még mindig ragaszkodik a mancsát a 3 lyuk, és ha a kísérlet nem sikerül, az egér a szabályok szerint meg kell mozgatni az első lyuk lyuk a 2. számú, hol fog szenvedni egy szomorú sorsát.
