普及层次第三讲递归递推分治.ppt

[算法分析] 利用递推公式进行求解，因为N 不大于100，因此定义数组时10个下标变量就足够了。 为了避免反复过程调用，我们采用以下主要步骤： 1、先利用双重循环将10以内的方案数计算后，存放在数组A中； 2、输入N； 3、在一重循环中，利用公式直接求和。 4、输出方案数K。 [程序清单] 略 [运行数据及测试结果] 递归与分治基本原理 递推与递归 递归与递推表面看来是相逆的过程，其实也是相似的，最终的计算都是从小算到大。 递推的使用环境要求高导致了递推的高效性，递推没有重复计算什么数据，保持了高效。 递归大多数会重复计算子问题，导致时间浪费，所以一般不要使用过深的递归，甚至会空间溢出。 棋盘覆盖问题 还可以将棋盘覆盖推广到一般情况： 大数的运算 加法 减法 乘法 100！ 93 326215 443944 152681 699263 856266 700490 715968 264381 621468 592963 895217 599993 229915 608914 463976 156578 286253 697920 827223 758251 185210 916864 000000 000000 000000 000000 除法 …… 大整数的乘法 问题描述： 设X和Y都是n位的二进制整数，请设计一个有效的算法，可以进行两个n位大整数的乘法运算。 分析： 1.小学的方法：O n2 效率太低 大整数的乘法 2.可以用分治法的原理设计一个更有效的算法。 将n位的二进制整数分为2段： 大整数的乘法 效率： 4次n/2位整数乘法 AC, AD,BC, BD ； 3次不超过n位整数加法； 2次移位 分别对应乘以2n和2n/2 所有加法和移位共用O n 步计算。 改进：把 1 式稍作修改： XY AC2n + A－B D－C +AC+BD 2n/2 + BD 2 效率： 3次n/2位整数乘法 AC, BD, A－B D－C ； 6次不超过n位整数加、减法和2次移位； begin //两个n位整数相乘 伪代码 X abs X ; Y abs Y ; if n 1 return S*X*Y ; else begin A: X的左边n/2位； B: X的右边n/2位； C: Y的左边n/2位； D: Y的右边n/2位； m1: Mult A, C, n/2 ; m2: Mult A-B, D-C, n/2 ; m3: Mult B, D, n/2 ; S: S* m1* 2n + m1+m2+m3 *2n/2+m3 ; return S; end;End; 大整数的乘法 分析 传统的方法：O n2 ?效率太低 分治法: O n1.59 ü较大的改进 更快的方法？ 对于大整数乘法，它能在O nlogn 时间内解决。 是否能找到线性时间的算法？ 目前为止还没有结果 。 循环赛日程表 例如： 循环赛日程表 分析： 法1：分治策略 按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。 递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。 循环赛日程表 分析 法2：递推法 迭代法 循环赛日程表 递推法 迭代法 即2k个选手的比赛日程在2k-1个选手的比赛日程基础上通过迭代完成，每次迭代，将问题分为4个部分： 左上角： 2k-1个选手前半程的比赛日程 左下角：另2k-1个选手前半程的比赛日程，由左上角加2k-1得到 右上角：将左下角抄到右上角，得到另2k-1个选手后半程的比赛日程。 右下角：将左上角抄到右下角，得到2k-1个选手后半程的比赛日程。 谢 谢！ 8 8 7 7 8 6 6 7 5 4 4 6 5 5 4 3 2 1 1 3 3 2 2 1 12 11 11 10 9 9 12 12 11 10 10 9 8 7 7 6 5 5 8 8 7 6 6 5 4 3 3 2 1 1 4 4 3 2 2 1 1 1 1 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 1 × 1 1 0 1 A n/2位 B n/2位 C n/2位 D n/2位 X Y 则： X A2n/2+B（乘2n/2，相当于左移n/2位） Y C2n/2+D 于是： XY A2n/2+B C2n/2+D AC2n + AD+BC 2n/2 + BD 1 时间复杂性分析 T n O n2 ?没有改进 时间复杂性分析 T n O nlog3 O n1.59 ü较