“Garri Potter va falsafa toshi”ning oxirida qiziq bir topishmoq bor. Garri va Germiona xonaga kirishadi, shundan so'ng unga kirishlar sehrli olov bilan to'sib qo'yiladi va ular faqat quyidagi topishmoqni hal qilish orqali uni tark etishlari mumkin:
["Garri Potter va falsafa toshi" kitobining "xalq tarjimasi" dan]Oldingizda xavf, orqangizda najot,
Oramizdan topgan ikki kishi sizga yordam beradi;
Ettidan biri bilan siz oldinga siljishda davom etasiz
Ikkinchisi sizni darhol qaytarib oladi.
Ikkimizda faqat qichitqi sharob topasiz,
Uchtasi esa yashirincha bir qatorda turib halokatga olib keladi.
Shunday qilib, qaysi birini tatib ko'rishni tanlang,
Buning uchun biz to'rtta maslahat beramiz.
Bekorga zahar o'zining halokatli issiqligini yashirishga urindi,
Siz uni doimo sharobning chap tomonida topasiz,
Va bilingki, chekkalarda boshqa sovg'a bor,
Ammo davom etmoqchi bo'lsangiz, hech kim yordam bermaydi.
Hammamizning o'lchamimiz har xil, chetdan chetga,
Sizning o'limingiz kichikda o'tirmaydi, lekin kattada ham emas;
Ikkinchisi o'ng uchidan, ikkinchisi esa chapdan
Ular bir-biriga o'xshamasa ham, egizaklar kabi ta'mga ega.
Oddiy qilib aytganda, ular qaysi idishlarda qanday iksirlar borligini tushunishlari kerak.
Ushbu maqolada biz dasturlash yordamida ushbu jumboqning barcha mumkin bo'lgan 42 ta variantini hal qilamiz va natijalar diagrammasini chizamiz (yuqoridagi rasm kabi, faqat ancha kattaroq).
Bir soniya kutib turing, 42 ta variant qaerdan paydo bo'ldi?
Buning sababi, "kichikroq" va "kattaroq" iksirlarning joylashuvi ko'rsatilmagan. Kattasi yetti joydan birida bo'lishi mumkin, bu kichikroq uchun qolgan 6 ta variantni beradi, jami 7 * 6 = 42. JK Rouling paydo bo'lganida qanday tartibni nazarda tutganini aniq bilib bo'lmaydi. Bu topishmoq bilan, agar u sizning Twitteringizda bu haqda gapirmasa. Xo'sh, o'sha muqarrar kun kelguncha, biz tasodifiy versiyani tanlashimiz va u bilan ishlashimiz mumkin. Biroq, uning yechilishi kafolati bo'lmaydi, shuning uchun biz umumiy manfaat uchun ishlaymiz, topishmoqning barcha 42 variantini hal qilamiz (yoki ularning yechilmasligini isbotlaymiz).
Allaqachon QAROR QILING
Birinchidan, bu erda oddiy so'zlar bilan ifodalangan jumboqning barcha cheklovlari:
- Ikkita zararsiz iksir bor, 3 ta zaharli, biri oldinga borishga imkon beradi, ikkinchisi esa orqaga qaytishga imkon beradi.
- Ikkita zararsiz iksirning har birining chap tomonida zaharlisi bor.
- Ikkala tomonning iksirlari har xil va ularning hech biri oldinga siljishga imkon bermaydi.
- Eng katta va eng kichik idishlarda zahar yo'q.
- Chapdagi ikkinchi shisha va o'ngdagi ikkinchi shisha bir xil iksirni o'z ichiga oladi.
Bu bilan qanday kurashish mumkin? Keling, quyidagi variantni ko'rib chiqaylik. E'tibor bering, topishmoqda aytilganidek, qatorda hajmi bo'yicha boshqalardan kichikroq 1 shisha va boshqalardan 1 shisha kattaroq.
Keling, barcha variantlarni ahmoqona ko'rib chiqishga harakat qilaylik - bir vaqtning o'zida bitta shishani oling va tarkib uchun barcha mumkin bo'lgan variantlarni tanlang.
Misol uchun, birinchi shishada 3-sonli cheklov tufayli bizni oldinga siljitadigan iksir bo'lishi mumkin emas. Bundan tashqari, 2-sonli cheklov tufayli u xavfsiz iksirni o'z ichiga olmaydi - uning chap tomonida zahar bo'lishi mumkin emas. Bu bizga zaharli iksir va qaytaruvchi iksir variantlarini qoldiradi. Keling, ikkala variantni ham sinab ko'raylik.
Quyidagi rasmlarda yashil iksirlar zaharni, apelsin xavfsiz ichimliklarni, ko'k - orqaga harakatlanadigan, binafsha rang esa oldinga siljishini anglatadi.
Keling, ushbu jarayonni ikkala ish varianti uchun takrorlaymiz - ikkinchi shishani oling va navbat bilan barcha maqbul kontent variantlarini sinab ko'ring. Bu bizga quyidagilarni beradi:
Shu nuqtai nazardan harakat qilishni davom ettirib, yuqorida sanab o'tilgan cheklovlarni buzmasdan, ba'zi bir shishani iksir bilan to'ldirish mumkin bo'lmagan barcha variantlardan voz kechsak, biz yagona maqbul variantga erishamiz:
Tabiiyki, bizda yechim topish kafolati yo'q edi. Hech qanday yechim bo'lishi mumkin emas yoki bir nechta bo'lishi mumkin (va agar sizda bir nechta echim bo'lsa, bu topishmoqni yechishning iloji yo'qligi bilan bir xil, chunki siz qaysi iksir to'g'ri ekanligini bilmaysiz).
Algoritmni barcha variantlarga qo'llash bizga quyidagi echimlarni beradi. Topishmoqning 8 ta variantida yechish mumkin, 8 ta variantda yechim yoʻq va 26 ta variantda bir nechta yechim mavjud.
Yechimlar haqida ko'proq
Topishmoqning barcha hal qilingan versiyalarida umumiy narsa bormi? Ha! E'tibor bering, ularda eng kichik yoki eng katta shishalar 2 yoki 6-o'rinlarda joylashgan. Bu bizga 2 va 6-shishalarda №4 va №5 cheklovlar tufayli xavfsiz iksirlar mavjud degan xulosaga kelishimizga imkon beradi. Ushbu qadamsiz biz bu idishlarda zahar bo'lish ehtimolini yo'q qila olmaymiz va biz bir nechta mumkin bo'lgan echimlarga ega bo'lamiz. Shuningdek, hal qilingan variantlar ikkinchi "maxsus" shishani (eng kichik yoki eng katta) 3 yoki 4-o'ringa qo'yishni talab qiladi. Aks holda, bizni oldinga siljitadigan iksirning aniq joyini topib bo'lmaydi.
natijalar
Kitobdan iqtibos bilan yakunlayman.
Germiona baland ovozda nafas chiqardi va Garri uning jilmayib turganini payqab hayratda qoldi - bu uning xayoliga kelgan oxirgi narsa edi. - Ajoyib, - dedi Germiona. - Bu sehr emas - bu mantiq, topishmoq. Ko'pgina buyuk sehrgarlar mantiqqa ega emaslar va ular bu erda abadiy qolib ketishadi."
Ammo bir daqiqa kutib turing - ehtimol biz kitobdagi dialog asosida topishmoqning kanonik versiyasini aniqlay olamiz:
“Tushundim”, dedi u. "Eng kichik shisha bizni qora olovdan o'tib, toshga olib boradi."
...
"Va qaysi biri sizga binafsha olovdan qaytishga imkon beradi?"
Germiona qatorning o'ng tomonidagi dumaloq shishani ko'rsatdi.
Jin ursin. Ushbu parametr hali ham bizga bir nechta echimlarni beradi. Tvit, DR.
da
Agar siz ushbu jumboqni hal qilish va diagrammalarni chizish uchun kodga qiziqsangiz, mumkin .
Manba: www.habr.com