fortran语言编程第一章.

第1章引论FORTRAN语言前一页休息2计算机算法解决某类具体问题的方法和步骤→算法例如看电影，通常需要如下的步骤来实现：买电影票持票按时到指定电影院进场按指定座位坐下看电影退场前一页休息3计算机算法利用计算机解决某类问题的方法和步骤→计算机算法，简称算法分为数值算法和非数值算法两大类前一页休息4算法按处理对象分类数值算法数值计算非数值算法应用范围十分广泛，最常见的是事务管理领域，例如图书检索、人事管理、行车调度管理等前一页休息5算法的表示表示一个算法，可以用不同的方法，常用的有：●自然语言●传统流程图●结构化流程图-三种基本结构的流程图-N-S流程图●伪代码●IPO图前一页休息6[例1]用自然语言描述求解“5!=？”的算法步骤5：输出结果120步骤1：先求1×2，得到结果2步骤4：步骤3的结果24乘以5，得最终结果120步骤2：步骤1的结果2乘以3，得到结果6步骤3：步骤2的结果6乘以4，得到结果24前一页休息7[例2]用自然语言描述求解“n!=？”的算法S7：输出TS6：若I≤n成立，返回重新执行S4，以及其后的步骤S5、S6S5：将I+1IS4：将T×ITS3：将1IS2:将1TS1：输入n值设一个变量（T）代表被乘数，另外一个变量（I）代表乘数，直接将每一步的乘积放在被乘数T变量中前一页休息8传统流程图表示美国国家标准化协会ANSI规定的常用流程图符号前一页休息9[例3]用传统流程图描述求解“n!=？”的算法开始1T2IT×ITI+1IIn输出T结束是否前一页休息10[例4]用传统流程图表示“判定一个大于或等于3的正整数是否是素数？”的算法前一页休息11[例4]用传统流程图表示“判定一个大于或等于3的正整数是否是素数？”的算法思路分析：所谓素数（质数），是指除了1和该数本身外不能被其他任何整数整除的数。因此，判断一个数n（n≥3）是否是素数的方法为，将n作为被除数，并用2到（n-1）之间的各个整数轮流作为除数，若都不能被整除，则n为素数。前一页休息12前一页休息13前一页休息14结构化流程图表示三种基本结构的流程图N-S流程图前一页休息15三种基本结构的流程图(1)顺序结构aABb前一页休息16(2)选择结构(又称选取结构)前一页休息17(3)循环结构(又称重复结构)当型循环结构直到型循环结构当型循环和直到型循环结构条件互逆前一页休息18三种基本结构的共同点只有一个入口，图中的a点一个出口，图中的b点结构内的每一部分都有机会被执行结构内不存在“死循环”由这三种基本结构所构成的算法称为结构化算法，并可组合应用来解决任何复杂问题。前一页休息191971年由两位美国学者提出了一种新的流程图形式，这种流程图完全去掉了带箭头的流程线，称为N-S流程图。N-S流程图前一页休息20⑴顺序结构AB⑵选择结构前一页休息21⑶循环结构前一页休息22[例5]用N-S流程图表示求5!的算法前一页休息23[例6]用N-S流程图表示表示“判定一个大于或等于3的正整数是否是素数？”的算法前一页休息24[例7]用N-S流程图表示“判定2000～2500年中的每一年是否闰年，将结果输出。”的算法前一页休息25[例7]用N-S流程图表示“判定2000～2500年中的每一年是否闰年，将结果输出。”的算法思路分析：能被4整除但不能被100整除的年份，或者能被100整除同时又能被400整除的年份，是闰年。前一页休息26前一页休息27[例8]用伪代码表示求5!的算法BEGINt1i2dountili5tt*iii+1enddowritetEND前一页休息28课堂练习1如果将求解阶乘的问题改一下改为：计算1×3×5×7×9×11请用自然语言描述其算法？前一页休息29参考答案S1：将1TS2：将3IS3：将T×ITS4：将I+2IS5：若I11成立，返回重新执行S3及S4S6：输出T得到结果10395前一页休息30用自然语言描述求解“百钱百鸡”的算法一只公鸡值五文钱一只母鸡值三文钱三只小鸡值一文钱请问用一百文钱买一百只鸡，公鸡、母鸡和小鸡各有几只？课堂练习2前一页休息31分析：假设公鸡、母鸡和小鸡的个数分别为x,y和z数学模型5X+3Y+Z/3=100X+Y+Z=100z=(100-5*x-3*y)*3←z是3的倍数z=100-x-y前一页休息32参考答案S1：X0S2：Y0S3：100-X-YZS4:如果Z能被3整除，同时5*X+3*Y+Z/3等于100，则X,Y,Z的值为一个合理的解，输出X,Y,ZS5：Y+1YS6：如果Y33，返回执行S3、S4和S5S7：X+1XS8：如果X20，返回执行S2、S3、S4和S5S9：算法结束前一页休息33课堂练习3给出输入n个数据，找出最大的数算法N-S流程图前一页休息34参考答案前一页休息35算法设计策略【例】设有算式：ABCD－CDC=ABC，其中的A，B，C，D均为一位非负整数，要求找出A，B，C，D各值。前一页休息36算法设计策略--枚举法思路分析：在有限的范围中，列举和检验所有可能的结果，从中找出那些符合要求的候选解作为问题的解。例如：设正整数A、B、C、D，A和C的取值范围应是[1,9]，B和D的取值范围应是[0,9]，分别对相应范围中的每一个数值进行检测，输出满足条件（1000×A＋100×B＋10×C＋D）－（100×C＋10×D＋C）=（100×A＋10×B＋C）的数值。前一页休息37算法描述：fora←1step1until9doforb←0step1until9doforc←1step1until9doford←0step1until9dox←1000×a＋100×b＋10×c＋dy←100×c＋10×d＋cz←100×a＋10×b＋cifx-y=zthen输出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算法的主要特征有效性所有操作都应能有效地执行，并能得到确定的结果有穷性总是可以在执行有限步有限的时间内完成确定性每个操作必须是明确的，对于相同的输入只能得出相同的结果输入一个算法可有零个或多个输入输出一个算法可以有一个或多个输出。任何一个算法至少应有一个输出前一页休息41算法的主要因素正确性算法应该满足具体问题的需求，正确反映求解问题对输入、输出和加工处理等方面的需求。可读性可读性好的算法有助于对算法的理解，易于调试和修改等健壮性当输入了非法数据时，算法应能适当地做出反映或进行处理，输出表示错误性质的信息并中止高效性算法的时间开销和空间开销往往是相互制约的，对高时间效率和低内存空间占用量的要求，只能根据问题的性质折中处理前一页休息42算法复杂性分析通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法所需要的存储空间少和执行更快等。我们要对这些可行的算法进行分析，才能知道哪一个算法效率更高。前一页休息43[例9]欲在按升序排列的n个元素a1,a2,…,an(ai≤ai+1)中查找是否有与b相同的元素。算法一：从第一个元素a1开始逐一比较。此时，最好的情况是a1就是要查找的元素，只需比较一次。最坏情况则需要比较n次，即一直比较到an才能得到结果；假定每个元素与b相同是等概率的，则平均需要比较n/2次。前一页休息44算法二：采用折半查找(二分查找)的方法，即先用位居‘中点’的元素a（n/2）与b比较，若b=a（n/2），则查找成功。若b≠a（n/2），同时b＜a（n/2），则在a1,a2,……,a（n/2-1）中采用上述方法继续查找；否则在a（n/2+1）,a（n/2+2）,……,an采用上述方法继续查找。这种算法最多也只需要比较log2n次。前一页休息45算法复杂性分析算法的复杂性分析是对算法效率的度量，是算法运行所需要的计算机资源的量，这个量是只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。需要的时间资源的量称作时间复杂性，需要的存储空间资源的量称作空间复杂性。前一页休息46随着计算机运算速度和存储容量的直线增长，有人认为低效的算法可以由高速的计算机来弥补，这种观点实际上是不正确的。因为，随着经济的发展、社会的进步、科学研究的深入，要求计算机解决的问题越来越复杂、规模越来越大，其超线性增长导致的时耗的增长和空间需求的增长，决非计算机速度和容量的线性增长带来的时耗减少和存储空间的扩大所能抵消。因此，利用计算机解决实际问题时，应着眼于寻求更高效的算法。前一页休息47结构化程序设计思想面向过程的结构化程序设计，可以归结为“程序=算法+数据结构”。这种设计方法以算法为核心，特点是数据与程序分离，即数据与数据处理分离。前一页休息48软件开发过程软件的开发过程前一页休息49软件开发过程软件的开发过程前一页休息50软件开发过程软件的开发过程前一页休息51软件开发过程软件的开发过程前一页休息52软件开发过程软件的开发过程前一页休息53软件开发过程软件的开发过程前一页休息54软件开发过程软件的开发过程前一页休息55程序设计方法程序设计是一个将人类思维转化为计算机思维的过程，可分为面向过程的程序设计和面向对象的程序设计两大类。前一页休息56面向过程的程序设计过程是为了得到问题的解而执行的一步步的操作；面向过程的程序设计是一种基于功能分析及每个功能由计算机的一个操作过程实现的程序设计方法，又称为传统的程序设计。面向过程程序设计的关键是规划算法和数据结构。前一页休息57面向对象的程序设计面向对象程序设计模拟自然界认识和处理事物的方法,将数据和对数据的操作方法组织在一起，形成一个相对独立的整体，称为对象对象是活动的，对象行为靠消息触发而激活面向对象程序设计的关键是确定对象并对其分类前一页休息58程序设计过程传统的程序设计过程主要包括以下几个阶段：1．分析问题通过原始资料，取得对问题的一个清晰的理解，进而确定解决问题的目标（称为输出）以及实现该目标所需要的条件（称为输入）。前一页休息59程序设计过程2．设计算法与数据结构数据结构描述了问题涉及的对象之间的联系和组织结构；算法描述了求解问题的步骤或规则。设计合理的数据结构往往可以简化算法，而好的算法又使程序具有更高的效率。前一页休息60程序设计过程3．检查算法使用多组样本数据，通过手工计算，对方案的正确性进行证明和验证。前一页休息61程序设计过程4．编码实现选用一种程序设计语言（如FORTRAN语言）将算法转换成计算机能够理解的程序（称为编程）。良好的编程风格是程序具备可靠性、可读性和可维护性的基本保证。前一页休息62程序设计过程5．测试和调式程序“测试”是在计算机上用样本数据运行程序，测试代码的正确性。“调式”就是查找和排除程序错误，直到能够得到正确的运行结果为止。通常将程序中的错误称为bug，它可能是语法错误，也可能是逻辑错误。大多数语法错误容易找到和改正，但逻辑错误就较难找到，因为导致逻辑错误的原因很多。前一页休息63程序设计语言为计算机编写软件需要使用程序设计语言。FORTRAN语言，用于科学计算极为简单，是目前用于科学计算的程序设计语言之一。前一页休息64