算法与数据结构基础培训资料.ppt

大学计算机;第6章 算法与数据结构基础;;;;*;6.1.2算法的特性;6.1.3算法与计算机程序;*;（2）、流程图 用图直观地描述一个工作过程的具体步骤 ;6.1.5算法的设计要求 ;6.2算法策略; 穷举法的特点是算法设计比较简单，解的可能为有限种，一一列举问题所涉及的所有情形。 例如： 在QQ上，OicqPassOver这个工具穷举用户的口令，它根据机器性能最高可以每秒测试20000个口令，如果口令简单，一分钟内，密码就会遭到破译。 ;穷举法运用于一些经典问题;用穷举算法解决问题，通常可以从两个方面进行分析： 1、问题所涉及的情况：问题所涉及的情况有哪些，情况的种数可不可以确定。把它描述出来。 2、答案需要满足的条件：分析出来的这些情况，需要满足什么条件，才成为问题的答案，把这些条件描述出来。 由于穷举法穷举的数据量过大，效率较低，对于小规模的问题还是适用的，但是问题规模一旦扩大，穷举法就没有什么可取性了。一般巧妙和高效算法很少来自穷举法。;6.2.2 回溯法; 回溯算法也叫试探法，是一种选优有哪些信誉好的足球投注网站法，按选优条件向前有哪些信誉好的足球投注网站，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 回溯法的指导思想：走不通，就掉头 回溯法在有哪些信誉好的足球投注网站过程中通过对约束条件的判定，排除错误答案，提高了有哪些信誉好的足球投注网站效率。;网络爬虫;回溯法的本质也是一种穷举法，但与穷举法相比，回溯法的“聪明”之处在于能适时“回头”，若再往前走不可能得到解，就回溯，退一步另找线路，这样可省去大量的无效操作。因此，回溯与穷举相比，回溯更适宜于量比较大，候选解比较多的问题。;6.2.3 递归法;所谓递归就是一个函数或过程可以直接或间接地调用自己。 递归分为直接递归和间接递归两种方法。 如果一个算法直接调用自己，称为直接递归调用； 如果一个算法A调用另一个算法B，而算法B又调用算法A，则此种递归称为间接递归调用。;1、n！问题;2、汉诺塔（Hanoi）问题 ;使用递归时必须符合以下三个条件： （1）可将一个问题转化为一个新的问题，而新问题的解决方法仍与原问题的解法相同，只不过所处理的对象有所不同而已，即它们只是有规律的递增或递减。 （2）可以通过转化过程使问题回到对原问题的求解。 （3）必须要有一个明确的结束递归的条件，否则递归会无止境地进行下去。 递归对某些问题而言存在重复调用，导致算法效率不高。;6.2.4 分治法;1、找出伪币;方法1;方法2;方法3;分析;根据以上比较，第三种方法就是分治法，可以得到以下的采用分治方法的结论： 1、参与比较的硬币数量越多，使用该方法来实现就越快，而且投机性大大减少； 2、解决方法关键在于能将大问题分割成若干小问题； 3、小问题与原有问题是完全类似的。;2、二分法;分治法所能解决的问题一般具有以下几个特征： （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。 （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。;6.2.5 贪心法;1、商场找零;2、最短距离;贪心法主要有以下两个特点： （1）贪心选择性质：算法中每一步选择都是当前看似最佳的选择，这种选择依赖于已做出的选择，但不依赖于未作出的选择。 （2）最优子结构性质：算法中每一次都取得了最优解（即局部最优解），要保证最后的结果最优，则必须满足全局最优解包含局部最优解。;6.2.6 动态规划;动态规划所处理的对象是多阶段决策问题。 多阶段决策问题，是指这样的一类特殊的活动过程，问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，形成一个决策序列，该决策序列也称为一个策略。;1、最短距离;2、背包问题;背包问题; 这个方程的含义是：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。 如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。;多阶段决策问题的最优化求解目标是获取导致问题最优值的最优决策序列（最优策略），即得到最优解。 动态规划思想实质是分治思想和冗余解决方法的结合。 动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生