递归的关系算法--汉诺塔分析

Aslcwd

首先汉诺塔是研究递归关系的，也就是f(x)与f(x-1)，只研究x阶函数与比其小1个阶的函数关系。
为了计算有终止条件，需要研究一个初值，一般使用0阶或者1阶，事实上并不影响
小甲鱼老师在带你学C带你飞，递归讲到一个实现程序
定义汉诺塔函数，hanoi(n,x,y,z)

hanoi( 1号,2号,3号,4号 )
1号空填写，汉诺塔的堆数，堆数定义为，最小的片在顶部，依次增大塔片，保持连续状态的片数n，称n层
2号位填写，汉诺塔的起始柱子
3号位填写，汉诺塔的媒介柱子
4号位填写，汉诺塔的目标柱子

设置三根柱子X，Y，Z

例1.把3层的汉诺塔，从Y移动到X
就应该把3填入1号位，表示数量，Y填到2号位表示起始，X填到4号位置表示目标，Z填到3号位表示媒介
hanoi(3,Y,Z,X)

例2.把7层的汉诺塔，从Z移动到Y
hanoi(7,Z,X,Y)

接下来拆分，把5层汉诺塔从X移到Z
法一，hanoi(5,X,Y,Z)
法二，将5层，看成4层加一片
步骤1：将4层汉诺塔X移动到Y  >>        写成函数hanoi(4,X,Z,Y)
步骤2：将X一片移动到Z                >>  无法写成函数 打印出来X移动到Z
步骤3：将4层汉诺塔Y移动到Z  >>  写成函数hanoi(4,Y,X,Z)
法二的步骤1，3都能用低1阶函数写出来，只有步骤2需要显示打印出来

总结：
hanoi(n,X,Y,Z) 等价于 hanoi(n-1,X,Z,Y) 然后X到Z 再hanoi(n-1,Y,X,Z)

定终止条件
hanoi(1,X,Y,Z) 就是直接打印 X到Z
拆分一下试试，hanoi(0,X,Z,Y) 然后X到Z 再hanoi(0,Y,X,Z)
hanoi(0,X,Y,Z) 就是什么也没有是空的
因此结束条件就是n==0时，给一个空操作

#include <stdio.h>

char *zhu(char);                        //        这里是字符串的指针字符函数，输入字符串，函数运算，返回字符串的指针
char *zhu(char a)
{
        switch(a)
        {
                case 'x':return "第一根柱子";
                case 'y':return "第二根柱子";
                case 'z':return "第三根柱子";
        }
}

void hanoi(int,char,char,char);
void hanoi(int n,char x,char y,char z)
{
        if(n==0)                                                //        汉诺塔0层，空操作，啥也没有
        {
        }
        else                                                        //        否则就拆分
        {
                hanoi(n-1,x,z,y);
                printf("%s  移到  %s\n",zhu(x),zhu(z));
                hanoi(n-1,y,x,z);
        }
}


int main()
{
        int num;
        printf("请输入汉诺塔层数：");
        scanf("%d",&num);
       
        hanoi(num,'x','y','z');
       
        return 0;
}

zjhahaha

感谢楼主，终于把此类问题搞清楚了。至少有头绪了。

zjhahaha

def hannuo(n, s,m,d):
    global count
    if n==1:
        print(n,s,"-->",d)
        count+=1
    elf n>1:
        hannuo(n-1,s,d,m)
        print(n,s,"-->",d)
        count+=1
        hannuo(n-1,m,ds)
count=0
han=hannuo(3,'a','b','c')


1 a --> b
2 a --> c
1 b --> c
3 a --> b
1 c --> a
2 c --> b
1 a --> b
4 a --> c
1 b --> c
2 b --> a
1 c --> a
3 b --> c
1 a --> b
2 a --> c
1 b --> c
15

Aslcwd

zjhahaha 发表于 2019-6-28 09:17
感谢楼主，终于把此类问题搞清楚了。至少有头绪了。