學步園

遞歸，一句話概括就是：把大問題分解成結構類似的小問題，分解，計算小問題，再合併（即子函數的返回）。

漢羅塔問題描述：

有三個杆子，依次標記為A,B,C。還有n個大小不同的盤子，較大的盤子放在較小的盤子的下面，依次放置在A桿上，現在要通過若干次操作將所有盤子移到C桿上，且不能違反下列規則：

1.每次只能移動一個盤子

2.不允許大的盤子出現在小的盤子的上面

下面我們來用遞歸的方法分析一下：

1.分解

把盤子中每兩個看成一個整體，以兩個位單位進行移動.那麼如果n=5,5=3+2，問題3就不具有和大問題相同的結構了（在遞歸中，分解時需要注意大問題和子問題是否類似，能否通過同一套方法解決）。最終只能分成每次一個盤子的小問題。最終分解方案是n=(n-1)+1，n-1=(n-2)+1,···，2=1+1。描述為：

對於n個盤子而言(起始桿A,介質桿B,目標杆C)：(注意每次的起始，介質，目標都不一樣)  

    a.將n-1個盤子從A通過C桿為介質移動到B

    b.將第n個盤子從A直接移動到C

    c.將n-1個盤子從B通過A桿為介質移動到C

對於n-1個盤子而言(起始桿A,介質桿C,目標杆B)：  

    a.將n-2個盤子從A通過B桿為介質移動到C

    b.將第n-1個盤子從A直接移動到B

    c.將n-2個盤子從C通過A桿為介質移動到B

總結：

對x個盤子而言（起始s,介質j,目標d）

    a.將x-1個盤子從s通過d桿移動到j(第一個必須把x-1個盤移到介質桿上去)

    b.將第x個盤子從s直接移動到d

    c.將x-1個盤子從j通過s桿移動到d

2.計算

小問題指的是：將一個盤子從A桿移動到C桿，可以不違反任何規則下直接移動了

3.合併

合併是分解的逆過程，漢羅塔問題中就是指子函數的返回

最終程序如下：

#include <stdio.h>

void move(int n,char start,char jiezhi,char des)
{
	//n=1時，直接移動
	if (n==1)
	{
		printf("%c->%c\n",start,des);
		return;
	}

	//將x-1個盤子從s通過d桿移動到j(第一個必須把x-1個盤移到介質桿上去)
	move(n-1,start,des,jiezhi);

	//將第x個盤子從s直接移動到d
	printf("%c->%c\n",start,des);

	//將x-1個盤子從j通過s桿移動到d
	move(n-1,jiezhi,start,des);
}


void main()
{
	move(3,'A','B','C');
}

一起學習，一起進步，歡迎訪問我的博客：http://blog.csdn.net/wanghao109