《02第二章 程序的灵魂——算法.ppt》由会员分享，可在线阅读，更多相关《02第二章 程序的灵魂——算法.ppt（69页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章第二章 程序的灵魂程序的灵魂算法算法本章要点本章要点v算法的概念算法的概念v算法的表示算法的表示v结构化程序设计方法结构化程序设计方法本章内容本章内容2.1 2.1 算法的概念算法的概念2.2 2.2 简单算法举例简单算法举例2.3 2.3 算法的特性算法的特性2.4 2.4 怎样表示一个算法怎样表示一个算法2.5 2.5 结构化程序设计方法结构化程序设计方法 2.1 算法的概念算法的概念一个程序应包括两个方面的内容一个程序应包括两个方面的内容:v对数据的描述：数据结构对数据的描述：数据结构(data structure)v对操作的描述：算法对操作的描述：算法(algorithm)著名计
2、算机科学家沃思提出一个公式:数据结构数据结构+算法算法=程序程序 数据结构算法程序设计方法语言工具数据结构算法程序设计方法语言工具完整的程序设计应该是:2.1 算法的概念算法的概念 广义地说，为解决一个问题而采取的方法和步广义地说，为解决一个问题而采取的方法和步骤，就称为骤，就称为“算法算法”。v方法方法1：1+2，+3，+4，一直加到，一直加到100 加加99次次v方法方法2：100+(1+99)+(2+98)+(49+51)+50 =100+49100+50 加加51次次对同一个问题，可有不同的解题方法和步骤对同一个问题，可有不同的解题方法和步骤例：例：求求2.1 算法的概念算法的概念 为
3、了有效地进行解题，不仅需要保证算法正为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。希确，还要考虑算法的质量，选择合适的算法。希望方法简单，运算步骤少。望方法简单，运算步骤少。计算机算法可分为两大类别：计算机算法可分为两大类别：v数值运算算法：求数值解，例如求方程的根、求数值运算算法：求数值解，例如求方程的根、求函数的定积分等。函数的定积分等。v非数值运算：包括的面十分广泛，最常见的是用非数值运算：包括的面十分广泛，最常见的是用于事务管理领域，例如图书检索、人事管理、行于事务管理领域，例如图书检索、人事管理、行车调度管理等。车调度管理等。2.2 简单算法举例简单算
4、法举例例例2.1:求求12345 步骤步骤1 1：先求：先求1 12 2，得到结果，得到结果2 2步骤步骤2 2：将步骤：将步骤1 1得到的乘积得到的乘积2 2再乘以再乘以3 3，得到结果，得到结果6 6步骤步骤3 3：将：将6 6再乘以再乘以4 4，得，得2424步骤步骤4 4：将：将2424再乘以再乘以5 5，得，得120120如果要求如果要求1 12 210001000，则要写，则要写999999个步骤个步骤2.2 简单算法举例简单算法举例 S1：使：使p=1。S2：使：使i=2。S3：使：使pi，乘积仍放在，乘积仍放在p中，可表示为中，可表示为pi p S4：使：使i的值加的值加1，即
5、，即i+1 i。S5：如果：如果i不大于不大于5，返回重新执行步骤，返回重新执行步骤S3以及其后的以及其后的步骤步骤S4和和S5；否则，算法结束。最后得到；否则，算法结束。最后得到p的值就是的值就是5!的值。的值。可以设两个变量：可以设两个变量：一个变量代表被乘数，一个变一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。设将每一步骤的乘积放在被乘数变量中。设p p为被为被乘数，乘数，i i为乘数。用循环算法来求结果为乘数。用循环算法来求结果,算法可算法可改写：改写：2.2 简单算法举例简单算法举例S1
6、：1pS2：3 iS3：pi pS4：i+2 pS5：若：若i11，返回，返回S3。否则，结束。否则，结束。如果题目改为：求如果题目改为：求1 13 35 51111作很少的作很少的改动：改动：2.2 简单算法举例简单算法举例 用这种方法表示的算法具有通用性、灵活用这种方法表示的算法具有通用性、灵活性。性。S3S3到到S5S5组成一个循环，在实现算法时组成一个循环，在实现算法时 要要反复多次执行反复多次执行S3S3，S4S4，S5S5等步骤，直到某一时等步骤，直到某一时刻，执行刻，执行S5S5步骤时经过判断，乘数步骤时经过判断，乘数i i已超过规已超过规定的数值而不返回定的数值而不返回S3S3
7、步骤为止。此时算法结束，步骤为止。此时算法结束，变量变量p p的值就是所求结果。的值就是所求结果。2.2 简单算法举例简单算法举例#include void main()int p=1,i=2;int n;printf(请输入请输入n的值：的值：);scanf(%d,&n);while(i=n)p*=i;i=i+1;printf(%d!=%dn,n,p);2.2 简单算法举例简单算法举例#include void main()int p=1,i=2;int n;printf(请输入请输入n的值：的值：);scanf(%d,&n);while(p*=i+,i=n);printf(%d!=%dn,
8、n,p);2.2 简单算法举例简单算法举例例例2.2 有有50个学生，要求将他们之中成绩在个学生，要求将他们之中成绩在80分以分以上者打印出来。设上者打印出来。设n表示学号，表示学号，n1代表第一个学生代表第一个学生学号，学号，代表第代表第i个学生学号。用个学生学号。用G代表学生成绩代表学生成绩，gi代表第代表第i个学生成绩，算法表示如下个学生成绩，算法表示如下:S1S1：1 1 i i S2 S2：如果：如果8080，则输出，则输出n ni i和和g gi i，否则不输出。，否则不输出。S3S3：i+1 i+1 i i S4 S4：如果：如果i50i50，返回，返回S2S2，继续执行。否则算
9、法结束，继续执行。否则算法结束 变量变量i i作为下标，用来控制序号作为下标，用来控制序号(第几个学生，第几个学生，第几个成绩第几个成绩)。当。当i i超过超过5050时，表示时，表示 已对已对5050个学生个学生的成绩处理完毕，算法结束。的成绩处理完毕，算法结束。2.2 简单算法举例简单算法举例#include#include#include void main()int score50;int i=0;srand(unsigned)time(NULL);while(i50)scorei+=rand()%101;printf(成绩在成绩在80分以上的同学为：分以上的同学为：n);for(i=
10、0;i=80)printf(学号学号%d，成绩，成绩%dn,i+1,scorei);2.2 简单算法举例简单算法举例例例2.3 判定判定20002500年中的每一年是否闰年，将年中的每一年是否闰年，将结果输出。结果输出。分析：分析：闰年的条件是：闰年的条件是：(1)(1)能被能被4 4整除，但不能被整除，但不能被100100整除整除的年份都是闰年，如的年份都是闰年，如1996,20041996,2004年是闰年；年是闰年；(2)(2)能被能被100100整除，又能被整除，又能被400400整除的年份是闰年。如整除的年份是闰年。如1600,20001600,2000年年是闰年。不符合这两个条件的
11、年份不是闰年。是闰年。不符合这两个条件的年份不是闰年。2.2 简单算法举例简单算法举例设设y y为被检测的年份，算法可表示如下为被检测的年份，算法可表示如下：S1S1：2000 2000 y yS2S2：若：若y y不能被不能被4 4整除，则输出整除，则输出y y“不是闰年不是闰年”。然后转。然后转到到S6S6。S3S3：若：若y y能被能被4 4整除，不能被整除，不能被100100整除，则输出整除，则输出y y“是闰是闰年年”。然后转到。然后转到S6S6。S4S4：若：若y y能被能被100100整除，又能被整除，又能被400400整除，输出整除，输出y y“是闰是闰年年”，否则输出，否则输
12、出“不是闰年不是闰年”。然后转到然后转到S6S6。S5:S5:输出输出y y“不是闰年不是闰年”。S6S6：y+1 y+1 y yS7S7：当：当y2500y2500时，转时，转S2S2继续执行，如继续执行，如y y25002500，算法，算法停止。停止。2.2 简单算法举例简单算法举例 以上算法中每做一步都以上算法中每做一步都分别分离出一些范围分别分离出一些范围(已能判定为闰年或非已能判定为闰年或非闰年闰年)，逐步缩小范围，逐步缩小范围，直至执行直至执行S5S5时，只可能时，只可能是非闰年。是非闰年。“其它其它”包括能被包括能被4 4整除，整除，又能被又能被100100整除，而不整除，而不能
13、被能被400400整除的那些年整除的那些年份份(如如1990)1990)是非闰年。是非闰年。2.2 简单算法举例简单算法举例#include void main()int year;printf(请输入年份：请输入年份：);scanf(%d,&year);if(year%4=0&year%100!=0|year%100=0&year%400=0)printf(%d是闰年是闰年n,year);elseprintf(%d不是闰年不是闰年n,year);2.2 简单算法举例简单算法举例例例2.4 求求算法如下算法如下：S1S1：sign=1sign=1 S2 S2：sum=1sum=1 S3 S3：
14、deno=2deno=2 S4 S4：sign=(-1)sign=(-1)signsign S5 S5：term=signterm=sign(1/deno)(1/deno)S6 S6：sum=sum+termsum=sum+term S7 S7：deno=deno+1deno=deno+1 S8 S8：若：若deno100deno100返回返回S4S4，否则算法结束。，否则算法结束。单词作变量名，以使算单词作变量名，以使算法更易于理解：法更易于理解：sum表示累加和，表示累加和，deno是是英文分母（英文分母（denom inator）缩写，）缩写，sign代表代表数值的符号，数值的符号，te
15、rm代表代表某一项。某一项。反复执行反复执行S4S4到到S8S8步骤，直到分母大于步骤，直到分母大于100100为止。为止。一共执行了一共执行了9999次循环，向次循环，向sumsum累加入了累加入了9999个分数。个分数。sumsum最后的值就是多项式的值。最后的值就是多项式的值。2.2 简单算法举例简单算法举例#include#include void main()int sign=1,deno=2;float sum=1.0,term;while(deno=100)sign=(-1)*sign;term=sign*(1/(float)deno);sum+=term;deno+;print
16、f(算式的和为：算式的和为：%fn,sum);2.2 简单算法举例简单算法举例 例例2.5 对一个大于或等于对一个大于或等于3的正整数，判断它的正整数，判断它是不是一个素数。是不是一个素数。概念：概念：所谓素数，是指除了所谓素数，是指除了1 1和该数本身之外，不能被和该数本身之外，不能被其它任何整数整除的数。例如，其它任何整数整除的数。例如，1313是素数。因为它是素数。因为它不能被不能被2 2，3 3，4 4，1212整除。整除。分析：分析：判断一个数判断一个数n(n3)n(n3)是否素数的方法：是否素数的方法：将将n n作为被除数，将作为被除数，将2 2到到(n-1)(n-1)各个整数轮流
17、作为除数，各个整数轮流作为除数，如果都不能被整除，则如果都不能被整除，则n n为素数。为素数。2.2 简单算法举例简单算法举例算法如下算法如下：S1S1：输入：输入n n的值的值S2S2：i=2 i=2 （i i作为除数）作为除数）S3S3：n n被被i i除，得余数除，得余数r rS4S4：如果：如果r=0r=0，表示，表示n n能被能被i i整除，则打印整除，则打印n n“不是不是素数素数”，算法结束。否则执行，算法结束。否则执行S5S5S5S5：i+1i+1i iS6S6：如果：如果in-1in-1，返回，返回S3S3。否则打印。否则打印 n n“是素数是素数”。然后结束。然后结束。实际
18、上，实际上，n n不必被不必被2 2到到(n-1)(n-1)的整数除，只需被的整数除，只需被2 2到到n/2n/2间整数除，甚至只需被间整数除，甚至只需被2 2到到 之间的整数除即可。之间的整数除即可。2.2 简单算法举例简单算法举例#include#include void main()int i=2,k,flag=0,n;printf(请输入请输入n的值：的值：);scanf(%d,&n);k=(int)sqrt(n);while(i=k)if(n%i=0)flag=1;break;i+;if(flag)printf(%d不是素数不是素数n,n);elseprintf(%d是素数是素数n,
19、n);2.3 算法的特性算法的特性v有穷性：有穷性：包含有限的操作步骤。包含有限的操作步骤。v确定性：确定性：算法中的每一个步骤都应当是确定的。算法中的每一个步骤都应当是确定的。v有零个或多个输入：有零个或多个输入：输入是指在执行算法时需要输入是指在执行算法时需要从外界取得必要的信息。从外界取得必要的信息。v有一个或多个输出：有一个或多个输出：算法的目的是为了求解，算法的目的是为了求解，“解解”就是输出。就是输出。v有效性：有效性：算法中的每一个步骤都应当能有效地执算法中的每一个步骤都应当能有效地执行，并得到确定的结果行，并得到确定的结果 。一个算法应该具有以下特点：一个算法应该具有以下特点：
20、2.4 算法的表示算法的表示可以用不同的方法表示算法，常用的有：可以用不同的方法表示算法，常用的有：自然语言自然语言传统流程图传统流程图结构化流程图结构化流程图伪代码伪代码PADPAD图图2.4.1 用自然语言表示算法用自然语言表示算法 自然语言就是人们日常使用的语言，可以是自然语言就是人们日常使用的语言，可以是汉语或英语或其它语言。用自然语言表示通俗易汉语或英语或其它语言。用自然语言表示通俗易懂，但文字冗长，容易出现懂，但文字冗长，容易出现“歧义性歧义性”。自然语。自然语言表示的含义往往不大严格，要根据上下文才能言表示的含义往往不大严格，要根据上下文才能判断其正确含义，描述包含分支和循环的算
21、法时判断其正确含义，描述包含分支和循环的算法时也不很方便。因此，除了那些很简单的问题外，也不很方便。因此，除了那些很简单的问题外，一般不用自然语言描述算法。一般不用自然语言描述算法。2.4.2 用流程图表示算法用流程图表示算法美国国家标准化协会美国国家标准化协会ANSI(American National ANSI(American National Standard Institute)Standard Institute)规定了一些常用的流程图符号：规定了一些常用的流程图符号：起止框起止框判断框判断框处理框处理框输入输入/输出框输出框注释框注释框流向线流向线连接点连接点2.4.2 用流程图
22、表示算法用流程图表示算法例例2.6 将求将求5!的算法用流程图表示的算法用流程图表示如果需要将最后结果打如果需要将最后结果打印出来，可在菱形框的印出来，可在菱形框的下面加一个输出框。下面加一个输出框。2.4.2 用流程图表示算法用流程图表示算法 例例2.7 将例将例2.2的算的算法用流程图表示。打印法用流程图表示。打印50名名 学生中成绩在学生中成绩在80分以上者的学号和成绩。分以上者的学号和成绩。2.4.2 用流程图表示算法用流程图表示算法如果如果包括这如果如果包括这个输入数据的部个输入数据的部分，流程图为分，流程图为2.4.2 用流程图表示算法用流程图表示算法 例例2.8 将将例例2.3判
23、定闰判定闰年的算法用年的算法用流程图表示流程图表示 用流程图表示算法要比用文字描述算法逻辑清晰、易于理解。2.4.2 用流程图表示算法用流程图表示算法例例2.9 将例将例2.4的算法用流程图表示的算法用流程图表示 2.4.2 用流程图表示算法用流程图表示算法 例例2.10 将例将例2.5判断素数判断素数的算法用流程图表示的算法用流程图表示 2.4.2 用流程图表示算法用流程图表示算法小结：小结：v流程图是表示算法的较好的工具。一个流程图是表示算法的较好的工具。一个流程图包括以下几部分流程图包括以下几部分：(1)表示相应操作的框；表示相应操作的框；(2)带箭头的流程线；带箭头的流程线；(3)框内
24、外必要的文字说明。框内外必要的文字说明。2.4.3 三种基本结构和改进的流程图三种基本结构和改进的流程图1.1.传统流程图的弊端传统流程图的弊端 传统流程图用流程线指出各框的执行顺序，传统流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可对流程线的使用没有严格限制。因此，使用者可以毫不受限制地使流程随意地转向，使流程图变以毫不受限制地使流程随意地转向，使流程图变得毫无规律，阅读者要花很大精力去追踪流程，得毫无规律，阅读者要花很大精力去追踪流程，使人难以理解算法的逻辑。如图：使人难以理解算法的逻辑。如图：2.4.3 三种基本结构和改进的流程图三种基本结构和改进的流程图传
25、统流程图的流程可以是：传统流程图的流程可以是：这种如同乱麻一样的算法称为这种如同乱麻一样的算法称为BSBS型算法，意型算法，意为一碗面条为一碗面条(A Bowl of Spaghetti)(A Bowl of Spaghetti)，乱无头绪。，乱无头绪。缺点：缺点：难以阅读、修改，使算法的可靠难以阅读、修改，使算法的可靠性和可维护性难以保证。性和可维护性难以保证。解决办法：解决办法：必须限制箭头的滥用，即不必须限制箭头的滥用，即不允许无规律地使流程随意转向，只能顺允许无规律地使流程随意转向，只能顺序地进行下去。序地进行下去。2.4.3 三种基本结构和改进的流程图三种基本结构和改进的流程图2.2
26、.三种基本结构三种基本结构 BohraBohra和和JacopiniJacopini提出了以下三种基本结构：提出了以下三种基本结构：顺序结构、选择结构、循环结构顺序结构、选择结构、循环结构 用这三种基本结构作为表示一个良好算法的用这三种基本结构作为表示一个良好算法的基本单元。基本单元。2.4.3 三种基本结构和改进的流程图三种基本结构和改进的流程图三种基本结构的图示：三种基本结构的图示：顺序结构顺序结构选择结构选择结构2.4.3 三种基本结构和改进的流程图三种基本结构和改进的流程图循环循环结构的图示：结构的图示：当型当型(While型型)循环结构循环结构 直到型直到型(Until型型)循环循环
27、 2.4.3 三种基本结构和改进的流程图三种基本结构和改进的流程图三种基本结构的共同特点：三种基本结构的共同特点：(1)(1)只有一个入口。只有一个入口。(2)(2)只有一个出口。（只有一个出口。（请注意：请注意：一个菱形判断框有两一个菱形判断框有两个出口，而一个选择结构只有一个出口。不要将个出口，而一个选择结构只有一个出口。不要将菱形框的出口和选择结构的出口混淆。）菱形框的出口和选择结构的出口混淆。）(3)(3)结构内的每一部分都有机会被执行到。结构内的每一部分都有机会被执行到。(4)(4)结构内不存在结构内不存在“死循环死循环”(无终止的循环无终止的循环)。2.4.3 三种基本结构和改进的
28、流程图三种基本结构和改进的流程图 图中没有一条从入图中没有一条从入口到出口的路径通过口到出口的路径通过A A框框不正确的流程表示：不正确的流程表示：流程内的死循环流程内的死循环2.4.3 三种基本结构和改进的流程图三种基本结构和改进的流程图小结：小结：v由三种基本结构顺序组成的算法结构，可以由三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。由基本结构所构成解决任何复杂的问题。由基本结构所构成的算法属于的算法属于“结构化结构化”的算法，它不存在的算法，它不存在无规律的转向，只在本基本结构内才允许无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳转。存在分支和向前或向后的跳转。2
29、.4.3 三种基本结构和改进的流程图三种基本结构和改进的流程图扩展：扩展：v只要具有上述四个只要具有上述四个特点的都可以作为特点的都可以作为基本结构。可以自基本结构。可以自己定义基本结构，己定义基本结构，并由这些基本结构并由这些基本结构组成结构化程序。组成结构化程序。此图符合基本结构的特点此图符合基本结构的特点2.4.3 三种基本结构和改进的流程图三种基本结构和改进的流程图 这是一个多分支这是一个多分支选择结构，根据表达选择结构，根据表达式的值决定执行路线。式的值决定执行路线。虚线框内的结构是一虚线框内的结构是一个入口一个出口，并个入口一个出口，并且有上述全部的四个且有上述全部的四个特点。由此
30、构成的算特点。由此构成的算法结构也是结构化的法结构也是结构化的算法。可以认为这是算法。可以认为这是由三种基本结构所派由三种基本结构所派生出来的。生出来的。2.4.4 用用N-S流程图表示算法流程图表示算法 19731973年美国学者年美国学者I.NassiI.Nassi和和B.ShneidermanB.Shneiderman提出了提出了一种新的流程图形式。在这种流程图中，完全去掉一种新的流程图形式。在这种流程图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，了带箭头的流程线。全部算法写在一个矩形框内，在该框内还可以包含其它的从属于它的框，或者说，在该框内还可以包含其它的从属于它的框，或
31、者说，由一些基本的框组成一个大的框。这种流程图又称由一些基本的框组成一个大的框。这种流程图又称N-SN-S结构化流程图。结构化流程图。2.4.4 用用N-S流程图表示算法流程图表示算法 N-SN-S流程图用以下的流程图符号：流程图用以下的流程图符号：(1)顺序结构顺序结构(2)选择结构选择结构(3)循环结构循环结构2.4.4 用用N-S流程图表示算法流程图表示算法 用三种用三种N-SN-S流程图中的基本框，可以组成复杂的流程图中的基本框，可以组成复杂的N-SN-S流流程图。图中的程图。图中的A A框或框或B B框，可以是一个简单的操作，也框，可以是一个简单的操作，也可以是三个基本结构之一。可以
32、是三个基本结构之一。A框可以是一个选择结构框可以是一个选择结构 B框可以是一个循环结构框可以是一个循环结构 2.4.4 用用N-S流程图表示算法流程图表示算法例例2.11 将例将例2.1的求的求5!算法用算法用N-S图表示图表示2.4.4 用用N-S流程图表示算法流程图表示算法例例2.12 将例将例2.2的算法用的算法用N-S图图表示。（打印表示。（打印50名学生中成绩高名学生中成绩高于于80分的学号和分的学号和成绩）成绩）没有输入数据没有输入数据2.4.4 用用N-S流程图表示算法流程图表示算法例例2.12 将例将例2.2的算法用的算法用N-S图图表示。（打印表示。（打印50名学生中成绩高名
33、学生中成绩高于于80分的学号和分的学号和成绩）成绩）有输入数据有输入数据2.4.4 用用N-S流程图表示算法流程图表示算法例例2.13 将例将例2.3判判定闰年的算定闰年的算法用法用N-S图图表示表示2.4.4 用用N-S流程图表示算法流程图表示算法例例2.14 将例将例2.4的算的算法用法用N-S图表示图表示2.4.4 用用N-S流程图表示算法流程图表示算法例例2.15 将例将例2.5判别判别素数的算法用素数的算法用N-S流流程图表示。程图表示。传统流程图分析：传统流程图分析：此图不符合基本结构特点！此图不符合基本结构特点！由于不能分解为三种基本结由于不能分解为三种基本结构，就无法直接用构，
34、就无法直接用N-SN-S流程流程图的三种基本结构的符号来图的三种基本结构的符号来表示。因此，应当先作必要表示。因此，应当先作必要的变换。的变换。出口出口1出口出口22.4.4 用用N-S流程图表示算法流程图表示算法例例2.15 将例将例2.5判别判别素数的算法用素数的算法用N-S流流程图表示。程图表示。传统流程图变换为：传统流程图变换为：一个出口一个出口2.4.4 用用N-S流程图表示算法流程图表示算法用用N-S流流程程图图表表示示：2.4.4 用用N-S流程图表示算法流程图表示算法N-SN-S图表示算法的优点图表示算法的优点v比文字描述直观、形象、比文字描述直观、形象、易于理解；比传统易于理
35、解；比传统流程图紧凑易画。尤其是它废除了流程线，流程图紧凑易画。尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成整个算法结构是由各个基本结构按顺序组成的，的，N-S流程图中的上下顺序就是执行时的流程图中的上下顺序就是执行时的顺序。用顺序。用N-S图表示的算法都是结构化的算图表示的算法都是结构化的算法，因为它不可能出现流程无规律的跳转，法，因为它不可能出现流程无规律的跳转，而只能自上而下地顺序执行。而只能自上而下地顺序执行。2.4.4 用用N-S流程图表示算法流程图表示算法小结：小结：v一个结构化的算法是由一些基本结构顺序组成一个结构化的算法是由一些基本结构顺序组成的。在基本结构之间
36、不存在向前或向后的跳转，的。在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内流程的转移只存在于一个基本结构范围之内(如如循环中流程的跳转循环中流程的跳转)；一；一 个非结构化的算法可个非结构化的算法可以用一个等价的结构化算法代替，其功能不变以用一个等价的结构化算法代替，其功能不变。如果一个算法不能分解为若干个基本结构，。如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法。则它必然不是一个结构化的算法。2.4.5 用伪代码表示算法用伪代码表示算法v概念：概念：伪代码是用介于自然语言和计算机语言之伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算
37、法。间的文字和符号来描述算法。v特点：特点：它如同一篇文章一样它如同一篇文章一样 ，自上而下地写下，自上而下地写下来。每一行来。每一行(或几行或几行)表示一个基本操作。它不用表示一个基本操作。它不用图形符号，因此书写方便图形符号，因此书写方便 、格式紧凑，也比较、格式紧凑，也比较好懂，也便于向计算机语言算法好懂，也便于向计算机语言算法(即程序即程序)过渡。过渡。v用处：用处：适用于设计过程中需要反复修改时的流程适用于设计过程中需要反复修改时的流程描述。描述。2.4.5 用伪代码表示算法用伪代码表示算法 IF x is positive THEN print x ELSE print-x也可以用
38、汉字伪代码表示：也可以用汉字伪代码表示：若若 x为正为正 打印打印 x 否则否则 打印打印-x也可以中英文混用，如：也可以中英文混用，如：IF x 为正为正 print x ELSE print-x例：例：“打印打印x x的绝对值的绝对值”的算法可以用伪代码表的算法可以用伪代码表示为：示为：2.4.5 用伪代码表示算法用伪代码表示算法开始开始 置置t的初值为的初值为1 置置i的初值为的初值为2 当当i=5，执行下面操作：，执行下面操作：使使t=ti 使使i=i+1 循环体到此结束循环体到此结束 输出输出t的值的值 结束结束也可以写成以下形式：也可以写成以下形式：BEGIN算法开始算法开始 1t
39、 2 i while i5 ti t i+1 i print t END算法结束算法结束例例2.16 求求5!。用伪代。用伪代码表示算法：码表示算法：2.4.5 用伪代码表示算法用伪代码表示算法例例2.17 输出输出50个学生个学生中成绩高于中成绩高于80分者的分者的学号和成绩。学号和成绩。用伪代码表示算法：用伪代码表示算法：BEGIN算法开始算法开始 1 i while i50 input ni and gi i+1 i 1 i while i50 if gi80 print ni and gi i+1 i END算法结束算法结束2.4.6 用计算机语言表示算法用计算机语言表示算法v概念：概
40、念：用计算机实现算法。计算机是无法识别流用计算机实现算法。计算机是无法识别流程图和伪代码的。只有用计算机语言编写的程序程图和伪代码的。只有用计算机语言编写的程序才能被计算机执行。因此在用流程图或伪代码描才能被计算机执行。因此在用流程图或伪代码描述出一个算法后，还要将它转换成计算机语言程述出一个算法后，还要将它转换成计算机语言程序。序。v特点：特点：用计算机语言表示算法必须严格遵循所用用计算机语言表示算法必须严格遵循所用的语言的语法规则，这是和伪代码不同的。的语言的语法规则，这是和伪代码不同的。v用处：用处：要完成一件工作，包括设计算法和实现算要完成一件工作，包括设计算法和实现算法两个部分。设计
41、算法的目的是为了实现算法。法两个部分。设计算法的目的是为了实现算法。2.4.6 用计算机语言表示算法用计算机语言表示算法#include void main()int i,t;t=1;i=2;while(i=5)t=t*i;i=i+1;printf(%dn,t);例例 2.20 将例将例2.16表表示的算法（求示的算法（求5!）用）用C语言表示。语言表示。2.4.6 用计算机语言表示算法用计算机语言表示算法v应当强调说明：应当强调说明：写出了写出了C C程序，仍然只是程序，仍然只是描述了算法，并未实现算法。只有运行程描述了算法，并未实现算法。只有运行程序才是实现算法。应该说，用计算机语言序才是
42、实现算法。应该说，用计算机语言表示的算法是计算机能够执行的算法。表示的算法是计算机能够执行的算法。2.5 结构化程序设计方法结构化程序设计方法v一个结构化程序一个结构化程序 就是用高级语言表示的结构化算就是用高级语言表示的结构化算法。用三种基本结构组成的程序必然是结构化的程法。用三种基本结构组成的程序必然是结构化的程序，这种程序便于编写、便于阅读、便于修改和维序，这种程序便于编写、便于阅读、便于修改和维护。护。v结构化程序设计强调程序设计风格和程序结构的规结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。范化，提倡清晰的结构。v结构化程序设计方法的基本思路是：把一个复杂问结构化
43、程序设计方法的基本思路是：把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。控制在人们容易理解和处理的范围内。2.5 结构化程序设计方法结构化程序设计方法采取以下方法来保证得到结构化的程序：采取以下方法来保证得到结构化的程序：v自顶向下；自顶向下；v逐步细化；逐步细化；v模块化设计；模块化设计；v结构化编码。结构化编码。两种不同的方法：两种不同的方法：v自顶向下，逐步细化；自顶向下，逐步细化；v自下而上，逐步积累。自下而上，逐步积累。2.5 结构化程序设计方法结构化程序设计方法 用这种方法逐步分解，直到作者认为
44、可以直接将用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫各小段表达为文字语句为止。这种方法就叫 做做“自顶自顶向下，逐步细化向下，逐步细化”。2.5 结构化程序设计方法结构化程序设计方法自顶向下，逐步细化方法的优点：自顶向下，逐步细化方法的优点：考虑周全，结构清晰，层次分明，作者容考虑周全，结构清晰，层次分明，作者容易写，读者容易看。如果发现某一部分中有易写，读者容易看。如果发现某一部分中有一段内容不妥，需要修改，只需找出该部分一段内容不妥，需要修改，只需找出该部分修改有关段落即可，与其它部分无关。我们修改有关段落即可，与其它部分无关。我们提倡用这种方法设计程
45、序。这就是用工程的提倡用这种方法设计程序。这就是用工程的方法设计程序。方法设计程序。2.5 结构化程序设计方法结构化程序设计方法模块设计的方法：模块设计的方法：模块化设计的思想实际上是一种模块化设计的思想实际上是一种“分而治之分而治之”的思的思想，把一个大任务分为若干个子任务，每一个子任想，把一个大任务分为若干个子任务，每一个子任务就相对简单了。务就相对简单了。在拿到一个程序模块以后，根据程序模块的功能将在拿到一个程序模块以后，根据程序模块的功能将它划分为若干个子模块，如果这些子模块的规模还它划分为若干个子模块，如果这些子模块的规模还嫌大，还再可以划分为更小的模块。这个过程采用嫌大，还再可以划分为更小的模块。这个过程采用自顶向下方法来实现。自顶向下方法来实现。子模块一般不超过子模块一般不超过5050行。行。划分子模块时应注意模块的独立性，即：使一个模划分子模块时应注意模块的独立性，即：使一个模块完成一项功能，耦合性愈少愈好。块完成一项功能，耦合性愈少愈好。