算法语言与数据结构(第5章).ppt

算法语言与数据结构 信息与物流管理系王健 西安财经学院管理学院 第5章函数 第5章函数 程序 6 3 cpp 验证素数程序 作者 wuwh 编制时间 2002年10月20日 主要功能 可验证某数是否为素数 include 预编译命令 include 预编译命令intcheckprime int 子函数声明intmain 主函数 inta 0 定义整型变量 初始化为0cout a 键盘输入一个整数 用实参a调用子函数 该子函数的 返回值作为if语句的分支条件if checkprime a checkprime a 为1cout a 是素数 endl else checkprime a 为0cout a 不是素数 endl 主函数结束 第5章函数 用实参a调用子函数 该子函数的 返回值作为if语句的分支条件if checkprime a checkprime a 为1cout a 是素数 endl else checkprime a 为0cout a 不是素数 endl 主函数结束 第5章函数 Tcheckprime a Fcout a cout a 是素数 endl 不是素数 endl 第5章函数 boolcheckprime intb 子函数 b为形式参数 intk 0 定义整型变量 并初始化for k 2 k sqrt double b k 循环 if b k 0 如果b能够被k整除 则返回0 可理解为 抢先 返回0 有了return0 后面的return1不起作用了return0 return1 b不能被k整除 则返回1 第5章函数 boolcheckprime intb intk 0 for k 2 k sqrt double b k if b k 0 return0 return1 第5章函数 boolcheckprime intb 子函数 intk 0 形式参数for k 2 k sqrt double b k K 1 if b k 0 return0 return1 b不能被k整除 则返回1 说明b是质数 第5章函数 讲这一程序的目的 如何定义一个函数主函数怎样调用子函数实在参数和形式参数返回值是什么意思 主函数与子函数的配合 主函数通过实参去调用子函数将实参赋给子函数中的形参 子函数运算之后 又将调用结果返回给主函数一个值 这个值作为主函数判断该实参是素数与否的根据 两者配合得天衣无缝 第5章函数 在checkprime intb 函数中 有return0和return1两处不同 如果先有return0了 后面一条return1就不起作用了 不会既执行return0又执行return1 第5章函数 函数的说明放在主函数之前 告诉系统有自定义的子函数可以被调用 例 boolcheckprime int 函数的定义函数返回值的类型函数名 类型名形式参数1 类型名形式参数2 函数体说明部分语句部分 形式参数和实在参数boolcheckprime intaf 定义af是形式参数 特点 1 未被调用不占内存单元 2 被调用后系统为其分配内存单元 3 调用结束释放内存单元 4 作用域限定在子函数内 属于局部变量 被调用函数嵌套在if语句中 a是实在参数if checkPrime a 主函数调用checkPrime af 子函数形式参数 实在参数是一个具有确定值的表达式一个函数在调用子函数时 要将实在参数赋给形式参数调用时1717实在参数a形式参数af 调用输入a子函数if checkPrime a checkPrime af 执行if语句for i 2 3 1 0af i 0 0输出输出return0return1a是质数a不是质数返回 intmain inta 0 cout a if checkprime a boolcheckprime intb intk 0 for k 2 k sqrt double b k if b k 0 return0 return1 cout a 是素数 endl elsecout a 不是素数 endl 美声唱法歌手大奖赛裁判人数n 10 打分范围60 x 100 10人中打分的最大值max10人中打分的最小值min10人打分总和为sum选手最后得分为 sum Max Min N 2 程序 6 2 cpp 作者 wuwh 编制时间 2002年10月20日 主要功能 给歌手打分 include includeintMax int int intMin int int intmain intp 0 intq 100 intsum 0 x 0 inti 1 for i 1 i x p Max x p q Min x q sum sum x cout 选手得分 sum p q 10 2 intMax inta intb if a b returna elsereturnb intMin intc intd if c d returnc elsereturnd 问题 编程求解 现假定n 6 k 4思路 1 该式可分解为2 定义一个函数 i 1 2 nl k 让l 4 i 1 2 6这个函数可以表示 3 再定义一个函数让m n i 1 2 m 即可得解 程序 6 2 cpp 作者 wuwh 编制时间 2002年10月12日 主要功能 求幂函数的和 介绍函数 include 预编译命令constintn 6 定义常量n为6constintk 4 定义常量k为4intSOP intm intl 声明函数SOPintpower intp intq 声明函数power 输出结果 其中SOP n k 为被调用函数intmain 主函数 cout Sumof k 提示信息 fromthpowersofintegers1to n is SOP n k endl 以下函数是被主程序调用的函数 功能 计算1 2 m的l次幂的和intSOP intm intl m l为形参 inti sum sum 0 初始化累加器for i 1 i m i sum sum power i l 累加returnsum 返回值 以下函数是被函数sop n k 调用的函数 功能 计算p的q次幂intpower intp intq inti product product 1 初始化累乘器for i 1 i q i product product p 累乘returnproduct intSOP intm intl m6l4power 1 l 1intpower intp intq power 2 l 116intpower intp intq 16power m l 1296intpower intp intq 22751296 数据类型函数名 形式参数表 例 intpower intp intn power为函数名 要以英文字母开头 int是函数值的数据类型 这里是int 整型 intp intn 括号中的p n为函数的形式参数 形式参数也要定义其数据类型 函数定义的一般格式 形式参数与实在参数 1 形式参数是在定义函数时放在函数名后括号中的参数 在未进行函数调用时 并不对形式参数分配内存单元 在发生函数调用时 立刻给形式参数分配内存单元 调用结束后 释放掉行参所占的内存单元 2 因此 形参变量属于局部变量 其作用域在它所在的函数体内 3 在定义函数的时候 必须指定形参变量的类型 如下所示 intpower intp intn 函数体 c 4 实在参数是一个具有确定值的表达式 函数在调用时 将实在参数赋给形式参数 比如 主函数调用SOP n k 这时 n k为实在参数 n的值为6 k的值为4 在被调用函数定义中 intSOP m l 中的m l为形式参数 在SOP被调用时 系统给m l这两个形式参数分配了内存单元 之后 n的值6赋给m k的值4赋给l power i l 处在SOP m l 函数中 表示SOP函数去调用power函数 其中i l为实在参数 而intpower p q 中的p q为形式参数 比如 执行SOP 6 4 时 l 4 m 6 当i 1时 sum sum power 1 4 这里1 4为实在参数 调用power p q 两个形式参数p q分别被赋以1 4 递推是计算机数值计算中的一个重要算法 可以将复杂的运算化为若干重复的简单运算 充分发挥计算机长于重复处理的特点 现举一例 递推 例5 3 A B C D E五人合伙夜间捕鱼 凌晨时都疲惫不堪 各自在河边的树丛中找地方睡着了 日上三竿 A第一个醒来 他将鱼平分作五份 把多余的一条扔回湖中 拿自己的一份回家去了 B第二个醒来 也将鱼平分为五份 扔掉多余的一条 只拿走自己的一份 接着C D E依次醒来 也都按同样的办法分鱼 问五人至少合伙捕到多少条鱼 每个人醒来后看到的鱼数是多少条 解题思路 假定A B C D E五人的编号分别为1 2 3 4 5 整数数组fish k 表示第k个人所看到的鱼数 fish 1 表示A所看到的鱼数 fish 2 表示B所看到的鱼数 fish 1 为五人合伙捕鱼的总鱼数fish 2 fish 1 1 4 5fish 3 fish 2 1 4 5fish 4 fish 3 1 4 5fish 5 fish 4 1 4 5 写成一般式fish i fish i 1 1 4 5i 2 3 5这个公式可用于知A看到的鱼数去推算B看到的 再推算C看到的 现在要求的是A看到的 能否倒过来 先知E看到的再反推D看到的 直到A看到的 为此将上式改写为 fish i 1 fish i 5 4 1i 5 4 2 分析上式 当i 5时 fish 5 表示E醒来所看到的鱼数 该数应满足被 整除后余 即fish 5 5 12 当i 5时 fish i 1 表示D醒来所看到的鱼数 这个数既要满足fish 4 fish 5 5 4 1又要满足fish 4 5 1显然 fish 4 不能不是整数 这个结论同样可以用至fish 3 fish 2 和fish 1 3 按题意要求5人合伙捕到的最少鱼数 可以从小往大枚举 可以先让E所看到的鱼数最少为6条 即fish 5 初始化为6来试 之后每次增加5再试 直至递推到fish 1 得整数且除以5之后的余数为1 根据上述思路 我们可以构思如下的程序框图 该图可分为三部分 1 是说明部分 包含定义数组fish 6 并初始化为1和定义循环控制变量i 并初始化为0 2 是do while直到型循环 其循环体又含两块 2 1是枚举过程中的fish 5 的初值设置 一开始fish 5 1 5 以后每次增5 2 2是一个for循环 i的初值为4 终值为1 步长为 1 该循环的循环体是一个分支语句 如果fish i 1 不能被4整除 则跳出for循环 使用break语句 否则 从fish i 1 算出fish i 当由break语句让程序退出循环时 意味着某人看到的鱼数不是整数 当然不是所求 必须令fish 5 加5后再试 即重新进入直到型循环dowhile的循环体 当着正常退出for循环时 一定是控制变量i从初值4 一步一步执行到终值1 每一步的鱼数均为整数 最后i 0 表示计算完毕 且也达到了退出直到型循环的条件 3 输出计算结果 程序名 5 3 c 五人合伙捕鱼 作者 wuwh 编制时间 2002年10月2日 主要功能 递推算法的实现 include 预编译命令voidmain 主函数 intfish 6 1 1 1 1 1 1 整型数组 记录每人醒来后看到的鱼数inti 0 do fish 5 fish 5 5 让E看到的鱼数增5 for i 4 i 1 i if fish i 1 4 0 break 跳出for循环elsefish i fish i 1 5 4 1 计算第i人看到的鱼数 while i 1 当i 1继续做do循环 输出计算结果for i 1 i 5 i printf fish d d I fish i 3121A2496B1996C1596D1276E 递推数列的定义一个数列从某一项起 它的任何一项都可以用它前面的若干项来确定 这样的数列称为递推数列 表示某项与前面若干项的关系称为递推公式 例如 1 2 n 1 n 令fact n 为n的阶乘fact n n fact n 1 通项公式 fact 1 1 边界条件 递归 递归算法在可计算性理论中占有重要地位 它是算法设计的有力工具 对于拓展编程思路非常有用 就递归算法而言并不涉及高深数学知识 只不过初学者要建立起递归概念不十分容易 我们先从一个最简单的例子导入 递归及其实现 用递归算法求n 定义 函数fact n n fact n 1 n 1 则有fact n nfact n 1 已知fact 1 1 为了表述得直观清晰 我们定义两个结点 或结点和与结点 图示的直观性与思维助力 1 或结点 A为 或结点 A依不同条件会有两种不同的取值 B或C 结点用表示 如果有多于2种取值 可用下图 条件为Z1 Z2 Zn 取值为B或C 或G 2 与结点 与结点要涂实心 相关联的B与C之间要用弧线连起来 A为与结点 A的最终取值为C结点的值 但为了求得C的值 得先求出B结点的值 C是B的函数 仍以求n 为例画出如下与或图 A为或结点 B为直接可解结点 值为1 C为与结点 当n 1时 A的取值即C的值 而C的值即E的值 为了求得E的值 需要先求出D的值 D值fact n 1 乘以n即为E的值 与结点可能有多个相关联的点 这时可描述为下图 A结点的值最终为D的值 但为了求D需先求B和C 从图上看 先求左边的点才能求最右边的点的值 我们约定最右边D点的值就是A结点的值 下面我们以3 为例来画与或结点图 目的是体会递归的含义 C 1D 2 C 2B D 2E 3 B 3 2 6A E 6 下面画出了调用和返回的递归示意图 从图可以想象 欲求fact 3 先要求fact 2 要求fact 2 先求fact 1 就象剥一颗圆白菜 从外向里 一层层剥下来 到了菜心 遇到1的阶乘 其值为1 到达了递归的边界 然后再用fact n n fact n 1 这个普遍公式 从里向外倒推回去得到fact n 的值 为了把这个问题说得再透彻一点 我们画了如下的流程图 为了形象地描述递归过程 将上图改画成下图 在这个图中 内层 与 外层 有着相同的结构 它们之间 你中有我 我中有你 呈现相互依存的关系 为了进一步讲清递归的概念 将递归与递推做一比较 仍以求阶乘为例 递推是从已知的初始条件出发 逐次去求所需要的阶乘值 如求3 初始条件fact 1 1fact 2 2 fact 1 2fact 3 3 fact 2 6 这相当于从菜心 推到 外层 而递归算法的出发点不放在初始条件上 而放在求解的目标上 从所求的未知项出发逐次调用本身的求解过程 直到递归的边界 即初始条件 就本例而言 读者会认为递归算法可能是多余的 费力而不讨好 但许多实际问题不可能或不容易找到显而易见的递推关系 这时递归算法就表现出了明显的优越性 下面我们将会看到 递归算法比较符合人的思维方式 逻辑性强 可将问题描述得简单扼要 具有良好的可读性 易于理解 许多看来相当复杂 或难以下手的问题 如果能够使用递归算法就会使问题变得易于处理 下面举一个尽人皆知的例子哈诺 Hanoi 塔问题 故事 相传在古代印度的Bramah庙中 有位僧人整天把三根柱子上的金盘倒来倒去 原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去 移动过程中恪守下述规则 每次只允许移动一只盘 且大盘不得落在小盘上面 有人会觉得这很简单 真的动手移盘就会发现 如以每秒移动一只盘子的话 按照上述规则将64只盘子从一个柱子移至另一个柱子上 所需时间约为5800亿年 怎样编写这种程序 思路上还是先从最简单的情况分析起 搬一搬看 慢慢理出思路 1 在A柱上只有一只盘子 假定盘号为1 这时只需将该盘从A搬至C 一次完成 记为move1fromAtoC 演示 1 2 在A柱上有二只盘子 1为小盘 2为大盘 第 1 步将1号盘从A移至B 这是为了让2号盘能移动 第 2 步将2号盘从A移至C 第 3 步再将1号盘从B移至C 这三步记为 演示 2 1 move1fromAtoB move2fromAtoC move3formBtoC 3 在A柱上有3只盘子 从小到大分别为1号 2号 3号第 1 步将1号盘和2号盘视为一个整体 先将二者作为整体从A移至B 给3号盘创造能够一次移至C的机会 这一步记为move 2 A C B 意思是将上面的2只盘子作为整体从A借助C移至B 第 2 步将3号盘从A移至C 一次到位 记为move3fromAtoC第 3 步处于B上的作为一个整体的2只盘子 再移至C 这一步记为move 2 B A C 意思是将2只盘子作为整体从B借助A移至C 所谓借助是什么意思 等这件事做完了不言自明 move 3 A B C 3 演示 移动3个盘子的分解 move 3 A B C 2 1 3 4 从题目的约束条件看 大盘上可以随便摞小盘 相反则不允许 在将1号和2号盘当整体从A移至B的过程中move 2 A C B 实际上是分解为以下三步第 1 1步 move1formAtoC 第 1 2步 move2formAtoB 第 1 3步 move1formCtoB 经过以上步骤 将1号和2号盘作为整体从A移至B 为3号盘从A移至C创造了条件 同样 3号盘一旦到了C 就要考虑如何实现将1号和2号盘当整体从B移至C的过程了 实际上move 2 B A C 也要分解为三步 第 3 1步 move1formBtoA 第 3 2步 move2formBtoC 第 3 3步 move1formAtoC 5 看move 2 A C B 是说要将2只盘子从A搬至B 但没有C是不行的 因为第 1 1步就要将1盘从A移到C 给2盘创造条件从A移至B 然后再把1盘从C移至B 看到这里就能明白借助C的含义了 因此 在构思搬移过程的参量时 要把3个柱子都用上 6 定义搬移函数move n A B C 物理意义是将n只盘子从A经B搬到C 考虑到前面已经研究过的 1 2 3 步 可以将搬移过程用如下的与或结点图表示 这里用与或结点的含义是分解为 1 2 3 步 这3步是相关的 相互依存的 而且是有序的 从左至右执行 move n A B C 分解为3步 1 move n 1 A C B 理解为将上面的n 1只盘子作为一个整体从A经C移至B 2 输出n AtoC 理解将n号盘从A移至C 是直接可解结点 3 Move n 1 B A C 理解为将上面的n 1只盘子作为一个整体从B经A移至C 这里显然是一种递归定义 当着解move n 1 A C B 时又可想到 将其分解为3步 第1步 将上面的n 2只盘子作为一个整体从A经B到C move n 2 A B C 第2步 第n 1号盘子从A直接移至B 即n 1 AtoB 第3步 再将上面的n 2只盘子作为一个整体从C经A移至B move n 2 C A B 下面 我们还是以3只盘子为例画出递归的与或图 这个图很象一颗倒置着的树 结点move 3 A B C 是树根 与结点是树的分枝 叶子都是直接可解结点 程序 6 hanoi2002 cpp 作者 wuwh 编制时间 2002年10月13日 主要功能 用递归求解Hanoi问题 include 预编译命令intstep 1 整型全局变量 预置1 步数voidmove intm charp charq charr 声明要用到的被调用函数voidmain 主函数 主程序开始intn 整型变量 n为盘数 printf 请输入盘数n 提示信息scanf d 调用函数move n a b c 主函数结束 以下函数是被主程序调用的函数 函数名 move 输入 m 整型变量 表示盘子数目 p q r为字符型变量 表示柱子标号 返回值 无voidmove intm charp charq charr 自定义函数体开始if m 1 如果m为1 则为直接可解结点 直接可解结点 输出移盘信息printf d move1 fromptor step step 步数加1 else 如果不为1 则要调用move m 1 move m 1 p r q 递归调用move m 1 直接可解结点 输出移盘信息printf d move dfromptor step m step 步数加1move m 1 q p r 递归调用move m 1 自定义函数体结束 m n n 1c m n m 0 n 0n mn m c m 1 n c m 1 n 1 c m 1 n c m 1 n 1 0m1 程序 6 7 cpp 编制时间 2002年10月28日 主要功能 计算组和数C m n include 预编译命令Usingnamespacestd 计算C m n 即从m个数中取n个数的组合数intC intm intn if m 0 n 0 m n return0 if m n C m m 1return1 if n 1 C m 1 mreturnm C m n C m 1 n C m 1 n 1 returnC m 1 n C m 1 n 1 intmain 主函数开始 测试一些结果cout C 6 0 Cmn 6 0 endl cout C 6 1 Cmn 6 1 endl cout C 6 2 Cmn 6 2 endl cout C 6 6 Cmn 6 6 endl return0 主函数结束 递归算法举例 青蛙过河 讨论问题 青蛙过河 该题是2000年全国青少年信息学奥林匹克的一道试题 叙述如下 一条小溪尺寸不大 青蛙可以从左岸跳到右岸 在左岸有一石柱L 面积只容得下一只青蛙落脚 同样右岸也有一石柱R 面积也只容得下一只青蛙落脚 有一队青蛙从尺寸上一个比一个小 我们将青蛙从小到大 用1 2 n编号 规定初始时这队青蛙只能趴在左岸的石头L上 按编号一个落一个 小的落在大的上面 不允许大的在小的上面 在小溪中有S个石柱 有y片荷叶 规定溪中的柱子上允许一只青蛙落脚 如有多只同样要求按编号一个落一个 大的在下 小的在上 而且必须编号相邻 对于荷叶只允许一只青蛙落脚 不允许多只在其上 对于右岸的石柱R 与左岸的石柱L一样允许多个青蛙落脚 但须一个落一个 小的在上 大的在下 且编号相邻 当青蛙从左岸的L上跳走后就不允许再跳回来 同样 从左岸L上跳至右岸R 或从溪中荷叶或溪中石柱跳至右岸R上的青蛙也不允许再离开 问在已知溪中有S根石柱和y片荷叶的情况下 最多能跳过多少只青蛙 思路 1 简化问题 探索规律 先从个别再到一般 要善于对多个因素作分解 孤立出一个一个因素来分析 化难为易 2 定义函数Jump s y 最多可跳过河的青蛙数其中 S 河中柱子数y 荷叶数 3 先看简单情况 河中无柱子 S 0 Jump 0 y 当y 1时 Jump 0 1 2 第一步 1 跳到荷叶上 第二步 2 从L直接跳至R上 第三步 1 再从荷叶跳至R上 如下图 1 2 当y 2时 Jump 0 2 3 1 2 3 3只青蛙落在L上 第一步 1 从L跳至叶1上 第二步 2 从L跳至叶2上 第三步 3 从L直接跳至R上 第四步 2 从叶2跳至R上 第五步 1 从叶1跳至R上 采用归纳法 Jump 0 y y 1 再看Jump S y 先看一个最简单情况 S 1 y 1 从图上看出需要9步 跳过4只青蛙 1 青蛙从L Y 2 青蛙从L S 1 青蛙从Y S 3 青蛙从L Y 4 青蛙从L R 3 青蛙从Y R 1 青蛙从S Y 2 青蛙从S R 1 青蛙从Y R 表一 为了将过河过程描述得更清楚 我们给出了表1 表中L1L2L3L4表示左岸石柱上落在一起的青蛙的高度位置 L1在最上面 L4在最下面的位置 引入这个信息就可比较容易地看出对青蛙占位的约束条件 同理R1R2R3R4也是如此 对水中石柱S 也分成两个高度位置S1S2 对荷叶Y无须分层 因为它只允许一只青蛙落在其上 t 0为初始时刻 青蛙从小到大落在石柱L上 t 1为第一步 1 从L跳至荷叶Y上 L上只剩2 3 4 T 2为第二步 2 从L跳至石柱S上 处在S2位置上 L上只剩3 和4 T 3为第三步 1 从Y跳至S 将Y清空 这时你看 S上有1 2 L上有3 4 好象是原来在L上的4只青蛙 分成了上下两部分 上面的2只通过荷叶y转移到了S上 这一过程是一分为二的过程 即将L上的一队青蛙 分解为两个队 每队各二只 且将上面的二只转移到了S上 这时我们可以考虑形成两个系统 一个是L Y R系统 一个是S Y R系统 前者二只青蛙号大 后者二只青蛙号小 先跳号大的 再跳号小的 从第五步到第九步可以看出的确是这么做的 2 Y R S L 3 1 L Y S 将L上的一半青蛙转移到S上L Y R 将L上的青蛙转移到R上S Y R 将S上的青蛙转移到R上对于LYR系统 相当于Jump 0 1 对于SYR系统 相当于Jump 0 1 两个系统之和为2 Jump 0 1 因此有 Jump 1 1 2 Jump 0 1 2 2 4 现在再看S 2 y 1Jump 2 1 我们将河中的两个石柱称作S1和S2 荷叶叫y 考虑先将L上的青蛙的一半借助于S2和y转移到S1上 当然是一半小号的青蛙在S1上 大的留在L上 S 2 y 1 S S1 S2S1 S2 S 1LYRS2S1231 L S2 Y S1以S1为跳转的目的地 从L经S2Y到S1 相当于JAMP 1 1 4 即S1上有4只青蛙 L上还保留4只 12Y345162L7S213S1824 L R Y S2 S1 YRLS2S1LS2YRS1S2YR 这样LS1S2yR系统分解为 LS2yR系统 S1S2yR系统 2 LS2yR系统 2 Jump 1 1 用归纳法Jump S y 2 Jump S 1 y 5 将上述分析出来的规律写成递归形式的与或结点图为 举例 S 3 y 4 算Jump 3 4 程序 6 5 cpp 作者 wuwh 编制时间 2002年10月20日 主要功能 青蛙过河 include 预编译命令intJump int int 声明有被调用函数voidmain 主函数 主程序开始ints 0 y 0 sum 0 整型变量 s为河中石柱数 y为荷叶数cout s 输入正整数scout y 输入正整数ysum Jump s y Jump s y 为被调用函数cout Jump s 输出结果 y sum endl 主程序结束 程序 6 5 cpp 作者 wuwh 编制时间 2002年10月20日 主要功能 青蛙过河 递归 include 预编译命令intJump int int 声明有被调用函数intmain 主函数 ints 0 y 0 sum 0 cout s 输入正整数scout y 输入正整数ysum Jump s y Jump s y 为被调用函数cout Jump s 输出结果 y sum endl 以下函数是被主程序调用的函数intJump intr intz 自定义函数 r z为形参 自定义函数体开始intk 0 整型变量if r 0 如果r为0 则为直接可解结点 k z 1 直接可解结点 k值为z 1else 如果r不为0 则要调用Jump r 1 z k 2 Jump r 1 z return k 将k的值返回给Jump s y 自定义函数体结束 递归算法举例 快速排序 快速排序的思路 1 将待排序的数据放入数组a中 下标从z到y 2 取a z 放变量k中 通过分区处理 为k选择应该排定的位置 这时要将比k大的数放右边 比k小的数放左边 当k到达最终位置后 由k划分了左右两个集合 然后再用同样的思路处理左集合与右集合 3 令sort z y 为将数组元素从下标为z到下标为y的y z 1个元素从小到大排序 zm 1mm 1y m 1m 1 zmy zy k 我们画出与或图来阐述快速排序的思路 Asort z y z yz yBC不做事DEF分区处理sort z m 1 sort m 1 y 分区处理 1 让k a z 2 将k放在a m 3 使a z a z 1 a m 1 y 则什么也不做 这是直接可解结点 C结点是在z y情况下A结点的解 C是一个与结点 要对C求解需分解为三步 依次为 1 先解D结点 D结点是一个直接可解结点 功能是进行所谓的分区处理 规定这一步要做的事情是 1 将a z 中的元素放到它应该在的位置上 比如m位置 这时a m a z 2 让下标从z到m 1的数组元素小于等a m 3 让下标从m 1到y的数组元素大于a m 比如a数组中a z 5 经分组处理后 5送至a 4 5到位后 其左边a 0 a 3 的值都小于5 其右边a 5 a 6 大于5 见下图 a z y a m 下标 下标 z m 1 y m 1 2 再解E结点 这时要处理的是a 0 a 3 3 再解F结点 处理a 5 a 6 下面按照这种思路构思一个快速排序的程序框图 voidsort intarray intzz intyy intz y i k 下面举例说明排序过程 图1a数组中有7个元素待排序1让k a z a 0 5 z y 图1 k 2进入直到型循环执行 1 a y a 6 4不满足当循环条件 y不动 执行 2 z y 做两件事 a z a y 即a 0 a 6 4 z z 1 0 1 1 见图2 z y 图2 k 执行 3 图2中的a 1 k 满足当循环条件 z z 1 2 z增1后的情况如图3 图3的情况不再满足当循环条件 z y 图3 k 执行 4 a y a z 即a 6 a 2 6 见图4 这时z y还得执行直到型循环的循环体 z y 图4 k 执行 1 a y a 6 6 6 k满足当循环的条件 y y 1 6 1 5见图5 之后退出当循环 因为a y 3 k z y 图5 k 执行 2 a z a y 并让z z 1 3 见图6 z y 图6 k 执行 3 由于a 3 1k 退出循环 见图7 z y 图7 k 执行 4 a z a y a 5 7 见图8这时仍然z y 应继续执行直到型循环的循环体 z y 图8 k 执行 1 a y 7 k 让y y 1 4 见图9 z y 图9 k 之后 z y 退出直到型循环 做a z k z 4 a 4 5 这是5的最终位置 5将整个数据分成左右两个集合 见图10 z y 图10 左 右 k 用上述思路去排左边的部分从z 0到y 3 见图11 让k a z a 0 4 然后进到直到型循环 执行 1 a y 1 k 不满足当循环的条件 y不动 执行 2 a z a y z z 1 1 见图12 z y 图12 z y 图11 k 执行 3 a z k z z 1 2 a 2 k z z 1 3 这时z y 不会执行 4 同时退出直到型循环 见图13 然后做a z k 即a 3 4 见图14 左边也排好了 图14 z y 图13 z y k k 4 用上述思路去排右边的部分 见图15 让k a z a 5 7 进入直到型循环 执行 1 a y 6 k y不动执行 2 a z a y 6 z z 1 5 1 6 见图16 图16 z y 图15 z y k 这时z y 不再执行 3 4 退出直到型循环后 做a z k 见图17 图17 z y k 在有了递归调用函数之后 主程序很容易写 主程序中应包含1 定义整型变量 数组a 10 i 2 用循环结构输入待排序的数 将其放入a数组 3 调用sort函数 使用三个实际参数a 将数组a当实参 0 数组下标下界 9 数组下标上界 4 输出排序结果下面给出参考程序 分两页 程序 6 6 cpp 作者 wuwh 编制时间 2002年10月28日 主要功能 快速排序 include 预编译命令voidsort intarray intzz intyy 被调用函数 数组array zz yy为形参 函数体开始intz y i k 定义变量if zz k y 2 1 右边的元素 k 让y往中间移if zk 让array z array y array z 送给array y while z y 第2件事 结束 array z k 第3件事 k已排到位for i zz i a i sort a 0 9 调用sort函数 实参为数组a和0 9cout 排序结果为 提示信息for i 0 i 10 i cout a i 输出排序结果cout endl 主函数结束 程序 6 6 cpp 作者 wuwh 编制时间 2002年10月28日 主要功能 快速排序 include 预编译命令voidsort intarray intzz intyy 被调用函数 数组array zz yy为形参 函数体开始intz y i k 定义变量if zz yy 如果zz yy 则做下列7件事 7件事开始z zz y yy k array z 第1件事 do 第2件事 开始 while z k y 2 1 右边的元素 k 让y往中间移if zk array y array z while z y 第2件事 结束 kzywhile z k y 2 1 右边的元素 k 让y往中间移 kzyif z y array z array y z z 1 kzywhile z y zy5261734zy4261734kzy54261736zy4231736zy4231776zy4231576 array z k 第3件事 k已排到位for i zz i yy i 第4件事 输出 cout a i array i cout endl 第5件事 换行sort array zz z 1 第6件事 排左边部分sort array z 1 yy 第7件事 排右边部分 7件事结束 函数体结束 voidmain 主函数开始 inta 10 i 整型变量cout a i sort a 0 9 调用sort函数 实参为数组a和0 9cout 排序结果为 提示信息for i 0 i 10 i cout a i 输出排序结果cout endl 主函数结束 研究sort a 0 9 主函数调用sort a 0 9 实在参数子函数中sort array zz yy 形式参数a09Arrayzzyy 研究sort a 0 9 a35614798020123456789array35614798020123456789 小结 1 数组也可作参数 数组为实参 数组为形参 2 只在被调用时系统才为array zz yy分配内存单元 调用后释放掉内存单元 3 zz和yy为数组的下标 是参加排序的数组元素的左右边界 递归算法举例 分书问题 教学目标 巩固用递归思想编写程序教学内容 分书问题题目 有编号分别为0 1 2 3 4的五本书 准备分给A B C D E五个人 每个人阅读兴趣用一个二维数组加以描述 希望你写一个程序 输出所有分书方案 让人人皆大欢喜 假定5个人对5本书的阅读兴趣如下表 01234ABCDE 人 书 1 定义一个整型的二维数组 将表中的阅读喜好用初始化方法赋给这个二维数组 可定义intlike 5 5 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 2 定义一个整型一维数组book 5 用来记录书是否已被选用 用下标作为五本书的标号 被选过元素值为1 未被选过元素值为0 初始化皆置0 intbook 5 0 0 0 0 0 解题思路 3 画出思路图定义Try i 试着给第i人分书 i 0 1 4 说明 1 试着给第i个人分书 先试分0号书 再分1号书 分2号书 因此有一个与结点 让j表示书j 0 1 2 3 4 2 LP为循环结构的循环体 3 条件C是由两部分 与 起来的 第i个人喜欢j书 且j书尚未被分走 满足这个条件是第i人能够得到j书的条件 4 如果不满足C条件 则什么也不做 这是直接可解结点 5 满足C条件 做三件事 sh1第一件事 将j书分给i 用一个数组take i j 记住书j给了i 同时记录j书已被选用 book j 1 sh2第二件事 查看i是否为4 如果不为4 表示尚未将所有5个人所要的书分完 这时应递归再试下一人 即Try i 1 如果i 4 则应先使方案数n n 1 然后输出第n个方案下的每个人所得之书 Sh3第三件事 回溯 让第i人退回j书 恢复j书尚未被选的标志 即book j 0 这是在已输出第n个方案之后 去寻找下一个分书方案所必需的 6 在有了上述的与或图之后 我们很容易写出一个程序框图 先看被调用函数Try i 的框图 程序 6 7 cpp 作者 wuwh 编制时间 2002年10月28日 主要功能 分书问题 include 预编译命令inttake 5 n 整型变量intlike 5 5 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 整型变量 定义数组 初始化intbook 5 0 0 0 0 0 整型变量 定义数组 初始化 下面讨论主程序应该做的事情1 将分书方案号预置02 从第0号人 A 开始试分书 调用Try 0 voidTry inti 函数体开始intj k 定义变量for j 0 j0 记录j书待分 voidTry inti intj k for j 0 j0 记录j书待分 includeinttake 5 n intlike 5 5 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 intbook 5 0 0 0 0 0 voidTry inti 函数体开始intj k 定义变量for j 0 j0 book j 0 如果满足分书条件作下列事 take i j book j 1 把j号书给i 记录j书已分if i 4 输出分书方案 n 让方案数加1cout 第 n 个方案 n 输出分书方案号for k 0 k 4 k cout take k 号书分给 char k 65 endl cout endl 换行 elseTry i 1 如果i 4 继续给下一人分书 递归调用Try i 1 book j 0 让i把书退还 回溯 voidmain 主函数 主函数开始n 0 分书方案号预置0Try 0 调用Try函数 实参为0 主函数结束 结束 RelatedDocuments CompetitorsYoumaywanttoallocateoneslidepercompetitorStrengthsYourstrengthsrelativetocompetitorsWeaknessesYourweaknessesrelativetocompetitor ChartDocuments example1 2ndQtr 3rdQtr 4thQtr 92 70 50 example2 example3 example4 1stQtr ChartDocuments example1 2ndQtr 3rdQtr 4thQtr 100 75 50 example2 example3 example4 1stQtr 25 text1 RelatedDocuments text3 text2 text1 text2 text3 RelatedDocuments text1 text2 text3 text4 RelatedDocuments text4 text5 text6 RelatedDocuments text3 text2 text1