2003C语言第二章（续）.pptVIP

第二章 算法 通过本章的学习，了解有关算法的基本知识和程序设计时对问题求解的步骤，掌握1~2种算法的表示方法。 算法 解决问题的过程中，动作的执行顺序称为算法 任何结构化的程序都是按一定的顺序执行一系列动作的结果。 在结构化程序设计中，确定解决问题的具体方法和步骤，再编制好一组让计算机可以执行的程序，让计算机按人们指定的步骤有效地工作。 根据制定的算法，编写出计算机可执行的命令序列，就是编制程序。 重点：掌握分析问题、解决问题的方法，锻炼分析、分解，并最终归纳整理出算法的能力。 2．1问题分析 计算机是用来表示和处理数据的工具。 一、定义（在计算机存储器中表示的）数据。 二、描述算法（列出处理这些数据的步骤）。 2．2问题解的描述 【例1】：编程，计算和打印三个数的和及平均值。 分析： 3个输入（3个变量num1，num2，num3）； 　2个输出（和sum及平均值aver） 　2步计算（求和、求平均值） 通过以上分析可标识数据、结构类型及构造算法。 问题求解的步骤 １.了解已知什么，求什么？ ２.设计算法。对于比较复杂的问题，可以用辅助工具（流程图、N-S图描述算法）。 ３.选择合适的数据结构。即确定数据类型和数据的组织方式。用什么方法，用到什么结构（选择、循环），用到几个数据、分别为什么类型。 ４ .根据确定的算法编程。 ５. 上机调试、执行、修改。 ６.分析结果。 算法的特性 1．有穷性。一个算法应包含有限的操作步骤， 而不能是无限的。 2．确定性。算法中的每一个步骤都应该是确定 的，其含义是唯一的。 3．有零个或多个输入。所谓输入是指在执行算 法时需要从外界取得必要的信息。 4．有一个或多个输出。 5．有效性。算法中的每一个步骤都应当有效地 执行，并得到确定的结果。 如何表示算法 1．用自然语言表示算法 2．用流程图表示算法 3．用N-S流程图表示算法 4．用伪代码表示算法 5．用PAD图表示算法 几种常用的流程图 顺序结构——自顶向下，无分支，无转移 选择结构——有分支，需条件判断 循环结构——有转移，某些语句可重复执行 当型循环（while） 直到型循环(until) 例题分析 【例1】：编程，计算和打印三个数的和及平均值。 分析： 3个输入（3个变量num1，num2，num3）； 　2个输出（和sum及平均值aver） 　2步计算（求和、求平均值） 通过以上分析可标识数据、结构类型及构造算法。 源程序如下： #include stdio.h Void main( ) { float num1,num2,num3,sun,ave; printf(“please input 3 numbers:”); scanf(“%f%f%f”,num1,num2,num3); sum=num1+num2+num3; ave=sum/3; printf(“sum=%f,ave=%f”,sum,ave); } 【例2】已知三角形的三边，求三角形面积 分析： 1．确定输入（a、b、c）、输出（三角形面积area） 2．确定计算方法。 由数学知识可得： 源程序如下： 算法举例 【例4】 求N! 算术方法： 5！=1*2*3*4*5 10！=1*2*3*4*5*6*7*8*9*10 100！= 1*2*3*4*5 *…99*100 N！= 1*2*3*4*5 *… （N-1）*N 对于最后一个式子，在计算机中是无法表示的，因此我们应对算法进行改进。 改进方法：设两个变量：一个变量T代表被乘数，一个变量 I代表乘数。每一次相乘的结果再放入T中，同时将I 加一，再进行运算，具体运算如下: 对于5！=1*2*3*4*5，则N=5 1. T=1 I=2 T=T*I=2 I=I+1=3 2. T=T*I=2*3 I=I+1=4 3. T=T*I=6*4=24 I=I+1=5 4. T=T*I=24*5=120 I=I+1=6 还执行T=T*I ? 此时I 〉N, 运算到此结束. 对于10！=1*2*3*4*5*6*7*8*9*10，则N=10 1.T=1 I=2 T=T*I=2 I=I+1=3 2.T=T*I=2*3 I=I+1=4 3.T=T*I=6*4=24 I=I+1=5 4.T=T*I=24*5=120 I=I+1=6 …… 9.