递归问题-整数划分-汉诺塔

1.递归的概念

例子1：整数划分问题

将正整数表示成一系列正整数之和 n=n1+n2+n3.....+nm

在正整数n的所有不同划分中，将最大加数不大于m的划分个数记作q(n,m)。可以建立（q,m）的如下递归关系。

• q(n,1)=1, n>=1;

• q(n,m)=q(n,n), m>=n;

• q(n,n)=1+q(n,n-1), m=n;

• q(n,m)=q(n,m-1)+q(n-m,m), n>m>1;

包含m和不包含m两种情况：正整数n的最大加数不大于m的划分由最大加数<=m-1的划分和最大加数=m的划分组成。

q(n,m-1): 将m范围降低1，即不包含m，包含m情况另考虑。

q(n-m,m): n=m+m1+m2+m3... m+m1+m2+m3... 决定了划分个数。

例子2 汉诺塔问题

A: n

B: 0

C: 0

目的：将A上的全部圆环移到C上，前题:一次只可以移动一个。

方法：现将A上的1个移动到B上，再将A上的n-1个移动到C上，最后将B上的一个移动到C上，采用递归的办法。

• m=n时（m为要移动的个数）

  0、A：n B：0 C：0

  1、A：n-1 B：1 C：0

  2、A：0 B：1 C：n-1

  3、A：0 B：0 C：n

• m=n-1 （将A上的n-1个移到C上）

  0、A：n-1 B：0 C：0

  1、A：n-2 B：1 C：0

  2、A：0 B：1 C：n-2

  3、A：0 B：0 C：n-1

• ...........

总结：

• 递归算法设计：

  • 将规模较大的原问题分解为一个或多个规模更小的与原问题类似的子问题-递归步骤。

  • 确定一个或多个无需分解可直接求解的子问题-终止条件。

• 递归算法特点：

  • 优点：结构清晰，可读性强，容易用数学归纳法来证明算法的正确性，为设计算法、调试程序带来很大方便。

  • 缺点：运行效率率较低，，、无论是耗费的计算时间还是占用的存储空间都比飞递归算法要多。