Kot Leopold este foarte foame. El vrea să prindă și să mănânce mouse-ul de la toate costurile, dar este de dorit să se rapid.
Mouse-ul ascuns în spatele peretelui, acesta este un sistem de cinci nurci dispuse unul lângă celălalt pe o linie dreaptă. Fiecare pereche de nurca adiacente (1 și 2, 2 si 3, 3 și 4, 4 și 5) leagăn interconectate. Evident, se mută sunt ascunse undeva în grosimea peretelui.
Kot Leopold nu știe exact unde mouse-ul este, din moment ce el nu a văzut. Dar el știe că înainte de fiecare încercare de ea ar fi undeva într-una din cele cinci vizuini. La fiecare din încercarea sa de pisica ar putea lipi laba într-unul din nurcă (dar numai în unul), și verificați gaura pentru prezența a mouse-ului. Dacă încercarea a fost de succes, mouse-ul este prins. Dacă încercarea nu a avut succes, iar mouse-ul in studiu nu a fost vizuini, mouse-ul înainte de următoarea pisica această încercare merge neapărat în gaura adiacentă (aceasta este starea problemei). De exemplu, nurcă № 3 în caz de eșec al mouse-ului pisica poate rula pe sau nurcă № 2 sau în nurcă № 4. Din nurcă № 1 - numai № 2; din № 5 - № 4 numai.
Numărul de încercări nu se limitează la Leopold, dar el vrea să prindă mouse-ul cât mai mult posibil pentru cea mai mică sumă de încercări.
Întrebare: poate, în astfel de circumstanțe Leopold prinde chiar un mouse și, dacă da, cât de multe încercări va avea nevoie și ce algoritmul va prinde mouse-ul?
Evident, trebuie mai întâi să decideți care gaura poate fi un mouse, și apoi verificați versiunea a secvenței. Având în vedere faptul că mouse-ul după fiecare pisica această încercare merge în gaura adiacentă, se intercalează secvențial găurile chiar și-impare. Să presupunem că este în gaura ciudat.
- Verificați gaura 3, în cazul în care nu este acolo, aceasta înseamnă 1 sau 5 și a alerga peste 2 sau 4.
- Urmatoarea gaura încercare 2, din nou goală, apoi, în 4 gaura, și apoi ascunse în 3 sau 5.
- Acum, pisica este necesară pentru a încerca 3 gaura, ceea ce ar exclude posibilitatea de mouse-ului pentru a trece la cealaltă parte a nurca, și mouse-ul de evacuare gaura 5.
- Următoarea mișcare - 4 găuri de control, în care mouse-ul trebuie să fie cel corect inițial ipoteza noastră. În caz contrar, mouse-ul s-au refugiat la începutul jocului chiar și într-o gaură, și este în prezent în ciudat.
- Re-verifica gaura 4, așa că ar trebui să fie deja într-una din chiar găuri.
- Dacă nu, atunci ea a fost într-o gaură cu numărul 2. Apoi, pisica încă lipi laba în 3 gaura și dacă încercarea eșuează, mouse-ul în conformitate cu normele vor trebui să se mute de la prima gaură la numărul gaura 2, în cazul în care acesta va suferi o soartă tristă.
