梵塔问题 【问题描述】已知有三根针分别用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步。
|