الگوریتم و کد برج های هانوی در ++C

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

مساله ی برج های هانوی (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, سی پلاس پلاس - ++C

سفارش انجام پروژه های برنامه نویسی

کلیک کنید

۱۶ نظر

عاطفه

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++
  …
  
  پاسخ

الگوریتم و کد برج های هانوی در ++C

مطالب آموزنده مشابه:

۱۶ نظر

نظرتان را برای ما بنویسید لغو پاسخ