Ханой мұнаралары

Ханой мұнаралары-ті қалай ойнайсыз?

«Ханой мұнаралары» — 1883 жылы француз математигі Эдуар Лукас ойлап тапқан әлемге әйгілі жұмбақ. Бастапқыда барлық дискілер сол жақ тірекке көлемі азаятын ретпен орналастырылады; мақсат — оларды барлығын оң жақ тірекке көшіру. Әрбір жүрісте тек бір таяқшадағы жоғарғы дискіні басқа таяқшаға ауыстыруға болады, ал үлкен дискіні кіші дискінің үстіне ешқашан қоюға болмайды. n диск үшін қажетті жүрістер санының ең аз мөлшері 2ⁿ−1.

1. Бастапқыда барлық дискілер ең үлкенінен ең кішісіне дейін сол жақтағы таяқшаға орналастырылады.
2. Бір ғана қозғалыспен жоғарғы дискіні кез келген таяқшадан басқа таяқшаға ауыстыра аласыз.
3. Үлкен диск ешқашан кіші дисктің үстіне қойылмайды.
4. Барлық дискілерді ең оң жақтағы таяқшаға ауыстырғаннан кейін жұмбақ шешіледі; ең жақсы шешім – n диск үшін 2ⁿ−1 қозғалыс (мұнда n – диск саны).
5. Сіз 3-тен 8-ге дейінгі қиындық деңгейін таңдай аласыз, «Hint» функциясын пайдаланып кез келген уақытта келесі ең жақсы жүрісті көре аласыз немесе «Undo» функциясын пайдаланып соңғы жүрісіңізді кері қайтара аласыз.

Ханой мұнаралары стратегия бойынша кеңестер

• n-дискілі жұмбақты шешу үшін алдымен жоғарғы n–1 дискіні көмекші таяқшаға жылжытып, содан кейін ең үлкен дискіні мақсатқа жылжытып, ақырында қалған n–1 дискіні мақсатқа жылжытыңыз — бұл ойлау тәсілі әр деңгейде жұмыс істейді.
• Фигураларды қажетсіз алға-артқа жылжытпаңыз; әрбір жүріс мақсатты болуы тиіс.
• Егер тұрып қалсаңыз, «Hint» батырмасын пайдаланып, ең қысқа шешімдегі келесі қадамды көре аласыз.

Ханой мұнаралары-тің тарихы

Ханой мұнаралары — әлемге әйгілі жұмбақ, оны алғаш рет 1883 жылы француз математигі Эдуар Лукас ұсынған, және содан бері математика мен компьютерлік ғылымды оқытуда рекурсияны түсіндіру үшін қолданылып келеді.

Аңызға сәйкес, ғибадатханадағы діни қызметкерлер осы ережелерге сәйкес 64 алтын дискіні тасып жүр; олар барлығын тасып бітіргенде әлем соңы басталады. 64 дискіні тасудың оңтайлы шешімі 2⁶⁴−1 қадамды талап етеді — тіпті секундына бір қадам жасаса да, бұл ғаламның жасынан да ұзақ уақытты алады!

Басқа атаулар: Ханой мұнарасы, Ханой мұнарасы, Диск жұмбағы