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

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

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

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

Եթե դու անցել ես ռեկուրսիայի հոդվածը, ապա դու պատրաստ ես տեսնել մեկ այլ խնդիր, որտեղ մի քանի անգամ ռեկուրսիա օգտագործելն օգնում է։ Այն կոչվում է Հանոյի աշտարակներ։ Դու ունես երեք սեպ և n սկավառակ՝ բոլորը տարբեր չափերի։ Սեպերը անվանենք A, B և C, իսկ սկավառակները համարակալենք ամենափոքրից՝ 1, մինչև ամենամեծը՝ n։ Սկզբում բոլոր n սկավառակներն A սեպի վրա են, ներքևից վերև մեծից փոքր շարված այնպես, որ n-ն ամենաներքևում է, իսկ 1-ը՝ ամենավերում Ահա ինչպիսի տեսք ունեն Հանոյի աշտարակները, եթե n=5
Նպատակն է n սկավառակներն A սեպից տեղափոխել դեպի B:
Հեշտ է հնչում, չէ՞։ Դա իրականում այնքան էլ պարզ չէ, որովհետև պետք է պահպանես երկու կանոն․
  1. Ամեն քայլին կարող ես շարժել միայն մեկ սկավառակ։
  2. Ոչ մի սկավառակ պետք է իրենից փոքր սկավառակի վերևում չլինի։ Օրինակ, եթե սեպի վրա սկավառակ 3-ն է, ուրեմն սկավառակ 3-ից ներքև ընկած սկավառակները պետք է դրանից մեծ լինեն։
Հնարավոր է՝ մտածես, թե այս խնդիրն այնքան էլ կարևոր չէ։ Այդպես չէ։ Լեգենդները պատմում են, որ Ասիայում ինչ-որ տեղ (Տիբեթ, Վիետնամ, Հնդկաստան. որն ուզում ես ընտրիր) ճգնավորներն այս խնդիրը լուծում են 64 սկավառակով, և, ըստ լեգենդի, այն ժամանակ, երբ ճգնավորները 64 սկավառակը տեղափոխեն A սեպից B սեպը, աշխարհի վերջը կգա։ Եթե դա ճիշտ է, պե՞տք է արդյոք խուճապի մատնվել։
Սկզբում արի տեսնենք, թե ինչպես կարող ենք խնդիրը լուծել ռեկուրսիայով։ Կսկսենք շատ հեշտ դեպքից․ մեկ սկավառակ, այսինքն՝ n=1։ Մեր առաջնային դեպքը կլինի n=1-ը։ Միշտ կարող ես սկավառակ 1-ը տեղափոխել A սեպից B-ն, որովհետև դու գիտես, որ դրանից ներքև ընկած սկավառակները պետք է լինեն ավելի մեծ։ Եվ ոչ մի առանձնահատուկ բան չկա A և B սեպերի մեջ։ Դու կարող ես սկավառակ 1-ը տեղափոխել B սեպից C-ն, եթե ուզում ես, կամ C սեպից A-ն, կամ առհասարակ կամայական սեպից կամայականը։ Հանոյի աշտարակների խնդիրը մի սկավառակով լուծելը ակնհայտ է, և այն միայն պահանջում է մեկ սկավառակի մեկ տեղափոխություն։
Իսկ ինչպե՞ս ենք լուծում խնդիրը, երբ n=2։ Այն կարող ես լուծել երեք քայլով։ Ահա ինչպիսի տեսք ունի այն սկզբում․
Սկզբում սկավառակ 1-ը տեղափոխիր A սեպից C-ն․
Ուշադրություն դարձրու, որ մենք C սեպն օգտագործում ենք որպես օգնող սեպ, որտեղ կդնենք սկավառակ 1-ը, որպեսզի կարողանանք տեղափոխել սկավառակ 2\ -ը։ Հիմա, երբ սկավառակ 2-ը՝ ամենամեծ սկավառակը, կարող ենք տեղաշարժել, տեղաշարժիր այն B սեպի վրա․
Եվ վերջում սկավառակ 1-ը տեղափոխիր C սկավառակից B․
Այս լուծումը պահանջում է երեք քայլ, և կրկին ինչ-որ առանձնահատուկ բան չենք տեսնում A-ից B տեղափոխելու մեջ։ Դրանք կարող ես տեղաշարժել B-ից C-ն՝ A սեպն օգտագործելով որպես օգնող սեպ․ սկավառակ 1-ը տեղաշարժիր B-ից դեպի A, հետո սկավառակ 2-ը՝ B-ից C և վերջում՝ սկավառակ 1-ը՝ A-ից C։ Համամի՞տ ես, որ երեք քայլով 1 և 2 սկավառակները կարող ես տեղափոխել կամայական սեպից դեպի մեկ ուրիշ սեպը (Ասա՝ «շատ այո»):

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

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

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