حل برج های هانوی ، آموزش الگوریتم و کد

تاریخ نگارش مطلب: 2014/07/22 نویسنده: فرهاد دلیرانی

در این مطلب آموزشی ما به تعریف مسئله برج های هانوی و الگوریتم و کد حل آن می پردازیم.

فهرست مطالب

1 مسئله برج های هانوی
- 1.1 تعریف مسئله
  - 1.1.1 قوانین
2 پیاده سازی کد مسئله برج های هانوی
- 2.1 زبان سی پلاس پلاس

مسئله برج های هانوی

مساله ی برج های هانوی (towers of Hanoi) از مساله های معروف در زمینه الگوریتم های بازگشتی است که در آن تعدادی دیسک را باید از میله ای به میله ی دیگر منتقل کرد.

تعریف مسئله

شرایط اولیه: ۳ میله که یکی از آنها حاوی تعدادی دیسک است که از پایین به بالا از بزرگ به کوچک قرار گرفته اند.

مسآله: همه ی دیسک ها را باید به یک میله ی خالی منتقل کنید.

قوانین

۱-هنگام حرکت دادن دیسکها هیچ دیسکی روی دیسک کوچکتر از خود قرار نگیرد.

۲-درهر بار حرکت دادن دیسک ها نمیتوان بیش از یک دیسک را منتقل کرد.

حل: فرض کنیم n دیسک داریم و میله ها را origin , middle , destination مینامیم که ابتدا دیسکها در origin قرار دارند وباید به destination منتقل شوند. فرض کنیم (H(n تابعی باشد که این کار را انجام میدهد n دیسک را به روش زیر منتقل میکنیم:

۱-با(H(n-1 ابتدا n-1 دیسک بالایی از میله ی origin را به middle منتقل میکنیم.

۲-آخرین دیسک موجود در origin را به destination منتقل میکنیم.

۳-با(H(n-1 درآخر n-1 دیسک موجود در میله ی origin را به destination منتقل میکنیم.

پس داریم:(H(n)=H(n-1)+1+H(n-1 یعنی H(n)=2H(n-1)+1

پیاده سازی کد مسئله برج های هانوی

زبان سی پلاس پلاس

کد این مساله به زبان سی پلاس پلاس( ++C):

#include "stdafx.h"
#include <iostream>
using namespace std;
void hanoi(int disk, int or, int des)
{ 
//or=origion, des=destination
int mid=6-(or+des);
if(disk==1)
{
cout<<or<<"->"<<des<<endl;
}
else
{
hanoi(disk-1, or, mid);
cout<<or<<"->"<<des<<endl;
hanoi(disk-1,mid , des);
}
}
int main(void)
{
int dno,or,des; //number of disks, origion, destination
cout<<"\tHanoi towers, tower 1, tower 2, tower 3 (inputs are numbers 1,2 and 3): "<<endl<<endl;
//avoiding possible mistakes while entering inputs by using do-while loops
do
{
cout<<"Enter the number of disks: ";
cin>>dno;
}
while(dno<1);
do{
cout<<"Enter the origion: ";
cin>>or;
}
while(or>3 || or<1);
do
{
cout<<"Enter the destination: ";
cin>>des;
}
while(des>3 || des<1 || des==or);
hanoi(dno,or,des);
cin.get();
return 0;
}

#include "stdafx.h"

#include <iostream>

using namespace std;

void hanoi(int disk, int or, int des)

{

//or=origion, des=destination

int mid=6-(or+des);

if(disk==1)

{

cout<<or<<"->"<<des<<endl;

}

else

{

hanoi(disk-1, or, mid);

cout<<or<<"->"<<des<<endl;

hanoi(disk-1,mid , des);

}

int main(void)

{

int dno,or,des; //number of disks, origion, destination

cout<<"\tHanoi towers, tower 1, tower 2, tower 3 (inputs are numbers 1,2 and 3): "<<endl<<endl;

//avoiding possible mistakes while entering inputs by using do-while loops

{

cout<<"Enter the number of disks: ";

cin>>dno;

}

while(dno<1);

do{

cout<<"Enter the origion: ";

cin>>or;

}

while(or>3 || or<1);

{

cout<<"Enter the destination: ";

cin>>des;

}

while(des>3 || des<1 || des==or);

hanoi(dno,or,des);

cin.get();

return 0;

}

جالب است بدانیم که جواب تابع بازگشتی در این مساله برابر است با: hanoi(n)=(2^n)-1 یعنی تابع به اندازه ی hanoi(n)=(2^n)-1 فراخوانی میشود, پس با انجام

همین تعداد حرکت دیسکها از origin به destination منتقل میشوند.

۱۶

تقسیم و حل - Divide and conquer

۱۶ نظر

عاطفه
2016/03/14 در 17:40
با Dew اجرا میشه خط اول پاک کنید به جای متغییر or هرجا داشتید مثلا ori بذارید درست میشه
پاسخ
سارا
2016/03/01 در 21:58
خواهش میکنم بیشتر راجع به درس برنامه نویسی پیشرفته سوال و حل تمرین بذارید..من با برنامه نویسی مشکل دارم شدید..ممنون
پاسخ
parva
2016/01/13 در 08:57
ایا کسی open gl کار کرده و طراحی اسم با اسپیلاین (توابع بیزیه) رو بلده؟؟؟
پاسخ

مریم

2015/11/28 در 19:41

کد مشابه و ساده تر!!!

#include 
using namespace std;
void Hanoi(int n, char from, char to, char help) {
if (n > 0) {
Hanoi(n - 1, from, help, to);
cout << "Move from " << from << " to " << to <> Ndisks;
Hanoi(Ndisks, '1', '2', '3');
return 0;
}

#include

using namespace std;

void Hanoi(int n, char from, char to, char help) {

if (n > 0) {

Hanoi(n - 1, from, help, to);

cout << "Move from " << from << " to " << to <> Ndisks;

Hanoi(Ndisks, '1', '2', '3');

return 0;

}

پاسخ

تسلا
2015/06/18 در 23:24
از چه برنامه ای برای اجراش استفاده کنیم؟
با تشکر
پاسخ
- فرهاد دلیرانی
  2015/06/25 در 09:00
  ویژوال استادیو مایکروسافت
  پاسخ
- M.B.N.A
  2015/10/06 در 23:20
  باکدبلاک هم میشه برنامه سی پلاس پلاس نوشت واجراکرد
  پاسخ
  - رشاد شکری
    2015/10/07 در 11:26
    بله میشه تو codeblocks برنامه سی پلاس پلاس رو نوشت و اجرا کرد.
    به این لینک مراجعه کنید:
    http://wiki.codeblocks.org/index.php/Creating_a_new_project
    پاسخ
فرهاد دلیرانی
2015/04/01 در 15:57
دقیقا کدوم خط خطا می ده ؟ کد اون خط بذار و متن خطا رو هم همین طور.
پاسخ
m
2015/04/01 در 13:13
سلام…
چرا استفاده نکنم ؟
ببخشید اینا میپرسم ولی سینتکس چیه؟میشه یه توضیح بدید…
شرمنده
پاسخ
- فرهاد دلیرانی
  2015/04/01 در 15:57
  اون تعریف خط اول برای ویژوال استادیو است.
  پاسخ
- محمد جمالی
  2015/04/01 در 18:29
  از استاندارد های بروز تر استفاده کنید
  سینتکس : نحوه نوشتن کد در زبان های مختلف
  پاسخ
m
2015/03/31 در 11:30
سلام خسته نباشید
آقای دلیرانی ببخشید کد برج هانوی به زبن سی شارپ یا سی پلاس پلاس؟
من میخوام اجراش را در dev c++بگیرم ولی اجرا نمیده در خط اول و خط چهارم خطا میده…
اگه بخوام به زبان سی شارپ بنویسم چیکار باید کنم؟
ممنون اگه کمکم کنید…
پاسخ
- محمد جمالی
  2015/03/31 در 20:50
  اکیدا توصیه میکنم از dev استفاده نکنید
  اما برای کامپایل خط اول را حذف کنید
  برای c# کافیست سینتکس آن را عوض کنید
  پاسخ
m
2015/03/17 در 13:08
سلام خسته نباشید اگه بخواهیم برج هانوی را بصورت گرافیکی بنویسیم باید چیکار کنیم با c#؟؟؟؟؟؟؟؟؟؟؟؟؟
میشه کمکم کنید
۱دنیا ممنون
پاسخ
- محمد جمالی
  2015/03/26 در 12:04
  سلام
  ابزار های زیادی موجود هستند !
  C#
  QT
  OpenGl
  microsoft visual c++
  …
  پاسخ