From Wikipedia, the free encyclopedia
Հանոյի աշտարակ (կոչվում է նաև Բրահմայի աշտարակ կամ Լուկասի աշտարակ[1]), մաթեմատիկական խաղ կամ գլուխկոտրուկ է։ Այն բաղկացած է երեք ձողերից, և մի շարք տարբեր չափերի սկավառակներից, որոնք կարող է տեղադրել ցանկացած ձողի վրա։ Գլուխկոտրուկը սկսվում է ինչ-որ քանակով սկավառակների՝ առաջին ձողի վրա կոկիկ, վերևից դեպի ներքև աճման կարգով դասավորված, շարքից։
Գլուխկոտրուկի նպատակն է՝ տեղաշարժել սկավառակների ամբողջ շարքն առաջին ձողից մյուս երկու ձողերից մեկի վրա՝ հետևելով այս կանոններին.
Երեք սկավառակի դեպքում գլուխկոտրուկը կարելի է լուծել յոթ քայլով։ Հանոյի աշտարակը գլուխկոտրուկը լուծելու քայլերի մինիմալ քանաքկը 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]։
Խաղ գլուխկոտրուկի պարզ լուծումը։
Սկավառկների զույգ քանակի դեպքում.
Սկավառակների կենտ քանակի դեպքում.
Երկու դեպքում էլ ընդհանուր քայլերի քանակը՝ '2n-1 է, որտեղ n է։
Իտերատիվ լուծման ձև է նաև.
Համարակալեք սկավառկները 1-ից n (մեծ սկավառկից փոքր սկավառակ)
Հիմա ավելացեք այս պայամնները.
Առաջին քայլից հետո, հետևելով այս կանոններին, հնարավոր կլինի միայն մեկ թույլատրելի քայլ կատարել։ Քայլերի այս հերթականությունը համարվում է գլուխկոտրուկի Իտերատիվ լուծում։
Գլուխկոտրուկը ռեկուրսիվ կերպով լուծելու համար պետք է խնդիրը բաժանել ավելի փոքր խնդրի հետո այդ դրանք բաժանել ավելի փոքր խնդրիներ և այդպես շարունակ մինչև խնդիրը լուծվի։ Օրինակ`
nսկավառակները A-ից B ձող տեղափոխելու համար.
Վերը նշված է ռեկուսրվ ալգորիթմը։ 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 ձողը դատարկ։
Մաթեմատիկական ինդուկցիայի շնորհիվ, կարելի է ապացուցել, որ վերին մեթոդը պահանջում է մինիմալ թույլատրելի քայլերի քանակ, և որ ստացված լուծումը միակն է, որ ունի մինիմալ քայլերի քանակ։ Օգտագործելով ռեկուրսիվ հարաբերությունները, մինիմալ քայլերի շարքը, որ պահանջում է այս լուծումը կարելի է հաշվել՝-ով։ Այս արդյունքը ստացվում է, երբ առաջին և երրորդ քայլերը կատարում են քայլեր և երկրորդ քայլը կատարում է մեկ քայլ, ստացվում է՝ ։
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.