梵塔问题

梵塔问题

【问题描述】已知有三根针分别用1、2、3表示。在一号针中从小到大放n 个盘子，现要求把所有的盘子从1针全部移到3针。移动规则是：使用2针作为过渡针，每次只移动一块盘子，且每根针上不能出现大盘压小盘，找出移动次数最小的方案。

【分析】这是一个经典的递归问题。

递归的思路：如果想把 n 个盘子放到3针上，就应该先把n-1个盘子放到2针上。然后把1针最底部的盘子移动到3针，再把2针上的n-1个盘子移动到3针上。

void  move(int n, int a, int b, int c)		//  a是盘子来源，b是暂存区、c是目标
{  if (n==1)       cout<<a<<"->"<<c<<endl;		//  只有一根针时直接移动
else    {      move(n-1,a,c,b);		//  先把n-1个盘子移动到#2上
cout<<a<<"->"<<c<<endl;      move(n-1,b,a,c);          }    }		//  把n-1个盘子移动到#3上

调用：move(n,1,2,3);

时间复杂度：O(2n)。n 层梵塔至少要移动2n－1步。