算法设计与分析 课件 3.4-递归 - 典型应用 - 整数划分.pptx

算法设计与分析

递归-典型应用-整数划分;将一个正整数表示成一系列正整数之和。

正整数n的一个这种表示称为它的一个划分。

正整数n的不同划分个数称为正整数n的划分数。

问题：给出一个正整数n，求出其划分数。

比如对于6而言,其划分共11种：

6；

5＋1；

4＋2，4＋1＋1；

3＋3，3＋2＋1，3＋1＋1＋1；

2＋2＋2，2＋2＋1＋1，2＋1＋1＋1＋1；

1＋1＋1＋1＋1＋1；;在正整数n的所有不同划分中，将最大加数不大于m的划分个数记作q(n,m)。

可以建立如下递归关系：

（1）q(n,1)=1,n=1;

（2）q(n,m)=q(n,n),m=n;

（3）q(n,n)=1+q(n,n-1);

（4）q(n,m)=q(n,m-1)+q(n-m,m)nm1;;用一个形如intq(intn,intm)的函数表示

输入：n,m

输出：n的最大整数不超过m的划分数

1、if(n1)or(m1)thenreturn0;

2、if(n=1)or(m=1)thenreturn1;

3、if(nm)thenreturnq(n,n);

4、if(m=n)thenreturnq(n,m-1)+1;

5、returnq(n,m-1)+q(n-m,m);;问题：打印整数n的全部划分。

用不完全归纳法：

n=2可拆分成2=1+1

n=3可拆分成3=1+2=

1+1+1

n=4可拆分成4=1+3=

1+1+2=

1+1+1+1=

2+2

……;分析：

用数组a存储n的一种拆分,可得出以下递归关系

对于一个n而言,按a[1]分类，有a[1]=1,a[1]=2,…,a[1]=n/2,共n/2大类拆分。

每一类拆分时，a[1]=i,a[2]=n-i,从k=2，继续

从a[k]开始拆分，a[k]能否再拆分取决于：

a[k]/2是否大于等于a[k-1]。;split(intt)：对数a[t]进行划分

输入：t表示要拆分的数在a数组中的下标

输出：a[t]的划分

1：fork=1totdo

2：输出a[k];

3：j=t;L=a[j];

4：fori=a[j-1]toL/2dobegin

5：a[j]=i;a[j+1]=L-i;

6：split(j+1);

7：end;;测试