题解 | #Bits#_牛客博客

题目描述

Nancy喜欢做游戏！汉诺塔是一个神奇的游戏，神奇在哪里呢？给出3根柱子，最开始时n个盘子按照大小被置于最左的柱子。如果盘子数为偶数，则需要将她们全部移动到最右侧的柱子上，否则将她们移动到中间的柱子上。那么，Nancy该怎样移动呢？请你输出汉诺塔游戏的过程叭！

输入描述：

共一行：一个整数n，表示最开始n个盘子（编号为1到n）的放置方法。
数据满足：2≤n≤11。

输出描述：

共 $2^n$ 组：每组n+2行，每行3×(2n+1)+4个字符，用.表示空白区域，用|表示柱子区域，用*表示盘子。组与组之间请输出3×(2n+1)+4个-。具体输出方式请参看样例进行理解。

示例

输入

2

输出

...................
...|.....|.....|...
..***....|.....|...
.*****...|.....|...
-------------------
...................
...|.....|.....|...
...|.....|.....|...
.*****..***....|...
-------------------
...................
...|.....|.....|...
...|.....|.....|...
...|....***..*****.
-------------------
...................
...|.....|.....|...
...|.....|....***..
...|.....|...*****.

思路

小故事：大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。

一、递归思路

char s[14][74];//图案
int h[3]/*记录每根柱子的圆盘数*/,N;//圆盘总数
void create(int sn,int d){for(int i=-d,c=(N+1)*(sn*2+1);i<=d;++i)s[h[sn]][c+i]='*';++h[sn];}//放置圆盘
int delete(int sn)//移走圆盘
{
    --h[sn];
    int c=(N+1)*(sn*2+1),d=1;
    while(s[h[sn]][c+d+1]=='*')++d;
    for(int j=-d;j<=d;++j)s[h[sn]][c+j]=j?'.':'|';
    return d;
}
void move(int F,int V,int T,int n)
{
    if(n==1)
    {
        create(T,delete(F));
        for(int i=N+2;i>=0;--i)puts(s[i]);
    }
    else move(F,T,V,n-1),move(F,V,T,1),move(V,F,T,n-1);
}
main()
{
    scanf("%d",&N);
    for(int i=N+1;i>=0;--i)for(int j=6*N+6;j>=0;--j)s[i][j]='.';
    for(int j=6*N+6;j>=0;--j)s[N+2][j]='-';
    for(int i=N;i>=0;--i)for(int j=5*N+5;j>=N+1;j-=2*N+2)s[i][j]='|';
    for(int i=0;i<N;++i)create(0,N-i);//在第一根柱子按从大到小的顺序放置圆盘
    for(int i=N+1;i>=0;--i)puts(s[i]); 
    move(0,1+N%2,2-N%2,N);
}

二、用栈实现递归行为

将move(0,1+N%2,2-N%2,N);替换为以下代码即可。

    int d=0;struct{char F,V,T;int n;}F[2*N-1];
    F[d].F=0,F[d].V=1+N%2,F[d].T=2-N%2,F[d++].n=N;
    while(d)
    {
        int f=F[--d].F,v=F[d].V,t=F[d].T,n=F[d].n;
        if(n==1)
        {
            create(t,delete(f));
            for(int i=N+2;i>=0;--i)puts(s[i]);
        }
        else
        F[d].F=v,F[d].V=f,F[d].T=t,F[d++].n=n-1,//与函数调用顺序相反
        F[d].F=f,F[d].V=v,F[d].T=t,F[d++].n=1,
        F[d].F=f,F[d].V=t,F[d].T=v,F[d++].n=n-1;
    }

三、手工模拟栈帧实现函数递归

函数调用栈由许多个栈帧组成，每个栈帧都有一个pc；
函数调用即在栈帧的顶部加上一个栈帧，将栈帧的pc初始化为0，并传入参数；函数的返回就是把顶部的栈帧抹掉。
执行一条语句，即取top_most的栈帧上的pc所指的语句执行。
实现如下：

#define call(...)({*++top=(Frame){0,__VA_ARGS__};})
#define ret()({top--;})
#define goto(loc)({f->pc=(loc)-1;})
#define create(sn,d)do{for(int j=-(d),c=(N+1)*((sn)*2+1);j<=(d);++j)s[h[(sn)]][c+j]='*';++h[(sn)];}while(0)
#define delete(sn)({\
--h[(sn)];\
int c=(N+1)*((sn)*2+1),d=1;\
while(s[h[(sn)]][c+d+1]=='*')++d;\
for(int j=-d;j<=d;++j)s[h[(sn)]][c+j]=j?'.':'|';\
d;})
int main()
{
    int h[3]={},N;
    scanf("%d",&N);
    char s[N+3][6*N+8];
    for(int i=N+2;i>=0;--i)s[i][6*N+7]=0;
    for(int i=N+1;i>=0;--i)for(int j=6*N+6;j>=0;--j)s[i][j]='.';
    for(int j=6*N+6;j>=0;--j)s[N+2][j]='-';
    for(int i=N;i>=0;--i)for(int j=5*N+5;j>=N+1;j-=2*N+2)s[i][j]='|';
    for(int i=N;i>0;++i)create(0,i);
    for(int i=N+1;i>=0;--i)puts(s[i]);
    typedef struct{int pc,n;char from,via,to;}Frame;
    Frame stk[2*N-1],*top=stk-1;
    call(N,0,1+N%2,2-N%2);
    for(Frame*f;(f=top)>=stk;f->pc++)
    {
        int n=f->n,from=f->from,via=f->via,to=f->to;
        switch(f->pc)
        {
            case 0:if(n==1){int d=delete(from);create(to,d);for(int i=N+2;i>=0;--i)puts(s[i]);goto(4);}break;//这里不能直接写成create(to,delete(from)),原因是宏函数展开导致递减运算符重复计算。
            case 1:call(n-1,from,to,via);break;
            case 2:call(1,from,via,to);break;
            case 3:call(n-1,via,from,to);break;
            case 4:ret();break;
            default:return -1;
        }
    }
    return 0;
}

题外

如何写出以下代码的非递归形式

int f(int n)
{
    if(n<=1)return 1;
    return f(n-1)+g(n-2);
}
int g(int n)
{
    if(n<=1)return 1;
    return f(n+1)+g(n-1);
}