fortran语言编程第一章

1、第第1 1章章 引论引论FORTRANFORTRAN语言语言 前一页 休息2计算机算法计算机算法l 解 决 某 类 具 体 问 题 的 方 法 和 步 骤解 决 某 类 具 体 问 题 的 方 法 和 步 骤例如例如 看电影，通常需要如下的步骤来实现：看电影，通常需要如下的步骤来实现：买电影买电影票票 持票按时到指定电影院进场持票按时到指定电影院进场按指定座位坐下按指定座位坐下看电影看电影退场退场 前一页 休息3计算机算法计算机算法l利用计算机解决某类问题的方法和步利用计算机解决某类问题的方法和步骤骤 前一页 休息4算法按处理对象分类算法按处理对象分类l 数值算法数值算法数值计算数值计算l 非

2、数值算法非数值算法应用范围十分广泛，最常见的是事务应用范围十分广泛，最常见的是事务管理领域，例如图书检索、人事管理、管理领域，例如图书检索、人事管理、行车调度管理等行车调度管理等 前一页 休息5算法的表示算法的表示表示一个算法，可以用不同的方法，常用的有：表示一个算法，可以用不同的方法，常用的有： 自然语言自然语言 传统流程图传统流程图 结构化流程图结构化流程图 - 三种基本结构的流程图三种基本结构的流程图 - N-S流程图流程图 伪代码伪代码 IPO图图 前一页 休息6例例1用自然语言描述求解用自然语言描述求解“5!=？”的算法的算法 步骤步骤5：输出结果：输出结果120步骤步骤1：先求：先

3、求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+1IS4：将：将TI T S3：将：将1I S2: 将将 1TS1：输入：输入n值值设一个变量（设一个变量（T）代表）代

4、表被乘数，另外一个被乘数，另外一个变量（变量（I）代表乘）代表乘数，直接将每一步数，直接将每一步的乘积放在被乘数的乘积放在被乘数T变量中变量中 前一页 休息8传统流程图表示传统流程图表示 美国国家标准化协会美国国家标准化协会ANSI 规定的常用流程图符号规定的常用流程图符号 前一页 休息9例例3用传统流程图描述求解用传统流程图描述求解“n!=？”的算的算法法 开始开始 1 T 2 I TI T I+1 I I n 输出输出T 结束结束 是是否否 前一页 休息10例例4 用传统流程图表示用传统流程图表示 “判定一个大于或判定一个大于或 等于等于3的正整数是的正整数是 否是素数？否是素数？”的算法

5、的算法 前一页 休息11例例4用传统流程图表示用传统流程图表示“判定一个大于判定一个大于或等于或等于3的正整数是否是素数？的正整数是否是素数？”的算的算法法思路分析：思路分析：所谓素数（质数），是指除了所谓素数（质数），是指除了1和该数本和该数本身外不能被其他任何整数整除的数。身外不能被其他任何整数整除的数。因此，判断一个数因此，判断一个数n（n3）是否是素数）是否是素数的方法为，将的方法为，将n作为被除数，并用作为被除数，并用2到到（n-1）之间的各个整数轮流作为除数，）之间的各个整数轮流作为除数，若都不能被整除，则若都不能被整除，则n为素数。为素数。 前一页 休息12 前一页 休息13 前

6、一页 休息14结构化流程图表示结构化流程图表示l三种基本结构的流程图三种基本结构的流程图lN-S流程图流程图 前一页 休息15 (1)顺序结构顺序结构 a A B b 前一页 休息16(2) (2) 选择结构选择结构( (又称选取结构又称选取结构) ) 前一页 休息17(3) (3) 循环结构循环结构( (又称重复结构又称重复结构) ) 当型循环结构当型循环结构 直到型循环结构直到型循环结构当型循环和直到型循环结构条件互逆当型循环和直到型循环结构条件互逆 前一页 休息18三种基本结构的共同点三种基本结构的共同点l 只有一个入口，图中的只有一个入口，图中的a点点l 一个出口，图中的一个出口，图中

7、的b点点l 结构内的每一部分都有机会被执行结构内的每一部分都有机会被执行l 结构内不存在结构内不存在“死循环死循环” 由这三种基本结构所构成的算法由这三种基本结构所构成的算法称为称为结构化算法结构化算法，并可组合应用来，并可组合应用来解决任何复杂问题。解决任何复杂问题。 前一页 休息19 1971年由两位美国学年由两位美国学者提出了一种新的流程图形者提出了一种新的流程图形式，这种流程图完全去掉了式，这种流程图完全去掉了带箭头的流程线，称为带箭头的流程线，称为N-S流程图流程图。 N-S流程图流程图 前一页 休息20 顺序结构顺序结构 A B 选择结构选择结构 前一页 休息21 循环结构循环结构

8、 前一页 休息22例例5 用用N-S流程图表示求流程图表示求5!的算法的算法 前一页 休息23例例6 用用N-S流程图表示流程图表示表示表示“判定一个大于或等判定一个大于或等于于3的正整数是否是素数？的正整数是否是素数？”的算法的算法 前一页 休息24例例7 用用N-S流程图表示流程图表示 “判定判定20002500年年 中的每一年是否闰年，中的每一年是否闰年， 将结果输出。将结果输出。”的算法的算法 前一页 休息25例例7用用N-S流程图表示流程图表示“判定判定20002500年中的每年中的每一年是否闰年，将结果输出。一年是否闰年，将结果输出。”的算法的算法思路分析：思路分析： 能被能被4整

9、除但不能被整除但不能被100整除的年整除的年份，或者能被份，或者能被100整除同时又能整除同时又能被被400整除的年份，是闰年。整除的年份，是闰年。 前一页 休息26 前一页 休息27 例例88用伪代码表示求用伪代码表示求5!5!的算法的算法BEGIN t1 i2 do until i5 tt*i ii+1 enddo write tEND 前一页 休息28课堂练习课堂练习1 1如果将求解阶乘的问题改一下改为：如果将求解阶乘的问题改一下改为：计算计算1357911 请用自然语言描述其算法？请用自然语言描述其算法？ 前一页 休息29参考答案参考答案S1：将：将1 TS2：将：将3 IS3：将：将

10、TI TS4：将：将I+2 IS5：若：若I 11成立，返回重新执行成立，返回重新执行S3及及S4S6：输出：输出T 前一页 休息30用自然语言描述求解用自然语言描述求解“百钱百鸡百钱百鸡”的算的算法法 一只公鸡值五文钱一只公鸡值五文钱 一只母鸡值三文钱一只母鸡值三文钱 三只小鸡值一文钱三只小鸡值一文钱请问用一百文钱买一百只鸡，公鸡、母鸡请问用一百文钱买一百只鸡，公鸡、母鸡 和小鸡各有几只？和小鸡各有几只？课堂练习课堂练习2 2 前一页 休息31分析：分析：假设公鸡、母鸡和小鸡的个数分别为假设公鸡、母鸡和小鸡的个数分别为x,y和和z 数学模型数学模型 5X+3Y+Z/3=100 X+Y+Z=1

11、00 z=(100-5*x-3*y)*3 z是是3的倍数的倍数 z=100-x-y 前一页 休息32参考答案参考答案S1： X 0 S2： Y 0 S3：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 3给出给出 输入输入n个数据，找出最大的数个

12、数据，找出最大的数 算法算法N-S流程图流程图 前一页 休息34参考答案参考答案 前一页 休息35算法设计策略算法设计策略【例】 设有算式：A B C DC D C=A B C，其中的A，B，C，D均为一位非负整数，要求找出A，B，C，D各值。 前一页 休息36算法设计策略算法设计策略-枚举法枚举法 思路分析思路分析：l在有限的范围中，列举和检验所有可能的结果，从中在有限的范围中，列举和检验所有可能的结果，从中找出那些符合要求的候选解作为问题的解。找出那些符合要求的候选解作为问题的解。例如：设正整数例如：设正整数A A、B B、C C、D D，A A和和C C的取值范围应是的取值范围应是1,1

13、, 99，B B和和D D的取值范围应是的取值范围应是0,0, 99，分别对相应范围中，分别对相应范围中的每一个数值进行检测，输出满足条件（的每一个数值进行检测，输出满足条件（10001000A A100100B B1010C CD D）（）（100100C C1010D DC C）= =（100100A A1010B BC C）的数值。）的数值。 前一页 休息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 x1000a1

14、00b10cd y100c10dc z100a10bc if x-y=z then 输出输出a，b，c，d 前一页 休息38对付复杂性的基本方法对付复杂性的基本方法按功能划分按功能划分若干基本模块若干基本模块树状的程序结构树状的程序结构算法设计策略算法设计策略-分而治之分而治之 前一页 休息39算法设计策略算法设计策略-递归法递归法 当求解问题满足：当求解问题满足： (1) (1)：有递推关系：有递推关系 (2) (2)：有出口，通常使用递归法。：有出口，通常使用递归法。例如：求例如：求f(n)=n!f(n)=n! 可以理解为当可以理解为当n=1n=1时，时，f(n)=1(f(n)=1(出口出

15、口) ) 当当n=kn=k时，时，f(k)=f(k-1)f(k)=f(k-1)* *k(k(递推关系递推关系) )所以，可以用递归法求所以，可以用递归法求n!n! 前一页 休息40算法的主要特征算法的主要特征 有效性有效性 所有操作都应能有效地执行，并能得到确所有操作都应能有效地执行，并能得到确定的结果定的结果有穷性有穷性 总是可以在执行有限步有限的时间内完成总是可以在执行有限步有限的时间内完成确定性确定性 每个操作必须是明确的，对于相同的输每个操作必须是明确的，对于相同的输 入只能得出相同的结果入只能得出相同的结果输输 入入 一个算法可有零个或多个输入一个算法可有零个或多个输入输输 出出 一

16、个算法可以有一个或多个输出。一个算法可以有一个或多个输出。 任何一个算法至少应有一个输出任何一个算法至少应有一个输出 前一页 休息41算法的主要因素算法的主要因素 正确性正确性 算法应该满足具体问题的需求，正确反映求解算法应该满足具体问题的需求，正确反映求解 问题对输入、输出和加工处理等方面的需求。问题对输入、输出和加工处理等方面的需求。可读性可读性 可读性好的算法有助于对算法的理解，易于调可读性好的算法有助于对算法的理解，易于调 试和修改等试和修改等健壮性健壮性 当输入了非法数据时，算法应能适当地做出反当输入了非法数据时，算法应能适当地做出反 映或进行处理，输出表示错误性质的信息并中止映或进

17、行处理，输出表示错误性质的信息并中止高效性高效性 算法的时间开销和空间开销往往是相互制约的，算法的时间开销和空间开销往往是相互制约的， 对高时间效率和低内存空间占用量的要求，只能对高时间效率和低内存空间占用量的要求，只能 根据问题的性质折中处理根据问题的性质折中处理 前一页 休息42算法复杂性分析算法复杂性分析 前一页 休息43 例例99欲在按升序排列的欲在按升序排列的n n个元素个元素 a a1 1,a,a2 2, ,a,an n(a(ai iaai+1i+1) )中查找中查找 是否有与是否有与b b相同的元素。相同的元素。 算法一：从第一个元素算法一：从第一个元素a1开始逐一比较。开始逐一

18、比较。此时，最好的情况是此时，最好的情况是a1就是要查找的元素，就是要查找的元素，只需比较一次。最坏情况则需要比较只需比较一次。最坏情况则需要比较n次，次，即一直比较到即一直比较到an才能得到结果；假定每个才能得到结果；假定每个元素与元素与b相同是等概率的，则平均需要比相同是等概率的，则平均需要比较较n/2次。次。 前一页 休息44算法二：采用折半查找算法二：采用折半查找( (二分查找二分查找) )的方法，即的方法，即先用位居先用位居中点中点的元素的元素a a（n/2n/2）与与b b比较，比较， 若若b= ab= a（n/2n/2），则查找成功。，则查找成功。 若若baba（n/2n/2），

19、同时，同时b ba a（n/2n/2），则在，则在a a1 1,a,a2 2, ,a,a（n/2-1n/2-1）中采用上述方法继续查找；中采用上述方法继续查找； 否则在否则在a a（n/2+1n/2+1）,a,a（n/2+2n/2+2）, ,a,an n采用上述采用上述方法继续查找。方法继续查找。 这种算法最多也只需要比较这种算法最多也只需要比较loglog2 2n n次。次。 前一页 休息45算法复杂性分析算法复杂性分析 前一页 休息46 前一页 休息47结构化程序设计思想结构化程序设计思想 前一页 休息48软件开发过程软件开发过程软件的开发过程软件的开发过程 前一页 休息49软件开发过程软

20、件开发过程软件的开发过程软件的开发过程 前一页 休息50软件开发过程软件开发过程软件的开发过程软件的开发过程 前一页 休息51软件开发过程软件开发过程软件的开发过程软件的开发过程 前一页 休息52软件开发过程软件开发过程软件的开发过程软件的开发过程 前一页 休息53软件开发过程软件开发过程软件的开发过程软件的开发过程 前一页 休息54软件开发过程软件开发过程软件的开发过程软件的开发过程 前一页 休息55程序设计方法程序设计方法 程序设计是一个将人类思维转化程序设计是一个将人类思维转化为计算机思维的过程，可分为为计算机思维的过程，可分为面向过面向过程的程序设计程的程序设计和和面向对象的程序设计面

21、向对象的程序设计两大类。两大类。 前一页 休息56面向过程的程序设计面向过程的程序设计 l过程是过程是为了得到问题的解而执行的一步步的为了得到问题的解而执行的一步步的操作；操作；l面向过程的程序设计面向过程的程序设计是一种基于功能分析及是一种基于功能分析及每个功能由计算机的一个操作过程实现的程每个功能由计算机的一个操作过程实现的程序设计方法，又称为传统的程序设计。序设计方法，又称为传统的程序设计。l面向过程程序设计的面向过程程序设计的关键是规划算法和数据关键是规划算法和数据结构。结构。 前一页 休息57面向对象的程序设计面向对象的程序设计 l面向对象程序设计面向对象程序设计模拟自然界认识和处理

22、事模拟自然界认识和处理事物的方法物的方法,将数据和对数据的操作方法组织在将数据和对数据的操作方法组织在一起，形成一个相对独立的整体，称为一起，形成一个相对独立的整体，称为对象对象l对象是活动的，对象行为靠消息触发而激活对象是活动的，对象行为靠消息触发而激活l面向对象程序设计的面向对象程序设计的关键是确定对象并对其关键是确定对象并对其分类分类 前一页 休息58程序设计过程程序设计过程传统的程序设计过程主要包括以下几个阶段：传统的程序设计过程主要包括以下几个阶段：1分析问题分析问题 通过原始资料，取得对问题的一个清晰的通过原始资料，取得对问题的一个清晰的理解，进而确定解决问题的目标（称为理解，进而确定解决问题的目标（称为输出输出）以及实现该目标所需要的条件（称为以及实现该目标所需要的条件（称为输入输入）。）。 前一页 休息59程序设计过程程序设计过程2设计算法与数据结构设计算法与数据结构 数据结构描述了问题涉及的对象之间的联数据结构描述了问题涉及的对象之间的联系和组织结构系和组织结构；算法描述了求解问题的步算法描述了求解问题的步骤或规则骤或规则。设计合理的数据结构往往可以。设计合理的数据