数据结构：思想与方法-翁惠玉-27783第十五章幻灯片.ppt

* 分书问题 有编号为0，1，2，3，4的5本书，准备分给5个人A，B，C，D，E，每个人的阅读兴趣用一个二维数组描述： Like[i][j] = true i喜欢书j Like[i][j] = false i不喜欢书j 写一个程序，输出所有皆大欢喜的分书方案 0 0 1 1 0 1 1 0 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 0 1 * 存储设计 用一个二维数组like存储用户的兴趣 用一个一维的整型数组take表示某本书分给了某人。Take[j] = i表示第j本书给了第i个人。 * 解题思路 依次尝试把书j分给人i。 如果第i个人不喜欢第j本书，则尝试下一本书，如果喜欢，并且第j本书尚未分配，则把书j分配给i。 如果i是最后一个人，则方案数加1，输出该方案。否则调用try（i+1)为第i+1个人分书。 回溯。让第i个人退回书j，尝试下一个j，即寻找下一个可行的方案 由于在每次try中都要用到like，take以及目前找到的方案数n，因此可将它们作为全局变量，以免每次函数调用时都要带一大串参数。 设计一个函数try(i)给第i个人分书。 * void trynext(int i) { int j, k; for (j=0; j5; ++j) { if (like[i][j] take[j] == -1) { take[j] = i; if (i == 4) { n++; cout \n第 n 种方案: endl; cout 书\t人 endl; for (k=0; k5; k++) cout k \t char(take[k]+A) endl; } else trynext(i+1); take[j] = -1; } } } * 当like矩阵的值为 调用trynext(0);的结果为： 第1种方案： 书 人 0 B 1 C 2 A 3 D 4 E 第2种方案： 书 人 0 B 1 E 2 A 3 D 4 C * 第15章 算法设计技术 枚举法 贪婪法 分而治之法 动态规划 回溯法 随机算法 介绍通用的算法设计模式 * 随机算法 在算法中，至少有一个地方使用随机数作决策。 随机算法的时间复杂度取决于选择的随机数 随机算法的时间复杂度用期望的运行时间来表示。一般假设随机数的选择是均匀分布的 例如，在快速排序中将中间点用随机数来选择，则快速排序成为一个随机算法。可以证明，期望的时间复杂度为O(NlogN) * 随机算法实例 跳表 素数检测 * 跳表 以O(logN)的期望的时间复杂性支持插入和删除的数据结构 跳表的概念：支持动态查找必须用链表，但链表查找的时间为N。可以用增加链的方式提高查找效率 增加一条链，让头节点指向第二个节点，第二个节点指向第四个节点，第四个节点指向第六个节点，…。查找时间为 再增加一条链，让头节点指向第四个节点，第四个节点指向第八个节点，第八个节点指向第十二个节点，…。查找时间为 推而广之，对于2iN≤2i+1个节点，设置i条链，第j条链指向其后的第2j个节点 * 8 2 10 11 13 19 20 22 23 25 8 2 10 13 19 20 23 25 11 22 8 2 10 13 19 20 23 25 11 22 * 查找过程（节点x） 首先查找第i条链，如下一节点比x大，则查找第i-1条链，否则继续查找第i条链。依次执行，直到找到或找不到x 最坏情况下的时间性能： * 插入过程 当插入一节点时，所有的节点都要变化。为了避免这个变化，插入采用随机算法 定义：有k条链的节点称为level-k节点 在跳表中，level-i的节点有N/2i个，即level-i的节点出现的概率为1/2i。 插入过程： 查找到插入点 生成一个新节点 按概率生成节点的level 插入该节点 因此跳表并不一定是严格的隔2i个节点有一条第i层的链，而只是从概率上讲符合此分布 * 随机算法实例 跳表 素数检测 * 素数检测 方法一：依次检测1到N能否被N整除，如果能被整除的数的个数等于2，则N是素数。时间复杂度为O（