1.2-设计方法.ppt

1.2 算法设计基本方法 列举法 ( 穷举法、枚举法) 例:百钱买百鸡 设每只母鸡值3元， 每只公鸡值2元， 两只小鸡值1元。 现要用100元钱买100只鸡， 设计买鸡方案。 假设买母鸡I只，公鸡J只，小鸡K只 对算法进行优化 FOR I＝0 TO 33 DO FOR J＝0 TO 50－1.5I DO { K＝100－I－J IF (3I＋2J＋0.5K＝100) THEN OUTPUT I，J，K } RETURN 关于列举法 如何得到问题每一个可能的解? 有哪些信誉好的足球投注网站空间的问题 如果列举量无限怎么办? 补充例: 桌上有6根火柴棒,你的任务是用它们搭建起4个等边三角形. 补充例：我的三个小孩的年龄有多大？ A:你能算出我的三个儿子年龄有多大吗？ B:可以 A:他们三个的年龄之积是36 B:很好,但我需要更多提示 A:他们三个的年龄之和等于那栋房子的窗户个数 B:我还要一点信息来解你的难题 A:我的大儿子眼睛是蓝色的 B:够了,我知道答案了. 2. 归纳法 通过列举少量的特殊情况，经过分析，最后找出一般的关系。 3. 递推 初始条件 递推关系式 补充例 4. 递归 例: 编写一个过程，对于输入的参数n，依次打印输出自然数1到n。非递归算法 PROCEDURE WRT(n) FOR k＝1 TO n DO OUTPUT k RETURN 输出自然数1到n的递归算法 补充例：Hanoi塔 塔A上有一叠共n个圆盘,自下而上,由大到小叠在一起. 现要求将塔座A上的这叠圆盘移到塔座B上,并仍按同样顺序叠置. 移动规则: (1)每次只能移动一个圆盘; (2) 任何时候都不允许将较大的圆盘压在较小的圆盘之上; (3) 在满足规则(1)和(2)的前提下,可将圆盘移至A,B,C中任一塔座上. Void Hanoi( int n, int A, int B, int C ) { if (n0) { Hanoi(n-1,A,C,B) Move(n,A,B); Hanoi(n-1,C,B,A) } } 5. 减半递推技术 “减半” - 将问题的规模减半，而问题的性质不变 “递推” - 重复“减半”的过程 矩阵乘法 C = AB 矩阵乘法 C = AB 设A和B是两个n×n的矩阵 采用减半递推技术 (分治算法)A和B是两个n×n矩阵 n=2k 设计算n阶方阵乘积所需乘法次数为M(n) n=2k 采用减半递推技术 + Strassen 矩阵乘法 计算两个n阶矩阵相乘 例1.3: 二分法求方程实根的减半递推过程 分治算法 - Divide and Conquer , DC 分解 子问题互相独立且与原问题相同, 是原问题的较小模式 不断分解下去 各个击破 递归地解这些子问题 合并 分治算法 - Divide and Conquer , DC 2m维的棋盘上有一个洞(即移去了一个方格), 请用一些L形的积木来覆盖整个棋盘,积木的方向无所谓. 6. 回溯法 例:求解皇后问题 由n2个方块排成n行n列的正方形称为“n元棋盘”。 如果两个皇后位于棋盘上的同一行或同一列或同一对角线上，则称它们为互相攻击。 现要求找使n元棋盘上的n个皇后互不攻击的所有布局。 作业 Q Q Q Q Q Q Q Q 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 八皇后在棋盘上分布的各种可能的格局数是多少? * 1. 列举法 2. 归纳法 3. 递推 4. 递归 5. 减半递推技术 6. 回溯法 FOR I＝0 TO 100 DO FOR J＝0 TO 100 DO FOR K＝0 TO 100 DO { M＝I＋J＋K //鸡 N＝3I＋2J＋0.5K //钱 IF ((M＝100)and(N＝100)) THEN OUTPUT I，J，K } RETURN 总循环次数为1013 总循环次数为： (100-3I)/2 = 50-1.5I 自己调用自己的过程称为递归调用过程. 直接递归和间接递归 PROCEDURE WRT1(n) IF (n≠0) THEN { WRT1(n－1) OUTPUT n } R