00342高级语言程序设计(一)自考复习资料：算法

自考生网为考生收集整理了“00342高级语言程序设计(一)自考复习资料：算法“以供考生们复习使用。自考教材每隔几年都会更新、变动，但相关知识大体不变，考生们抓住考点进行复习即可。

更多资料点此查看：高级语言程序设计(一)自考教材、高级语言程序设计(一)题库、高级语言程序设计(一)网课（精讲）、高级语言程序设计(一)视频课程（串讲）

算法

计算机程序的目的是让计算机帮助人们完成一项工作，为此作为人指挥计算机的语言序列——程序，必须解决两个核心问题，即“做什么”和“怎么做”。

对于“做什么”的问题，需要在计算机程序设计的前半阶段完成，即确定计算机程序的功能，这对于大型程序设计是至关重要的；而对于“怎么做”的问题，则需要针对具体问题设计算法。

计算机可以解决多种信息处理的问题，但人们必须事先用计算机能够理解的语言（即程序设计语言）详细描述解决问题的步骤，即首先进行程序设计。对稍复杂一些的问题，要直接写出解决该问题的计算机程序是比较困难的。因此，人们把程序设计的任务分成两个步骤：第一步，不使用程序设计语言而使用一种较简单明了的表达方式设计出解决给定问题的算法；第二步，根据设计好的算法使用某种程序设计语言编写对应于该算法的程序。第二步工作要比第一步容易得多。因此，算法设计是使用计算机解决问题的过程中_个极为重要的环节。

简言之，解决问题的步骤序列就是算法。利用计算机解决问题需要有算法，在日常生活中做任何事情也都有它的算法。例如，烹调书中告诉人们烘烤面包的原料与操作步骤，这就是烤面包的算法；从北京开车去天津的路线就是从北京开车去天津的算法。例如编写“从宿舍起床赶到教室上课”的“程序”，则程序功能是“上午八点前进入教室坐好”。为了做到这一点，就要对上午八点之前的“活动”（算法）进行设计了。例如必须做到：

1）7：20前离开宿舍。

2）7：50前离开食堂。

3）8：00前进入教室。

这就是一个简单的算法，当然用于计算机的算法一般要复杂得多。

任何一个能够解决问题的算法都必须具备以下五个特性，即可执行性、确定性、有穷性、有输入信息的说明和有输出信息的步骤。

1）可执行性。算法中的每一步骤都是可执行的。显然，这是一个正确算法必须具备的性质。例如，若在解决某问题的步骤序列中有一步“到商店去替我买支圆珠笔”，这个步骤是计算机无法执行的，这一解决问题的步骤序列就不是算法。

2）确定性。算法中的每一步骤必须是明确定义的，不得有任何歧义性（非确定性）。例如，“用10和2进行算术运算”是一个有歧义的步骤，而“计算10加2的和”则具有确定性的步骤。如果一个解题的步骤序列中有的步骤是不明确的，则使用这样的解题步骤序列就不能保证获得问题的准确答案。自然，这样的解题步骤序列也不能称之为算法。

3）有穷性。一个算法必须在执行有穷步骤之后结束。如果一个解题步骤序列永远不能结束，则永远得不到问题的解答。因此，有始无终的解题步骤序列不是算法。

4）有输入信息的说明。有的算法可以没有输入信息，然而绝大多数算法都具有输入信息。

5）有输出信息的步骤。既然算法是用来解决给定问题的，则一个正确的算法必须将人们所关心的问题答案输岀。因此，一个算法应当至少有一个输出问题答案的步骤。

为了获得易读、易懂、易修改和扩充的算法，人们经过长期的实践认为必须采取以下三种措施：

1）利用自顶向下的方法设计算法。

2）只利用顺序、选择和循环三种基本结构构造算法。

3）具有优美的算法表达风格。

下面举例说明在计算机程序设计中如何设计具体算法，希望读者能够举一反三，灵活地对要解决的问题设计出最佳算法。

［例1-1］计算1×2×......×9×10

算法一:

分析：可以采用最原始的方法计算，即：

步骤1 先计算1×2,得到结果2；

步骤2 将步骤］得到的乘积2再乘以3,得6；

步骤3 将6再乘以4,得24；

步骤4 将24再乘以5,得120；

步骤9 将362 880乘以10,得3 628 800,即是最后结果。

虽然这样的算法是正确的，但过于烦琐。若要计算1×2×......× 10000,则要写9999个步骤，显然这是不可取的，而且每次都直接使用上一个步骤的计算结果（如2、6、24、120等）也不方便。应当找到一种通用的表示方法，通过分析可发现规律：乘数是前一个数加1=利用这一规律，得到第二种算法。

算法二：

分析：设两个变量，一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积存放在被乘数的变量中。例如，设t为被乘数，i为乘数，利用循环算法进行计算，则算法可改写如下：

其中，S1、S2…代表步骤1、步骤2…。S是Step（步骤）的缩写，这是书写算法的习惯用法。

请读者仔细分析这一算法，能否得到预期的结果。显然这个算法比前面列出的算法简洁。

如果将题目改为“计算1X3X5X7X9X11”，算法只需进行很少的改动即可：

可以看出，用这种方法描述的算法具有通用性、灵活性。S3-S5组成一个循环，在实现算法时，要反复多次执行S3、S4、S5步骤，直到某一时刻，执行S5时经过判断，乘数i已经超过所规定的数值而不再返回执行S3为止。此时算法结束，变量t的值即所求。

所有计算机高级语言中都有实现循环的语句。因此，上述算法不仅正确，而且是计算机能够实现的较好算法。"

【例1-2】要求将120个学生中成绩在60分以上者打印岀来。

分析：用n表示学生的学号，nl代表第一个学生的学号，ni代表第i个学生的学号；用g代表学生的成绩，gi代表第i个学生的成绩。

算法如下：

本例中，变量i作为下标，用于控制序号(第几个学生，第几个成绩)。当i>120时，表示已对120个学生的成绩处理完毕，算法结束。

【例1-3】输入一个大于或等于3的正整数,判断它是否为质数。

分析：质数是指除了1和该数本身外，不能被其他任何整数整除的数。例如，13是质数，因为它不能被2,3,4,12整除。

判断一个正整数n(nN3)是否为质数的方法很简单，即将n作为被除数，将2-(n-1)的各个整数依次作为除数，如果都不能被整除，则n为质数。

算法如下：

实际上，n不必被2〜(n-1)的所有整数整除，只需被2〜n/2的整数整除即可，甚至只需被之间的整数整除即可。例如，判断13是否为质数，只需将13被2、3整除即可，如果都不能整除，则n必为质数。S6步骤可改为：

在设计算法时，应当仔细分析所需判断的条件，如何一步一步缩小判断范围。对于有些问题，判断的先后次序是无所谓的，而有些问题，判断条件的先后次序是不能任意颠倒的，读者可根据具体问题具体分析。

通过以上几个例子，可以初步了解怎样设计一个算法。

更多相关内容可查看“自考复习资料”栏目。