数据结构--汉诺塔问题

清疚 2023-07-03 14:29 122阅读 0赞

# 数据结构–汉诺塔问题 #

我列举了两种解法—递归和非递归

1、这是递归解法
    
    #include<iostream>
    using namespace std;
    int j = 1;
    void move(char a, char c)
    {
        
    	cout << j++ << " " << a << "--->" << c << endl;
    }
    void Hanio(int n,char a,char b,char c)
    {
        
    	if (n == 1)
    	{
        
    		move(a, c);
    		return;
    	}
    	Hanio(n - 1, a, c,b);
    	move(a, c);
    	Hanio(n - 1, b, a,c);
    }
    int main()
    {
        
    	int n;
    	cin >> n;
    	cin.get();
    	Hanio(n, 'a', 'b', 'c');
    	cin.get();
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk_size_16_color_FFFFFF_t_70]

2、非递归解法，使用堆栈
    
    #include<iostream>
    using namespace std;
     
    const int Maxsize = 100;
    typedef struct {
               //建立一个汉诺塔模型，n是盘个数，ABC是三个柱子
    	int N;
    	char A;
    	char B;
    	char C;
    }Mode;
     
    typedef struct {
        		//建立一个堆栈
    	Mode Data[Maxsize];
    	int Top;
    }Stack;
     
    Mode ERROR;
    void Push(Stack * Ptr, Mode item)		//压进堆栈
    {
        
    	if (Ptr->Top == Maxsize - 1)return;
    	else
    	{
        
    		Ptr->Data[++(Ptr->Top)] = item;
    		return;
    	}
    }
    Mode Pop(Stack * Ptr)				//弹出堆栈
    {
        
    	if (Ptr->Top == -1)return ERROR;
    	else
    	{
        
    		Ptr->Top--;
    		return Ptr->Data[Ptr->Top + 1];
     
    	}
    }
    void Hanio(int n)				//求汉诺塔解决子程序
    {
        
    	Mode P, toPush;
    	Stack S;
     
    	P.N = n;				//建立一个汉诺塔型 的结构体，n是盘数
    	P.A = 'a';
    	P.B = 'b';
    	P.C = 'c';
    	S.Top = -1;
     
    	Push(&S, P);			//（n,a,b,c）可以分解为三个问题（n-1,a,b,c）（2,a,b,c）（n-1,b,a,c）,然后反着压进堆栈
    	while (S.Top != -1)		//看栈是不是空的
    	{
        
    		P = Pop(&S);		
    		if (P.N == 1)	
    			cout << P.A << "--->" << P.C;
    		else
    		{
        
    			toPush.N = P.N - 1;
    			toPush.A = P.B;
    			toPush.B = P.A;
    			toPush.C = P.C;
    			Push(&S, toPush);
     
    			toPush.N = 1;
    			toPush.A = P.A;
    			toPush.B = P.B;
    			toPush.C = P.C;
    			Push(&S, toPush);
     
    			toPush.N = P.N - 1;
    			toPush.A = P.A;
    			toPush.B = P.C;
    			toPush.C = P.B;
    			Push(&S, toPush);
    		}
    	}
    }
     
    int main()
    {
        
    	/*int n;
    	cin >> n;*/
    	
    	Hanio(3);
    	
    	cin.get();
    	return 0;
    }

3、这是百度上的一个问题答案
    
    #include <fstream> 
    #include <iostream> 
    using namespace std; 
    ofstream fout("out.txt"); 
    void Move(int n,char x,char y) 
    {
         
    fout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl; 
    } 
    
    void Hannoi(int n,char a,char b,char c) 
    {
         
    if(n==1) 
    Move(1,a,c); 
    else 
    {
         
    Hannoi(n-1,a,c,b); 
    Move(n,a,c); 
    Hannoi(n-1,b,a,c); 
    } 
    } 
    int main() 
    {
         
    fout<<"以下是7层汉诺塔的解法:"<<endl; 
    Hannoi(7,'a','b','c'); //调用 
    fout.close(); 
    cout<<"输出完毕!"<<endl; 
    return 0;

## 【说明】 ##

汉诺塔使用递归的方法来实现的  
可能你对递归还没理解透，反正记住，程序总是一步一步的按顺序执行，有调用函数就先在调用的地方设个断点，转入函数执行，执行完了又返回断点，万变不离其宗!

程序执行的顺序  
Hannoi(7,‘a’,‘b’,‘c’);这里调用函数，转入函数执行并传入参数n=7

第一步，执行判断语句，根据n的值进入else执行  
第二步，执行Hannoi(n-1,a,c,b);这时是调用函数本身，也就是所谓的递归了，你看传入的值n-1，相当于传入n=6，还有a,c,b,的值，这个要注意顺序，在调用的时候a,c,b的值是第一次传入的值  
第三步，执行Hannoi(int n,char a,char b,char c)函数，这点能理解吧，这次传入的值n=6了，但是a,b,c,的值相对于第一次的值有改变了哦，可以理解成，a(2)=a(1),b(2)=c(1),c(2)=b(1),这里括号里代表函数调用的次数，其实这里最容易弄混的就是，a,b,c的值，自己用本子把每次传入的值的a,b,c按传入顺序列出来，会容易理解些  
同样，执行判断，n>1进入else,按顺序执行，先执行Hannoi(n-1,a,c,b);然后又是调用本身，注意传入的值，是a(2),c(2),b(2),又转入去执行Hannoi(int n,char a,char b,char c)函数,这时接收的值a(3)=a(2),b(3)=c(2),c(3)=b(2)，就像在兜圈子是吧，没错。后面你自己做张表来理一下。  
这样兜圈子直到n=1。你看Hannoi(n-1,a,c,b);每次n都是减了1的，所以n-1次递归的时候，就直接执行if(n==1)里面的了，终于有所改变了是吧，他执行的是Move(1,a,c); 也就是输出函数，执行完Move(int n,char x,char y) 返回原来的调用的那个断点。继续向后。没有语句了，就返回上次调用的函数，上次调用Hannoi(int n,char a,char b,char c)是谁呢，就是n-2次的Hannoi(int n,char a,char b,char c)中的Hannoi(n-1,a,c,b);调用的他啊，返回到这里，继续向后又遇到Move(n,a,c); 这里不用讲解了吧，输出后返回来，继续向后执行Hannoi(n-1,b,a,c); 新的递归开始了，看你再列个新的表理一下呢，注意传入的值和他的顺序，还有n的值这时是多少。

其实我的讲解你可能看的也不是很清楚，关键是要理解到递归他无非就是调用自己，调用完返回就是返回上次调用的地方，也是他自己，只是俩次的函数使用中的值是不一样的，这个值呢，最好拿笔记下来，并写个次数才容易理解和分析。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200207120135677.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk=,size_16,color_FFFFFF,t_70