Հանոյի աշտարակ

Հանոյի աշտարակ (կոչվում է նաև Բրահմայի աշտարակ կամ Լուկասի աշտարակ), մաթեմատիկական խաղ կամ գլուխկոտրուկ է։ Այն բաղկացած է երեք ձողերից, և մի շարք տարբեր չափերի սկավառակներից, որոնք կարող է տեղադրել ցանկացած ձողի վրա։ Գլուխկոտրուկը սկսվում է ինչ-որ քանակով սկավառակների՝ առաջին ձողի վրա կոկիկ, վերևից դեպի ներքև աճման կարգով դասավորված, շարքից։

Հանոյի աշտարակի մոդել` բաղկացած 8 սկավառակից

Հանոյի աշտարակի անիմացիոն լուծումը (4 սկավառակ)

Հանոյի աշտարակի ինտերակտիվ ցուցադրումը Մեխիկոյի Universum թանգարանում

Գլուխկոտրուկի նպատակն է՝ տեղաշարժել սկավառակների ամբողջ շարքն առաջին ձողից մյուս երկու ձողերից մեկի վրա՝ հետևելով այս կանոններին.

1. Միաժամանակ միայն մեկ սկավառակ է կարելի տեղաշարժել։
2. Ամեն մի քայլ իրենից ներկայացնում է վերին սկավառակի տեղափոխումը մի ձողից մյուս ձող, այսինքն սկավառակը կարելի է տեղաշարժել միայն այն դեպքում, երբ այն գտնվում է շարքի ամենավերևում։
3. Սկավառակը չի կարելի տեղադրել իրենից ավելի փոքր սկավառակի վրա։

Երեք սկավառակի դեպքում գլուխկոտրուկը կարելի է լուծել յոթ քայլով։ Հանոյի աշտարակը գլուխկոտրուկը լուծելու քայլերի մինիմալ քանաքկը 2ⁿ-1 է, որտեղ n -ը սկավառակների քանակն է։

Ծագում

Գլուխկոտրուկը առաջին անգամ հրապարակվել է Արևմուտքում, ֆրանսիացի մաթեմատիկոս՝ Էդուարդ Լուկասի կողմից, 1883 թ.-ին։ Մի պատմություն կա ըստ որի Կաշի Վիշվանաթում գտնվող հնդկական տաճարում գտնվող մեծ սենյակում կա 3 հին հաղորդագրություններ՝ շրջապատված 64 ոսկե սկավառակներով։ Բրահմայի քուրմերը, հետևելով Բրահմայի կանոններին, տեղաշարժել են սկավառակները՝ հին ժամանակներից, հին մարգարեության կարգադրությամբ։ Այդտեղից էլ եկել է Բրահմայի գլուխկոտրուկ անվանումը։ Ըստ լեգենդի, երբ վերջին քայլը կկատարվի, աշխարհի վերջը եկած կլինի։ Դեռ պարզ չէ, թե Լուկասը հորինել է այդ լեգենդը, թե դրանից ոգեշնչվել։
Եթե լեգենդը ճշմարիտ է և քուրմերը ունակ են մեկ վայրկյանում սկավառակները տեղաշարժել՝ ամենաքիչ քայլերով, ապա ամբողջ գործընթացը կտևեր 2⁶⁴-1 վայրկյան կամ մոտավորապես 585 միլիարդ տարի կամ 18,446,744,073,709,551,615 քայլ՝ ավարտելու համար կամ էլ արևի ներկայիս տարիքից 127 անգամ շատ ժամանակ։
Գոյություն ունի այս լեգենդի շատ տարբերակներ։ Ըստ որոշ պատմությունների, տաճարը վանքն է, իսկ քուրմերը վանականներն են։ Ենթադրվում է, որ տաճարը կամ վանքը գտնվում են տարբեր վայրերում՝ ներառելով Հանոյը և Վիետնամը, և կարող են կապված լինել ինչ-որ կրոնի հետ։ Այլ տարբերակներում ենթադրվում է, որ տաճարը կառուցվել է աշխարհի ստեղծման առաջին օրը, իսկ քուրմերը և վանականները ոչ թե մեկ վայրկյանում, այլ մեկ օրում՝ մեկ քայլ են կատարում։

Լուծում

Խնդրի լուծումը չորս սկավառակներով

Գլուխկոտրուկը կարելի է լուծել ցանկացած քանակի սկավառակներով, չնայած խաղ գլուխկոտրուկը ունի 7-ից 9-ը սկավառակ։ Հանոյի աշտարակը գլուխկոտրուկը լուծելու քայլերի մինիմալ քանաքկը 2ⁿ-1 է, որտեղ n -ը սկավառակների քանակն է։

Իտերատիվ լուծում

Խաղ գլուխկոտրուկի պարզ լուծումը։

Սկավառկների զույգ քանակի դեպքում.

• կատարեք թուլյատրելի քայլ A ձողից B ձող
• կատարեք թուլյատրելի քայլ A ձողից C ձող
• կատարեք թուլյատրելի քայլ B ձողից C ձող
• կրկնեք մինչև խաղի ավարտը

Սկավառակների կենտ քանակի դեպքում.

• կատարեք թուլյատրելի քայլ A ձողից C ձող
• կատարեք թուլյատրելի քայլ A ձողից B ձող
• կատարեք թուլյատրելի քայլ C ձողից B ձող
• կրկնեք մինչև խաղի ավարտը

Երկու դեպքում էլ ընդհանուր քայլերի քանակը՝ '2ⁿ-1 է, որտեղ n է։

Համարժեք իտերատիվ լուծում

Իտերատիվ լուծման ձև է նաև.

Համարակալեք սկավառկները 1-ից n (մեծ սկավառկից փոքր սկավառակ)

• եթե n-ը զույգ է, ապա առաջին քայլում սկավառակը պետք է տեղափոխել սկզբնական (A) ձողից օգտագործվող ձող (B)
• եթե n-ը կենտ է, ապա առաջին քայլում սկավառակը պետք է տեղափոխել սկզբնական (A) ձողից վերջնական ձող (C)

Հիմա ավելացեք այս պայամնները.

• չի կարելի կենտ թվով սկավառակը տեղադրել այլ կենտ թվով սկավառկի վրա
• չի կարելի զույգ թվով սկավառակը տեղադրել այլ զույգ թվով սկավառկի վրա
• չի կարելի հետ քայլ կատարել (չի կարելի սկավառակը հետ դնել այն ձողի վրա, որի վրայից վերցրել էիք` նախորդ քայլում)

Առաջին քայլից հետո, հետևելով այս կանոններին, հնարավոր կլինի միայն մեկ թույլատրելի քայլ կատարել։ Քայլերի այս հերթականությունը համարվում է գլուխկոտրուկի Իտերատիվ լուծում։

Ռեկուրսիվ լուծում

Գլուխկոտրուկը ռեկուրսիվ կերպով լուծելու համար պետք է խնդիրը բաժանել ավելի փոքր խնդրի հետո այդ դրանք բաժանել ավելի փոքր խնդրիներ և այդպես շարունակ մինչև խնդիրը լուծվի։ Օրինակ`

• Համարակալեք ձողերը` A, B, C
• n -ը թող լինի սկավառակների ընդհանուր քանակը
• Համարակալեք սկավառակները 1-ից (ամենափոքր, վերին) n (ամենամեծ, ստորին)

nսկավառակները A-ից B ձող տեղափոխելու համար.

1. Տեղափոխեք n-1 սկավառակները A-ից B: Այս դեպում A ձողի վրա միայն n -ը կմնա։
2. Տեղափոխեք n սկավառակը A-ից C:
3. Տեղափոխեք n-1 սկավառակները B-ից C, որպեսզի դրանք լինեն n սկավառակի վրա։

Վերը նշված է ռեկուսրվ ալգորիթմը։ 1-ից 3 քայլերը կատարելու համար, կիրառվում է նույնալգորիթմը`n-1 : Ամբողջ գործընթացը վերջավոր քայլերի շարք է, քանի որ ինչ-որ մի պահ ալգորիթմը կդառնա n=1 ։ Այս քայլը՝ A ձողից B ձող տեղափոխելը, պարտադիր է։ Այս մոտեցմանը, դինամի ծրագրավորման հետ, կարելի է տալ խիստ մաթեմատիկական ֆորմալիզմ։ Այն հաճախ օգտագործվում է ծրագրավորման դասընթացներ տալուց, որպես ռեկուրսիայի օրինակ։

Ռեկուրսիվ լուծման տրամաբանական վերլուծությունը

Ինչպես և շատ մաթեմատիկական գլուխկոտրուկներում, խնդիրը ավելի հեշտ կլինի լուծել եթե սկզբից լուծենք գլխավոր խնդիրը՝ ինչպես տեղափոխենք h(h=height) բարձրության սկավառկների աշտարակը՝ սկզբնական A ձողից վերջնական C ձող, թողնելով B-ն որպես դատարկ ձող և ենթադրել, որ t≠f։ Առաջինը, նկատենք, որ այս խնդիրը սիմետրիկ է ձողերի անունների տեղափոխման խնդրին (սիմետրիկ S3 խումբ)։ Եթե լուծումը գիտենք որպես A-ից B ձող տեղափոխում, ապա փոխելով ձողերի անունները, նույն լուծումը կարելի է օգտագործել հետագայում ցանկացած ընտրված սկզբնական և վերջնական ձողի համար։ Եթե նույնիսկ մեկ սկավառկ կա կամ չկա ոչ մի սկավառակ, միևնույն է խնդիրը չնչին է։ Եթե h=1, ապա սկավառակը տեղափոխեք A ձողից B ձող։ Եթե h>1, ապա քայլերից ինչ-որ մեկում պետք է ամենամեծ սկավառակը տեղափոխել A ձողից մեկ այլ ձող, ցանկալի է C ձող։ Միակ դեպքը, որի ժամանակ սա հնարավոր է՝ երբ բոլոր փոքր h-1 սկավառակները B ձողի վրա են։ հետևաբար, բոլոր h-1 փոքր սկավառակները պետք է տեղափոխել A-ից B։ Այնուհետև տեղափոխեք ամենամեծ սկավառակը և վերջապես h-1 փոքր սկավառկները տեղափոխեք B-ից C։ Ամենամեծ սկավառակի ներկայությունը չի խոչընդոտում h-1 փոքր սկավառկների տեղափոխմանը և կարելի է այն ժամանակավորապես անտեսել։ Հիմա մնում է միայն h-1 սկավառակները տեղափոխել մի ձողից մյուսը։ Սկզբից A-ից B և հետո B-ից C, բայց նույն մեթոդը կարելի է կիրառել երկու անգամ էլ՝ փոխելով ձողերի անունները։ Նույն կերպ խնդիրը կարելի է լուծել, իջենցելով h-1-ը h-2, h-3 և այդպես շարունակ, մինչև միայն մեկ սկավառակ մնա։ Սա կոչվում է ռեկուրսիա։ Այս ալգորիթմը կարելի է նաև ներկայացնել այսպես. Դասակարգել սկավառակները աճման կարգով՝ բնական թվերով, այսինքն 0-ից սկսած, բայց չներառելով h-ը։ Այդ պատճառով էլ 0 սկավառակը ամենափոքրը կլինի, իսկ h-1 սկավառակը՝ ամենամեծը։

Այս մեթոդը իրենից ներկայացնում է սկավառկների՝ A-ից B ձող տեղափուխումը, թողնելով B ձողը դատարկ։

• Քայլ առաջին . Եթե h>1, ապա սկզբից օգտագործեք այս մեթոդը և h-1 փոքր սկավառակները տեղափոխեք A ձողից B։
• Քայլ երկրորդ . Այժմ ամենամեծ սկավառակը՝ h սկավառակը կարելի է տեղափոխել A ձողից C։
• Քայլ երրորդ . Եթե h>1, ապա կրկին օգտագործենք այս մեթոդը, որպեսզի h-1 սկավառակները տեղափոխենք B ձողից C։

Մաթեմատիկական ինդուկցիայի շնորհիվ, կարելի է ապացուցել, որ վերին մեթոդը պահանջում է մինիմալ թույլատրելի քայլերի քանակ, և որ ստացված լուծումը միակն է, որ ունի մինիմալ քայլերի քանակ։ Օգտագործելով ռեկուրսիվ հարաբերությունները, մինիմալ քայլերի շարքը, որ պահանջում է այս լուծումը կարելի է հաշվել՝$2^{h}-1$-ով։ Այս արդյունքը ստացվում է, երբ առաջին և երրորդ քայլերը կատարում են $T_{h-1}$ քայլեր և երկրորդ քայլը կատարում է մեկ քայլ, ստացվում է՝ $T_{h}=2T_{h-1}+1$։

A = [3, 2, 1]
B = []
C = []

def move(n, source, target, auxiliary):
    if n > 0:
        # move n - 1 disks from source to auxiliary, so they are out of the way
        move(n - 1, source, auxiliary, target)

        # move the nth disk from source to target
        target.append(source.pop())

        # Display our progress
        print(A, B, C, '##############', sep = '\n')

        # move the n - 1 disks that we left on auxiliary onto target
        move(n - 1, auxiliary, target, source)

# initiate call from source A to target C with auxiliary B
move(3, A, C, B)

Ոչ ռեկուրսիվ լուծումը

Ռեկուրսիվ ալգորիթմով՝ սկավառկները մի ձողից մյուսը տեղափոխելու շատ տարբերակներ կան։

Գրաֆիկական ներկայացումը

Պասկալով ներկայացումը

type

   st = (left, middle, right);
   nat = 1..maxint;

var

   m: nat; {m – число дисков}

procedure move(n: nat; s1, sw, sk: st); {перемещение n дисков с s1 на sk}

   procedure step;
   {перемещение одного диска с s1 на sk}

       procedure print(s: st);
           begin
               case s of
                   left: write(' лев. ');
                   middle: write(' средн. ');
                   right: write(' прав. ')
               end;
           end;

       begin {step}
           write(' снять диск с ');
           print(s1);
           write(' надеть на  ');
           print(sk);
           writeln
       end;

   begin {move}
       if n = 1 then
           step
       else begin
           move(n - 1, s1, sk, sw);
           step;
           move(n-1, sw, s1, sk)
       end
   end;

begin

   read(m); {число дисков}
   writeln('для ', m:3, ' дисков следует произвести ',
   'следующие действия:');
   move(m, left, middle, right);

readln end.