首页 > 代码库 > 汉诺塔VII

汉诺塔VII

HDU1997  题意:排列汉诺塔需要的最小步数是2^N-1  排列过程中会生成2^N个排列,判断一个序列是否发生了额外的移动步数,也就是完成汉诺塔话费的步数多余2^N-1.

模拟法:

1:在正确的排列中,最大的n盘一定在a或c柱上,否则false

2:如果n在a柱上,剩下n-1个盘处在a->b的过程中

3:如果n在c柱上,剩下n-1个盘处在b->c的过程中

4:重复123直到n=0

可以看出是O(N)的时间复杂度。

技术分享
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn=69;
 5 int x[4][maxn];
 6 int d[4];
 7 void input()
 8 {   
 9     for(int i=1;i<=3;i++)
10     {
11         scanf("%d",&x[i][0]);
12         for(int j=1;j<=x[i][0];j++)
13             scanf("%d",&x[i][j]);
14     }
15     d[1]=d[2]=d[3]=1;
16 }
17 bool cal(int a,int b,int c,int n)
18 {
19     if(n<1)return true;
20     if(n==x[a][d[a]]&&d[a]<=x[a][0]){d[a]++;return cal(a,c,b,n-1);} //use a,b,c don‘t use 123
21     // d[a]<=x[a][0] WTF data stored before maybe influence next process
22          //test {d[a]++;cout<<x[a][d[a]-1]<<" "<<d[a]-1<<endl;return cal(a,c,b,n-1);}
23     if(n==x[c][d[c]]&&d[c]<=x[c][0]){d[c]++;return cal(b,a,c,n-1);}
24     //{d[c]++;cout<<x[c][d[c]-1]<<" "<<d[c]-1<<endl;return cal(b,a,c,n-1);}
25     return false;
26 }
27 
28 int main()
29 {
30     int n,t;
31     cin>>t;
32     while(t--)
33     {
34         scanf("%d",&n);
35         input();
36         bool k=cal(1,2,3,n);
37         if(k) cout<<"true"<<endl;
38         else cout<<"false"<<endl;
39     }
40 
41     return 0;
42 }
View Code

 

汉诺塔VII