《计算机算法初步》PPT课件.ppt

第三章计算机算法初步 一 解题方法及算法概念二 算法举例 穷举法三 算法举例 递推与迭代法四 良好的编程风格 计算机求解问题的一般过程 问题分析阶段认真分析问题 建立正确的模型 找出解题方法数据结构设计阶段找出所涉及的数据信息 根据已经建立的正确模型设计相应的数据结构算法设计阶段根据数据结构 详细设计计算步骤 并加以描述编码与调试阶段用计算机语言实现所描述的算法 并调试正确 一 解题方法及算法概念 举例 求绿化带宽度 如图 在长500m 宽300m的地域内保护80000m2的地块 求沿四周植树建设绿化带的宽度 分析 把题目中提出的问题数学化 设x 绿化带宽度length 地块长度width 地块宽度area 保护面积 列出计算式 area length 2x width 2x 得到一元二次方程 4x2 2 length width x length width area 0 找出计算方法X 根据求根公式求解方程找出算法用C语言写出程序调试和测试 算法概念 算法解题过程 步骤 的具体描述可完全精确执行 有确定结果的有穷指令序列算法的控制结构选择结构 如 C语言的if语句 循环结构 如 C语言的while语句 顺序结构 语句组 3种结构可以满足各种算法的所有控制要求 算法描述的必要性 程序设计过程算法设计程序实现算法描述 描述解题逻辑 验证正确性独立于程序设计语言程序实现 利用程序设计语言的功能 实现算法熟悉语言的语法 语义 支撑环境 算法描述方法 自然语言描述易于理解 与计算机语言差别较大 不严谨 容易出现二义性图形方式描述比较直观 无二义性 易于掌握 过度为编码比较容易流程图 P60表3 1 N S图 PAD图等伪代码方式描述很严谨 与计算机语言很接近 很容易过度为编码 掌握的难度略大 起止框 I O框 处理框 判断框 调用框 连接框 有向边 常用流程图符号 P60表3 1 用流程图表示算法 循环结构 用N S图表示算法 顺序结构 选择结构 当型循环 先判断条件 直到型循环 后判断条件 用PAD图表示算法 A B 顺序结构 P 选择结构 当型循环 先判断条件 直到型循环 后判断条件 A B 伪码描述例 求5个整数之和 数据分析sum保存已经输入的整数之和算法描述 赋值0 sum重复执行5次2 1读入一个整数2 2累加到sum输出整数和sum仅考虑主要的数据对象和控制结构程序实现阶段考虑数据对象和控制结构的具体实现 3 1实例1 考试成绩统计 任务 输入某班级人数和某课程的考试成绩 100分制 输出及格率 60 和不及格率 问题分析 基本方法 输入学生人数后 逐个输入成绩 判断及格否 统计及格人数和不及格人数数据分析班级人数num及格人数pass不及格人数fail输入成绩score 过程描述 流程图 初值设置0 pass0 fail 读入成绩 score 读入学生人数 num num 0 score 60 fail加一num减一 pass加一num减一 计算及格率pass pass fail 和不及格率fail pass fail 并输出 Y N Y N 算法的验证 模拟算法的计算过程 跟踪数据的变化 程序结构设计 本题 流程图的结构从外层到内层顺序 循环 选择程序结构复合语句 while语句 if语句while条件 num 0if条件 score 60细节问题输出格式 65 5 涉及浮点数的处理 程序实现 includemain intnum pass fail score while 0 num printf 输入分数 scanf d num pass fail printf passed f n float pass num 100 printf failed f n float fail num 100 pass fail 0 printf 请输入学生人数 scanf d 初值设置和输入学生人数 输出及格率和不及格率 输入分数统计及格人数和不及格人数 语言现象 赋值表达式pass fail 0 赋值运算符 右结合简化赋值 自反运算 复合赋值 pass 1等价于pass pass 1自动类型变换printf passed lf n 100 0 pass num 强制类型变换 类型名 表达式 改变其数据类型 转义字符 或 用于输出 设计方法分析 计算机科学家尼克劳斯 沃思 NiklausWirth 提出Programs Algorithms DataStrcture程序 算法 数据结构程序设计过程问题定义 输入输出要求 数据与格式 数据结构 分析需要保存的信息 组织数据结构算法设计 编制解题步骤程序编码 选用程序设计语言 实现解题步骤程序测试 排错和测试 例3 2求解一元二次方程 问题分析一元二次方程可以写成ax2 bx c 0方程由三个系数a b c惟一确定需要用户输入三个系数 然后根据一元二次方程的求解规则计算最终的结果 并将结果显示输出 流程剖析 变量t1 t2保存数学计算中的中间结果 输入a b c b2 4ac t1 t1 0 Y N t1 t2 t1 0 输出 b 2a 输出 b t2 2a 输出 无解 Y N 程序实现 include includemain inta b c t1 doublet2 scanf d d d 类型转换 数学函数说明 求平方根 强制类型转换 程序测试 测试设计考虑数据的各种取值 准备测试用例检查每个程序分支b2 4ac等于0 大于0 小于0测试用例121b2 4ac 0263b2 4ac 12433b2 4ac 39 TC程序跟踪 TURBOC跟踪调试F7单步跟踪设置监视点 Watch Ctrl F7输入变量名跟踪过程message窗将显示被跟踪变量的值 学习方法 算法的学习 长期任务 利用变量就是存储器的概念 考虑解题过程中必须保存的数据利用3种控制结构 顺序 选择 循环 考虑数据变化过程 设计处理过程应能够熟练地设计数据结构和简单的算法程序设计语言的学习阅读程序实例 理解新的语言现象程序设计实践 上机排错调试对主要语言功能和上机编程操作应该达到十分熟练 二 算法举例 穷举法 P63 穷举法也称为枚举法 是一种一一列举各种情况的求解问题的方法 基本思想 对问题的所有可能情形一一罗列 直到找出符合条件的解或将全部可能情形都测试过为止 实例3素数的判断题目判断给定的整数 大于1 是否为素数 问题分析素数 质数 是指除了1和它本身外 没有其它因子的大于1的整数 例如23131723等是素数41220等不是素数 编程思路 要判断给定整数a是不是素数 应该根据素数的定义 用2 3 a 1分别去试除如果其中有能整除a的数 则a不是素数如果这些数都不能整除a 则a是素数只要找到一个能整除a的数 就能断定a不是素数 因此这时应提前退出循环循环结束后判是哪种情况 输出相应信息 算法流程图 P64 算法描述 else includemain inti a printf Inputa 1 scanf d for i 2 i a 1 i if a i 0 break if i a 1 用2 3 a 1去试 找到因子提前退出 若真 说明正常退出 是素数 若假 说明提前退出 不是素数 printf disaprimenumber n a printf disnotaprimenumber n a 讨论为减少循环次数 只需用2 a 2之间或用2 a1 2之间的整数试除 第一次运行 Inputa 1 11 11isaprimenumber 第二次运行 Inputa 1 15 15isnotaprimenumber 运行情况 3 4实例4百钱买百鸡 问题陈述某人有钱百枚 希望买一百只鸡 假设不同的鸡价格不同 公鸡5枚钱一只 母鸡3枚钱一只 而1枚钱可以买3只小鸡 试问如果正好使用百枚钱买到一百只鸡 其中有几只公鸡 母鸡和小鸡 解题思路 穷举法 考虑公鸡 母鸡和小鸡数量的所有可能的取值 依次检查是否构成了问题的解 找出价钱正好是100的组合约束条件 各种鸡的数量一定小于100 数量之和为100数据结构公鸡数量x母鸡数量y小鸡数量z 数学模型 算法设计 用伪码表示 1 0 x2 如果x 100 5 即20 2 1 0 y2 2 如果y 100 3 即33 2 2 1 0 z2 2 2 如果z 1002 2 2 1 如果x y z 100并且5x 3y z 3 1002 2 2 1 1 输出x y z 解 2 2 2 2 z 重复2 2 22 2 3 y 重复2 22 3 x 重复23 结束 流程图 程序实现 循环控制变量明确的情况 采用for语句包括循环次数固定的情况实数的比较不用x y用fabs x y 1e 5 差的绝对值小于10 5 程序编码 include includemain intx y z 公鸡 母鸡 小鸡的个数 for x 0 x 100 5 x for y 0 y 100 3 y for z 0 z 100 z if x y z 100 结果与分析 x 0 y 25 z 75x 4 y 18 z 78x 8 y 11 z 81x 12 y 4 z 84笨拙的穷举法符合计算机解题的特点 程序说明 逻辑运算与求x的绝对值数学计算头文件 math h 浮点数的判断问题 机器中二进制表示的浮点数是有误差的判断问题 doublex y if x y 应使用if fabs x y 0 00001 控制误差限制在一定的精度内即可 浮点常量的默认类型为doublefloatx if x 1 2 注意 类型不一致 可写成 1e 5 includemain intx y z for x 0 x 20 x for y 0 y 33 y for z 0 z 100 z if x y z 100 程序代码 用精确值整型处理 改进的程序代码 减少执行时间 includemain intx y z for x 0 x 20 x for y 0 y 33 y z 100 x y if 15 x 9 y z 300 printf x d y d z d n x y z 只用两层循环 穷举法小结 基本方法通过分析 确定可能的取值范围对该范围的每个值进行检测 找出所有符合要求的值可以用循环语句实现穷举优点容易理解 不会遗漏某些解缺点时间效率欠佳 穷举法小结 特点常用于问题有多个 有限 解的情况当没有或很难找到解析方式求解时可使用穷举法时间效率不是最佳的 三 算法举例 递推与迭代法 在计算机数值计算中 递推也称为迭代 递推基本策略是将复杂的运算划分为可以重复操作的若干个简单的运算 进而充分利用计算机擅长重复计算的特点 递推求解的基本思想 不断用变量的旧值递推其新值的过程 采用循环结构完成一个迭代处理过程 关键在于找出递推公式和边界条件 初始值 终止条件 P67 实例5Fibonacci序列 问题 Fibonacci 斐波那契 序列有如下定义 要求 输出斐波纳契 Fibonacci 级数的前三十项 并一行输出6项 问题分析解决Fibonacci序列的递推计算方法 1 序列的头两个数已知 2 已知连续的两个Fibonacci数 可以算下一个数 数据对象解决应用问题 a b next long类型 解决输出问题 n int类型 求解过程 a b next第5项 next第3项 a b next第4项 a b next第6项 2 8 1 2 3 2 3 5 3 5 next a b a b b next 规律 算法流程 选择结构 includemain inti n longa b next a b 1 printf 8ld 8ld a b n 2 处理前两项 for i 3 i 30 i next a b a b b next 处理后28项 printf 8ld next n if n 6 0 printf n 输出并控制换行 程序实现 运行结果如下 112358132134558914423337761098715972584418167651094617711286574636875025121393196418317811514229832040 实例6 求圆周率 问题分析圆周率 的计算公式 4 4 3 4 5 4 7 4 9 4 11 数据对象PI表示圆周率 float或double 而且有一定的精度要求 item 每一个数据项 类型同PI sign 保存符号 算法描述 终止条件 由于数据项的绝对值是递减的 且相邻项的符号不同 如果第n个数据项的绝对值已经小于精度值 则前n项之和一定已经满足精度 include includemain intsign 1 longi 1 doublePI 0 0 item do item sign 4 0 2 i 1 sign sign PI item while fabs item 1e 4 数据项精度控制循环 printf PI lf n PI 程序代码 实例7 按位分解整数P71 题目要求从键盘输入一个整数 然后将它的每一位分解成独立的数字字符并输出之 问题分析利用整除和求余运算实现将整数分解例如 对整数73267326 1000可得到最高位7 7326 1000可得到其余的位数326这种方法要求首先获得整数最高位的权 本例为1000 然后从高向低逐个分离出每位数字 算法描述 includemain longx y n printf Enteraninteger scanf ld 程序代码 递推与迭代法小结 思路利用上一个或上几个值推出后一个值 使后一个值与问题的解更接近要点建立递推或迭代关系 递推公式 有明确的初始值有明确的结束条件 3 5实例5统计数字字符的出现次数 任务统计一行输入字符中每个数字字符的出现次数数据分析应保存10个整数 需要一组相关数据 设置数组intdigits 10 每个元素存一个数字字符的出现次数例如 数字字符3的出现次数保存在digits 3 中输入字符ch 算法的描述 穷举法 1 digits数组元素初始化为02 读入一个字符 ch3 如果ch不是换行符 则3 1如果ch是数字字符 则3 1 1digits ch 加一3 2读入一个字符 ch3 3重复处理34 输出digits数组 先考虑整体算法 digits数组初始化 digits ch 加1 再读ch ch n ch是数字 输出统计数字 读ch Y Y N N 流程图 算法细化 digits数组元素初始化1 设循环变量i为02 当i小于10时2 1设0 digits i 2 2i加一2 3重复2 局部算法与外部逻辑处理关系不大 输出digits数组1 设循环变量i为02 当i小于10时2 1输出digits i 2 2i加一2 3重复2 程序结构设计 算法过程分析3个循环 主算法 2个细化算法程序结构采用while语句循环控制 换行符检查 数组下标数据结构一维整数数组下标问题 数字字符 整数 利用ASCII值 ch 0 0 includemain intdigits 10 i 0 charch while i 0 利用字符的ASCII值 程序实现 自增运算赋值后加1 整数数组 逻辑与运算 程序说明 数组说明 定义 类型数组名 数组大小N 数组引用数组名 表达式 下标范围0到N 1 下标越界 编译查不出来 字符的运算以其ASCII值参加整数运算C语言支持不同类型的混合运算 如 c 2 是ASCII的值printf d c 2 101printf c c 2 e 结构化程序设计方法 自顶向下首先描述外层核心算法与主要数据对象突出解题逻辑 忽略细节控制结构不超过两层循环限制了算法的难度逐步求精在确立了外部算法的基础上逐步描述各个细节算法及其相关数据对象 如 上例中的digits初始化和输出 复杂情况下 细节算法仍应进一步逐步求精 数据与变量 数据的分析分析算法中 需要保存的数据有明确的意义 不多不少 避免重复变量的设置为数据的保存提供存储空间提供数据结构 如 数组等 避免同一变量在不同时刻代表不同的数据影响程序可读性的关键因素之一 方法分析 基于数学关系数学模型是解题方法算法是解题过程的描述 穷举 递推 程序设计是解题过程的具体实现穷举过程 迭代过程的算法实现可以用算法的循环控制编程中用循环语句实现实现细节熟悉各种运算 各种数据类型的使用方法 四 良好的编程风格 依据规约 编写正确的程序完全按要求实现功能格式一行一语句 太长的语句可占多行 使其不溢出画面 括号嵌套缩进对应 不要齐头并进适当留空格 空行等 增加可读性 下面是一段微软的代码 intWinMain HINSTANCEhInstance HINSTANCEhPrevInstance LPSTRlpCmdLine intnCmdShow MSGmsg HACCELhAccelTable InitializeglobalstringsLoadString hInstance IDS APP TITLE szTitle MAX LOADSTRING LoadString hInstance IDC A szWindowClass MAX LOADSTRING MyRegisterClass hInstance Performapplicationinitialization if InitInstance hInstance nCmdShow returnFALSE hAccelTable LoadAccelerators hInstance LPCTSTR IDC A Mainmessageloop while GetMessage 不好的例子 includeintmain printf Hello World n return0 main inti x max 0 for i 0 imax max x 与本书P47对比 每个变量有明确的角色注释 反映你的文字水平 文件注释函数注释程序片断关键点注释关键数据结构注释通常没必要每句话写注释程序员友好你的程序是给人看的 不要写的晦涩难懂 正确性可懂度时间复杂度空间复杂度健壮性可扩展性可移植性 本章小结 算法用一系列动作来描述问题求解的过程算法描述方法流程图 图形化的算法描述伪码 算法过程的动作说明算法设计与实现算法设计描述解题方法 程序设计描述算法的具体实现 排错方法算法设计错误 代入数据验证 对复杂算法无效 程序设计错误 编译检查 结果不对 或出现异常解决方法 跟踪调试 设置监视点 逐步检查 第三章作业 阅读教科书第三章练习题要求 提供变量说明 流程图73页 3 1 3 2 3 3 3 4上机作业74页 3 1 3 2换硬币 把1元人民币换成50枚5分 2分 1分的硬币 有多少种换法 自测题 自我检测 要求