Hanoi塔问题 （C语言代码）

汉诺塔移动次数问题：有n个盘子的塔借助另一个塔移动到第三个塔的次数为2^n-1;因为递推关系式为

move(n)=2move(n-1)+1; move(0)=0

故此题代码为

#include <stdio.h>
int res[80];

void calc(int n){
    //2^(n+1)
    int i,j;
    for(i=1;i<=n+1;i++)
    {
        for(j=0;j<80;j++)
            res[j]*=2;

        for(j=0;j<80;j++)
            if(res[j]>=10)
            {
                res[j+1]+=(res[j]/10);
                res[j]%=10;
            }
    }
    //2^(n+1)-2
    for(i=0;i<80;i++)
    {
        res[i]-=2;
        if(res[i]>=0) break;
        else res[i]=10+res[i];
    }

}

int main()
{
    int n,i;
    res[0]=1;
    scanf("%d",&n);
    //计算
    calc(n);
    //输出
    i=80-1;
    while(res[i]==0) i--;
    for(;i>=0;i--) printf("%d",res[i]);
    
    return 0;
}

汉诺塔递归求解
参考代码:

#include <stdio.h>
static int cnt=1;
void Hanoi(int n,int x,int y,int z)
{
    if(n>0)
    {
        Hanoi(n-1,x,z,y);
        printf("step %d:Move top disk from tower %d to top of tower %d\n",cnt++,x,y);
        Hanoi(n-1,z,y,x);
    }
}

int main()
{
    int n;
    scanf("%d",&n);

    Hanoi(n,1,2,3);
    return 0;
}

汉诺双塔递归求解

#include <stdio.h>

static int cnt=1;

void Hanoi(int n,int x,int y,int z)

{

    if(n>0)

    {

        Hanoi(n-1,x,z,y);

        printf("step %d:Move top disk from tower %d to top of tower %d\n",cnt++,x,y);

        Hanoi(n-1,z,y,x);

    }

}

int main()

{

    int n;

    scanf("%d",&n);

    Hanoi(n,1,2,3);

    printf("%d",(cnt-1)*2);

    return 0;

}