1、辅导课程二辅导课程二2.1算法的概念算法的概念2.2简单算法举例简单算法举例2.3算法的特性算法的特性2.4怎样表示一个算法怎样表示一个算法2.5结构化程序设计方法结构化程序设计方法习题习题第第2 2章章 程序的灵魂程序的灵魂算法算法一个程序应包括以下两方面内容一个程序应包括以下两方面内容:(1)对数据的描述。在程序中要指定数据的类型和对数据的描述。在程序中要指定数据的类型和数据的组织形式，即数据结构数据的组织形式，即数据结构(data structure)。(2)对操作的描述。即操作步骤，对操作的描述。即操作步骤，也就是算法也就是算法(algorithm)。数据是操作的对象，操作的目的是对数
2、据进行加数据是操作的对象，操作的目的是对数据进行加工处理，以得到期望的结果。作为程序设计人员，工处理，以得到期望的结果。作为程序设计人员，必须认真考虑和设计数据结构和操作步骤必须认真考虑和设计数据结构和操作步骤(即算法即算法)。因此，著名计算机科学家沃思因此，著名计算机科学家沃思(Nikiklaus Wirth)提提出一个公式出一个公式数据结构数据结构+算法算法=程序程序实际上，一个程序除了以上两个主要要素之外，还应实际上，一个程序除了以上两个主要要素之外，还应当采用结构化程序设计方法进行程序设计，并且用某当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示。因此，可以这样表示：一
3、种计算机语言表示。因此，可以这样表示：程序程序=算法算法+数据结构数据结构+程序设计方法程序设计方法+语言工具和语言工具和环境环境也就是说，以上也就是说，以上4个方面是一个程序设计人员所应具个方面是一个程序设计人员所应具备的知识。在设计一个程序时要综合运用这几方面的备的知识。在设计一个程序时要综合运用这几方面的知识。在这知识。在这4个方面中，算法是灵魂，数据结构是加个方面中，算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。工对象，语言是工具，编程需要采用合适的方法。算算法是解决法是解决“做什么做什么”和和“怎么做怎么做”的问题的问题。程序中的。程序中的操作语句，实际上就是算
4、法的体现。显然，操作语句，实际上就是算法的体现。显然，不了解算不了解算法就谈不上程序设计法就谈不上程序设计。本章的学习目的：通过介绍有关算法本章的学习目的：通过介绍有关算法的初步知识，让学习者能够了解如何编的初步知识，让学习者能够了解如何编写写C程序，从而为后面各章的学习建立程序，从而为后面各章的学习建立一定的基础。一定的基础。2.1 算算 法法 的的 概概 念念算法：为解决一个问题而采取的算法：为解决一个问题而采取的方法和步骤方法和步骤。对同一个问题，可以有不同的解题方法和步骤。对同一个问题，可以有不同的解题方法和步骤。方法有优劣之分。有的方法只需进行很少的步骤，方法有优劣之分。有的方法只需
5、进行很少的步骤，而有些方法则需要较多的步骤。而有些方法则需要较多的步骤。例：高斯求解例：高斯求解1到到100的连加。的连加。一般说，希望采用简单的和运算步骤少的方法。一般说，希望采用简单的和运算步骤少的方法。因此因此，为了有效地进行解题，不仅需要保证算，为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。法正确，还要考虑算法的质量，选择合适的算法。本书通过一些典型算法的介绍，帮助读本书通过一些典型算法的介绍，帮助读者了解如何设计一个算法，推动读者举者了解如何设计一个算法，推动读者举一反三。希望读者通过本章介绍的例子一反三。希望读者通过本章介绍的例子了解怎样提出问题，怎
6、样思考问题，怎了解怎样提出问题，怎样思考问题，怎样表示一个算法。样表示一个算法。2.2 简单算法举例简单算法举例例例2.1 求求12345。可以用最原始的方法进行。可以用最原始的方法进行。步骤步骤1：先求先求12，得到结果，得到结果2。步骤步骤2：将步骤将步骤1得到的乘积得到的乘积2再乘以再乘以3，得到结果，得到结果6。步骤步骤3：将将6再乘以再乘以4，得，得24。步骤步骤4：将将24再乘以再乘以5，得，得120。这就是最后的结果。这就是最后的结果。这样的算法虽然是正确的，但太繁琐。如果要求这样的算法虽然是正确的，但太繁琐。如果要求121000，则要写，则要写999个步骤，显然是不可取个步骤，
7、显然是不可取的。而且每次都直接使用上一步骤的数值结果的。而且每次都直接使用上一步骤的数值结果(如如2，6，24等等)，也不方便。应当找到一种通用的表示方法。，也不方便。应当找到一种通用的表示方法。可以设两个变量，一个变量代表被乘数，一个变量代可以设两个变量，一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每一步表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。今设骤的乘积放在被乘数变量中。今设p为被乘数，为被乘数，i为乘为乘数。用循环算法来求结果。可以将算法改写如下：数。用循环算法来求结果。可以将算法改写如下：S1：使使p=1S2：使使i=2S3：使
8、使pi，乘积仍放在变量乘积仍放在变量p中，可表示为中，可表示为pi=pS4：使使i的值加的值加1，即，即i+1=iS5：如果如果i不大于不大于5，返回重新执行步骤，返回重新执行步骤S3以及以及其后的步骤其后的步骤S4和和S5；否则，算法结束。最后得到否则，算法结束。最后得到p的值的值就是就是5!的值。的值。如果题目改为求如果题目改为求1357911。算法只需作很少的改动即可：算法只需作很少的改动即可：S1：1=pS2：3=iS3：pi=pS4：i+2=iS5：若若i11，返回，返回S3；否则，结束。否则，结束。可以看出，用这种方法表示的算法具有通用可以看出，用这种方法表示的算法具有通用性、灵活
9、性。性、灵活性。例例2.2 有有50个学生，要求将他们之中成绩在个学生，要求将他们之中成绩在80分以上者分以上者打印出来。用打印出来。用n表示学生学号，表示学生学号，n1代表第一个学生学号，代表第一个学生学号，ni代表第代表第i个学生学号。用个学生学号。用g代表学生成绩，代表学生成绩，gi代表第代表第i个个学生成绩，算法可表示如下。学生成绩，算法可表示如下。S1：1=iS2：如果：如果gi80，则打印，则打印ni和和gi，否则不打印，否则不打印S3：i+1=iS4：如果：如果i50，返回，返回S2，继续执行；否则，算法，继续执行；否则，算法结束。结束。本例中，变量本例中，变量i作为下标，用它来
10、控制序号作为下标，用它来控制序号(第几个学生，第几个学生，第几个成绩第几个成绩)。当。当i超过超过50时，表示已对时，表示已对50个学生的成绩个学生的成绩处理完毕，算法结束。处理完毕，算法结束。例例2.3 判定判定20002500年中的每一年是否闰年，年中的每一年是否闰年，将结果输出。将结果输出。在考虑算法时，应当仔细分在考虑算法时，应当仔细分析所需判断的条件，如何一析所需判断的条件，如何一步一步缩小被判断的范围。步一步缩小被判断的范围。有的问题，判断的先后次序有的问题，判断的先后次序是无所谓的，而有的问题，是无所谓的，而有的问题，判断条件的先后次序是不能判断条件的先后次序是不能任意颠倒的，读
11、者可根据具任意颠倒的，读者可根据具体问题决定其逻辑。体问题决定其逻辑。请自学例请自学例2.4和例和例2.52.3 算法的特性算法的特性 一个算法应该具有以下特点：一个算法应该具有以下特点：1.有穷性有穷性 一个算法应包含有限的操作步骤，而不能是无一个算法应包含有限的操作步骤，而不能是无限的。限的。事实上，事实上，“有穷性有穷性”往往指往往指“在合理的范围之在合理的范围之内内”。究竟什么算。究竟什么算“合理限度合理限度”，并无严格标准，并无严格标准，由人们的常识和需要而定。由人们的常识和需要而定。2.确定性确定性 算法中的每一个步骤都应当是确定的，而不应算法中的每一个步骤都应当是确定的，而不应当
12、是含糊的、模棱两可的。当是含糊的、模棱两可的。3.有零个或多个输入有零个或多个输入 所谓输入是指在执行算法时需要从外界取得必要的信息。所谓输入是指在执行算法时需要从外界取得必要的信息。一个算法也可以没有输入。一个算法也可以没有输入。4.有一个或多个输出有一个或多个输出 算法的目的是为了求解，算法的目的是为了求解，“解解”就是输出。没有输出的就是输出。没有输出的算法是没有意义的。算法是没有意义的。5.有效性有效性 算法中的每一个步骤都应当能有效地执行，并得到确定算法中的每一个步骤都应当能有效地执行，并得到确定的结果。的结果。对于不熟悉计算机程序设计的人来说，他们可以只需对于不熟悉计算机程序设计的
13、人来说，他们可以只需根据算法的要求给以必要的输入，就能得到输出的结果。根据算法的要求给以必要的输入，就能得到输出的结果。但对于程序设计人员来说，必须会设计算法，并且根据但对于程序设计人员来说，必须会设计算法，并且根据算法编写程序。算法编写程序。2.4 怎样表示一个算法怎样表示一个算法为了表示一个算法，可以用不同的方法。常用的有为了表示一个算法，可以用不同的方法。常用的有自然语言、传统流程图、结构化流程图、伪代码、自然语言、传统流程图、结构化流程图、伪代码、PAD图等。图等。2.4.1 用自然语言表示算法用自然语言表示算法 用自然语言表示通俗易懂，但文字冗长，用自然语言表示通俗易懂，但文字冗长，
14、容易出容易出现现“歧义性歧义性”。自然语言表示的含义往往不太严格，。自然语言表示的含义往往不太严格，要根据上下文才能判断其正确含义。此外，用自然要根据上下文才能判断其正确含义。此外，用自然语言描述包含分支和循环的算法，不很方便语言描述包含分支和循环的算法，不很方便(如例如例2.5的算法的算法)。因此，除了很简单的问题以外，一般。因此，除了很简单的问题以外，一般不用自然语言描述算法。不用自然语言描述算法。2.4.2 用流程图表示算法用流程图表示算法流程图是用一些图框表示流程图是用一些图框表示各种操作。用图形表示算各种操作。用图形表示算法，直观形象，易于理解。法，直观形象，易于理解。美国国家标准化
15、协会美国国家标准化协会ANSI(American National Standard Institute)规定了规定了一些常用的流程图符号一些常用的流程图符号(见见图图2.3)。图图2.3图图2.4中菱形框的作用是对一个给定的条件进行判中菱形框的作用是对一个给定的条件进行判断，根据给定的条件是否成立来决定如何执行其后断，根据给定的条件是否成立来决定如何执行其后的操作。它有一个入口，两个出口。的操作。它有一个入口，两个出口。图图 2.4图图 2.52.4.3 三种基本结构和改进的流程图三种基本结构和改进的流程图1.传统流程图的弊端传统流程图的弊端传统的流程图用流程线指出各框的执行顺序，传统的流程
16、图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用对流程线的使用没有严格限制。因此，使用者可以不受限制地使流程随意地转来转去，者可以不受限制地使流程随意地转来转去，使流程图变得毫无规律。这种情况如图使流程图变得毫无规律。这种情况如图2.13所示。所示。这种算法难以阅读，也难以修改，从而使算这种算法难以阅读，也难以修改，从而使算法的可靠性和可维护性难以保证。如果我们法的可靠性和可维护性难以保证。如果我们写出的算法能限制流程的无规律任意转向，写出的算法能限制流程的无规律任意转向，阅读起来就很方便。阅读起来就很方便。但是，算法上难免会包含一些分支和循环，而但是，算法上难免会包含一些
17、分支和循环，而不可能全部由一个一个框顺序组成。为了解决不可能全部由一个一个框顺序组成。为了解决这个问题，人们规定出几种基本结构，然后由这个问题，人们规定出几种基本结构，然后由这些基本结构按一定规律组成一个算法结构，这些基本结构按一定规律组成一个算法结构，整个算法的结构是由上而下地将各个基本结构整个算法的结构是由上而下地将各个基本结构顺序排列起来的。这样算法的质量就能得到保顺序排列起来的。这样算法的质量就能得到保证和提高。证和提高。2.三种基本结构三种基本结构1966年，年，Bohra和和Jacopini提出了以下三种基本结构，提出了以下三种基本结构，作为表示一个良好算法的基本单元。作为表示一个
18、良好算法的基本单元。(1)顺序结构，最简单的一种基本结构。顺序结构，最简单的一种基本结构。(2)选择结构，或称选取结构，或称分支结构，此选择结构，或称选取结构，或称分支结构，此结构包含判断框，根据判断结果选择执行的内容。结构包含判断框，根据判断结果选择执行的内容。有两种分支结构：有两种分支结构：双分支结构双分支结构多分支结构多分支结构(3)循环结构，它又称重复结构。有两类循环结构：循环结构，它又称重复结构。有两类循环结构：当型循环当型循环直到型循环直到型循环AB判断判断循环体循环体判断判断处理处理1处理处理2BA)顺序结构顺序结构B)分支结构分支结构C)循环结构循环结构循环体循环体判断判断判断
19、判断分支分支1分支分支2分支分支n(A)DO-UNTIL循环结构循环结构(B)多分支结构多分支结构As=0i=1i=100s=s+i开始开始Yi=i+1N输出输出S结束结束例：求从例：求从1到到100的和的和2.4.4 用用N-S流程图表示算法流程图表示算法既然用基本结构的顺序组合可以表示任何复既然用基本结构的顺序组合可以表示任何复杂的算法结构，那么基本结构之间的流程线杂的算法结构，那么基本结构之间的流程线就属多余的了。就属多余的了。1973年美国学者年美国学者I.Nassi和和B.Shneiderman提出提出了一种新的流程图形式。在这种流程图中，了一种新的流程图形式。在这种流程图中，完全去
20、掉了带箭头的流程线。全部算法写在完全去掉了带箭头的流程线。全部算法写在一个矩形框内，在该框内还可以包含其他的一个矩形框内，在该框内还可以包含其他的从属于它的框，或者说，由一些基本的框组从属于它的框，或者说，由一些基本的框组成一个大的框。这种流程图又称成一个大的框。这种流程图又称N-S结构化流结构化流程图。程图。N-S流程图用以下的流程图符号：流程图用以下的流程图符号：顺序结构顺序结构 选择结构选择结构1.循环结构循环结构DO-WHILE部分部分循环条件循环条件DO-UNTIL部分部分循环条件循环条件A（D)DO-WHILE循环循环(E)DO-UNTIL循环循环(F)调用子程序调用子程序第一个任
21、务第一个任务第二个任务第二个任务第三个任务第三个任务(A)顺序顺序True条件条件（B）IF-THEN-ELSECASE 条件条件值值1值值2值值3(C)CASE多分支多分支Falses=0,i=1ix2 then max=x1Else max=x2将将X3与与MAX的大数存于的大数存于MAX中中If x3max then max=x3程序（程序（C语言）语言）main()float x1,x2,x3,max;scanf (“%f,%f,%f”,&x1,&x2,&x3);If (x1x2)max=x1;else max=x2;If(x3max)max=x3;Printf(“the max nu
22、mber is:%f”,max);可见，模块化设计的思想实际上是一种可见，模块化设计的思想实际上是一种“分而治分而治之之”的思想，把一个大任务分为若干个子任务，的思想，把一个大任务分为若干个子任务，每一个子任务就相对简单了。每一个子任务就相对简单了。本章内容十分重要本章内容十分重要，是学习后面各章的基础。学，是学习后面各章的基础。学习程序设计的目的不只是学习一种特定的语言，习程序设计的目的不只是学习一种特定的语言，而是学习进行程序设计的一般方法。掌握了算法而是学习进行程序设计的一般方法。掌握了算法就是掌握了程序设计的灵魂，再学习有关的计算就是掌握了程序设计的灵魂，再学习有关的计算机语言知识，就能够顺利地编写出任何一种语言机语言知识，就能够顺利地编写出任何一种语言的程序。的程序。
