递归的力量(三):更多例子

昨天说了一些递归的简单应用,今天再说一点其他的应用吧。

不得不提的一个经典的问题是汉诺塔问题。问题是这样的:

有三个柱子,其中的一个上面套着八个圆盘,从下到上,圆盘按从大到小的顺序排列。要求把所有圆盘移动到另一个柱子上,并遵循以下规则:
  • 一次只能移动一个圆盘
  • 圆盘只能套在柱子上
  • 小圆盘只能放在比它大的圆盘上

要解决这个问题,用普通的方法来作实在是很困难。而用递归来解决呢? 会不会有一个容易的解决方案呢?

还是考虑递归的两个条件,是否可把问题规模缩小,是否存在简单情境。为了便于讨论,我们把圆盘现在所在的柱子称为源,把圆盘要移动到的柱子成为目的,另外一个柱子称为辅助。我们容易发现,要把最大的圆盘移动到目的,首先要把上面较小的七个圆盘移动到辅助上(注意,这是一个与原问题有着相同的形式且规模更小的问题),然后把大圆盘移动到目的上,在把七个较小圆盘从辅助移动到目的。可以看到,移动七个小圆盘其实与原问题形式相同而规模更小。好了,我们已经成功地缩小了问题规模。下面来找找简单情境。

很容易看到,当只有一个圆盘时,只要把它从源移动到目的就行了。这就是简单情境。

好,两个条件都具备了,我们可以开始写程序了。

void movesingledisk(char source, char target){
    printf("%c --> %cn", source, target);
}
void movehanoitower(char source, char target, char tmp, int n){
    if(n == 1)
          movesingledisk(source, target);
    else{
          movehanoitower(source, tmp , target, n - 1);
          movesingledisk(source, target);
          movehanoitower(tmp, target, source, n - 1)
    }
}

以上就是实现输出汉诺塔问题解的主要函数了。你可以编写一个主程序来调用它们。像这样:

int main(){
    move_hanoi_tower('A', 'B', 'C', 8);
    return 0;
}

不错吧,很简洁的,几行代码,就解决了这个问题。是不是很爽呢?不过这个递归调用的算法的复杂性如何呢?让我们来看看。

记规模为n的输入耗时T(n),则:

T(1) = 1 T(n) = 2<em>T(n-1) + 1 T(n) + 1= 2</em>(T(n-1) + 1) T(n) + 1 = (T(1) + 1) * ( 1 - (T(1)+1)^n) / ( 1 - (T(1)+1)) T(n) = 2^n - 1

这是一个很经典的例子,我们来给它改个版,留为今天的作业吧:

所有要求不变,添加如下要求: 圆盘不能从源直接移动到目的。 如何解决此问题?复杂度是多少?

喜欢这篇文章?

欢迎订阅 PureWeber.com - 纯粹互联网。接收免费的更新提醒,以及订阅读者独家优质内容。

段 志岩

喜读书,未破一卷;好哲学,不求甚解。

加入讨论

电子邮件地址不会被公开。 必填项已用*标注