例4排列问题 设计一个递归算法生成n个元素{r1,r2,rn}的全排列。 设R={r1,r2,rn}是要进行排列的n个元素，R=R-{r。 集合X中元素的全排列记为perm(X)。 (r)perm()表示在全排列perm(X)的每一个排列前加上前 缀得到的排列。R的全排列可归纳定义如下： 当n=1时，perm(R)=(),其中r是集合R中唯一的元素； 当n>1时，perm(R)由(r)perm(R),(r2)perm(R2),. (r)perm(R)构成。 N! 16
16 例4 排列问题 设计一个递归算法生成n个元素{r1 ,r2 ,…,rn}的全排列。 设R={r1 ,r2 ,…,rn }是要进行排列的n个元素，Ri=R-{ri }。 集合X中元素的全排列记为perm(X)。 (ri )perm(X)表示在全排列perm(X)的每一个排列前加上前 缀得到的排列。R的全排列可归纳定义如下： 当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素； 当n>1时，perm(R)由(r1 )perm(R1 )，(r2 )perm(R2 )，…， (rn )perm(Rn )构成。 N!
r1--t(1)=1 r1、r2---r1perm(R1) r2perm(R2) t(2)=2*t(1) r1、r2、r3 ÷r1perm(R1) ÷r2perm(R2) r3perm(R3) t(3)=3*T(2) ■■■ t(n)=n*t(n-1) 7
17 ❖ r1---t(1)=1 ❖ r1、r2---------r1perm(R1) r2perm(R2) ❖ t(2)=2*t(1) ❖ r1、r2、r3 ❖ r1perm(R1) ❖ r2perm(R2) ❖ r3perm(R3) ❖ t(3)=3*T(2) ❖ …………….. ❖ t(n)=n*t(n-1)
例5整数划分问题 将正整数n表示成一系列正整数之和： n=n1+n2+..+nk, 其中n1≥n2≥..≥nk21,k21。 。正整数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。 18
18 ❖ 例5 整数划分问题 ❖ 将正整数n表示成一系列正整数之和： n=n1+n2+…+nk， ❖ 其中n1≥n2≥…≥nk≥1，k≥1。 ❖ 正整数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
前面的几个例子中，问题本身都具有比较明显的 递归关系，因而容易用递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分数，则难 以找到递归关系，因此考虑增加一个自变量：将 最大加数n1不大于m的划分个数记作q(n,m)。可 以建立q(n,m)的如下递归关系。 1 n=1m=1 q(n,n) n<m g(n,m)= 1+g(n,n-1) n=m g(n,m-1)+g(n-m,m) n>m>l 19
19 ❖ 前面的几个例子中，问题本身都具有比较明显的 递归关系，因而容易用递归函数直接求解。 ❖ 在本例中，如果设p(n)为正整数n的划分数，则难 以找到递归关系，因此考虑增加一个自变量：将 最大加数n1不大于m的划分个数记作q(n,m)。可 以建立q(n,m)的如下递归关系。 = = = − + − + − = 1 1, 1 ( , 1) ( , ) 1 ( , 1) ( , ) 1 ( , ) n m n m n m n m q n m q n m m q n n q n n q n m ?
(1)q(n,1)=1,n≥1； 当最大加数n1不大于1时，任何正整数n只有一种划分形式， 即n=1+1++1 (2)q(n,m)=q(n,n),mzn; 最大加数n实际上不能大于n。因此，q(1,m)=1。 (3)q(n,n)=1+q(n,n-1); 正整数n的划分由n1=n的划分和n1≤n-1的划 分组成。 (4)q(n,m)=q(n,m-1)+q(n-m,m),n>m>1; 正整数n的曼而数n1不大于m分虫n三m的划分和 n不包含m成 包含m的划分 20
20 (3) q(n,n)=1+q(n,n-1); ❖ 正整数n的划分由n1=n的划分和n1≤n-1的划 分组成。 (4) q(n,m)=q(n,m-1)+q(n-m,m),n>m>1; 正整数n的最大加数n1不大于m的划分由n1=m的划分和 n1≤m-1 的划分组成。 (1) q(n,1)=1,n1; 当最大加数n1不大于1时，任何正整数n只有一种划分形式， 即 n n = 1+1+ +1 (2) q(n,m)=q(n,n),mn; 最大加数n1实际上不能大于n。因此，q(1,m)=1。 不包含m 包含m的划分