Основи програмування на С ++ для початківців

Задача: Ханойська вежа

З розділів чистої математики (не заглиблюючись в деталях) відомо, що в формі рекурсивної формулювання може бути виражений будь обчислюваності алгоритм. Однією з найцікавіших ілюстрацій можливостей і мощі рекурсивних обчислень є завдання Ханойська вежа.

стверджується, що це завдання сформулювали і вирішують досі ченці якихось із монастирів Тибету. Завдання полягає в тому, щоб пірамідку з кілець (на манер дитячої іграшки), нанизану на один з 3-х стержнів, перенести на інший такий же стрижень, дотримуючись строгих правил:

    • пірамідка складається з N кілець різного розміру, укладених по спадаючій діаметра кілець один на інший;
    • перекладати за одну операцію можна тільки одне кільце з будь-якого штиря на будь-який ...
    • але тільки за умови, що класти можна тільки менше кільце зверху на більшу, але ніяк не навпаки;
    • потрібно, в підсумку, всю вихідну пірамідку, що лежить на штирі №1, перемістити на штир №3, використовуючи штир №2 як проміжний.

Наприклад, для 2-х кілець результат виходить такий ось послідовністю перекладань: 1 => 2 , 1 => 3 , 2 => 3

За переказом, це завдання з перекладання N = 10 кілець, вирішують тибетські монахи, і коли вони її, нарешті, вирішити, тоді і настане кінець світу ... Армагедон, в нашому західному нотації.

Для особливо охочих повправлятися, тут же формулюємо завдання №2: спробуйте вирішити цю завдання не рекурсивними методами (це дуже непросте заняття)!

А тепер запишемо рішення задачі:

рішення тут (якщо його таким можна назвати) полягає в тому, щоб при необхідності перенесення піраміди з n кілець з штиря з номером from на штир з номером to послідовно зробити наступне:

    • перенести (якимось чином) меншу піраміду з n-1 кілець тимчасово на штир з номером temp, щоб не заважала…
    • перенести залишився єдине нижню (найбільше) кільце на результуючий штир з номером to
    • після чого, точно так само як в першому пункті, відрізати піраміду (n-1 кілець) з номера temp поверх цього найбільшого кільця на штир з номером to.

Тут важливо те, що ми не знаємо яким чином, і не вміємо виконати 1-й і 3-й пункт нашої програми, але сподіваємося, що він буде рекурсивний розкручуватися за аналогією, за тим же алгоритмом, але для меншого числа n-1 (основоположний принцип рекурсії)… поки n не стане рівним 1 – а там вже зовсім просто.

І ось як розгортається рішення для різних N:

Можете виконати цю програму для N = 10 (тільки не спровокує тим кінець світу!) і переконатися, що число перестановок для цього буде потрібно 1023. І взагалі, для будь-якого N число перестановок буде 2**(N – 1), що являє собою дуже високу ступінь зростання обчислювальної складності задачі - експонентну.

залишити коментар

Ваша електронна адреса не буде опублікований. Обов'язкові поля позначені * *