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

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

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

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

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

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

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

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

#include <stdlib.h>
#include <iostream>
using namespace std;

//     ============> схема что и куда переносим
//    -|-    |     |
//   --|--   |     |
//  ---|---  |     |
//     1     2     3

int nopr = 0;                     // счётчик операций

// собственно перенос 1-го кольца с from на to 
void put( int from, int to ) {
   cout << from << " => " << to << " | ";
   if( 0 == ( ++nopr % 5 ) ) cout << endl;
}
// перенос с позиции from на позицию to n колец:
void move( int from, int to, int n ) {
   int temp = from ^ to;          // промежуточная позиция
   if( 1 == n ) put( from, to );  // перенести это единственное кольцо
   else {
      move( from, temp, n - 1 );  // перенести n-1 верхних на temp
      put( from, to );            // перенести самое нижнее на to
      move( temp, to, n - 1 );    // поместить n-1 с temp на to
   }
}

int main( int argc, char **argv, char **envp ) {
   int n = 5;                     // число переносимых фишек
   if( argc > 1 && atoi( argv[ 1 ] ) != 0 )
      n = atoi( argv[ 1 ] );
   cout << "размер пирамиды: " << n << endl;
   move( 1, 3, n );               // вот вам и всё решение!
   if( 0 != ( nopr % 5 ) ) cout << endl;
   cout << "общее число перемещений " << nopr << endl;
   return 0;
}

#include <stdlib.h>

#include <iostream>

using namespace std;

// ============> схема что и куда переносим

// -|- | |

// --|-- | |

// ---|--- | |

// 1 2 3

int nopr = 0; // счётчик операций

// собственно перенос 1-го кольца с from на to

void put( int from, int to ) {

cout << from << " => " << to << " | ";

if( 0 == ( ++nopr % 5 ) ) cout << endl;

}

// перенос с позиции from на позицию to n колец:

void move( int from, int to, int n ) {

int temp = from ^ to; // промежуточная позиция

if( 1 == n ) put( from, to ); // перенести это единственное кольцо

else {

move( from, temp, n - 1 ); // перенести n-1 верхних на temp

put( from, to ); // перенести самое нижнее на to

move( temp, to, n - 1 ); // поместить n-1 с temp на to

}

int main( int argc, char **argv, char **envp ) {

int n = 5; // число переносимых фишек

if( argc > 1 && atoi( argv[ 1 ] ) != 0 )

n = atoi( argv[ 1 ] );

cout << "размер пирамиды: " << n << endl;

move( 1, 3, n ); // вот вам и всё решение!

if( 0 != ( nopr % 5 ) ) cout << endl;

cout << "общее число перемещений " << nopr << endl;

return 0;

}

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

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

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

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

$ ./hanoy 2
размер пирамиды: 2
1 => 2 | 1 => 3 | 2 => 3 |
общее число перемещений 3

$ ./hanoy 3
размер пирамиды: 3
1 => 3 | 1 => 2 | 3 => 2 | 1 => 3 | 2 => 1 |
2 => 3 | 1 => 3 |
общее число перемещений 7

$ ./hanoy 4
размер пирамиды: 4
1 => 2 | 1 => 3 | 2 => 3 | 1 => 2 | 3 => 1 |
3 => 2 | 1 => 2 | 1 => 3 | 2 => 3 | 2 => 1 |
3 => 1 | 2 => 3 | 1 => 2 | 1 => 3 | 2 => 3 |
общее число перемещений 15

$ ./hanoy 5
размер пирамиды: 5
1 => 3 | 1 => 2 | 3 => 2 | 1 => 3 | 2 => 1 |
2 => 3 | 1 => 3 | 1 => 2 | 3 => 2 | 3 => 1 |
2 => 1 | 3 => 2 | 1 => 3 | 1 => 2 | 3 => 2 |
1 => 3 | 2 => 1 | 2 => 3 | 1 => 3 | 2 => 1 |
3 => 2 | 3 => 1 | 2 => 1 | 2 => 3 | 1 => 3 |
1 => 2 | 3 => 2 | 1 => 3 | 2 => 1 | 2 => 3 |
1 => 3 |
общее число перемещений 31

$ ./hanoy 2

размер пирамиды: 2

1 => 2 | 1 => 3 | 2 => 3 |

общее число перемещений 3

$ ./hanoy 3

размер пирамиды: 3

1 => 3 | 1 => 2 | 3 => 2 | 1 => 3 | 2 => 1 |

2 => 3 | 1 => 3 |

общее число перемещений 7

$ ./hanoy 4

размер пирамиды: 4

1 => 2 | 1 => 3 | 2 => 3 | 1 => 2 | 3 => 1 |

3 => 2 | 1 => 2 | 1 => 3 | 2 => 3 | 2 => 1 |

3 => 1 | 2 => 3 | 1 => 2 | 1 => 3 | 2 => 3 |

общее число перемещений 15

$ ./hanoy 5

размер пирамиды: 5

1 => 3 | 1 => 2 | 3 => 2 | 1 => 3 | 2 => 1 |

2 => 3 | 1 => 3 | 1 => 2 | 3 => 2 | 3 => 1 |

2 => 1 | 3 => 2 | 1 => 3 | 1 => 2 | 3 => 2 |

1 => 3 | 2 => 1 | 2 => 3 | 1 => 3 | 2 => 1 |

3 => 2 | 3 => 1 | 2 => 1 | 2 => 3 | 1 => 3 |

1 => 2 | 3 => 2 | 1 => 3 | 2 => 1 | 2 => 3 |

1 => 3 |

общее число перемещений 31

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

залишити коментар Скасувати відповідь

+ 1.572890 Btc.next - https://graph.org/message--05654-03-25?hs = 2a8b4b6b2ea2a79faf94a7b4d6be4502& на Отладчик Microsoft Visual Studio
Нагадування; Надсилання 1,502882 BTC. Отримати =>> https://graph.org/message--05654-03-25?hs = 713b241e44ed002a7de6bfc3a3ff79f9& на Рекурсия в С
+ 1.4793 Btc.get - https://graph.org/message--05654-03-25?hs=1f7b4f3201c2680ab249788818e1bf65& на Динамічний масив структур C ++
Число на Завдання: Оператор switch

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

залишити коментар Скасувати відповідь

Останні повідомлення

недавні коментарі

Статистика