n阶Hanoi塔问题 - 算法设计与分析实验1

Myth丶恋晨 2022-06-04 10:00 125阅读 0赞

由于实验指导书上没有给出具体的问题描述，这里把ACM的算法描述列了出来:

问题: 假设有三个分别命名为X、Y和Z的塔座，在塔座X上插有n个直径大小各不相同、依小到大编号为1,2,…,n的圆盘。现要求将X轴上的n个圆盘移至塔座Z上并仍按同样顺序叠排，圆盘移动时必须遵循下列规则：  
1）每次只能移动一个圆盘；  
2）圆盘可以插在X、Y和Z中的任一塔座上；  
3）任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。  
如何实现移动圆盘的操作呢？当n=1时，问题比较简单，只要将编号为1的圆盘从塔座X直接移至塔座Z上即可；当n>1时，需利用塔座Y作辅助塔座，若能设法将压在编号为n的圆盘之上的n-1个圆盘从塔座X（依照上述法则）移至塔座Y上，则可先将编号为n的圆盘从塔座X移至塔座Z上，然后再将塔座Y上的n-1个圆盘（依照上述法则）移至塔座Z上。而如何将n-1个圆盘从一个塔座移至另一个塔座的问题是一个和原问题具有相同特征属性的问题，只是问题的规模小1，因此可以用同样的方法求解。由此可得如下图算法所示的求解n阶Hanoi塔问题的C函数。  
![这里写图片描述][SouthEast]

算法实现:

#include <stdio.h> 
    int c=0;  
    void move(char x,int n,char z){  
        printf("%d. Move disk %d from %c to %c \n",++c,n,x,z);  
    }  
    void hanoi(int n,char x,char y,char z){  
        if(n==1)  
            move(x,1,z);//将编号1的圆盘从x移到z  
        else{  
            hanoi(n-1,x,z,y);//将x上编号1--n-1的圆盘移到y,z做辅助  
            move(x,n,z);//将编号为n的圆盘从x移到z  
            hanoi(n-1,y,x,z);//将y上编号为1--n-1的圆盘移到z，x做辅助  
        }  
    }  
    int main(){  
        int n;
        printf("请输入你汉诺塔的阶数:") ;
        scanf("%d",&n);
        hanoi(n,'x','y','z');  
        return 0;
    }

运行结果:  
![这里写图片描述][SouthEast 1]

3阶是7步，  
然后以此类推  
f(4)=f(3)+1+f(3)=15  
f(5)=f(4)+1+f(4)=31  
f(6)=f(5)+1+f(5)=63  
f(7)=f(6)+1+f(6)=127  
f(8)=f(7)+1+f(7)=255  
f(9)=f(8)+1+f(8)=511  
这样就完成了这个算法。

[SouthEast]: /images/20220604/86ca3b3eb6834e35898ec4ee515e155d.png
[SouthEast 1]: /images/20220604/1b53362a38e04379875fde3af66390e1.png