程序设计初步讲义

《程序设计初步讲义》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章程序设计初步第3章程序设计初步3.1算法初步及其描述方法3.1.1算法初步1.什么是算法算法是为解决一个特定问题而采取的特定的有限的步骤。广义地说，做任何事情都有算法，例如一张太极拳打法图解也可以看作是一个“太极拳算法”。因此，算法概念不限于算术问题，而是具有更广泛的含义。从计算机应用的角度来说，算法是指完成一个任务所需要的具体步骤和方法（解决问题的方案）。也就是说给定初始状态或输入数据，经过计算机程序的有限次运算，能够得出所要求或期望的终止状态或输出数据。【算法3.1】给定两个正整数p和q，求其最大公因数。古希腊数学

2、家欧几里德给出的算法：步骤1：如果p

3、果问题比较复杂，计算步骤很多，则应通过编写计算机程序，使用计算机解决。2.算法的特征算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。一个算法应该具有以下五个重要的特征：(1)有穷性：一个算法必须保证执行有限步之后结束。(2)确切性：算法的每一步骤必须有确切的定义。(3)输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定义了初始条件。(4)输出

4、：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。(5)可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。·67·第3章程序设计初步3.算法的类型和结构(1)算法的类型算法可分为两大类：数值算法和非数值算法。数值算法是为数学问题形成一个构造性解法的完备而确切的描述，并规定方法中仅允许使用加、减、乘、除等基本的算术运算。非数值算法广泛应用在“数据处理”的场合。需要对大量的信息（数据）进行加工处理，包括转换、分类、查找、排序和存储等。常用的算法有穷举、递推、顺序查找和冒

5、泡排序等。(2)算法的结构一个算法是由“结构”和“原操作”构成的。原操作包括：输入、输出、赋值和比较等。算法的三种基本结构是：顺序结构、分支结构和循环结构。用这三种基本结构可以表示任意一个复杂的算法。①顺序结构顺序结构是指通过安排操作的排列顺序来决定算法流程的结构。在这种结构中，各个操作是依次执行的。顺序结构是由若干个依次执行的处理块组成，这是任何一个算法都离不开的基本主体结构。②分支结构在绝大多数情况下，算法不会按部就班地从第一条操作执行到最后一条操作，往往由特定的条件决定执行哪个操作，这就是分支结构。分支结构是以条件或情

6、况的判断为起始点，它是人脑判断思维活动的抽象。最基本的分支结构是二分支结构，根据判断逻辑是否成立而决定选择哪一边的处理块去执行。③循环结构循环结构是指在算法设计中，从某处开始有规律地反复执行某一处理块，这个处理块称为循环体。循环体的执行次数由一个控制循环条件决定。满足条件反复做，不满足则停止。3.1.2算法的描述工具设计一个算法可以根据问题的不同需要用某种语言符号来描述。目前最常用的几种算法描述工具有：自然语言、流程图、N-S图、伪代码等。1.自然语言自然语言就是人们日常使用的语言，可以是中文、英文等。用自然语言表示的算法通

7、俗易懂，但一般篇幅较冗长，表达上不易准确，易引起理解上的“歧义性”（即对同一段文字，不同的人会有不同的理解）。【算法3.2】输入3个数，求其最大数。分析：该算法可以使用分支结构表示。设num1，num2，num3存放3个数，max存放其最大值。为求其最大数，只要对3个数进行比较，可按如下步骤去做：S1：输入3个数num1，num2，num3；S2：先把第1个数num1的值赋给max；S3：将num2与max比较，如果num2>max，则把num2的值赋给max，否则，不做任何事情。S4：将num3与max比较，如果num3>

8、max，则把num3的值赋给max，否则，不做任何事情。·67·第3章程序设计初步S5：输出max的值，即最大值。【算法3.3】求1+2+3+…+100。分析：该算法可以使用循环结构表示。设n存放1到100之间的整数，sum存放1到100的和，即sum=1+2+3+…+100，可按如下步骤