计+算+机+常+用+算+法.ppt

计算机常用算法 安吉实验初中陈国锋 7 动态规划 1 穷举法 枚举法 2 递归法 3 回溯法 4 模拟法 6 分治法 5 贪心法 枚举法 穷举法 枚举法 通常也称为穷举法 是指在一个有穷的可能的解的集合中 枚举出集合中的每一个元素 用题目给定的约束条件去判断其是否符合条件 若满足条件 则该元素即为整个问题的解 否则就不是问题的解 枚举的思想往往是最容易想到的一种解题策略 枚举法从本质上说是一种搜索的算法 但适用枚举法解题必须满足下列条件 1 可预先确定解元素的个数n 且问题的规模不是特别大 2 对于每个解变量A1 A2 An的可能值必须为一个连续的值域 枚举法的算法流程 设ai1为解变量Ai的最小值 aik为解变量的最大值 其中1 i n A1 a11 a12 a1K A2 a21 A22 A2K Ai ai1 Ai2 AiK An an1 An2 AnK 我们称解变量为枚举变量 例如某问题的枚举变量有三个 A1 A2 A3 A1 1 2 A2 2 3 4 A3 5 6 7 则问题的可能解为 A1 A2 A3 1 2 5 1 2 6 1 2 7 1 3 5 1 3 6 1 3 7 1 4 5 1 4 6 1 4 7 2 2 5 2 2 6 2 2 7 2 3 5 2 3 6 2 3 7 2 4 5 2 4 6 2 4 7 在上述18个可能解的集合中 满足问题给定的检验条件的解元素即为问题的解 枚举法的优化方法 1 减少枚举的变量 在使用枚举法之前 先考虑一下解元素之间的关联 将一些非枚举不可的解元素列为枚举变量 其他元素通过计算得出解元素的可能值 例1 巧妙填数 将1 9这9个数字填入到9个空格中 每一横行的三个数字组成一个三位数 如果要使第二行的三个三位数是第一行的2倍 第三行的三位数是第一行的三倍 应怎样填数 如图 2 减少枚举变量的值域 3 分解约束条件 将拆分的约束条件嵌套在相应的循环体间 本题目有9个格子 要求填数 如果不考虑问题给出的条件 共有9 362880种方案 在这些方案中符合条件的即为解 因此可以用枚举法 但仔细分析问题 显然第一行的数不会超过400 实际上只要确定第一行的数就可以根据条件算出其他两行的数了 这样仅需枚举400次 例2 有四个学生 上地理课时提出我国四大淡水湖的排序如下 甲 洞庭湖最大 洪泽湖最小 鄱阳湖第三 乙 洪泽湖最大 洞庭湖最小 鄱阳湖第二 太湖第三 丙 洪泽湖最小 洞庭湖第三 丁 鄱阳湖最大 太湖最小 洪泽湖第二 洞庭湖第三 对于各个湖泊应处的地位 每个人只说对了一个 根据以上情况 编程序判断各个湖泊应处的地位 算法分析 本题是一个逻辑判断题 一般的逻辑判断题都采用枚举法进行解决 四个湖的大小分别可以有4 24种排列可能 因为24比较小 因此我们对每种情况进行枚举 然后根据给定的条件判断哪些符合问题的要求 源程序 例3 最佳游览路线 某旅游区的街道成网格状 其中东西向的街道都是旅游街 南北向的街道都是林阴道 由于游客众多 旅游街被规定为单行道 游客在旅游街上只能从西向东走 在林阴道上则既可从南向北走 也可以从北向南走 阿龙想到这个旅游街游玩 他的好友阿福给了他一些建议 用分值表示所有旅游街相邻两个路口之见的街道值得游览的程度 分值是从 100到100的整数 所有林阴道不打分 所有分值不可能全是负分 如图 北 南 东 西 输入数据 输入文件是input txt 文件的第一行是两个整数m和n 之间用一个空格隔开 m表示有多少条旅游街 1 m 100 n表示有多少条林阴道 1 n 20001 接下来的m行依次给出了由北向南每条旅游街的分值信息 每行有n 1个整数 依次表示了自西向东旅游街每一小段的分值 同一行相邻两个数之间用一个空格隔开 输出数据 输出文件是output txt 文件只有一行 是一个整数 表示你的程序找到的最佳游览线路的总分值 Lij为第I条旅游街上自西向东第j段的分值 1 i m 1 j n 1 例如样例中L12 17 L23 34 L34 34 我们将网格状的旅游区街道以林阴道为界分为n 1个段 每一段由m条旅游街的对应成段 即第j段成为 L1j L2j Lmj 1 j n 1 由于浏览方向规定横向自西向东 纵向即可沿林阴道由南向北 也可由北向南 而横行的街段有分值 纵行无分值 因此最佳游览路现必须具备如下三个特证 1 来自若干个连续的段 每一个段中取一个分值 2 每一个分值是所在段中最大的 3 起点段和终点段任意 但途经段的分值和最大 设Li为第i个段中的分值最大的段 即Li max L1i L2i Lmi 1 i n 1 例如对于样例数据 L1 max 50 17 42 17 L2 max 47 19 3 3 L3 max 36 34 43 36 L4 max 30 13 34 34 L5 max 23 8 45 8 我们把段设为顶点 所在段的最大分值设为顶点的权 各顶点按自西向东的顺序相连 组成一条游览路线 显然 如果确定西端为起点 东端为终点 则这条游览路线的总分值最大 问题是某些段的最大分值可能是负值 而最优游览路线的起点和终点任意 在这种情况下 上述游览路线就不是最佳了 因此 我们只能枚举这条游览路线的所有可能的子路线 从中找出一条子路线i i 1 j 1 i j n 1 使得经过顶点的权和Li Li 1 Lj最大 算法 best 0 sum 0 fori 1ton 2doforj i 1ton 1dobeginsum sum Lj Li Lj ifsum bestthenbest sum end 显然 n在1 20001之间 时间复杂度比较高 于是 我们必须对这个算法进行优化 仍然从顶点1开始枚举最优路线 若当前子路线延伸至顶点时我们发现总分值sum 0 则应放弃当前的子路线 因为无论Li 1为何值 当前子路线延伸至顶点i 1后的总分值不会大于Li 1 因此应该从顶点i 1开始重新考虑新的子路线 优化后的算法 best 0 sum 0 fori 1ton 1dobeginsum sum Li Ifsum bestthenbest sum ifsum 0thensum 0 End 递归法 一个函数 过程 概念或数学结构 如果在其定义或说明内部直接或间接地出现有其本身的引用 或者是为了描述问题的某一状态 必须用到它的上一状态 而描述上一状态 又必须用到它的上一状态 这种用自己来定义自己的方法 称之为递归或者是递归定义 在程序设计中 过程或函数直接或者间接调用自己 就被称为递归调用 子程序直接调用自己 称为直接递归 嵌套关系的子程序a和b 内层的b调用外层的a 是间接递归 平级关系的子程序a和b 其中a调用了b b又调用了a 这也是间接递归 数学函数式递归 例1 阶乘n 1 2 3 n 1 n 算法分析 要求n 只需求出 n 1 因为n n n 1 要求出 n 1 只需求出 n 2 因为 n 1 n 1 n 2 所以可得到阶乘的递归定义式 programfactorial varn integer t longint functionfac n integer longint beginifn 0thenfac 1elsefac n fac n 1 end Beginwrite n readln n t fac n writeln n t End 例2 斐波那契数列0 1 1 2 3 5 8 13 21 34 55 从第三项开始 每一项是前两项的和 其递归定义式为 求此数列第n项 参考程序 varn integer functionfib n integer integer beginifn 0thenfib 0elseifn 1thenfib 1elsefib fib n 2 fib n 1 end beginwriteln inputn readln n ifn 0thenwriteln dataerror elsewriteln fib fib n end 例3 楼梯共有n层台阶 上楼可以一步走一层 也可以一步走两层 编程序计算上n层台阶共有多少种走法 离散事件的递归 例1 简单的背包问题 设有一个背包 可以防如入的重量为s 现有n件物品 重量分别为t1 t2 t3 ti tn ti 1 i n 均为正整数 从n件物品中挑选若干件 使得放入背包的重量之和正好为s 算法分析 用snap s n 代表这一问题 1 先取最后一个物品tn放入背包中 若tn s 正好放入包中 问题解决 输出结果 n tn 2 若tn1 那么问题可以转化为从剩下的n 1件物品中选取若干件 使得它们的重量和等于包里剩下的可放入重量 s tn 即snap s tn n 1 而选中的tn还要看后续的问题snap s tn n 1 是否有解 无解的话说明先取的tn不合适 就要放弃tn 在剩余物品中重新开始挑选 即有snap s n snap s n 1 3 若tn s 则不能放入包中 还得继续挑选 若还剩物品 即n 1 那么问题转化为从剩余n 1件物品中选取若干个 使得她们的重量和等于s 即snap s n snap s n 1 在2 3 中就出现了递归定义 而1 是有解时递归结束的条件 如果无解时 只有当2 3 中所剩的物品不够的话问题就不能继续执行 这也是递归结束的条件 回溯法 回溯是重要的算法之一 有一些问题 要求找到一组解 或要求找到一个满足某些限制的最优解 对于解决这样的问题 可以通过使用彻底的搜索方法来解决 然而 彻底搜索的运算量很大 有时大到计算机承受不了的程度 彻底的搜索 要进行大量的比较 大量的舍弃 以大量的运算 大量的时间为代价 因此 用穷举法解某些实际问题是不现实的 回溯算法为我们提供了一个好方法 使用回溯法可以大大减少实际的搜索 例如 迷宫问题 八皇后问题 骑士周游世界问题 算法思想 通过对问题的分析 找出一个解决问题的线索 然后沿着这个线索往前试探 若试探成功 就得到解 若试探失败 就逐步往回退 换别的路线再往前试探 实际上是广度与深度搜索结合的搜索 深度搜索过程中碰到条件不满足 则退回上一层 在每一层上也进行全面的搜索 关键 找到回溯的条件 求解八皇后问题 在n n个方块排成n行n列的棋盘上 如果两个皇后位于同一行 同一列或同一对角线上 则称它们互相攻击 现在要求找出使棋盘上n个皇后互不攻击布局 列号 8 2 4 1 7 5 3 6 分析 为了找出互不攻击的布局 需要对n n个方案进行检查 将有攻击的布局剔除掉 这是一种例举法 但这种方法对于较大的n 其工作量会急剧的增大 而逐一例举是没有必要的 算法 由于在第一行上的皇后在第一列 则第二行上的皇后就不可能在第一列 首先将每一行上安置一个皇后 并假设第i个皇后在第i行上 用一个一维数组queen 1 n 用于记录安放皇后的过程中随时记录第i行上的皇后所在的列号 由此可知 在这种情况下 实际上已经剔除了两个皇后在同一行的可能性 因此 在安置每一行上的皇后时 只需考虑每两个皇后不能在同一列或同一对角线上的可能性 从第一行 即i 1 开始布局 设前i 1行上的皇后已布局好 即它们互不攻击 现考虑安排第i行上皇后位置 使之与前i 1行上的皇后也互不攻击 为了实现这一点 可以从第i行皇后的当前位置开始向右搜索 引进集合a b c分别表示各列 各条右对角线和各条左对角线上是否放置了皇后 在同一右对角线上 i j是常量 在同一左对角线上 i j是常量 第i行第j列上放皇后在第i j条右对角线和第i j条左对角线上 能放皇后时为真 不能放皇后时为假 数组queen存放各行皇后所在的列号 骑士周游问题 骑士周游问题 给定一个n n的方阵 共有n2个区域 有一个国际象棋的马置于一个区域上 要求找到一条路径 使马按国际象棋的规则 从开始区域出发 不重复地把n2个区域都恰好经过一次 分析1 由于马按 日 字走 马从本区域起一步最多能达到八个区域 设马所在区域坐标为 i j 则下一步能达到的8个位置的坐标如下 分析2 马从初始位置 i j 开始 按8个方向 从 1 8 走 如下一位置在方阵中而且未到过 则马跳到该位置 继续走 如果8个方向的位置都不能落脚 则退一步 上一步为当前步 再按下一个方向继续试跳 算法 Procedure过程名 Begin准备初值 repeatwhile选择范围不超过边界且工作未完成dobegin分析条件 保证不满足条件不进行 if成功then进栈 由第选择开始进入下一层次 往下走 else本层更换选择 横向走 end if工作未完成then退栈 原来的上一层更换为下一选择 回溯 上层横向走 until全部工作完成 输出 end 随机数的介绍在自然界和日常生活中 许多现象具有不确定的性质 有些问题甚至很难建立数学模型 或者很难用计算机建立递推 递归 枚举 回溯法等算法 在这种情况下 一般采用模拟策略 在对实际问题中的随机现象进行数学模拟时 利用计算机产生的随机数是必不可少的 由于用计算机产生的随机数总是受字长的限制 其随机的意义要比实际问题中真实的随机变量稍差 因此 通常将计算机产生的随机数称为伪随机数 TURBO PASCAL的系统中有两个产生伪随机数的单元 Randomize过程 伪随机数发生器初始化 Random range 函数 产生一个范围在0 x range的伪随机数x range和x都为word类型 模拟法 模拟法 就是模拟某个过程 通过改变数学的各种参数 进而观察变更这些参数所引起过程状态的变化 一般题目给定或者隐含某一概率 设计者利用随机函数和取整函数设定某一范围的随机值 将符合概率的随机值作为参数 然后根据这一模拟的数学模型展开算法 模拟策略的关键 是如何按照概率的要求确定随机值的范围 这个随机值设计得好 模拟效果就好 例一 甲乙两人抓n个棋子 谁抓最后一个谁赢 每一次只能抓一个或两个 但不能为零个 甲方为计算机 对弈方为乙 由随机数替代 设计一个程序使计算机尽可能赢 输入 棋子数n 先下手的方k k b 对方先下 k a 计算机先下 输出 游戏过程 一行表示一步 现有棋子数 被抓走的棋子数 最后一行为赢方的名字 这个问题的算法核心是 要置对方于死地 必须使余下的棋子是1 2 3的整数倍 因此 当甲方处在棋子数是3的倍数时要小心等待 一旦对方错一步 赶紧控制余下棋子数为3的倍数 设 b 乙方抓走的棋子数 每一次轮到乙方抓时 则随机产生b 1 random 2 a 甲方抓走的棋子数 轮到甲方抓时 若剩余的棋子数非3的整数倍 则应使抓掉后是3的整数倍 若剩余的棋子数为3的整数倍 则随机产生a 1 random 2 计算过程如下 输入棋子总数n和先下手一方的名字kRandomize Whilen0dobeginifk b thenbeginx random 2 b 1 x ifn b 0thenbegin输出现有0枚棋子 乙方抓走n枚棋子 输出乙方赢 break endelsebeginn n b 输出现有n枚棋子 乙方抓走b枚棋子 K a End Elsebegina nmod3 ifa0then 若剩余棋子数为3的整数倍 则调整每次抓的棋数 elsex random 2 a 1 x ifn a 0thenbegin输出现有0枚棋子 甲方抓走n枚棋子 输出甲方赢 break end Elsebeginn n a 输出现有n枚棋子 甲方抓走a枚棋子 K b End End End 练习 假设有一堆小石子 二人轮流去取 谁拿走最后一颗石子便输 先让甲规定石子总数N以及每次最多取多少颗数k n 2 k 1 甲每次取a颗 N k a均为随机数 乙怎样取赢的可能性最大 设甲为计算机产生的随机数 乙为由你编的计算机程序 猜数游戏 人和计算机做猜数游戏 人默想一个四位数 由计算机来猜 计算机将所猜的数显示到屏幕上 并问两个问题 1 有几个数字猜对了 2 猜对的数字中有几个位置也对 人通过键盘来回答这两个问题 计算机一次又一次地猜 直到猜对为止 比如我们默想的一个数是5122 假定计算机第一次猜1166 然后问你 1 有几个数字猜对了 1 2 猜对的数字中有几个位置也对 1假定计算机第二次猜1287 1 有几个数字猜对了 2 2 猜对的数字中有几个位置也对 0假定计算机第三次猜5122 1 有几个数字猜对了 4 2 猜对的数字中有几个位置也对 4计算机显示最后猜中的数 并报告共猜了几次 问题1 编程实现这样一个猜数的游戏程序 屏幕显示格式为 第二行显示计算机所猜的四位数 第三行提问猜对的数字个数 用 Number 第四行提问位置对的数字个数 用 Position 第五行显示当前已猜的步数 用 Stepxx 注 其中末尾数字由键盘输入 最后给出结束信息 其他由编程者自定 问题2 仍是这样一个游戏 但要求计算机既是猜数者 又要模拟默想这个数的人 要猜的数由键盘输入 屏幕显示格式为 第一行显示人所默想的数 用 xxxx 第二行至第五行同问题1 只不过末尾数字不再由键盘输入 而是计算机判断后自动显示 问题3 从文本文件guess dat中读入20个四位数 一个接一个让计算机猜 统计猜中所需的总步数 算法分析 1 计算机随机产生一个猜数设m 当前的猜数集合 varm array 1 9000 ofinteger t integer m的长度 初始时m 1000 1001 9999 t 9000每一次猜数时 从m 1 m t 中随机取出一个四位数 该数即为计算机的一个猜数 若m集合为空 t 0 时还未猜中 则游戏以失败告终 计算机产生猜数的过程如下 functionget next integer beginift0thenget next m random t 1 elseget next 1 返回失败信息 End get next 计算机产生的猜数必须与m集合中的每一个四位数比较 以确定其中哪些四位数与猜数默想一方的应答信息相符 出于逐位比较的方便 我们将猜数由整数类型转化为整数数组类型 设 n 由计算机产生的猜数 即n get next now n转化为整数数组now 0 3 定义如下 typenowtype array 0 3 of0 9varnow nowtype 转化过程如下 procedureput n integer varnow nowtype beginforI 0to3dobeginnow 3 i nmod10 n ndiv10 end for end put 2 缩小猜数范围 计算机从m集合中随机产生一个猜数now后 默想方必须应答 由键盘输入或由计算机计算 猜对多少个数字 其中有多少个数字位置也对 根据这一信息 我们将m集合中的每一个元素与now比较 由比较结果确定哪些元素应从m集合中去除 设 key m集合中的某元素或默想数 其数据类型为nowtype Now 计算机产生的猜数 其数据类型亦为nowtype 我们通过test1 key now 函数计算key中有多少数字曾在now中出现 我们通过test2 key now 函数计算key中有多少数字曾在now中出现且位置一一对应 functiontest1 key now nowtype integer varh i j integer h为key和now中的相同数字个数 mark array 0 3 ofboolean now和key间有重复数字的标志 beginfillchar mark sizeof mark false mark初始化 h 0 forI 1to3do 依次搜索key中的每一个数字 beginj 0 在now中寻找与key i 相同的数字now j while jnow j or mark j doj j 1 ifj 3thenbeginmark j true h h 1 end then end for test1 h End test1 Functiontest2 key now nowtype integer varh integer beginh 0 forI 0todoifkey i now i thenh h 1 Test h End test2 我们通过test2 key now 函数计算key中有多少数字曾在now中出现且位置一一对应 当默想数为key 计算机产生的猜数为now时 我们可以通过调用上述两个函数猜出猜对的数字个数t1 t1 test1 key now 和猜对的数字中位置也对的数字个数t2 t2 test2 key now 若t14或者t24 则计算机将now与m集合中的每一个四位数一一比较 将m中与now的相同数字个数为t1且相同数字中位置对应的数字个数为t2的所有四位数m i 1t1 or test2 key now t2 then从m集合中剔除m i UntilI t 形成m的一个子集 m 1 m t 1t1 or test2 key now t2 thenbeginm i m t t t 1 I I 1 end then UntilI t End delete 算法流程 问题 1 的算法 forI 1to9000dom i I 999 t 9000 randomize Repeatn get next ifn 1thenbegin打印猜数失败西信息 halt end then Put n now 打印计算机产生的猜数now 输入猜对的数字个数t1和猜对数字中位置也对的数字个数t2 Delete now Until t1 4 and t2 4 问题2的算法 设step 猜中一个数的不数 step 0 m集合初始化 读默想数key Repeatn get next put n now t1 test1 key now t2 test2 key now 输出t1和t2 Step step 1 Delete now Until t1 4 and t2 4 问题3的算法 设total 猜中二十个数的总步数Total 0 Fork 0to19dobegin执行问题2的算法 Total total step End for 输出猜中20个数所需的总步数total 题目1 某国为了防御敌国的导弹袭击 发展出一种导弹拦截系统 但是这种拦截系统有一个缺陷 虽然它的第一发炮弹能够到达任意的高度 但是以后每一发炮弹都不能高于前一发的高度 某天 雷达捕捉到敌国的导弹来袭 由于该系统还在试用阶段 所以一套系统有可能不能拦截所有的导弹 输入导弹依次飞来的高度 雷达给出的高度不大于30000的正整数 计算要拦截所有的导弹最少需配备多少套这种导弹拦截系统 输入 导弹数n和n颗导弹依次飞来的高度 1 n 1000 输出 要拦截所有的导弹最少配备的系统数 贪心法 贪心法是从问题的某一个初始解出发 向给定的目标推进 但不同的是 推进的每一步不是依据某一固定的递推式 而是做一个当时看似最佳的贪心选择 不断地将问题实例归纳为更小的相似的子问题 并期望通过所做的局部最优选择产生出一个全局最优解 算法分析 k 当前配备的系统数 L k 被第k套系统拦截的最后一枚导弹的高度 简称系统k的最低高度 1 k n 1 设导弹1被系统1所拦截 k 1 L k 导弹1的高度 然后依次分析导弹2 3 导弹n的高度 2 若导弹i的高度高于所有系统的最低高度 则断定导弹i不能被这些系统所拦截 应增设一套系统来拦截导弹i k k 1 L k 导弹i的高度 3若导弹i的高度低于某些系统的最低高度 那么导弹I均可被这些系统所拦截 究竟选择哪个系统拦截可使得配备的系统数最少 采取贪心策略 选择其中最低高度最小 即导弹的的高度与系统最低高度最接近 的一套系统p L p min L j L j 导弹的的高度 L p 导弹的的高度 这样 可以使得被一套系统拦截的导弹数尽可能增多 4 依次类推 直至分析了n枚导弹的高度为止 此时得出的k便为应配备的最少系统数 K 1 L 1 导弹1的高度 ForI 2tondobeginp 0 forj 1tokdoif L j 导弹I的高度 and p 0 or L j L p thenp j Ifp 0thenbegink k 1 L k 导弹I的高度 endelseL p 导弹I的高度 End 输出应配备的最少系统数k 旅行家问题一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市 假设出发时油箱是空的 给定两城市之间的距离D1 汽车油箱的容量C 以升为单位 每升汽油能行驶的距离D2 出发时每升汽油价格为p 沿途有N个油站 1 N 100 油站离出发点的距离为di 该油站每升汽油的价格为pi i 1 n 计算结果四舍五入至小数点后两位 如果无法到达目的地 则输出 Nosolution 输入 D1 C D2 P N以下含n行 其中第 1 i n 行为油站号i该油站距出发点的距离di该油站每升汽油的价格Pi输出 最少的费用 分治策略指的是分而治之的方法 当我们处理大规模问题时 求解可能比较困难 对于这类问题 我们可以将原问题分解成规模较小而结构与原问题相似的子问题 然后递归地解决这些子问题 最后由这些小问题的解构造出原问题的解 因此一个问题能否用分治法解决 关键是看该问题算法能否将原问题分成n个规模较小而结构与原问题相似的子问题 递归地解决这些子问题 然后合并其结果就得到原问题的解 当n 2时的分治法又称二分法 分治策略一般分为三个步骤 1 分解 将要解决的问题划分成若干个规模较小的同类问题 2 求解 当子问题划分得足够小时 用较简单的方法解决 3 合并 按原问题的要求 将子问题的解逐层合并成原问题的解 使用分治策略的问题常常要借助递归的结构 逐层求解 当问题规模达到某个简单情况时 解容易直接得出 而不必继续分解 其过程大致如下 分治策略 If问题不可分thenbegin直接求解 返回问题的解 elsebegin从原问题中划分出含1 n运算对象的子问题1 递归调用分治法过程 求出解1 从原问题中划分出含1 n运算对象的子问题2 递归调用分治法过程 求出解2 从原问题中划分出含1 n运算对象的子问题n 递归调用分治法过程 求出解n 将解1 解2 解n组合成整个问题的解 end 例1 求一组数中的最大值和最小值 算法分析 假设数据个数为n 存放在数组A 1 n 中 可以直接进行比较 min a 1 max a 1 fori 2tondoifa i maxthenmax a i elseifa i minthenmin a i 使用分治策略 把n n 2 个数据先分成两组 分别求最大值 最小值 然后分别将这两组的最大值和最小值进行比较 求出全部元素的最大值和最小值 若分组后元素个数还大于2 则再次分组 直至组内元素小于等于2 使用这一算法 比较次数为2 n 1 若n 10 则比较18次 源程序 例2 赛程问题有n个编号为1到n的运动员参加某项运动的单循环比赛 即每个运动员要和所有其他运动员进行一次比赛 试为这n个运动员安排一个比赛日程 使得每个运动员每天只能进行一场比赛 且整个比赛在n 1天内结束 输入数据 运动员人数n n0时 A i j 表示第i名运动员在第j天的比赛对手 算法分析 由于n个运动员要进行单循环比赛 且在n 1天内要结束全部比赛 经过分析 当且仅当n为2的整数次幂时 问题才有解 当然解是唯一的 这样可以将运动员分成两组 1 2 n 2和n 2 1 n 2 2 n 给第一组运动员安排一个比赛日程 得到一个n 2阶的方阵A1 同时给第二组的运动员安排一个比赛日程 同样得到一个n 2阶的方阵A2 考虑到比赛的性质 设定第i个运动员在某一天的比赛对手为第k个运动员 则第k个运动员在同一天的比赛对手必然是第i个运动员 即若有A i j k 则A k j i 因此原问题的解可以由分解后的两个子问题的解合并起来 同时每一个子问题又可以按照上述二分法分解下去 直至每个组中仅有2个运动员时为止 源程序 例3 设有20名学生的姓名 数学成绩 按照字典顺序存放学生姓名及其相对应的成绩于数组中 现从键盘输入一个学生的姓名 编程查找该学生是否在这20个学生中 如果在 请输出他的姓名及数学成绩 否则输出 NOFOUND 解析 1 根据题意 其数据存储结构为记录型数组 有两个域 姓名域 数学成绩域 2 数组中存放的数据 按照字典顺序存放学生姓名及相应成绩 3 查找一个学生的姓名及相应成绩 可以用顺序查找 即从第一个学生姓名开始 顺次查找到所需要的学生姓名 其时间复杂度为O n 4 采用二分查找 其时间复杂度为O long2n 算法如下 首先看将要查找学生的姓名与中间位置的a mid name是否相同 若相同则查找成功 输出该学生姓名和成绩 若查找学生姓名顺序大于中间位置学生姓名 则余下查找在数据序列的后半部分查找 若查找学生姓名顺序小于中间位置学生姓名 则余下查找在数据序列的前半部分查找 重复以上三步操作 直到查找到或查无此人为止 从以上的二分查找算法可以看出 他是将原问题的规模 化为子问题 对半 其子问题的算法与原问题相同 通过不断减少查找范围 快速查找所需要的数据 因此 这是一个高效算法 例4 AB两地的距离为S公里 甲 乙 丙三人从A地到B地共同完成任务 从A地出发时 A地有X Y两种出租车可供利用 已知三人步性速度都为V1 出租车Y速度为V2 并仅能载一人 出租车X的速度为V3 能载两人 问题是从A出发时X只能载一人 回头接人时才能载两人 试问怎样安排行程 才能使甲 乙 丙三人尽快同时到达B地后共同完成任务 已知V1 V2 V3 问题解析 1 从问题可以看出 要尽快同时到达B 则甲 乙 丙需要充分利用X Y两种出租车 2 根据图示可以说明安排方法 3 假设C点表示出租车X先载一人 设甲 的下车点 然后回头接乙 丙相遇于D点 4 D点表示出租车Y先载人 设乙 到E点下车 回头接丙相遇于G点 再回头追到乙于D点 这时出租车X正好到达D点 5 由此可以看出 甲乘车到C 从C步行到B 乙乘Y车到E 然后步行到D 再从D乘X车到达B地 丙步行到G点 被出租车Y接到D点会同乙乘出租车X到达B地 分治法 假设取AB的中点作为出租车X载甲的下车点 计算结果若甲先到达B 则实验点用折半方法往出发点靠 反之若乙丙先到达B则甲的下车点要向B靠 即在接近B的一半求新的实验点 这里设出发点到甲下车点的距离为k当确定甲下车点C后 接着用同样方法测试D点位置 此时测试区域为AC 确定点为D 在C D测试点确定后 再用二分法对区间AD试探乙乘出租车Y的下车点E 源程序 动态规划是对最优化问题的一种新的算法设计方法 在实际生活中 有这样的一类问题 它们的活动过程可以分为若干个阶段 而且在任意一个阶段x 过程在阶段x以后的行为 仅依赖于x阶段的过程状态 而与x之前过程如何达到这种状态的方式无关 这样的过程就构成一个多阶段决策过程 由此提出了解决这类问题的 最优化原理 创建了最优化问题的一种新的算法设计方法 动态规划 动态规划解题方法是一种高效率的解题方法 可以解决相当大的信息量 其时间复杂度通常为O n2 O n3 等 它适用的原则是优化原则 它可以将整体优化分解为若干个局部优化 动态规划算法 动态规划算法的一般模式 1 划分阶段 按照问题的时间或空间特征 把问题分为若干个阶段 在划分阶段时 注意有序或可排序 2 确定状态和状态变量 将问题发展到各个阶段时所处的各种情况用不同状态表示出来 3 确定决策并写出状态转移方程 一般是根据相邻两个阶段各状态之间的关系来确定决策 4 寻找终止条件 给出的状态转移方程是一个递推式 必须有一个递推的终止条件 5 编写程序 例如 求从A点到D点的最短路径 通过三段路程的最短路径可以用各自的最短路径 求他们的和 其和为AB BC CD的最短路径之和 将其作为整个问题的最短路径 且其解法为最优解 算法分析 穷举法 时间复杂度 n1 n2 n3 贪心法 时间复杂度 n1 n2 n3 可行 动态规划算法的应用 例1 设有一个三角形的数塔 顶点为根结点 每个结点有一个整数值 从顶点出发 可以向左走或向右走 如图 从根结点13出发向左 向右的路径长度可以是 13 11 7 14 7 其和为5213 11 12 14 13 其和为63若要求从根结点开始 找出一条路径 使路径之和最大 若存在多条请输出任意一条 解析 1 用穷举法 从根结点开始 将所有可能的路径求和 找出最大值 但算法时间复杂度使问题成为不可能 当N 1 P 1N 2 P 2N 3 P 4 N k P 2k 1 当N 50 P 249 500万亿条路径 2 用贪心法 本题若用贪心法则 13 11 12 14 13 其和为63 实际上存在另一条路径 13 8 26 15 24 其和为86 贪心法问题所在 眼光短浅 3 动态规划求解 动态规划求解问题的过程归纳为 自顶向下分析 自底向上计算 基本方法 划分阶段 按三角形的行 划分阶段 若有n行 则有n 1个阶段 找到问题求解的最优途径 A 从根结点13出发 选取它的两个方向中的一条支路 选择的依据是比较两个支路中其路径和最大的支路 B 设x为从11出发到底端的最大路径值 y为从8到底端的最大路径值 C ifx ythen选择x且取得最大和为13 xelse选择y且取得最大和为13 y这样 原先求根结点到底端的最大路径问题 变为从11出发和和从8出发求路径和的子问题 同理 求从11出发到底端的最大路径问题可以转化为从12出发和从7出发的最大路径问题 决策 路径和最大 状态转移方程 Fi max Fi 1 左 Fi 1 右 A 当到倒数第二层时 每个结点其后继仅有两个结点 可以直接比较 选择最大值为前进方向 从而求得从根结点开始到底端的最大路径 终止条件 B 自底向上计算从底层开始 本身数即为最大数 倒数第二层的计算 取决于底层的数据 12 6 18 13 14 27 24 15 39 24 8 32最后的路径为 13 8 26 8 24 4 数据结构及算法设计 A 图形转化 直角三角形 便于搜索 向下或向右B 用三维数组表示数塔 a x y 1 表示行 列及结点本身数据a x y 2 表示能够取得最大值a x y 3 表示前进方向 0向下 1向右 C 算法 数组初始化 输入每个结点值以及初始的最大路径 前进方向0 从倒数第二层开始向上一层求最大路径 共循环n 1次 从顶向下 输出路径 关键是j的值 由于行逐渐递增 表示向下 究竟是向下还是向右取决于列的值 若j的值比原先多1则向右 否则向下 源程序分析 例2 求一组数列的最长不下降序列 问题描述 设有一个正整数序列b1 b