posts - 2,comments - 0,trackbacks - 0

  最近看C算法,在讲到分治的时候,果然又看到了分治必讲的汉诺塔问题,不过书里同时又讲到了汉诺塔与二进制的关系,我觉得很有意思。

  汉诺塔(Hanoi)问题想必大家都很熟悉,玩过这个游戏的也不在少数,N个盘的汉诺塔最少能用2N-1次移动完成,用递归的方法,很容易写出一个求最优移动方法的程序:

1 void Hanoi(int N, int A, int B, int C)
2 {
3     if (N == 0) return;
4     Hanoi(N – 1, A, C, B);
5     printf(“%d-->%d\n”, A, C);
6     Hanoi(N – 1, B, A, C);
7 }

  下面我们要研究的是每次移动的规律。可以看到,这个程序的递归调用是对称的,每次递归中有两个递归调用,且每次调用求解问题的规模是一样的,下面我们以N=3为例画出这个递归调用的递归树如下:

  最右边一列方框就是程序的输出,如果我们按照圆盘的大小给圆盘加上编号,如最小的盘为1号,最大的盘为N号,那么最右面的那一列数字就是每次移动的圆盘,从上至下就是移动的顺序。在这个例子中就是先将1号盘从A柱移动到C柱,再把2号盘从A柱移动到B柱……

  观察这个序列1,2,1,3,1,2,1,可以发现1每隔一个数字就出现一次,那其它的数字呢,有什么规律?

  为了搞清这个问题,我们先看另一个问题,假设有一把可以折起来的尺子,我们想将他分成2N等分,怎么分呢?2等分自然是对折,4等分就是再对折,那么2N等分自然就是对折N次,在折痕处画一条线,尺子就被2N等分了。

  我们换一种方式,首先在尺子的1/2处画一条长为N的线,把尺子分为左边和右边,再分别在左边的1/2和右边的1/2处各画一条长为N-1的线,如此进行下去,每隔尺子的1/2i长度就画一条长为N-i+1的线,那么最后,每隔尺子的1/2N长度画一条长为1的线,画出来的结果如下图所示(N=5):

  这个问题同样可以使用递归来解决:

 1 void Draw(int N, int l, int r)
 2 {
 3     int m = (l + r) / 2;
 4     if (N > 0)
 5     {
 6         Draw(N – 1, l, m);
 7         printf(“%d\n”, N);
 8         Draw(N – 1, m, r);
 9     }
10 }

  注意到,这个递归调用也是对称的,而且每次递归的规模都与汉诺塔相同,那么他的递归调用是否跟汉诺塔一样呢?同样以N=3为例画出递归树:

  我们发现,他们的递归树确实是一样的,连右边的序列都是一样的。这是因为他们的递归结构相同,每次递归的规摸也是一样,因此这两个问题的本质是一样的。尺子上的刻度的长度序列就是汉诺塔移动圆盘的序列!

  那么这个序列到底有什么规律呢?尺子每次都是对折,也就是长度除以2,是否和2进制有关?以上面我们画出的那个N=3的尺子为例,我们把从1开始的二进制数写出来,看看有没有对应关系:       

        0001

        0010                   1

        0011

        0100                   2

        0101

        0110                   1

        0111

        1000                   3

        1001

        1010                  1

        1011

        1100                  2

        1101

        1110                  1

        1111

  

  发现了吗?这个序列的第i个数就等于2*i这个数的二进制末尾0的个数!

  如果还不太确定,可以把这个序列继续写下去,你会发现确实是这样的,而且这个序列中,1每隔1个数字就出现一次。想想我们在玩汉诺塔的时候,每一步其实只有两种选择:一是把最小的那个盘(因为他总在最上面)移动到别的杆上,二就是把某个杆上的第一个盘移动到另一个杆上(目标杆的盘必须比他大)。那么其实我们每隔一步就会移动一次最小的那个盘,这就对应了这个隔一个数字出现一次的1。

  这是为什么呢?我也不太清楚……

  总之,有了这个规律,我们就不用写递归程序了,只要把所有的偶数从小到大排开,计算他们末尾二进制的0的个数,我们就知道要移动哪个盘了。

 

  另外,这里是对于传统的汉诺塔,即3杆汉诺塔。那么4杆呢?5杆呢?N杆呢?对于N>3的情况,现在还没有一个确定的表达式可以计算出最少需要多少步,但是有一个递推公式。k杆汉诺塔问题即有n个圆盘,k个杆,圆盘初始在第一个杆上,要将圆盘移动到最后一个杆上。

  因为在最优解中,肯定会先将m个(1<=m<=n-1)个圆盘移动到某个中间杆上,再将剩下的n-m个圆盘通过剩下的k-1个杆移动到目标杆上,最后再将m个圆盘移动到目标杆上,因此有

  f(n,k)=min{2*f(m,k)+f(n-m,k-1)}, 1<=m<=n-1

posted @ 2011-11-21 16:47 LK 阅读(201) | 评论 (0)编辑 收藏

很久不曾写东西,也许只是因为懒已经深入骨髓了

算算毕业已经有5个月了,研究生的第一个学期也快进入尾声

记得去年的这个时候,我还走在铺满落叶的师大,在每天傍晚的广播声中走向景德楼,听着墨明棋妙,吃着香米糕,做着线性代数,时而侧头看看一直陪在身边的巧笑嫣然

很是怀念的感觉


不过,这不是一篇怀念,也不是一篇总结,那是另外的两篇,被很懒很懒的我有意无意放在角落里的诗篇

所以,我不会在这里说,过去怎样,现在怎样,将来怎样

研究生的生活是什么样的,过得好不好,充实还是空虚,这些已经被我抱怨过无数次的东西,这里也不会出现

我现在似乎发现了一种机遇,或者说适合自己的步调

那为何我还要继续懒下去呢?

我会在各个地方,写一些乱七八糟的东西,或纪念,或记录

这里不是一个假装文艺的地方,那就当作一个犯2B的地方吧


所以,骚年,这是一个新的开始

posted @ 2011-11-21 12:55 LK 阅读(60) | 评论 (0)编辑 收藏
仅列出标题