首页 > ACM题库 > HDU-杭电 > hdu 2587 很O_O的汉诺塔-递推-[解题报告]C++
2014
02-10

hdu 2587 很O_O的汉诺塔-递推-[解题报告]C++

很O_O的汉诺塔

问题描述 :

O_O汉诺塔包含n种不同大小盘,每种大小m个; 要求每次仅移动一个盘,不允许一个较大的盘放在较小盘上。 并且要求最后排列所有相等大小盘按原来从上到下次序,并且只能按规定的方向搬运,如图(比如A直接搬运到C是不允许的!). 求已知n,m的情况下 从A搬运到C所有盘所用的最少次数。

输入:

每行输入n和m两个整数 0<n<1000,0<m<100;

输出:

每行输入n和m两个整数 0<n<1000,0<m<100;

样例输入:

1 3
2 4

样例输出:

6
28

 看题传送门

吐槽题目 [email protected]@呢。

本来是想过一段时间在来写题解的,不过有人找我要。

本来排名是第8的。然后搞了半天,弄到了第五。不过代码最短~

截止目前就9个ID过,小小的成就感~

PS用G++内存小。。。

Rank Author Exe. Time Exe. Memory Code Len. Language Date
1 4bytes 0MS 204K 1961B C++ 2011-07-30 22:15:19
2 sunhaowen 0MS 212K 895B G++ 2009-05-25 14:17:40
3 ecjtuzhousc存档 0MS 232K 4614B G++ 2011-10-12 11:50:22
4 guoxiang 0MS 244K 893B C++ 2009-05-31 13:18:57
5 hr_whisper 0MS 248K 720B G++ 2013-08-13 10:41:31
6 acm29026 0MS 260K 4614B C++ 2009-05-25 10:24:36
7 hdjt2009 0MS 260K 4614B C++ 2009-05-25 10:39:56
8 topsky 0MS 276K 923B C++ 2009-05-25 15:08:17
9 ACOrz 0MS 372K 1019B G++ 2009-12-30 20:39:05

做这题一定要耐心。

 

先来简单的例子,如果m=1,也就是n种,每种1个。

那就是简单的汉诺塔。但题目要求路径为A->B ,B->C,C->A

可以这样:设n种时答案为a[n],(因为形成一个环,也可以理解为间隔一个移动的步数。)

1、n-1个盘子A移动到C ,a[n-1]

2、第n个从A->B  ,1次。

3、n-2个盘子C->B ,a[n-2]

4、第n-1个盘子C->A ,1

5、n-2个盘子C->A ,a[n-2]

6、第n个从B->C  ,1次。

7、n-1个盘子A移动到C ,a[n-1]

总的为a[n-1] + 1 + a[n-2] + 1 + a[n-2] + 1 + a[n-1]=2 * a[n-1]+ 2* a[n-2]+3

 

题目的要求是最后排列所有相等大小盘按原来从上到下次序,所以若m不为1,答案不是简单的m*a[n](我一开始就是直接。。。。。要不要这样T T)

讨论m>2的情况,等于2呢?别着急等下说。

设答案a[n],  

b[n]为m>2间隔移动的步数,移动后倒数第二类是反的(如A->C,C->B),

c[n]也为间隔移动,但是是最后几个顺序颠倒的移动(在n类是反的和n-1类是反的的情况下)(注意和b[n]区别,一个是移动前一个是后)。

d[n]为m>2相邻移动的步数,移动后倒数第一类是反的(如A->B,B->C,C->A)

 

例子以n=3,m=3的例子,1~3大小相同,为第一类。4~6同,7~9同写在前面的在上面

1、n-1类盘子A移动到C ,b[n-1](是类哦,不是个哦)

A:789

B:

C:321456

2、第n类一个个到B ,m

A:

B:987

C:321456

3、n-1类移动到A , d[n-1]

A: 321654

B:987

C:

4、第n类一个个到C, m

A: 321654

B:

C: 789

5、从A到C,但最后几个是反的,c[n-1]

A:

B:

C: 123456789

得到a[n]= b[n-1]+ d[n-1]+ c[n-1]+2*m;

一个个接着剖析。

 

要实现b[n]怎么弄?以从A->C为例

1、n-1类 A->C , b[n-1]

2、第n类A->B , m

3、n-1类 C->A , d[n-1]

4、第n类B->C , m

5、n-1类 A->C , b[n-1]

所以b[n]= 2*b[n-1]+2*m+d[n-1]

 

d[n]呢以从A->B为例

1、n-1类 A->C , b[n-1]

2、第n类A->B , m

3、n-1类 C->B, b[n-1]

所以d[n]= 2*b[n-1]+ m;

 

但你有木有发现,这样移动到相邻最底下顺序是反的!而用b的移动方法,第n-1类是反的。所以上面才会有c[n]的出现。

 

c[n]的目标很明确,在n是反的和n-1是反的的情况下,移动间隔。从A->C为例

1、n-1类从A->C ,n-2变反了,n-1反 。b[n-1]

2、第n类从A->B,(但是坑爹了,他是正顺,移动到C就会倒序!),m

3、n-1类从C->A  n-1正 ,d[n-1]

4、第n类从B->C, 反  ,m

5、n-1类从A->B   n-1反 ,d[n-1]

6、第n类从C->A, 正  ,m

7、n-1类从B->C   n-1正 ,d[n-1]

8、第n类从A->B, 反  ,m

9、n-1类从C->A   n-1反 ,d[n-1]

10、第n类从B->C, 正  ,m

11  n-1类从A->C   ,c[n-1] (现在n-1和n-2都是反的,往下递归)

 

c[n]= b[n-1]+ m+4*(d[n-1]+m)+c[n-1];

感觉坑爹?嗯没错!但还有更坑的。

m=2怎么办?

这是个特殊的,它的c[n]不符合上述规律,为什么?

假设n=5,m=2,同样编号,2号为一类

 经过和前面一样的步奏(见前面n=3,m=3的例子,n-1类移动回A后第n-1和第n-2类反了)

此时同样以A->C为例子。别忘了C[n]的目的。(n-1、n类都是反的)

你把1~6号移动到C的话,把8号移动到B而7号可以不动!!!

这样等下可以直接8号到C而不用坑爹的像上面一样移动4次!

过程如下

初始

A 12346587

B

C 9 10(对以后无影响,下面不写了,同样,为了方便n=4,下面就直接c[n]而不用c[n-1]了)

1、1~6移动到C  ,b[n-1]

A  87

B

C 124365

2、8号到B  ,1

A  7

B 8

C 124365

3、124365移动到A  ,d[n-1]

A  1243567

B 8

C

4、8号到C  ,1

A  1243567

B

C  8

5、124356到C ,b[n-1]

A  7

B

C  1234568

6、7到B ,  1

A

B 7

C  1234568

7、123456到A ,d[n-1]

A 123465

B 7

C 8

8、7号到C (与开始不同,开始是后面两类倒着的,所以得继续推) ,1

A 123465

B

C 78

9、1~4到C , b[n-2]

A 65

B

C 213478

10、6到B , 1

A 5

B 6

C 213478

11、 2134到A  ,d[n-2]

A 21435

B 6

C 78

12、6到C ,1

A 21435

B

C  678

13、2143到C ,b[n-2]

A 5

B

C  1243678

14、5到B  ,1

A

B  5

C  1243678

15、1243到A ,  d[n-2]

A 1234

B  5

C  678

16、5到C (有木有发现现在1234顺序是正的!!!), 1

A 1234

C  5678

17、1234到C  (直接调用答案) a[n-2]

 

综上:

m=2时,

C[n]=b[n-1] +1
+ d[n-1] +1+b[n-1]+1+d[n-1]+1

+b[n-2]+1+
d[n-2]
+ 1+ b[n-2]+1+d[n-2]+1+a[n-2]

=2* b[n-1]+ 4+ 2* d[n-1]+2* b[n-2] +4+2* d[n-2]+a[n-2]

 

m=1就是一开始分析的了。

坑爹吧?

 OKOK上代码~

#include<cstdio>
const int mod = 20090308;
const int MAXN=1002;
long long  a[MAXN],b[MAXN],c[MAXN],d[MAXN],m;
int n;
int main()
{
    a[0]=b[0]=c[0]=d[0]=0;
    while(scanf("%d%I64d",&n,&m)!=EOF)
    {
        if(m==1)
        {
            a[1]=2;
            for(int i=2;i<=n;i++)
                a[i] =( 2 * a[i-1]+ 2* a[i-2]+3 ) % mod;
        }
        else
        {
            a[1]=b[1]=c[1]=2*m;
            d[1]=m;
            for(int i=2;i<=n;i++)
            {
                d[i]= ( 2*b[i-1]+ m ) % mod;
                b[i]= ( 2*b[i-1]+2*m+d[i-1] ) % mod;
                if(m==2)
                    c[i]=( 2* b[i-1]+ 4+ 2* d[i-1]+2* b[i-2] + 4+2* d[i-2] +a[i-2] ) %mod;
                else
                    c[i]=( b[i-1]+ m+4*(d[i-1]+m)+c[i-1] ) % mod;
                a[i]= ( b[i-1]+ d[i-1]+ c[i-1]+2*m ) % mod;
            }
        }
        printf("%d\n",a[n]);
    }
    return 0;
}

解题转自:http://blog.csdn.net/murmured/article/details/9943947


  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  3. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.