当前位置:C++技术网 > 资讯 > C++递归总结(二)

C++递归总结(二)

更新时间:2018-12-18 18:00:33浏览次数:1+次

相关阅读 

递归总结c++(一)



有N个圆盘,依半径大小(半径都不同),自下而上套在A柱上,每次只允许移动最上面一个盘子到另外的柱子上去(除A柱外,还有B柱和C柱,开始时这两个柱子上无盘子),但绝不允许发生柱子上出现大盘子在上,小盘子在下的情况,现要求设计将A柱子上N个盘子搬移到C柱去的方法。

 

【算法分析】

    本题是典型的递归程序设计题。

    (1)当N=1 时,只有一个盘子,只需要移动一次:A—>C;

    (2)当N=2时,则需要移动三次:

        A------ 1 ------> B,       A ------ 2 ------> C,       B ------ 1------> C. 

    (3)如果N=3,则具体移动步骤为:






假设把第3步,第4步,第7步抽出来就相当于N=2的情况(把上面2片捆在一起,视为一片):


       所以可按“N=2”的移动步骤设计:

       ①如果N=0,则退出,即结束程序;否则继续往下执行;

       ②用C柱作为协助过渡,将A柱上的(N-1)片移到B柱上,调用过程mov(n-1, a,b,c);

       ③将A柱上剩下的一片直接移到C柱上;

       ④用A柱作为协助过渡,将B柱上的(N-1)移到C柱上,调用过程mov (n-1,b,c,a)。


参考代码:

#include<iostream>
using namespace std;
int k=0,n;
void mov(int n,char a,char c,char b)//用b柱作为协助过渡,将a柱上的(n)移到c柱上
{
    if (n==0) return;//如果n=0,则退出,即结束程序
    mov(n-1,a,b,c );//用c柱作为协助过渡,将a柱上的(n-1)片移到b柱上
    k++;
    cout <<k<<" :from "<<a <<"-->"<<c<<endl;
    mov(n-1,b,c,a );//用a柱作为协助过渡,将b柱上的(n-1)移到c柱上
}
int main()                                        
{
    cout<<"n=";
    cin>>n;
    mov(n,'a','c','b'); 
}