清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1递归的概念 例5整数划分问题 煎面的几个四子中_问题本身都具有比较明显的递归关系,因 布容蒡用递归函数直接求解。 本图此考溶省要数藏则+组影关 个数记作q(n,m)。可以建立q(n,m)的如下递归关系。 (3)qn,n)=1+q,n-1) 正整数n的划分由n1=n的划分和n1≤n-1的划分组成 (4)qn,m)=qn,m-1)+q(n-mm)n>m>1; 正整数n的最大加数n1不大于m的划分由n1=m的划分和 n1≤n-1的划分组成
(2) q(n,m)=q(n,n),mn; 最大加数n1实际上不能大于n。因此，q(1,m)=1。 (1) q(n,1)=1,n1; 当最大加数n1不大于1时，任何正整数n只有一种划分形式， 即 n n = 1+1+ +1 (4) q(n,m)=q(n,m-1)+q(n-m,m),n>m>1; 正整数n的最大加数n1不大于m的划分由n1=m的划分和 n1≤n-1 的划分组成。 (3) q(n,n)=1+q(n,n-1); 正整数n的划分由n1=n的划分和n1≤n-1的划分组成。 2.1 递归的概念 例5 整数划分问题 前面的几个例子中，问题本身都具有比较明显的递归关系，因 而容易用递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关 系，因此考虑增加一个自变量：将最大加数n1不大于m的划分 个数记作q(n,m)。可以建立q(n,m)的如下递归关系
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1递归的概念 例5整数划分问题 煎面的几个四子中_问题本身都具有比较明显的递归关系,因 布容蒡用递归函数直接求解。 本图此考溶省要数藏则+组影关 个数记作q(n,m)。可以建立q(n,m)的如下递归关系。 q(n, n) n m q(n, m) 1+q(n,n-1) 1三m q(n, m-1+q(n-m, m) n>m>1 正整数n的划分数p(n)=qnn)e
= = = − + − + − = 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 2.1 递归的概念 例5 整数划分问题 前面的几个例子中，问题本身都具有比较明显的递归关系，因 而容易用递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关 系，因此考虑增加一个自变量：将最大加数n1不大于m的划分 个数记作q(n,m)。可以建立q(n,m)的如下递归关系。 正整数n的划分数p(n)=q(n,n)
清华大学出版社 TSINGHUA UNIVERSITY PRESS A B
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1递归的概念 例6 Hano i塔问题 设ab,C是3个塔座。开始时,在塔座a上有一叠共η个圆 盘,,些圆 ,由大到小地叠在一起。各圆 盘从小到大编号为1,2…n,现要求将垤座a上的这一叠 移到拾座b上并仍按同样顺寺置。在移奇圆盘 时应遵守以下移动规如 规则1:每次只能移动1个圆盘; 规则2:任何时刻都不允许将较大的圆盘压在较小的圆盘 规则3:在满足移动规则1和2的前提下,可将圆盘移至 a,bC中任一塔座上。 A n
2.1 递归的概念 例6 Hanoi塔问题 设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆 盘，这些圆盘自下而上，由大到小地叠在一起。各圆 盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠 圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘 时应遵守以下移动规则： 规则1：每次只能移动1个圆盘； 规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘 之上； 规则3：在满足移动规则1和2的前提下，可将圆盘移至 a,b,c中任一塔座上