Задача про Ханойські вежі

Размещено на http://www.allbest.ru/

Міністерство освіти і науки України

Сумський державний університет

Кафедра інформатики

Курсова Робота

з дисципліни “Програмування”

на тему

“Задача про Ханойські вежі”

Виконала:

студентка групи ІН-32/1

Салтиш О.І.

Викладач:

Боровик В.О.

Суми, 2014

Вступ

У наш час важко уявити своє життя без комп'ютера, його вплив досяг неймовірно великих масштабів. Мало хто зараз не користується Інтернетом та хоча б найелементарнішими програмами.

Ми можемо помітити що за допомогою комп'ютерів значно збільшилась продуктивність праці, комп'ютерні програми дозволяють нам вирішувати складні задачі швидко, оптимізуючи наші дії і перекладаючи певну кількість розрахунків на програми.

Комп'ютери керують роботою інших комп'ютерів, при цьому зменшуючи фізичну працю людини, допомагають точно виконати розрахунки, швидко знайти необхідну інформацію. Комп'ютери потрібні нам як під час роботи так і в години дозвілля. Вони допомагають нам відпочивати від фізичної праці, багато хто, і діти і дорослі люблять грати в комп'ютерні ігри та вирішувати головоломки.

Моя робота присвячена саме цьому. Задача про Ханойські вежі, є не новою витівкою, але все ж такою гарною розминкою для мозку, як і в момент її створення.

Ця робота актуальна, для будь кого, хто любить грати в логічні ігри, і просто для того кому цікаво перевірити свої можливості.

Мета моєї роботи, за допомогою програмних засобів, реалізувати задачу про Ханойські вежі, і знайти відповідь на неї.

1. Постановка задачі

Одна із прадавніх легенд говорить: «У непрохідних джунглях недалеко від міста Ханоя є храм бога Брами. У ньому перебуває бронзова плита із трьома алмазними стрижнями. На один зі стрижнів бог при створенні миру нанизав 64 диски різних діаметрів із чистого золота. Найбільший диск лежить на бронзовій плиті, а інші утворюють піраміду, що зужується догори. Це вежа Брами. Працюючи день і ніч, жерці храму переносять диски з одного стрижня на інший, дотримуючись законів Брами:

1) диски можна переміщати з одного стрижня на іншій тільки по одному;

2) не можна класти більший диск на менший;

3) не можна відкладати диски убік, при переносі дисків з одного стрижня на інший можна використовувати проміжний третій стрижень, на якому диски повинні перебувати теж тільки у вигляді піраміди, що зужується догори.

Коли всі 64 диска будуть перенесені з одного стрижня на іншій, настане кінець світу.

Кількість перекладань, в залежності від кількості дисків, розраховується за формулою 2n - 1. А дле 64 дисків це 18 446 744 073 709 551 615 перекладань, і якщо рахувати, що одне перекладання буде займати лише секунду, це буде дорівнювати близько п'ятьом мільярдам століть.

Насправді ж, придумав її у кінці XIX століття французський математик Едуард Люка. Починаючи з 1883 року вона продавалась під різними назвами -- "Вежі Брахми", "Ломиголовка про кінець світу", "Пагода-ломиголовка", да і місце дії легенди неоднократно переносилось то у Китай, то у Тібет, але у підсумку "прижилось" у Вєтнамі -- разом з назвою "Ханойські вежі".

Отже треба перемістити n дисків з одного стрижня на інший(перший останній та проміжний стрижні, кількість дисків задає користувач), не перекладаючи за одик крок більше ніж один диск, і не кладучи більший на менший.

2. Математична модель

Математичною моделлю даної задачі є рекурентне співвідношення.

Рекурентні співвідношення мають принципове значення в аналізі алгоритмів. Якщо алгоритм влаштований так, що він розбивається на декілька менших підзадач, то можна описати час його роботи з допомогою рекурентного співвідношення.

"Рекурентний" означає "зворотний". Справді, метод рекурентних співвідношень, дозволяє знаходити значення деякої функції для заданої величини аргументу через менші значення аргументів. Стосовно комбінаторики цей метод дає можливість знаходити розв'язок комбінаторної задачі для n предметів через розв'язок аналогічної задачі з меншим числом предметів за допомогою деякого співвідношення, яке називається рекурент¬ним співвідношенням. Метод рекурентних співвідношень добре відомий з курсу шкільної математики, де він застосовувався при визначенні сум арифметичної і геометричної прогресій та при визначенні n-го члена цих прогресій.

Прикладами рекурентних співвідношень є:

Ряд чисел Фібоначчі.

Біном Н'ютона

3. Алгоритм реалізації задачі

При побудові алгоритму використовується підхід «розділяй і володарюй». Ідея полягає в наступному:

завдання розбивається на кілька підзадач меншого розміру;

вирішуються ці підзадачі;

рішення підзадач комбінуються, й виходить рішення вихідної задачі.

Як правило, завдання вирішуються безпосередньо, або за допомогою рекурсивного виклику.

Алгоритм називається рекурсивним, якщо при вирішенні деякої задачі він викликає сам себе для вирішення підзадачі.

Для того, щоб перекласти всю піраміду з дисків, треба спочатку перекласти все, що вище найбільшого диска, з першого на допоміжний стрижень, потім перекласти цей найбільший диск з першого на третій стрижень, а потім перекласти залишилася піраміду з другого на третій стрижень, користуючись допоміжним стрижнем.

4.Опис програми

При запуску програми з'являється робоче вікно.

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

Вхідні та вихідні дані

Вхідними даними є номер першого,останнього та проміжного стриженів, кількість дисків

Вихідними даними є алгоритм вирішення задачі(кроки переміщення дисків на стриженях), кількість кроків, графічна реалізація першого та останнього кроків

Опис функцій

void hanoi_towers(int quantity, int from, int to, int buf_peg) - функція підрахунку та виводу кроків перекладання дисків

double krok(double n) - функція яка підраховує кількість кроків

int BCX_Line (HWND,int,int,int,int,int=0,HDC=0) - функція для малювання лініїй

int Nachalo(int stolb,int k ) - функція, яка виводить на екран графічне представлення початкової ітерації

int Konec(int stolb,int k ) - функція, яка виводить на екран графічне представлення кінцевої ітерації

5.Код програмної реалізації

#include <windows.h> // Win32API Header File

#include <cstring>

#include <cstdio>

#include <iostream>

#include <cmath>

using namespace std;

#define Red RGB (255,0,0)

#define Lime RGB (206,255,0)

#define Blue RGB (0,0,255)

#define My RGB (50,100,40)

static HWND hConWnd;

int BCX_Line (HWND,int,int,int,int,int=0,HDC=0);

HWND GetConsoleWndHandle (void);

void hanoi_towers(int quantity, int from, int to, int buf_peg) //quantity-число колец, from-начальное положение колец(1-3),to-конечное положение колец(1-3)

{ //buf_peg - промежуточный колышек(1-3)

if (quantity != 0)

{

hanoi_towers(quantity-1, from, buf_peg, to);

cout << from << " -> " << to << endl;

hanoi_towers(quantity-1, buf_peg, to, from);

}

}

double krok(double n){

double k=pow(2,n)-1;

cout << "Количество шагов: " << k << endl;

}

int Nachalo(int stolb,int k ){

BCX_Line(hConWnd, 290, 30, 290,120, Blue);

BCX_Line(hConWnd, 370, 30, 370,120, Blue);

BCX_Line(hConWnd, 450, 30, 450,120, Blue);

BCX_Line(hConWnd, 220, 120,510,120, Blue);

//Strelka

BCX_Line(hConWnd, 520, 75, 600,75, Blue);

BCX_Line(hConWnd, 580, 55, 600,75, Blue);

BCX_Line(hConWnd, 580, 95, 600,75, Blue);

int l=114;

int m,n;

if(stolb==1)

{

m=245; n=335;

while(k!=0){

BCX_Line(hConWnd,m,l,n,l,Lime);

m=m+10;

n=n-10;

l=l-7;

k=k-1;

}

}

if(stolb==2)

{

m=325;n=415;

while(k!=0){

BCX_Line(hConWnd,m,l,n,l,Lime);

m=m+10;

n=n-10;

l=l-7;

k=k-1;

}

}

if(stolb==3)

{

m=405;n=495;

while(k!=0){

BCX_Line(hConWnd,m,l,n,l,Lime);

m=m+10;

n=n-10;

l=l-7;

k=k-1;

}

}

}

int Konec(int stolb,int k ){

BCX_Line(hConWnd, 290, 160, 290,250, Blue);

BCX_Line(hConWnd, 370, 160, 370,250, Blue);

BCX_Line(hConWnd, 450, 160, 450,250, Blue);

BCX_Line(hConWnd, 220, 250, 510,250, Blue);

int h=244;

int m,n;

if(stolb==1)

{

m=245;n=335;

while(k!=0){

BCX_Line(hConWnd,m,h,n,h,Lime);

m=m+10;

n=n-10;

h=h-7;

k=k-1;

}

}

if(stolb==2)

{

m=325;n=415;

while(k!=0){

BCX_Line(hConWnd,m,h,n,h,Lime);

m=m+10;

n=n-10;

h=h-7;

k=k-1;

}

}

if(stolb==3)

{

m=405;n=495;

while(k!=0){

BCX_Line(hConWnd,m,h,n,h,Lime);

m=m+10;

n=n-10;

h=h-7;

k=k-1;

}

}

}

int main()

{

int m,l,k,h,r;

double n;

setlocale(LC_ALL,"rus");

int start_peg, destination_peg, buffer_peg, plate_quantity;

cout << "Номер первого столбика(1-3):" << endl;

cin >> start_peg;

if (start_peg>3){

printf("Ви неправильно вказали номер стовпця!\n");

}

cout << "Номер конечного столбика(1-3):" << endl;

cin >> destination_peg;

cout << "Номер промежуточного столбика(1-3):" << endl;

cin >> buffer_peg;

cout << "Количество дисков(1-5):" << endl;

cin >> k;

hanoi_towers(k, start_peg, destination_peg, buffer_peg);

krok(k);

hConWnd = GetConsoleWndHandle();

if (hConWnd)

{

Nachalo(start_peg,k);

Konec(destination_peg,k);

getchar(); // wait

}

return 0;

}

int BCX_Line (HWND Wnd,int x1,int y1,int x2,int y2,int Pen,HDC DrawHDC)

{

int a,b=0;

HPEN hOPen;

// penstyle, width, color

HPEN hNPen = CreatePen(PS_SOLID, 2, Pen);

if (!DrawHDC) DrawHDC = GetDC(Wnd), b = 1;

hOPen = (HPEN)SelectObject(DrawHDC, hNPen);

// starting point of line

MoveToEx(DrawHDC, x1, y1, NULL);

// ending point of line

a = LineTo(DrawHDC, x2, y2);

DeleteObject(SelectObject(DrawHDC, hOPen));

if (b) ReleaseDC(Wnd, DrawHDC);

return a;

}

HWND GetConsoleWndHandle(void)

{

HWND hConWnd;

OSVERSIONINFO os;

char szTempTitle[64], szClassName[128], szOriginalTitle[1024];

os.dwOSVersionInfoSize = sizeof( OSVERSIONINFO );

GetVersionEx( &os );

// may not work on WIN9x

if ( os.dwPlatformId == VER_PLATFORM_WIN32s ) return 0;

GetConsoleTitle( szOriginalTitle, sizeof( szOriginalTitle ) );

sprintf( szTempTitle,"%u - %u", GetTickCount(), GetCurrentProcessId() );

SetConsoleTitle( szTempTitle );

Sleep( 40 );

// handle for NT

hConWnd = FindWindow( NULL, szTempTitle );

SetConsoleTitle( szOriginalTitle );

// may not work on WIN9x

if ( os.dwPlatformId == VER_PLATFORM_WIN32_WINDOWS )

{

hConWnd = GetWindow( hConWnd, GW_CHILD );

if ( hConWnd == NULL ) return 0;

GetClassName( hConWnd, szClassName, sizeof ( szClassName ) );

while ( strcmp( szClassName, "ttyGrab" ) != 0 )

{

hConWnd = GetNextWindow( hConWnd, GW_HWNDNEXT );

if ( hConWnd == NULL ) return 0;

GetClassName( hConWnd, szClassName, sizeof( szClassName ) );

}

}

return hConWnd;

}

6.Тестування програми

Рисунок 1

Рисунок 2

Висновок

В курсовій роботі спроектована і розроблена програма на мові С++, яка, на основі введених даних вирішує задачу, виводячи на екран данні про кожну ітерацію, загальну кількість кроків та графічно реалізує першу та останню їтерації

Список використаної літератури

задача вежа ханойський програма

Шилдт Г. C# Учебный курс. -- СПб.: Питер. 2002.

Лабор В. В. Си шарп: Создание приложений для Windows. -- Минск: Харвест. 2003.

Шилдт Г. Полный справочник по C++. -- М.: Вильямс. 2004.

Размещено на Allbest.ru

...