Հանոյի աշտարակներ. շարունակություն

Երբ Հանոյի աշտարակների խնդիը լուծում ես երեք սկավառակների համար, պետք է այնպես անես, որ սկավառակ 3-ը կարողանաս շարժել, որպեսզի այն տեղափոխես A սեպից B-ն։ Սկավառակ 3-ը տեղաշարժել կարողանալու համար պետք է 1 և 2 սկավառակները տեղաշարժես A-ից դեպի օգնող սեպը՝ C-ն․

Մի րոպե։ Բայց կարծես թե մի քայլով երկու սկավառակ տեղափոխեցինք՝ խախտելով առաջին կանոնը։ Իրականում դրանք մի քայլով չենք տեղաշարժել։ Հիշո՞ւմ ես, որ համամիտ էիր, որ կամայական սեպից մյուսը 1 և 2 սկավառակը կարող ենք տեղաշարժել երեք քայլով։ Վերևի իրավիճակը ցույց է տալիս, թե ինչ կունենաս երեք քայլ հետո (Սկավառակ 1-ը՝ A-ից B, սկավառակ 2-ը՝ A-ից C, սկավառակ 1-ը՝ B-ից C)։

Ավելին՝ 1 և 2 սկավառակներն A-ից C տեղափոխելով՝ դու ռեկուրսիայով լուծեցիր ենթախնդիր․ տեղափոխել 1-ից $n-1$n, minus, 1 սկավառակները (հիշիր, որ $n = 3$n, equals, 3) A սեպից դեպի C։ Ենթախնդիրը լուծելուց հետո կարող ես սկավառակ 3-ը տեղափոխել A-ից B․

Հիմա, վերջացնելու համար, պետք է ռեկուրսիայով լուծես 1-ից $n-1$n, minus, 1 սկավառակները C-ից B տեղափոխելու ենթախնդիրը։ Կրկին՝ համամիտ էիր, որ սա կարող ես անել երեք քայլով (սկավառակ 1-ը՝ C-ից A, սկավառակ 2-ը՝ C-ից B, սկավառակ 1-ը՝ A-ից B) և վերջ․

Եվ (դու գիտես, որ այս հարցն է գալիս) էակա՞ն է արդյոք, թե որ սեպից որ սեպը կտեղափոխենք 1-ից 3 սկավառակները։ Դրանք կարող ես նույնչափ քայլերով տեղափոխել կամայական սեպից մյուսը։ Օրինակ՝ B-ից C․

Անկախ նրանից, թե որ սեպից որը կգնաս, 1-ից 3 սկավառակները տեղափոխելու համար կպահանջվի յոթ քայլ։ Ուշադրություն դարձրու, որ երկու դեպք կա, երբ 1 և 2 սկավառակները շարժում ես երեք քայլով, և մի դեպք, երբ մի քայլով շարժում ես սկավառակ 3-ը։

Իսկ ի՞նչ կլինի $n = 4$n, equals, 4 դեպքում։ Քանի որ դու կարող ես ռեկուրսիայով լուծել 1-ից 3 սկավառակները մի սեպից մյուսը տեղափոխելու ենթախնդիրը, կարող ես լուծել նաև $n = 4$n, equals, 4 դեպքում․

Այս լուծումով սկավառակները շարժում ենք 15 անգամ (7 + 1 + 7) և, այո, դու կարող ես 1-ից 4 սկավառակները շարժել յուրաքանչյուր սեպից մյուսը։

Այս պահին դու, հնարավոր է, նկատել ես որոշ օրինաչափություններ։ Առաջին՝ դու կարող ես ռեկուրսիայով լուծել Հանոյի աշտարակների խնդիրը։ Եթե $n = 1$n, equals, 1, շարժիր միայն սկավառակ 1\ -ը։ Այլապես, երբ $n \geq 2$n, is greater than or equal to, 2, խնդիրը լուծիր երեք քայլով․

Երկրորդ՝ $n$n սկավառակի համար խնդիրը լուծելու համար պահանջվում է $2^n - 1$2, start superscript, n, end superscript, minus, 1 քայլ։ Մենք տեսանք, որ դա ճիշտ է սկզբի մի քանի դեպքի համար․

Եթե դու կարող ես լուծել խնդիրը $n-1$n, minus, 1 սկավառակների համար $2^{n-1} - 1$2, start superscript, n, minus, 1, end superscript, minus, 1 քայլով, ապա կարող ես լուծել խնդիրը $n$n սկավառակների համար $2^n - 1$2, start superscript, n, end superscript, minus, 1 քայլով։ Քեզ պետք է՝

Քայլերը գումարելով ստանում ենք $2^n - 1$2, start superscript, n, end superscript, minus, 1։

Վերադառնանք ճգնավորներին։ Նրանք օգտագործում են $n = 64$n, equals, 64 սկավառակ, հետևաբար նրանք խնդիրը կլուծեն $2^{64} - 1$2, start superscript, 64, end superscript, minus, 1 քայլ հետո։ Այս ճգնավորները, ենթադրենք, այնքան ունակ են և ուժեղ, որ առանց հանգստանալու յուրաքանչյուր վայրկյանում մեկ սկավառակ են տեղաշարժում։

Ինչքա՞ն է $2^{64} - 1$2, start superscript, 64, end superscript, minus, 1 վայրկյանը։ Կոպիտ կլորացնելով տարին 365,25 օրով՝ ստանում ենք 584,542,046,090,6263 տարի։ Դա 584+ միլիարդ գրողի տարած տարի է։ Արևն էլ մոտ մի հինգ-յոթ միլիարդ տարի հետո կկլանի Երկիր մոլորակը։ Հետևաբար, այո, աշխարհը կվերջանա, բայց անկախ նրանից, թե որքան ջանասեր կլինեն ճգնավորները, աշխարհը կվերջանա, նախքան նրանք կհասցնեն 64 սկավառակ տեղափոխել B սեպի վրա։

Մտածում ես՝ էլ ինչպե՞ս կարող ենք օգտագործել այս ալգորիթմը, բացի աշխարհի վերջի մասին խոսելուց։ Wikipedia-ում կգտնես մի քանի հետաքրքիր նյութեր և հավելվածներ։

Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։