[第三章计算机算法初步.ppt

第三章 计算机算法初步 计算机求解问题的一般过程 问题分析阶段 认真分析问题，建立正确的模型,找出解题方法 数据结构设计阶段 找出所涉及的数据信息，根据已经建立的正确模型设计相应的数据结构 算法设计阶段 根据数据结构，详细设计计算步骤，并加以描述 编码与调试阶段 用计算机语言实现所描述的算法，并调试正确 举例：求绿化带宽度 如图：在长500m、宽300m的地域内保护80000m2的地块，求沿四周植树建设绿化带的宽度。 得到一元二次方程：4x2-2(length+width)x+length*width-area = 0 找出计算方法 X= 根据求根公式求解方程 找出算法 用C语言写出程序 调试和测试 算法概念 算法 解题过程（步骤）的具体描述 可完全精确执行、有确定结果的有穷指令序列 算法的控制结构 选择结构（如：C语言的 if 语句） 循环结构（如：C语言的 while 语句） 顺序结构（语句组） 3种结构可以满足各种算法的所有控制要求 算法描述的必要性 程序设计过程 算法设计 程序实现 算法描述： 描述解题逻辑，验证正确性 独立于程序设计语言 程序实现： 利用程序设计语言的功能，实现算法 熟悉语言的语法、语义、支撑环境 算法描述方法 自然语言描述 易于理解；与计算机语言差别较大，不严谨，容易出现二义性 图形方式描述 比较直观，无二义性，易于掌握，过度为编码比较容易 流程图(P60 表3-1) 、N-S图、PAD图等 伪代码方式描述 很严谨，与计算机语言很接近，很容易过度为编码，掌握的难度略大 常用流程图符号 (P60 表3-1) 用流程图表示算法 用N-S图表示算法 用PAD图表示算法 伪码描述例：求5个整数之和 数据分析 sum 保存已经输入的整数之和 算法描述： 赋值 0 ? sum 重复执行 5 次 2.1 读入一个整数 2.2 累加到 sum 输出整数和 sum 仅考虑主要的数据对象和控制结构 程序实现阶段考虑数据对象和控制结构的具体实现 3.1 实例1：考试成绩统计 任务： 输入某班级人数和某课程的考试成绩（100分制），输出及格率(60)和不及格率。 问题分析（基本方法） 输入学生人数后，逐个输入成绩，判断及格否，统计及格人数和不及格人数 数据分析 班级人数 num 及格人数 pass 不及格人数 fail 输入成绩 score 过程描述（流程图） 算法的验证 模拟算法的计算过程，跟踪数据的变化 程序结构设计（本题） 流程图的结构 从外层到内层 顺序 ? 循环 ? 选择 程序结构 复合语句 ? while 语句 ? if 语句 while 条件：num == 0 if 条件：score 60 细节问题 输出格式： 65.5% 涉及浮点数的处理 程序实现 #include stdio.h main( ) { int num, pass, fail, score; while( 0 != num ) { } } 语言现象 赋值表达式 pass = (fail = 0) 赋值运算符 = 右结合 简化赋值（自反运算、复合赋值） pass += 1 等价于 pass = pass + 1 自动类型变换 printf(“passed %lf\%\n”,100.0*pass/num); 强制类型变换 （类型名）表达式 /* 改变其数据类型*/ 转义字符 \% 或 %% 用于输出 % 设计方法分析 计算机科学家尼克劳斯·沃思（Niklaus Wirth ）提出 Programs = Algorithms + Data Strcture 程序 = 算法 + 数据结构 程序设计过程 问题定义：输入输出要求（数据与格式） 数据结构：分析需要保存的信息，组织数据结构 算法设计：编制解题步骤 程序编码：选用程序设计语言，实现解题步骤 程序测试：排错和测试 例3-2 求解一元二次方程 问题分析 一元二次方程可以写成ax2+bx+c=0 方程由三个系数a、b、c惟一确定 需要用户输入三个系数，然后根据一元二次方程的求解规则计算最终的结果，并将结果显示输出 流程剖析 变量t1,t2 保存数学计算中的中间结果 程序实现 #include stdio.h #include math.h main( ) { int a, b, c, t1; double t2; scanf( “%d%d%d”, a, b, c ); t1 = b*b – 4*a*c; if( t1 == 0 ) printf( “x = %lf\n”, -b/(2.0*a) ); else if( t1 0