If you're seeing this message, it means we're having trouble loading external resources on our website.

Егер веб фильтрлерін қолдансаң, *.kastatic.org мен *.kasandbox.org домендері бұғатталмағанын тексер.

Негізгі бет

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

Егер сіз рекурсия тақырыбындағы сабақты өткен болсаңыз, онда сіз шешімін табуға бірнеше рет қайталанатын рекурсия әдісі көмектесетін тағы бір есепті қарастыруға дайынсыз. Ол есеп Ханой мұнаралары деп аталады. Сізге үш білік пен көлемдері әртүрлі n дискілер жиынтығы беріледі. Біліктерді A, B және C деп атайық және дискілерді ең кішкентайын 1 деп, ал ең үлкенін n деп 1-ден n-ге дейін нөмірлеп шығайық. Бастапқыда n-диск төменде, ал 1-диск жоғарыда болатындай етіп барлық n дискілер А білігінде төменнен жоғары қарай көлемнің кішірею ретімен орналасады. Төменде n=5 үшін Ханой мұнаралары көрсетілген:
A, B және C деп белгіленген үш мұнара берілген. А мұнарасында 5, 4, 3, 2 және 1 сандарымен нөмірленген дискілер бар. 5-диск төменде және 1-диск жоғарыда орналасқан. В және C мұнараларында дискілер жоқ.
Мақсатымыз - барлық n дискілерді А білігінен B білігіне көшіру.
A, B және C деп белгіленген үш мұнара берілген. B мұнарасында 5, 4, 3, 2 және 1 сандарымен нөмірленген дискілер бар. 5-диск төменде және 1-диск жоғарыда орналасқан. А және C мұнараларында дискілер жоқ.
Қарапайым болып көрінеді, солай емес пе? Бірақ шын мәнінде бұл оңай емес, себебі сіз келесі екі ережені сақтауыңыз керек:
  1. Бір уақытта тек бір дискіні жылжытуға болады. 2. Ешқандай диск өзінен кіші дискінің үстіне қойыла алмайды. Мысалы, егер 3-диск білікте болса, онда 3-дискінің астындағы барлық дискілердің нөмірлері 3-тен үлкен сандар болуы керек.
Сіз бұл есеп соншалықты маңызды емес деп ойлауыңыз мүмкін. Au contraire! (Керісінше!) Аңыз бойынша Азияның кез-келген жерінде (Тибет, Вьетнам, Үндістан — Интернеттегі қандай аңызды таңдасаңыз да) монахтар бұл есепті 64 диск жиынтығымен шешеді. Олар барлық 64 дискіні А-дан В-ға екі ережеге сәйкес жылжыту аяқталғаннан кейін ақырзаман келеді деп сенеді. Егер монахтар қателеспесе, біз көшеде дүрбелең жасауымыз керек пе?
Алдымен есепті рекурсивті түрде қалай шешуге болатынын қарастырайық. Біз өте қарапайым жағдайдан бастаймыз: бір диск, яғни n=1. Бұл жағдай біздің негізгі жағдайымыз болады. Сіз әрқашан 1-дискіні А-дан В-ға ауыстыра аласыз, себебі оның астындағы дискілер одан үлкенірек болуы керек екенін білесіз. Оған қоса А және В біліктеріне қатысты ешқандай ерекшелік жоқ. Қаласаңыз, 1-дискіні В-дан С-ға немесе С-дан А-ға немесе кез-келген біліктен кез-келген білікке көшіре аласыз. Бір дискісі бар Ханой мұнаралары есебін шешу тривиал болып табылады және ол бір дискіні бір рет жылжытуды талап етеді.
Дискілер саны екеу болса ше? n=2 болған кезде есепті қалай шығарасыз? Сіз мұны үш кезеңде жасай аласыз. Бұл басында осылай көрінеді:
A, B және C деп белгіленген үш білік берілген. А мұнарасының төменгі жағында 2-диск, ал жоғарғы жағында 1-диск бар. B және C мұнараларында дискілер жоқ.
Алдымен 1-дискіні А білігінен С білігіне көшіреміз.
A, B және C деп белгіленген үш білік берілген. А мұнарасында 2-диск бар. B мұнарасында дискілер жоқ. C мұнарасында 1-диск бар.
Біз C білігін қосалқы білік ретінде, яғни 2-дискіге жету үшін 1-дискіні орналастыратын орын ретінде қолданамыз. Енді ең төменгі 2-дискіге жол ашық, оны B-ға көшіреміз:
A, B және C деп белгіленген үш мұнара берілген. А мұнарасында диск жоқ. B мұнарасында 2-диск, ал C мұнарасында 1-диск бар.
Соңғы кезеңде 1-дискіні С білігінен В білігіне көшіреміз.
A, B және C деп белгіленген үш білік берілген. А мұнарасында диск жоқ. B мұнарасында төменде 2-диск және жоғарыда 1-диск бар. C мұнарасында диск жоқ.
Бұл шешім үш қадамнан тұрады және екі дискіні А-дан В-ға жылжытуда да ешқандай ерекшелік жоқ. Сіз оларды А білігін қосалқы білік ретінде алып B-дан С-ға ауыстыра аласыз: 1-дискіні B-дан A-ға, содан кейін 2-дискіні B-дан C-ға көшіріп, 1-дискіні А-дан C-ға көшіріп орналастыруды аяқтайсыз. 1- және 2-дискіні кез-келген біліктен кез-келген білікке үш қадаммен жылжытуға болатындығымен келісесіз бе? ("Иә" деп жауап беріңіз.)

Бұл мазмұн ынтымақтастықтың нәтижесі Дартмут компьютерлік ғылымы профессорлар [Томас Кормен](http://www.cs.dartmouth.edu / ~thc/) және [Дэвин Бэлком](http://www.cs.dartmouth.edu / ~devin/), сонымен қатар Хан академиясының компьютерлік оқу бағдарламасы бойынша тобы. Мазмұн лицензияланған CC-BY-NC-SA.