Skip to content

递归 & 递推

  • 解题重点在于假设出当前的状态以继子问题的状态，通过一步的操作找出状态的转移方式，这样就可以递归/递推了。

P1760 汉诺塔

普通的递归法就是，让前\(n-1\)个盘子移动到空柱子上，将第\(n\)个盘子移动到指定柱子，再将\(n-1\)个盘子移动到第\(n\)盘上。

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long 
using namespace std;
const int N=15510;
int n,ans;
int f(int n,int a,int b,int c){
    if(n==1){
        printf("move %lld from %lld to %lld\n",n,a,c);
        return 1;
    }
    int ans=1;
    ans+=f(n-1,a,c,b);
    printf("move %lld from %lld to %lld\n",n,a,c);
    ans+=f(n-1,b,a,c);
    return ans;
}
signed main(){
    scanf("%lld",&n);
    ans=f(n,1,2,3);
    printf("%lld\n",ans);
    return 0;
}

这样你会发现，\(f(n-1,a,c,b)\)与\(f(n-1,b,a,c)\)所用的步数时一样的，所以有结论： \(x[i]=2* x[i-1]+1\),即\(x[i]=2^i-1\).

~~所以高精度就不展示了~~

P1242

这道题也是同样。

只不过给出了将最终状态，那么我们可以将操作拆成三部分：

1) 将第一个位置改变的最大盘子上面的小盘子挪开到空余的柱子

2) 用一步将大盘子以到指定位置

3) 将小盘子挪到指定位置

由于对称性，第三步可以理解为将小盘子从最终状态挪到空余柱子。

~~然后你就发现，被Hack了~~

正确做法是：第一步有两种：

(假设将大盘子从柱子1挪到柱子2)

1) 小盘子到柱子3\(\to\)大盘子从1到2\(\to\)小盘子到最终状态

2) 小盘子到柱子2\(\to\)大盘子从1到3\(\to\)小盘子到柱子1\(\to\)大盘子从3到2\(\to\)小盘子到最终状态

这就是P1242 第11个点的\(Hack\)原理.

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int N=122,M=5e6+10;
int start[N],finish[N],mid[N];
int n,cnt,m;
struct node {
    int n,a,b;
} step1[M],step2[M];
void g(int n,int a,int b,int c,node *step) {
    if(n==0)return;
    g(n-1,a,c,b,step);
    step[++cnt].n=n,step[cnt].a=a,step[cnt].b=c;
    g(n-1,b,a,c,step);
    return;
}
int f(int* P,int i,int final,node *step) {
    if(i==0)return 0;
    if(P[i]==final)return f(P,i-1,final,step);
    int tmp=f(P,i-1,6-P[i]-final,step);
    step[++cnt].n=i,step[cnt].a=P[i],step[cnt].b=final;
    g(i-1,6-P[i]-final,P[i],final,step);
    return tmp+(1ll<<(i-1));
}
void print1(int cnt,int ans,int a,int b,node *step) {
    for(int i=a+1; i<=cnt; ++i) {
        swap(step[i].a,step[i].b);
    }
    for(int i=1; i<=b/2; ++i) {
        swap(step[i+a+1-1],step[cnt-i+1]);
    }
    for(int i=1; i<=ans; ++i) {
        printf("move %d from %c to %c\n",step[i].n,step[i].a+'A'-1,step[i].b+'A'-1);
    }
    printf("%lld",ans);
}
signed main() {
    scanf("%lld",&n);
    for(int i=1; i<=3; ++i) {
        scanf("%lld",&m);
        for(int k=1,p; k<=m; ++k)scanf("%lld",&p),start[p]=i;
    }
    for(int i=1; i<=3; ++i) {
        scanf("%lld",&m);
        for(int k=1,p; k<=m; ++k)scanf("%lld",&p),finish[p]=i;
    }
    while(start[n]==finish[n] && n>=1)--n;
    int ans=0,tmp1=0,tmp2=0,tmp3=0,tmp4=0;
    if(n>=1) {
        cnt=0;
        tmp1=f(start,n-1,6-start[n]-finish[n],step1)+1;
        step1[++cnt].n=n,step1[cnt].a=start[n],step1[cnt].b=finish[n];
        tmp2=f(finish,n-1,6-start[n]-finish[n],step1);
        cnt=0;
        tmp3+=f(start,n-1,finish[n],step2)+1;
        step2[++cnt].n=n,step2[cnt].a=start[n],step2[cnt].b=6-start[n]-finish[n];
        for(int i=1;i<n;++i)mid[i]=finish[n];
        mid[n]=6-start[n]-finish[n];
        tmp3+=f(mid,n-1,start[n],step2)+1;
        step2[++cnt].n=n,step2[cnt].a=6-start[n]-finish[n],step2[cnt].b=finish[n];
        tmp4=f(finish,n-1,start[n],step2);

        if(tmp1+tmp2<tmp3+tmp4) {
            ans=tmp1+tmp2;
            print1(ans,ans,tmp1,tmp2,step1);
        } else {
            ans=tmp3+tmp4;
            print1(ans,ans,tmp3,tmp4,step2);
        }
    }
    return 0;
}

P