经典递归有关问题-汉诺塔

经典递归问题--汉诺塔

递归的一个重要特征是找到解决问题过程中重复的部分，把问题的规模减小但是解决的方法不变。递归的另一个重要特征是问题的出口，也就是问题规模最小的时候的解。如果问题求解走到了出口部分，那么下面应该开始回朔。所以一个大问题经过递归后会分解为一个个小问题，在求得小问题的解后再来组成大问题的解。

例如递归里面很经典的汉诺塔问题：a,b,c三根轴，在a上面有n个积木，从上到下体积递减。现在要把a上的积木全部移到c上面，可以借助b，但是移动过程中要保证大的积木在下面。

同样的传统的模拟法很难讲述整个过程，因为要考虑大的积木在下面，所以感觉很烦琐。下面我们来分析一遍：

【1】假如n=1，那么直接a移到c a(1)-->c

【2】假如n=2，那么a(1)-->b，a(1)-->c，b(1)-->c。

【3】假如n=3，那么a(1)-->c, a(1)-->b, c(1)-->b, a(1)-->c, b(1)-->a, b(1)-->c, a(1)-->c

``````````````

仔细观察n=3的情况，a(1)-->c, a(1)-->b, c(1)-->b, a(1)-->c, b(1)-->a, b(1)-->c, a(1)-->c其实可以归结为：a(2)--->b, a(1)-->c, b(2)-->c

从宏观上看：也就先把a的两个积木移到b，再把剩下的一个移到c，最后把b的两个积木移到c。其中a把两个积木移到b和【2】a把两个积木移到c操作过程是一样的，只不过是参数改变了。所以我们把n=3的求解过程分解为两个n=2的求解过程和一个n=1的求解过程。

把上述过程推广到一般情况我们可以得到：移动任意积木数n可以分解成移动两次n-1和一次1 两个三个过程，而n-1次过程又可以分解为移动两次n-2的过程和一次1的过程，···一直递归直到问题的出口 n=1只有一个积木或者n=2两个积木，输出解并且开始回朔！每次回朔都由小问题的解组成大问题的解，最终得到整体的解！

我们可以得到代码如下：

#include<iostream>

using namespace std;
void move(char a,char b,char c,int n)
{
   if(n==1) 
   {
    cout<<a<<"-->"<<c<<endl;
    return ;
   }
  else if(n==2)
  {
	  cout<<a<<"-->"<<b<<endl;
	  cout<<a<<"-->"<<c<<endl;
	  cout<<b<<"-->"<<c<<endl;
  }
 else
 {
    move(a,c,b,n-1);
	move(a,b,c,1);
	move(b,a,c,n-1);
 }

}

int main()
{
	int n=0;
	while(cin>>n)
	{
	   move('a','b','c',n);
	   cout<<"writed by damon-lin whos blog is http://blog.****.net/linsheng9731"<<endl;
	}



 return 0;
}

经典递归有关问题-汉诺塔

相关推荐