Hanoi塔(分治法的應用)

1.分治法

分治法的設計思想是将一個難以直接解決的大問題分解成一些規模較小的相同問題，以便各個擊破，分而治之。

一般來說，分治算法在每一層遞歸上都有3個步驟：

（1）分解：将問題分解成一系列子問題。

（2）求解：遞歸地求解各子問題。若子問題足夠小，則直接求解。

（3）合并：将子問題的解合并成原問題的解。

2.Hanoi塔

分治法的典型應用：

void Hanoi(int n,char a,char b,char c) //将n個盤子從a通過b移動到c

{

　　if(n>1){

　　　　　Hanoi(n-1,a,c,b);//先将前n-1個盤子從a處通過b移動到b

　　　　　move(n,a,c);//将第n個盤子從a處直接移動到c

　　　　　Hanoi(n-1,b,a,c);//再将前n-1個盤子從了b處通過a移動到c

　　}else{

　　　　　move(n,a,c);//隻有一個盤子時，直接從a移動到c。遞歸出口

　　}

}