«Гарри Поттер және философия тасы» фильмінің соңында қызықты жұмбақ бар. Гарри мен Гермиона бөлмеге кіреді, содан кейін оның кіреберістері сиқырлы отпен жабылады және олар келесі жұмбақты шешу арқылы одан шыға алады:
Алдыңда қауіп, ал артыңда құтқару,
Арамыздан тапқан екі адам сізге көмектеседі;
Жетінің біреуімен сіз алға қарай жүресіз
Екіншісі сізді бірден қайтарады.
Екеумізден тек қалақай шарабы табасың,
Ал үшеуі бір қатарда жасырын тұрып, жойылады.
Ендеше, қайсысының дәмін татуға болатынын таңдаңыз,
Ол үшін біз төрт кеңес береміз.
Босқа уланды өзінің өлімші қызуын жасыруға тырысты,
Сіз оны әрқашан шараптың сол жағында табасыз,
Шеттегілер басқа сыйлық ұстайтынын біліңіз,
Бірақ жалғастырғың келсе, ешкім көмектеспейді.
Біз бәріміздің өлшеміміз әртүрлі, шетінен шетіне дейін,
Сіздің өліміңіз кішіде емес, үлкенде де емес;
Екіншісі оң жақтан, екіншісі сол жақтан
Бір-біріне ұқсамаса да, дәмі егіз сияқты.
[«Гарри Поттер және философия тасы» кітабының «халық аудармасынан»]
Қарапайым сөзбен айтқанда, олар қай бөтелкеде қандай еріткіш бар екенін түсінуі керек.
Бұл мақалада біз бағдарламалау арқылы осы басқатырғыштың барлық 42 мүмкін нұсқаларын шешеміз және нәтижелердің диаграммасын саламыз (жоғарыдағы суреттегідей, тек әлдеқайда үлкенірек).
Күте тұрыңыз, 42 нұсқа қайдан келді?
Себебі, «кіші» және «үлкен» сусындардың орындары көрсетілмеген. Үлкені жеті орынның бірінде болуы мүмкін, ол кішігірім үшін қалған 6 нұсқаны береді, барлығы 7 * 6 = 42. Дж.К.Роулинг келген кезде қандай аранжировканы ойлағанын дәл анықтау мүмкін емес. Бұл жұмбақпен, егер ол бұл туралы сіздің Twitter-де айтпаса. Сол еріксіз күн келгенше біз кездейсоқ нұсқаны таңдап, онымен жұмыс істей аламыз. Дегенмен, оның шешілу мүмкіндігіне кепілдік болмайды, сондықтан біз жұмбақтардың 42 нұсқасын түгел шешіп (немесе олардың шешілмейтіндігін дәлелдей отырып) ортақ игілікке жұмыс істейміз.
ШЕШІМ ҚАБЫЛДАУ
Біріншіден, қарапайым сөзбен қайталанған басқатырғыштың барлық шектеулері:
- Екі зиянсыз сусын бар, 3 улы, біреуі алға жүруге мүмкіндік береді, екіншісі кері кетуге мүмкіндік береді.
- Екі зиянсыз сусынның әрқайсысының сол жағында улы бар.
- Екі жақтың сусындары әртүрлі және олардың ешқайсысы алға жылжуға мүмкіндік бермейді.
- Ең үлкен және ең кішкентай бөтелкелерде улы заттар жоқ.
- Сол жақтағы екінші бөтелкеде және оң жақтағы екінші бөтелкеде бірдей сусын бар.
Мұнымен қалай күресуге болады? Келесі нұсқаны қарастырайық. Жұмбақта айтылғандай, қатарда өлшемі бойынша 1 бөтелке барлық басқалардан кішірек, ал қалғандарынан 1 бөтелке үлкенірек екенін ескеріңіз.
Келіңіздер, барлық опцияларды ақымақтықпен қарап шығуға тырысайық - бір уақытта бір бөтелке алып, мазмұнның барлық мүмкін нұсқаларын таңдаңыз.
Мысалы, бірінші бөтелкеде №3 шектеуге байланысты бізді алға жылжытатын сусын болуы мүмкін емес. Сондай-ақ оның құрамында №2 шектеуге байланысты қауіпсіз сусын жоқ - оның сол жағында у болуы мүмкін емес. Бұл бізге уландырғыш сусын мен кері қайтару сілтісінің нұсқаларын қалдырады. Екі нұсқаны да қолданып көрейік.
Келесі суреттерде жасыл сусындар уды, апельсин қауіпсіз сусындар, көк артқа жылжитын сусын, ал күлгін - алға жылжитын сусындар.
Бұл процесті екі жұмыс опциясы үшін де қайталайық - екінші бөтелкені алып, барлық қолайлы мазмұн опцияларын кезекпен қолданып көріңіз. Бұл бізге келесіні береді:
Осы бағытта әрекет етуді жалғастыра отырып және кейбір бөтелкелерді аталған шектеулерді бұзбай сусынмен толтыруға болмайтын барлық жұмыс нұсқаларынан бас тарта отырып, біз жалғыз қолайлы нұсқаға келеміз:
Әрине, бізде шешім табуға кепілдік болған жоқ. Шешім болмауы мүмкін немесе бірнеше болуы мүмкін (және сізде бірнеше шешім болса, бұл жұмбақ шешу мүмкін емес, өйткені сіз қай сусынның дұрыс екенін білмейсіз).
Алгоритмді барлық опцияларға қолдану бізге келесі шешімдерді береді. Жұмбақтың 8 нұсқасы шешілетін, 8 нұсқасының шешімі жоқ, 26 нұсқасының бірнеше шешімі бар.
Шешімдер туралы толығырақ
Жұмбақтың барлық шешілген нұсқаларында ортақ нәрсе бар ма? Иә! Оларда ең кішкентай немесе ең үлкен бөтелкелер 2-ші немесе 6-шы орындарда екенін ескеріңіз. Бұл №2 және №6 шектеулерге байланысты 4-ші және 5-шы бөтелкелерде қауіпсіз сусындар бар деген қорытынды жасауға мүмкіндік береді. Бұл қадамсыз біз бұл бөтелкелерде улану мүмкіндігін жоя алмаймыз және біз бірнеше ықтимал шешімдерді табамыз. Сондай-ақ шешілген опциялар екінші «арнайы» бөтелкені (ең кішкентай немесе ең үлкен) 3-ші немесе 4-ші орынға қоюды талап етеді. Әйтпесе, бізді алға жылжытатын сусынның нақты орнын табу мүмкін емес.
Нәтижелері
Кітаптан үзіндімен аяқтаймын.
Гермиона қатты дем шығарды, оның күлімсіреп тұрғанын байқаған Гарри таң қалды - бұл оның ойына келген соңғы нәрсе болды. - Керемет, - деді Гермиона. – Бұл сиқыр емес – бұл логика, жұмбақ. Көптеген ұлы сиқыршылардың логикасы жоқ және олар осында мәңгілікке қалады ».
Бірақ сәл күте тұрыңыз - мүмкін біз кітаптағы диалог негізінде жұмбақтың канондық нұсқасын анықтай аламыз:
«Түсіндім», - деді ол. «Ең кішкентай бөтелке бізді қара от арқылы және тасқа апарады».
...
«Ал, қайсысы сізге күлгін от арқылы оралуға мүмкіндік береді?»
Гермиона қатардың оң жағындағы дөңгелек бөтелкені көрсетті.
Қарғыс атсын. Бұл опция бізге әлі де бірнеше шешімдерді береді. Твит, DR.
код
Егер сізді осы басқатырғышты шешуге және диаграммаларды салуға арналған код қызықтырса, жасай аласыз .
Ақпарат көзі: www.habr.com