归东程子太军 一、递归的概念 SHANDONG UNIVERSITY OF TECINOLOGY 3会诗3会合3会学3会华A是会察 ●例5整数划分问题 将最大加数n不大于m的划分个数记作q(n,m)。 (1)q(n,1)=1,n≥1； 当最大加数n1不大于1时，任何正整数n只有一种划分形式， 即n=1+l+.+1 (2)qn,m)=qn,n),m≥n; 最大加数n实际上不能大于n。 (3)q(n,n)=1+q(n,n-1)i 正整数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的划分组成。 2025年4月3日 16
2025年4月3日 16 一、递归的概念 ⚫例5 整数划分问题 将最大加数n1不大于m的划分个数记作q(n,m)。 (4) q(n,m)=q(n,m-1)+q(n-m,m),n>m>1; 正整数n的最大加数n1不大于m的划分由n1=m的划分和 N1≤m-1 的划分组成。 (3) q(n,n)=1+q(n,n-1); 正整数n的划分由n1=n的划分和n1≤n-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
归本程上太军 一、递归的概念 SHANDONG UNIVERSITY OF TECHNOLOGY ●例5整数划分问题 1 n=1,m=1 q(n,n) n<m g(n,m)= 1+q(n,n-1) n=m g(n,m-1)+g(n-m,m) n>m>1 ●正整数n的划分数p(n)=q(n,n)。 2025年4月3日 17
2025年4月3日 17 一、递归的概念 ⚫ 例5 整数划分问题 ⚫ 正整数n的划分数p(n)=q(n,n)。 = = = − + − + − = 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
归东程子太军 SHANDONG UNIVERSITY OF TECINOLOGY 华容约深完是红器分深是容 int g(int n,int m) if ((n<1)(m 1))return 0; if((n =1)(m =1))return 1; if(n m)return q (n,n); if(n =m)return (q (n,m-1)+1); return (q (n,m-1)+q((n-m),m)); 2025年4月3日 18
2025年4月3日 18 ⚫int q(int n, int m) { if ((n < 1) || (m < 1)) return 0; if((n == 1) || (m == 1)) return 1; if(n < m) return q (n, n); if(n == m) return (q (n, m - 1) + 1); return (q (n, m-1)+ q( (n- m), m)); }
归本程上太军 SHANDONG UNIVERSITY OF TECHNOLOGY 一、 递归的概念 器会合会器空会空是路 ●例6 Hanoi塔问题 设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆 盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2，.， 现要求将塔座上的这一叠圆盘移到塔座c上，并仍按同样顺序叠置。 在移动圆盘时应遵守以下移动规则： 规则1：每次只能移动1个圆盘； 规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则3：在满足规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。 2025年4月3日 19
2025年4月3日 19 一、递归的概念 ⚫ 例6 Hanoi塔问题 设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆 盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,.,n, 现要求将塔座a上的这一叠圆盘移到塔座c上，并仍按同样顺序叠置。 在移动圆盘时应遵守以下移动规则： 规则1：每次只能移动1个圆盘； 规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则3：在满足规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上
白本程子太军 SHANDONG UNIVERSITY OF TECHNOLOOY 华会清学3会A空是品 汉诺塔问题可以通过以下三个步骤实现： ()将塔A上的n-1个碟子借助搭C先移到塔B上。 (2)把塔A上剩下的一个碟子移到搭C上。 (3)将n-1个碟子从塔B借助塔A移到塔C上。 显然，这是一个递归求解的过程 2025年4月3日 20
2025年4月3日 20 汉诺塔问题可以通过以下三个步骤实现： （1）将塔A上的n-1个碟子借助塔C先移到塔B上。 （2）把塔A上剩下的一个碟子移到塔C上。 （3）将n-1个碟子从塔B借助塔A移到塔C上。 显然，这是一个递归求解的过程