"Харри Поттер ба гүн ухааны чулуу" зохиолын төгсгөлд нэгэн сонирхолтой оньсого байдаг. Харри, Гермиона хоёр өрөөнд орж ирсний дараа орох хаалгыг ид шидийн галаар хаасан бөгөөд тэд зөвхөн дараах оньсого тааварт шийдснээр л гарч чадна.
Урд чинь аюул, цаана чинь аврал байна.
Бидний дунд олсон хоёр хүн танд туслах болно;
Долоогийн аль нэгийг авснаар та урагшлах болно
Нөгөөх нь чамайг шууд буцааж авна.
Бид хоёроос та зөвхөн хамхуултай дарс л олох болно.
Гурав нь нууцаар дараалан зогсох сүйрлийг авчирдаг.
Тиймээс алийг нь амтлахаа сонго,
Үүнийг хийхийн тулд бид дөрвөн зөвлөмжийг өгдөг.
Хор нь үхлийн халуунаа нуух гэж дэмий л оролдов.
Та түүнийг үргэлж дарсны зүүн талд олох болно.
Мөн ирмэг дээр байгаа хүмүүс өөр бэлэг барьж байгааг мэдээрэй.
Гэхдээ үргэлжлүүлэхийг хүсвэл хэн ч туслахгүй.
Бид бүгд өөр өөр хэмжээтэй, ирмэгээс ирмэг хүртэл,
Чиний үхэл багад суудаггүй, харин томд ч суудаггүй;
Хоёр дахь нь баруун төгсгөлөөс, хоёр дахь нь зүүнээс
Тэд адилхан биш ч гэсэн ихрүүд шиг амттай байдаг.
["Харри Поттер ба Философийн чулуу" номын "ардын орчуулга"-аас]
Энгийнээр хэлэхэд тэд ямар саванд ямар эм агуулагддагийг ойлгох хэрэгтэй.
Энэ нийтлэлд бид програмчлалын тусламжтайгаар энэ оньсогоын бүх боломжит 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