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

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Հանոյի աշտարակի մոդել` բաղկացած 8 սկավառակից
Հանոյի աշտարակի անիմացիոն լուծումը (4 սկավառակ)
Հանոյի աշտարակի ինտերակտիվ ցուցադրումը Մեխիկոյի Universum թանգարանում

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

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

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

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

Ծագումը[խմբագրել]

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

Լուծումը[խմբագրել]

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

Իտերատիվ լուծում[խմբագրել]

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

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

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

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

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

Երկու դեպքում էլ ընդհանուր քայլերի քանակը` '2n-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։

Ոչ ռեկուրսիվ լուծումը[խմբագրել]

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

Գրաֆիկական ներկայացումը[խմբագրել]

Ծանոթագրություններ[խմբագրել]

  1. Hofstadter, Douglas R. (1985)։ Metamagical Themas : Questing for the Essence of Mind and Pattern։ New York: Basic Books։ ISBN 0-465-04540-5։ 
  2. Spitznagel, Edward L. (1971)։ Selected topics in mathematics։ Holt, Rinehart and Winston, 137։ ISBN 0-03-084693-5։ 
  3. Moscovich, Ivan (2001)։ 1000 playthinks: puzzles, paradoxes, illusions & games։ Workman։ ISBN 0-7611-1826-8։ 
  4. Petković, Miodrag (2009)։ Famous Puzzles of Great Mathematicians։ AMS Bookstore, 197։ ISBN 0-8218-4814-3։