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

Եթե դու անցել ես ռեկուրսիայի հոդվածը, ապա դու պատրաստ ես տեսնել մեկ այլ խնդիր, որտեղ մի քանի անգամ ռեկուրսիա օգտագործելն օգնում է։ Այն կոչվում է Հանոյի աշտարակներ։ Դու ունես երեք սեպ և $n$n սկավառակ՝ բոլորը տարբեր չափերի։ Սեպերը անվանենք A, B և C, իսկ սկավառակները համարակալենք ամենափոքրից՝ 1, մինչև ամենամեծը՝ $n$n։ Սկզբում բոլոր $n$n սկավառակներն A սեպի վրա են, ներքևից վերև մեծից փոքր շարված այնպես, որ $n$n-ն ամենաներքևում է, իսկ 1-ը՝ ամենավերում Ահա ինչպիսի տեսք ունեն Հանոյի աշտարակները, եթե $n = 5$n, equals, 5․

Նպատակն է $n$n սկավառակներն A սեպից տեղափոխել դեպի B:

Հեշտ է հնչում, չէ՞։ Դա իրականում այնքան էլ պարզ չէ, որովհետև պետք է պահպանես երկու կանոն․

Հնարավոր է՝ մտածես, թե այս խնդիրն այնքան էլ կարևոր չէ։ Այդպես չէ։ Լեգենդները պատմում են, որ Ասիայում ինչ-որ տեղ (Տիբեթ, Վիետնամ, Հնդկաստան. որն ուզում ես ընտրիր) ճգնավորներն այս խնդիրը լուծում են 64 սկավառակով, և, ըստ լեգենդի, այն ժամանակ, երբ ճգնավորները 64 սկավառակը տեղափոխեն A սեպից B սեպը, աշխարհի վերջը կգա։ Եթե դա ճիշտ է, պե՞տք է արդյոք խուճապի մատնվել։

Սկզբում արի տեսնենք, թե ինչպես կարող ենք խնդիրը լուծել ռեկուրսիայով։ Կսկսենք շատ հեշտ դեպքից․ մեկ սկավառակ, այսինքն՝ $n = 1$n, equals, 1։ Մեր առաջնային դեպքը կլինի $n = 1$n, equals, 1-ը։ Միշտ կարող ես սկավառակ 1-ը տեղափոխել A սեպից B-ն, որովհետև դու գիտես, որ դրանից ներքև ընկած սկավառակները պետք է լինեն ավելի մեծ։ Եվ ոչ մի առանձնահատուկ բան չկա A և B սեպերի մեջ։ Դու կարող ես սկավառակ 1-ը տեղափոխել B սեպից C-ն, եթե ուզում ես, կամ C սեպից A-ն, կամ առհասարակ կամայական սեպից կամայականը։ Հանոյի աշտարակների խնդիրը մի սկավառակով լուծելը ակնհայտ է, և այն միայն պահանջում է մեկ սկավառակի մեկ տեղափոխություն։

Իսկ ինչպե՞ս ենք լուծում խնդիրը, երբ $n = 2$n, equals, 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-ի կողմից։