„Hario Poterio ir filosofinio akmens“ pabaigoje yra įdomi mįslė. Haris ir Hermiona įeina į kambarį, po kurio įėjimus į jį užstoja stebuklinga ugnis, o išeiti iš jo gali tik įmindami šią mįslę:
Prieš tave yra pavojus, o už tavęs – išgelbėjimas,
Du žmonės, kuriuos rasite tarp mūsų, jums padės;
Su vienu iš septynių jūs ir toliau eisite į priekį
Kitas jus tuoj pat parveš atgal.
Dviese rasite tik dilgėlių vyną,
Ir trys atneša sunaikinimą, stovėdami iš eilės slapta.
Taigi pasirinkite, iš kurio jums lemta paragauti,
Norėdami tai padaryti, pateikiame keturis patarimus.
Veltui nuodai bandė paslėpti savo mirtiną karštį,
Visada rasite jį vyno kairėje,
Ir žinokite, kad tie, kurie yra pakraščiuose, turi kitokią dovaną,
Bet jei nori tęsti, niekas nepadės.
Mes visi skirtingo dydžio, nuo krašto iki krašto,
Tavo mirtis slypi ne mažesniame, bet ir ne didesniame;
Antrasis iš dešiniojo galo ir antrasis iš kairės
Jų skonis panašus į dvynius, nors ir nepanašūs.
[iš knygos „Haris Poteris ir filosofo akmuo“ „liaudiško vertimo“]
Paprasčiau tariant, jie turi suprasti, kuriuose buteliuose yra kokie gėrimai.
Šiame straipsnyje programuodami išspręsime visus 42 galimus šio galvosūkio variantus ir nubraižysime rezultatų diagramą (kaip paveikslėlyje aukščiau, tik daug didesnę).
Palaukite, iš kur atsirado 42 variantai?
Taip yra todėl, kad „mažesnių“ ir „didesnių“ gėrimų vietos nenurodytos. Didesnė gali būti vienoje iš septynių vietų, o tai suteikia 6 likusias parinktis mažesnei, iš viso 7 * 6 = 42. Nebus galima tiksliai sužinoti, kokį išdėstymą JK Rowling turėjo omenyje, kai sugalvojo su šia mįsle, nebent ji apie tai kalba jūsų „Twitter“. Na, o kol ateis ta neišvengiama diena, galime pasirinkti atsitiktinį variantą ir su juo dirbti. Tačiau garantijos dėl jos įsprendžiamumo nebus, todėl dirbame bendram gėriui, įmindami visus 42 mįslės variantus (arba įrodydami jų neįveikiamumą).
JAU SPRENDIM
Pirma, čia pateikiami visi galvosūkio apribojimai, suformuluoti paprastai:
- Yra du nekenksmingi gėrimai, 3 nuodingi, vienas leidžiantis eiti į priekį ir kitas, leidžiantis grįžti atgal.
- Kiekvieno iš dviejų nekenksmingų mikstūrų kairėje pusėje yra nuodingas gėrimas.
- Abiejų pusių gėrimai yra skirtingi, ir nė vienas iš jų neleidžia judėti į priekį.
- Didžiausiuose ir mažiausiuose buteliuose nuodų nėra.
- Antrame butelyje kairėje ir antrame buteliuke dešinėje yra tas pats gėrimas.
Kaip su tuo susitvarkyti? Panagrinėkime toliau pateiktą variantą. Atkreipkite dėmesį, kad, kaip sako mįslė, eilėje yra 1 butelis mažesnis už visus kitus ir 1 butelis didesnis už visus kitus.
Pabandykime kvailai pereiti visus variantus – imkite po vieną buteliuką ir atrinkite visus įmanomus turinio variantus.
Pavyzdžiui, pirmame buteliuke negali būti gėrimo, kuris mus judina į priekį dėl apribojimo Nr. 3. Jame taip pat nėra saugaus gėrimo dėl apribojimo Nr. 2 – jo kairėje negali būti nuodų. Tai palieka mums nuodų gėrimo ir atmetimo gėrimo pasirinkimą. Išbandykime abu variantus.
Tolesniuose paveikslėliuose žalios spalvos gėrimai reiškia nuodus, oranžiniai – saugūs gėrimai, mėlyni – gėrimai, kurie juda atgal, o violetiniai – gėrimai, kurie juda į priekį.
Pakartokime šį procesą abiem darbo parinktims – paimkite antrą butelį ir pakaitomis išbandykite visas priimtinas turinio parinktis. Tai suteiks mums:
Toliau elgdamiesi taip ir atmesdami visas darbo galimybes, kai į kokį nors butelį negalima pripildyti gėrimo nepažeidžiant išvardytų apribojimų, pasieksime vienintelį priimtiną variantą:
Natūralu, kad neturėjome garantijų rasti sprendimą. Sprendimo gali nebūti arba gali būti keli (o jei turite kelis sprendimus, tai tas pats, kaip mįslės neįmanoma įminti, nes nežinote, kuris gėrimas yra teisingas).
Pritaikius algoritmą visoms parinktims, gauname šiuos sprendimus. 8 mįslės versijos yra įmanomos, 8 neturi sprendimų, o 26 - keli sprendimai.
Daugiau apie sprendimus
Ar visos išspręstos mįslės versijos turi ką nors bendro? Taip! Atkreipkite dėmesį, kad juose mažiausi arba didžiausi buteliai yra 2 arba 6 vietose. Tai leidžia daryti išvadą, kad 2 ir 6 buteliuose yra saugių gėrimų dėl #4 ir #5 apribojimų. Be šio žingsnio negalime pašalinti galimybės, kad šiuose buteliuose yra nuodų, ir mes galime rasti keletą galimų sprendimų. Taip pat išspręstos galimybės reikalauja, kad antrasis „specialus“ butelis (mažiausias arba didžiausias) būtų dedamas į 3 ar 4 vietą. Priešingu atveju nepavyks rasti tikslios gėrimo vietos, kuri mus stumia į priekį.
rezultatai
Baigsiu citata iš knygos.
Hermiona garsiai iškvėpė, o Haris apstulbęs pastebėjo, kad ji šypsosi – tai buvo paskutinis dalykas, kuris jam galėjo atsitikti. - Nuostabu, - pasakė Hermiona. – Tai ne magija – tai logika, mįslė. Daugelis didžiausių magų neturi nė trupučio logikos ir būtų čia įstrigę amžiams.
Bet palaukite – galbūt mes galime išsiaiškinti kanoninę mįslės versiją pagal dialogą iš knygos:
„Supratau“, – pasakė ji. „Mažiausias butelis nuves mus per juodą ugnį ir nuves iki akmens“.
...
"O kuris iš jų leis jums grįžti per purpurinę ugnį?"
Hermiona parodė į apvalų butelį dešinėje eilės pusėje.
Velnias. Ši parinktis vis tiek suteikia mums keletą sprendimų. Tviteryje, DR.
Kodas
Jei jus domina kodas, skirtas išspręsti šią galvosūkį ir nupiešti diagramas, galite tai padaryti .
Šaltinis: www.habr.com