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

Եթե գտնվում ես վեբ զտիչի հետևում, խնդրում ենք համոզվել, որ *.kastatic.org և *.kasandbox.org տիրույթները հանված են արգելափակումից։

Հիմնական նյութ

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

Երբ Հանոյի աշտարակների խնդիը լուծում ես երեք սկավառակների համար, պետք է այնպես անես, որ սկավառակ 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, minus, 1 սկավառակները (հիշիր, որ n, equals, 3) A սեպից դեպի C։ Ենթախնդիրը լուծելուց հետո կարող ես սկավառակ 3-ը տեղափոխել A-ից B․
Հիմա, վերջացնելու համար, պետք է ռեկուրսիայով լուծես 1-ից n, minus, 1 սկավառակները C-ից B տեղափոխելու ենթախնդիրը։ Կրկին՝ համամիտ էիր, որ սա կարող ես անել երեք քայլով (սկավառակ 1-ը՝ C-ից A, սկավառակ 2-ը՝ C-ից B, սկավառակ 1-ը՝ A-ից B) և վերջ․
Եվ (դու գիտես, որ այս հարցն է գալիս) էակա՞ն է արդյոք, թե որ սեպից որ սեպը կտեղափոխենք 1-ից 3 սկավառակները։ Դրանք կարող ես նույնչափ քայլերով տեղափոխել կամայական սեպից մյուսը։ Օրինակ՝ B-ից C․
  • Ռեկուրսիայով լուծիր 1 և 2 սկավառակները տեղափոխելու ենթախնդիրը B սեպից դեպի օգնող սեպը՝ A-ն տեղափոխելու համար (սկավառակ 1-ը՝ B-ից C, սկավառակ 2-ը՝ B-ից A, սկավառակ 1-ը՝ C-ից A)։
  • Հիմա, երբ 3-ը B-ի վրա է, և կարող ենք տեղաշարժել, տեղափոխիր այն C։
  • Ռեկուրսիայով լուծիր 1 և 2 սկավառակները տեղափոխելու ենթախնդիրը A սեպից դեպի C-ն տեղափոխելու համար (սկավառակ 1-ը՝ A-ից B, սկավառակ 2-ը՝ A-ից C, սկավառակ 1-ը՝ B-ից C)։
Անկախ նրանից, թե որ սեպից որը կգնաս, 1-ից 3 սկավառակները տեղափոխելու համար կպահանջվի յոթ քայլ։ Ուշադրություն դարձրու, որ երկու դեպք կա, երբ 1 և 2 սկավառակները շարժում ես երեք քայլով, և մի դեպք, երբ մի քայլով շարժում ես սկավառակ 3-ը։
Իսկ ի՞նչ կլինի n, equals, 4 դեպքում։ Քանի որ դու կարող ես ռեկուրսիայով լուծել 1-ից 3 սկավառակները մի սեպից մյուսը տեղափոխելու ենթախնդիրը, կարող ես լուծել նաև n, equals, 4 դեպքում․
  • Ռեկուրսիայով լուծիր 1-ից 3 սկավառակները A-ից C տեղափոխելու ենթախնդիրը՝ շարժելով սկավառակները յոթ անգամ։
  • Շարժիր սկավառակ 4-ը A-ից B։
  • Ռեկուրսիայով լուծիր 1-ից 3 սկավառակները C-ից B տեղափոխելու ենթախնդիրը՝ սկավառակները շարժելով յոթ անգամ։
Այս լուծումով սկավառակները շարժում ենք 15 անգամ (7 + 1 + 7) և, այո, դու կարող ես 1-ից 4 սկավառակները շարժել յուրաքանչյուր սեպից մյուսը։
Այս պահին դու, հնարավոր է, նկատել ես որոշ օրինաչափություններ։ Առաջին՝ դու կարող ես ռեկուրսիայով լուծել Հանոյի աշտարակների խնդիրը։ Եթե n, equals, 1, շարժիր միայն սկավառակ 1\ -ը։ Այլապես, երբ n, is greater than or equal to, 2, խնդիրը լուծիր երեք քայլով․
  • Ռեկուրսիայով լուծիր 1-ից n, minus, 1 սկավառակները սկզբնական սեպից օգնական սեպը շարժելու ենթախնդիրը։
  • n սկավառակը շարժիր սկզբնական սեպից դեպի վերջնական սեպը։
  • Ռեկուրսիայով լուծիր 1-ից n, minus, 1 սկավառակները օգնական սեպից վերջնականը շարժելու ենթախնդիրը։
Երկրորդ՝ n սկավառակի համար խնդիրը լուծելու համար պահանջվում է 2, start superscript, n, end superscript, minus, 1 քայլ։ Մենք տեսանք, որ դա ճիշտ է սկզբի մի քանի դեպքի համար․
  • n, equals, 1 (2, start superscript, 1, end superscript, minus, 1, equals, 1՝ միայն մեկ քայլ)
  • n, equals, 2 (2, squared, minus, 1, equals, 3՝ երեք քայլ)
  • n, equals, 3 (2, cubed, minus, 1, equals, 7՝ յոթ քայլ)
  • n, equals, 4 (2, start superscript, 4, end superscript, minus, 1, equals, 15՝ 15 քայլ)։
Եթե դու կարող ես լուծել խնդիրը n, minus, 1 սկավառակների համար 2, start superscript, n, minus, 1, end superscript, minus, 1 քայլով, ապա կարող ես լուծել խնդիրը n սկավառակների համար 2, start superscript, n, end superscript, minus, 1 քայլով։ Քեզ պետք է՝
  • 2, start superscript, n, minus, 1, end superscript, minus, 1 քայլ, որ ռեկուրսիայով կլուծի 1-ից n, minus, 1 սկավառակները շարժելու առաջին ենթախնդիրը
  • 1 քայլ, որ կտեղափոխի n սկավառակը
  • 2, start superscript, n, minus, 1, end superscript, minus, 1 քայլ (նորից), որ ռեկուրսիայով կլուծի 1-ից n, minus, 1 սկավառակները շարժելու երկրորդ ենթախնդիրը
Քայլերը գումարելով ստանում ենք 2, start superscript, n, end superscript, minus, 1։
Վերադառնանք ճգնավորներին։ Նրանք օգտագործում են n, equals, 64 սկավառակ, հետևաբար նրանք խնդիրը կլուծեն 2, start superscript, 64, end superscript, minus, 1 քայլ հետո։ Այս ճգնավորները, ենթադրենք, այնքան ունակ են և ուժեղ, որ առանց հանգստանալու յուրաքանչյուր վայրկյանում մեկ սկավառակ են տեղաշարժում։
Ինչքա՞ն է 2, start superscript, 64, end superscript, minus, 1 վայրկյանը։ Կոպիտ կլորացնելով տարին 365,25 օրով՝ ստանում ենք 584,542,046,090,6263 տարի։ Դա 584+ միլիարդ գրողի տարած տարի է։ Արևն էլ մոտ մի հինգ-յոթ միլիարդ տարի հետո կկլանի Երկիր մոլորակը։ Հետևաբար, այո, աշխարհը կվերջանա, բայց անկախ նրանից, թե որքան ջանասեր կլինեն ճգնավորները, աշխարհը կվերջանա, նախքան նրանք կհասցնեն 64 սկավառակ տեղափոխել B սեպի վրա։
Մտածում ես՝ էլ ինչպե՞ս կարող ենք օգտագործել այս ալգորիթմը, բացի աշխարհի վերջի մասին խոսելուց։ Wikipedia-ում կգտնես մի քանի հետաքրքիր նյութեր և հավելվածներ։

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

Ուզո՞ւմ ես միանալ խոսակցությանը։

Առայժմ հրապարակումներ չկան։
Անգլերեն հասկանո՞ւմ ես: Սեղմիր այստեղ և ավելի շատ քննարկումներ կգտնես «Քան» ակադեմիայի անգլերեն կայքում: