fortran语言编程第一章.ppt

1、第1章 引论,FORTRAN语言,2,计算机算法,解决某类具体问题的方法和步骤算法 例如 看电影，通常需要如下的步骤来实现：,买电影票,持票按时到指定电影院进场,按指定座位坐下,看电影,退场,3,计算机算法,利用计算机解决某类问题的方法和步骤计算机算法，简称算法 分为数值算法和非数值算法两大类,4,算法按处理对象分类,数值算法 数值计算 非数值算法 应用范围十分广泛，最常见的是事务管理领域，例如图书检索、人事管理、行车调度管理等,5,算法的表示,表示一个算法，可以用不同的方法，常用的有： 自然语言 传统流程图 结构化流程图 - 三种基本结构的流程图 - N-S流程图 伪代码 IPO图,6,例1

2、用自然语言描述求解“5!=？”的算法, 步骤5：输出结果120,步骤1：先求12，得到结果2, 步骤4：步骤3的结果24乘以5，得最终 结果120, 步骤2：步骤1的结果2乘以3，得到结果6, 步骤3：步骤2的结果6乘以4，得到结果24,7,例2用自然语言描述求解“n!=？”的算法,S7：输出T,S6：若In 成立，返回重新执行S4， 以及其后的步骤S5、S6,S5：将I+1I,S4：将TI T,S3：将1I,S2: 将 1T,S1：输入n值,设一个变量（T）代表被乘数，另外一个变量（I）代表乘数，直接将每一步的乘积放在被乘数T变量中,8,传统流程图表示,美国国家标准化协会ANSI 规定的常用

3、流程图符号,9,例3用传统流程图描述求解“n!=？”的算法,开始 1 T 2 I TI T I+1 I In 输出T 结束,是,否,10,例4 用传统流程图表示 “判定一个大于或 等于3的正整数是 否是素数？”的算法,11,例4用传统流程图表示“判定一个大于或等于3的正整数是否是素数？”的算法,思路分析： 所谓素数（质数），是指除了1和该数本身外不能被其他任何整数整除的数。 因此，判断一个数n（n3）是否是素数的方法为，将n作为被除数，并用2到（n-1）之间的各个整数轮流作为除数，若都不能被整除，则n为素数。,12,13,14,结构化流程图表示,三种基本结构的流程图 N-S流程图,15,三种基

4、本结构的流程图,(1)顺序结构 a A B b,16,(2) 选择结构(又称选取结构),17,(3) 循环结构(又称重复结构),当型循环结构 直到型循环结构 当型循环和直到型循环结构条件互逆,18,三种基本结构的共同点,只有一个入口，图中的a点 一个出口，图中的b点 结构内的每一部分都有机会被执行 结构内不存在“死循环”,由这三种基本结构所构成的算法称为结构化算法，并可组合应用来解决任何复杂问题。,19,1971年由两位美国学者提出了一种新的流程图形式，这种流程图完全去掉了带箭头的流程线，称为N-S流程图。,N-S流程图,20, 顺序结构,A B, 选择结构,21, 循环结构,22,例5 用N

5、-S流程图表示求5!的算法,23,例6 用N-S流程图表示表示“判定一个大于或等于3的正整数是否是素数？”的算法,24,例7 用N-S流程图表示 “判定20002500年 中的每一年是否闰年， 将结果输出。”的算法,25,例7用N-S流程图表示“判定20002500年中的每一年是否闰年，将结果输出。”的算法,思路分析： 能被4整除但不能被100整除的年份，或者能被100整除同时又能被400整除的年份，是闰年。,26,27,例8用伪代码表示求5!的算法,BEGIN t1 i2 do until i5 tt*i ii+1 enddo write t END,28,课堂练习1,如果将求解阶乘的问题改

6、一下改为： 计算1357911 请用自然语言描述其算法？,29,参考答案 S1：将1 T S2：将3 I S3：将TI T S4：将I+2 I S5：若I11成立，返回重新执行S3及S4 S6：输出T 得到结果10395,30,用自然语言描述求解“百钱百鸡”的算法 一只公鸡值五文钱 一只母鸡值三文钱 三只小鸡值一文钱 请问用一百文钱买一百只鸡，公鸡、母鸡 和小鸡各有几只？,课堂练习2,31,分析： 假设公鸡、母鸡和小鸡的个数分别为x,y和z 数学模型 5X+3Y+Z/3=100 X+Y+Z=100,z=(100-5*x-3*y)*3 z是3的倍数 z=100-x-y,32,参考答案 S1： X

7、 0 S2： Y 0 S3：100-X-Y Z S4: 如果Z能被3整除，同时5*X+3*Y+Z/3等于100， 则X,Y,Z的值为一个合理的解，输出X,Y,Z S5：Y+1 Y S6：如果Y33，返回执行S3、S4和S5 S7：X+1 X S8：如果X20，返回执行S2、S3、S4和S5 S9：算法结束,33,课堂练习3,给出 输入n个数据，找出最大的数 算法N-S流程图,34,参考答案,35,算法设计策略,【例】 设有算式：A B C DC D C=A B C，其中的A，B，C，D均为一位非负整数，要求找出A，B，C，D各值。,36,算法设计策略-枚举法,思路分析： 在有限的范围中，列举和

8、检验所有可能的结果，从中找出那些符合要求的候选解作为问题的解。 例如：设正整数A、B、C、D，A和C的取值范围应是1,9，B和D的取值范围应是0,9，分别对相应范围中的每一个数值进行检测，输出满足条件（1000A100B10CD）（100C10DC）=（100A10BC）的数值。,37,算法描述： for a1 step 1 until 9 do for b0 step 1 until 9 do for c1 step 1 until 9 do for d0 step 1 until 9 do x1000a100b10cd y100c10dc z100a10bc if x-y=z then 输

9、出a，b，c，d,38,对付复杂性的基本方法,按功能划分若干基本模块树状的程序结构,算法设计策略-分而治之,39,算法设计策略-递归法,当求解问题满足： (1)：有递推关系 (2)：有出口，通常使用递归法。 例如：求f(n)=n! 可以理解为当n=1时，f(n)=1(出口) 当n=k时，f(k)=f(k-1)*k(递推关系) 所以，可以用递归法求n!,40,算法的主要特征,有效性 所有操作都应能有效地执行，并能得到确 定的结果 有穷性 总是可以在执行有限步有限的时间内完成 确定性 每个操作必须是明确的，对于相同的输 入只能得出相同的结果 输 入 一个算法可有零个或多个输入 输 出 一个算法可以

10、有一个或多个输出。 任何一个算法至少应有一个输出,41,算法的主要因素,正确性 算法应该满足具体问题的需求，正确反映求解 问题对输入、输出和加工处理等方面的需求。 可读性 可读性好的算法有助于对算法的理解，易于调 试和修改等 健壮性 当输入了非法数据时，算法应能适当地做出反 映或进行处理，输出表示错误性质的信息并中止 高效性 算法的时间开销和空间开销往往是相互制约的， 对高时间效率和低内存空间占用量的要求，只能 根据问题的性质折中处理,42,算法复杂性分析,通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法所需要的存储空间少和执行更快等。我们要对这些可行的算法进行分析，才能知道哪一

11、个算法效率更高。,43,例9欲在按升序排列的n个元素 a1,a2,an(aiai+1)中查找 是否有与b相同的元素。,算法一：从第一个元素a1开始逐一比较。此时，最好的情况是a1就是要查找的元素，只需比较一次。最坏情况则需要比较n次，即一直比较到an才能得到结果；假定每个元素与b相同是等概率的，则平均需要比较n/2次。,44,算法二：采用折半查找(二分查找)的方法，即先用位居中点的元素a（n/2）与b比较， 若b= a（n/2），则查找成功。 若ba（n/2），同时ba（n/2），则在a1,a2,a（n/2-1）中采用上述方法继续查找； 否则在a（n/2+1）,a（n/2+2）,an采用上述方

12、法继续查找。 这种算法最多也只需要比较log2n次。,45,算法复杂性分析,算法的复杂性分析是对算法效率的度量，是算法运行所需要的计算机资源的量，这个量是只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。 需要的时间资源的量称作时间复杂性，需要的存储空间资源的量称作空间复杂性。,46,随着计算机运算速度和存储容量的直线增长，有人认为低效的算法可以由高速的计算机来弥补，这种观点实际上是不正确的。因为，随着经济的发展、社会的进步、科学研究的深入，要求计算机解决的问题越来越复杂、规模越来越大，其超线性增长导致的时耗的增长和空间需求的增长，决非计算机速度和容量的线性增长带来的时耗减少和存储空间

13、的扩大所能抵消。因此，利用计算机解决实际问题时，应着眼于寻求更高效的算法。,47,结构化程序设计思想,面向过程的结构化程序设计，可以归结为“程序=算法+数据结构”。这种设计方法以算法为核心，特点是数据与程序分离，即数据与数据处理分离。,48,软件开发过程,软件的开发过程,49,软件开发过程,软件的开发过程,50,软件开发过程,软件的开发过程,51,软件开发过程,软件的开发过程,52,软件开发过程,软件的开发过程,53,软件开发过程,软件的开发过程,54,软件开发过程,软件的开发过程,55,程序设计方法,程序设计是一个将人类思维转化为计算机思维的过程，可分为面向过程的程序设计和面向对象的程序设计

14、两大类。,56,面向过程的程序设计,过程是为了得到问题的解而执行的一步步的操作； 面向过程的程序设计是一种基于功能分析及每个功能由计算机的一个操作过程实现的程序设计方法，又称为传统的程序设计。 面向过程程序设计的关键是规划算法和数据结构。,57,面向对象的程序设计,面向对象程序设计模拟自然界认识和处理事物的方法,将数据和对数据的操作方法组织在一起，形成一个相对独立的整体，称为对象 对象是活动的，对象行为靠消息触发而激活 面向对象程序设计的关键是确定对象并对其分类,58,程序设计过程,传统的程序设计过程主要包括以下几个阶段： 1分析问题 通过原始资料，取得对问题的一个清晰的理解，进而确定解决问题的目标（称为输出）以及实现该目标所需要的条件（称为输入）。,59,程序设计过程,2设计算法与数据结构 数据结构描述了问题涉及的对象之间的联系和组织结构；算法描述了求解问题的步骤或规则。设计合理的数据结构往往可以简化算法，而好的算法又使程序具有更高的效率。,60,程序设计过程,3检查算法 使用多组样本数据，通过手工计算，对方案的正确性进行证明和验证。,61,程序设计过程,4编码实现 选用一种程序设计语言（如FORTRAN语言）将算法转换成计算机能够理解的程序（称为编程）。良好的编程风格是程序具备可靠性、可读性和可维护性