Fortran程序设计(第3章-程序的算法)课件

1、Fortran程序设计(第3章-程序的算法)第第3 3章章 程序的灵魂算法程序的灵魂算法3.1 3.1 算法的概念算法的概念3.2 3.2 简单算法的举例简单算法的举例3.3 3.3 算法的特性算法的特性3.4 3.4 怎样表示一个算法怎样表示一个算法Fortran程序设计(第3章-程序的算法)2第第3 3章章 程序的灵魂算法程序的灵魂算法一个程序包括以下两个方面的内容：一个程序包括以下两个方面的内容：1 1、对数据形式的描述。、对数据形式的描述。 在程序中要制定数据的类型和数据的组织形式，即数在程序中要制定数据的类型和数据的组织形式，即数据结构据结构。2 2、对操作的描述。即操作步骤，也就是

2、算法。、对操作的描述。即操作步骤，也就是算法。 数据是操作的对象，造作的目的就是对数据进行加工数据是操作的对象，造作的目的就是对数据进行加工处理，以得到期望的结果。作为程序设计人员，必须认真处理，以得到期望的结果。作为程序设计人员，必须认真考虑和设计数据结构和操作步骤（算法）。著名计算机科考虑和设计数据结构和操作步骤（算法）。著名计算机科学沃思提出一个公式：学沃思提出一个公式：数据结构算法程序。数据结构算法程序。 由于算法的重要性，在本章中先介绍有关算法的初步由于算法的重要性，在本章中先介绍有关算法的初步知识，以便为后面各章学习建立一定的基础。知识，以便为后面各章学习建立一定的基础。Fortr

3、an程序设计(第3章-程序的算法)3第第3 3章章 程序的灵魂算法程序的灵魂算法3.1 3.1 算法的概念算法的概念 广义地说，为解决一个问题而采取地方法和步广义地说，为解决一个问题而采取地方法和步骤，就称为骤，就称为“算法算法”（algorithmalgorithm）。列如，描述太）。列如，描述太极拳动作的图解，就是极拳动作的图解，就是“太极拳的算法太极拳的算法”。一首歌。一首歌曲的乐谱，也可以称为该歌曲的算法，因为它指定曲的乐谱，也可以称为该歌曲的算法，因为它指定了演奏歌曲的每一个步骤，按照它的规定就能演奏了演奏歌曲的每一个步骤，按照它的规定就能演奏出预定的曲子。出预定的曲子。计算机算法可

4、分为两大类：计算机算法可分为两大类： 数值运算算法数值运算算法 非数值运算算法非数值运算算法Fortran程序设计(第3章-程序的算法)4第第3 3章章 程序的灵魂算法程序的灵魂算法3.1 算法的概念算法的概念【例例3.1】求求1*2*3*4*5 可以用最原始的方法进行：可以用最原始的方法进行： 步骤步骤1：先求：先求1*2，得到结果，得到结果2。 步骤步骤2：将步骤：将步骤1得到的乘积得到的乘积2再乘以再乘以3，得到结，得到结果果6。 步骤步骤3：将：将6乘以乘以4，得，得24。 步骤步骤4：将：将24再乘以再乘以5，得，得120。Fortran程序设计(第3章-程序的算法)5第第3 3章章

5、 程序的灵魂算法程序的灵魂算法 这样得算法虽然是正确得，但太繁琐。如果这样得算法虽然是正确得，但太繁琐。如果求求1 1* *2 2* *3 3* * *10001000，则要写，则要写999999个步骤，显然是不个步骤，显然是不可取的。可取的。 可以设两个变量：一个变量代表被乘数，一可以设两个变量：一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。直接将每一步骤的乘积放在被乘数变量中。 设设p p为被乘数，为被乘数，i i为乘数。用循环算法来求结为乘数。用循环算法来求结果。可以将算法改写如下果。可以将

6、算法改写如下: :Fortran程序设计(第3章-程序的算法)6第第3 3章章 程序的灵魂算法程序的灵魂算法S1:使使p1S2:使使i2S3:使使p*I，乘积仍放在变量，乘积仍放在变量p中，可表示为：中，可表示为： p*i pS4:使使i的值加的值加1，即，即i1 iS5:如果如果i不大于不大于5，返回重新执行步骤，返回重新执行步骤S3以及其后的以及其后的 步骤步骤S4 和和S5；否则，算法结束。；否则，算法结束。Fortran程序设计(第3章-程序的算法)7第第3 3章章 程序的灵魂算法程序的灵魂算法【例例3.2】有有50个学生，要求将他们乘积在个学生，要求将他们乘积在80分以上的分以上的

7、学生和成绩输出。学生和成绩输出。 用用n表示学生学号，表示学生学号，n1代表第一个学生学号，代表第一个学生学号，ni代表代表第第i个学生学号。用个学生学号。用g代表学生乘积，代表学生乘积，gi代表第代表第i个学生成个学生成绩，算法可表示如下：绩，算法可表示如下： S1：1 I S2：如果：如果gi80，则输出，则输出ni和和gi；否则不输出；否则不输出 S3：i1 i S4：如果：如果i50，返回，返回s2，继续执行；否则，算法结束。，继续执行；否则，算法结束。 Fortran程序设计(第3章-程序的算法)8第第3 3章章 程序的灵魂算法程序的灵魂算法【列列3.3】判定判定20002500年中

8、哪一年为闰年。年中哪一年为闰年。 闰年的条件是：闰年的条件是：1、能被、能被4整除但又不能被整除但又不能被100整除的年份是闰年，如整除的年份是闰年，如1996年、年、2004年；年；2、能被、能被100整除又能被整除又能被400整除的年份是闰年，如整除的年份是闰年，如1600年、年、2000年。设年。设y为被检测的年份。可采用以下步骤：为被检测的年份。可采用以下步骤： S1：2000 y S2：若：若y不能被不能被4整除，则输出整除，则输出“y不是闰年不是闰年”。然后转到。然后转到S6 S3：若：若y能被能被4整除，不能被整除，不能被100整除，则输出整除，则输出“y是闰年是闰年”。然后转到

9、然后转到S6 Fortran程序设计(第3章-程序的算法)9第第3 3章章 程序的灵魂算法程序的灵魂算法【列列3.3】判定判定20002500年中哪一年为闰年。年中哪一年为闰年。 S4：若：若y能被能被100整除，又能被整除，又能被400整除，输出整除，输出“y是闰年是闰年”，然后转到然后转到S6 S5：输出：输出“y不是闰年不是闰年” S6：y1 y S7：当：当y 2500时，转时，转S2继续执行，否则算法停止。继续执行，否则算法停止。 如果如果i50，返回，返回s2，继续执行；否则，算法结束。，继续执行；否则，算法结束。 Fortran程序设计(第3章-程序的算法)10第第3 3章章 程

10、序的灵魂算法程序的灵魂算法【例例3.4】求求1-1/2+1/3-1/4+1/99-1/100 算法表示如下：算法表示如下： S1：sign=1 S2：sum=1 S3：deno=2 S4： sign=(-1)*sign S5 ：term=sign*(1/deno) S6 ：sum=sum+term S7 ：deno=deno1 S8 ：deno100返回返回S4；否则算法结束。；否则算法结束。Fortran程序设计(第3章-程序的算法)11第第3 3章章 程序的灵魂算法程序的灵魂算法【例例3.5】对一个大于等于对一个大于等于3的正整数，判断它是不是一个素数。的正整数，判断它是不是一个素数。 所

11、谓素数，是指除了所谓素数，是指除了1和该数的本身之外，不能被其它任何整数整除的和该数的本身之外，不能被其它任何整数整除的数。例如，数。例如，13是素数，因为它不能被是素数，因为它不能被2，3，4，12整除。整除。 判断一个数判断一个数n是否是素数的方法很简单；将是否是素数的方法很简单；将n作为被除数，将作为被除数，将2到到n1各各个整数先后作为除数，如果都不能被整除，则个整数先后作为除数，如果都不能被整除，则n为素数。为素数。 算法表示如下：算法表示如下： S1：输入：输入n的值的值 S2：i2（i作为除数）作为除数） S3：n被被i除，得余数除，得余数r S4：如果：如果r0，表示，表示n被

12、被i整除，则输出整除，则输出n“不是素数不是素数”，算法结束，算法结束; 否则执行否则执行S3 S5 ：i+1 i S6 ：如果：如果i n1，返回，返回S3，否则输出，否则输出n“是素数是素数”，然后结束。，然后结束。 Fortran程序设计(第3章-程序的算法)12第第3 3章章 程序的灵魂算法程序的灵魂算法 3.3 3.3 算法的特性算法的特性 一个程序应该具有以下特征：一个程序应该具有以下特征：1 1、有穷性。、有穷性。 一个算法应包含有限的操作步骤，而不能是无限的。事实一个算法应包含有限的操作步骤，而不能是无限的。事实上，上，“有穷性有穷性”往往指往往指“在合理的范围之内在合理的范围

13、之内”。如果让计算。如果让计算机执行一个历时机执行一个历时10001000年才能结束的算法，这虽然是有穷的，年才能结束的算法，这虽然是有穷的，但超过合理的限度，人们也不把它视为有效算法。究竟什么但超过合理的限度，人们也不把它视为有效算法。究竟什么算算“合理的限度合理的限度”，并无严格标准，由人们的常识和需要而，并无严格标准，由人们的常识和需要而定。定。2 2、确定性。、确定性。 算法中的每一个步骤应当是确定的，而不应该是含糊的、算法中的每一个步骤应当是确定的，而不应该是含糊的、模棱两可的。模棱两可的。Fortran程序设计(第3章-程序的算法)13第第3 3章章 程序的灵魂算法程序的灵魂算法3

14、.3 3.3 算法的特性算法的特性 一个程序应该具有以下特征：一个程序应该具有以下特征：3 3、有零个或多个输入。、有零个或多个输入。 所谓输入是指在执行算法时需要从外界取得必要的信所谓输入是指在执行算法时需要从外界取得必要的信息。息。4 4、有一个或多个输出。、有一个或多个输出。 算法的目的是为了求解，算法的目的是为了求解，“解解”就是输出。就是输出。5 5、有效性。、有效性。 算法中的每一个步骤都应当能有效的执行，并得到确算法中的每一个步骤都应当能有效的执行，并得到确定的结果。定的结果。Fortran程序设计(第3章-程序的算法)14第第3 3章章 程序的灵魂算法程序的灵魂算法3.4 3.

15、4 怎样表示一个算法怎样表示一个算法 为了表示一个算法，可以用不同的方法。为了表示一个算法，可以用不同的方法。常用的有：常用的有： 自然语言自然语言 传统流程图传统流程图 N-S N-S流程图流程图 伪代码伪代码 PDA PDA图等图等Fortran程序设计(第3章-程序的算法)15第第3 3章章 程序的灵魂算法程序的灵魂算法N-SN-S流程图介绍流程图介绍 19731973年美国学者年美国学者 I.Nassi I.Nassi 和和 B.Sheiderman B.Sheiderman 提出提出了一种新的流程图形式。在这种流程图中，完全去掉了一种新的流程图形式。在这种流程图中，完全去掉了带箭头的

16、流程线。全部算法写在一个矩形框内。在了带箭头的流程线。全部算法写在一个矩形框内。在该框内还可以包含其它的从属于它的框，或者说，由该框内还可以包含其它的从属于它的框，或者说，由一些基本的框组成一个大框。这种适于结构化程序设一些基本的框组成一个大框。这种适于结构化程序设计的流程图又称计的流程图又称N-SN-S结构化流程图。结构化流程图。 Fortran程序设计(第3章-程序的算法)16第第3 3章章 程序的灵魂算法程序的灵魂算法N-S流程图介绍流程图介绍 N-S流程图用以下的流程图符号流程图用以下的流程图符号:(1)顺序结构：顺序结构如下图所示。顺序结构：顺序结构如下图所示。A和和B两个框组成一个

17、顺序结两个框组成一个顺序结构。构。 A B Fortran程序设计(第3章-程序的算法)17第第3 3章章 程序的灵魂算法程序的灵魂算法N-SN-S流程图介绍流程图介绍 N-SN-S流程图用以下的流程图符号流程图用以下的流程图符号: :(2)(2)选择结构：选择结构如下图所示。当选择结构：选择结构如下图所示。当p p条件成立时执行条件成立时执行S S操作，操作，p p不成立则执行不成立则执行B B操作结构。操作结构。 p 成立 不成立 A BFortran程序设计(第3章-程序的算法)18第第3 3章章 程序的灵魂算法程序的灵魂算法(3)(3)循环结构：循环结构： 当型循环结构下，图符当型循环

18、结构下，图符表示先判断后执行，当表示先判断后执行，当p p条件条件成立时反复执行成立时反复执行A A操作，直到操作，直到p p条件不成立为止。条件不成立为止。 直到型循环结构下，图符直到型循环结构下，图符表示先执行后判断，当表示先执行后判断，当p p条件条件不成立时反复执行不成立时反复执行A A操作，直操作，直到到p p条件成立为止。条件成立为止。当p1A直到p2AFortran程序设计(第3章-程序的算法)19第第3 3章章 程序的灵魂算法程序的灵魂算法【例例3.113.11】将例将例3.13.1的求的求5 5！算法用！算法用N-SN-S图表示意。图表示意。 1 1T TT T2 2I IT

19、 T* *I II+1I+1I II I5 5打印打印T TFortran程序设计(第3章-程序的算法)20第第3 3章章 程序的灵魂算法程序的灵魂算法PROGRAM EXAMINTEGER P,IP=1I=2DO 10,WHILE (I.LT.6) P=P*I I=I+110 CONTINUE PRINT*,P ENDFortran程序设计(第3章-程序的算法)21第第3 3章章 程序的灵魂算法程序的灵魂算法【例例3.123.12】将例将例3.23.2的算法用的算法用N-SN-S图表示。将图表示。将5050名学生名学生成绩高于成绩高于8080分的学号和成绩打印出来。分的学号和成绩打印出来。F

20、ortran程序设计(第3章-程序的算法)22第第3 3章章 程序的灵魂算法程序的灵魂算法 PROGRAM EXAM INTEGER NUM,GRADE I=010 READ*,NUM,GRADE IF(GRADE.GT.80)PRINT*,NUM,GRADE I=I+1 IF(I50)GOTO 10 ENDFortran程序设计(第3章-程序的算法)23第第3 3章章 程序的灵魂算法程序的灵魂算法【例例3.133.13】将例将例3.33.3判定闰年的算法用判定闰年的算法用N-SN-S图表示。图表示。Fortran程序设计(第3章-程序的算法)24第第3 3章章 程序的灵魂算法程序的灵魂算法P

21、ROGRAM EXAMINTEGER YEARREDA*,YEARIF(MOD(YEAR,4).EQ.0)THEN IF(MOD(YEAR,100).NE.0)THEN PRINT*,是闰年是闰年 ELSE IF(MOD(YEAR,400).NE.0)THEN PRINT*,是闰年是闰年 ELSE PRINT*,不是闰年不是闰年 END IF END IF ELSE PRINT*,不是闰年不是闰年 END IF ENDFortran程序设计(第3章-程序的算法)25第第3 3章章 程序的灵魂算法程序的灵魂算法【例例3.143.14】将例将例3.43.4的算法用的算法用N-SN-S图表示。图表示

22、。 求求1-1/2+1/3-1/4+1-1/2+1/3-1/4+1/99-1/100+1/99-1/100。Fortran程序设计(第3章-程序的算法)26第第3 3章章 程序的灵魂算法程序的灵魂算法 PROGRAM EXAM SUM=1.0 DENO=2.0 SIGN=110 SIGN=(-1)*SIGN TERM=SIGN/DENO SUM=SUM+TERM DENO=DENO+1 IF(DENO.LE.100.0)GOTO 10 PRINT*,SUM ENDFortran程序设计(第3章-程序的算法)27第第3 3章章 程序的灵魂算法程序的灵魂算法用传统流程图表示求解以下问题的算法用传统

23、流程图表示求解以下问题的算法 有两个瓶子有两个瓶子A A和和B B，分别盛放醋和酱油，要求将他，分别盛放醋和酱油，要求将他们互换。们互换。 依次将依次将1010个数输入，要求将其中最大的数输出个数输入，要求将其中最大的数输出 有有3 3个数个数a a，b b，c c，要求按大小顺序把他们输出，要求按大小顺序把他们输出 求求1 12 23 3100100 判断一个数判断一个数n n能否同时被能否同时被3 3和和5 5整除整除 将将100100200200之间的素数输出之间的素数输出 求两个数求两个数m m和和n n的最大公约数的最大公约数Fortran程序设计(第3章-程序的算法)28第第3 3章章 程序的灵魂算法程序的灵魂算法例题例题1 1：有两个瓶子：有两个瓶子A A和和B B，分别盛放醋和酱油，要求将他，分别盛放醋和酱油，要求将他们互换。们互