《程学设计基础》由会员分享，可在线阅读，更多相关《程学设计基础（12页珍藏版）》请在金锄头文库上搜索。
1、算法的概念与伪代码的使用 算法 Algorithm 算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说， 就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序， 都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。一个算法应该具有以下五个重要的特征： 有穷性： 一个算法必须保证执行有限步之后结束； 确切性： 算法的每一步骤必须有确切的定义； 输入：一个算法有 0 个或多个输入，以刻画运算对象的初始情况，所谓 0 个输 入是指算法本身定除了初始条件； 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输 出的算法是毫无意义的； 可行性：
2、算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可 完成。 Did you know Algorithm 一词的由来 Algorithm(算法)一词本身就十分有趣。初看起来，这个词好像是某人打算要写 “Logarithm“(对数)一词但却把头四个字母写的前后颠倒了。这个词一直到 1957 年之前在 Websters New World Dictionary(韦氏新世界词典)中还未 出现，我们只能找到带有它的古代涵义的较老形式的“Algorism“(算术)，指的 是用阿拉伯数字进行算术运算的过程。在中世纪时，珠算家用算盘进行计算， 而算术家用算术进行计算。中世纪之后，对这个词的起源已经
3、拿不准了，早期 的语言学家试图推断它的来历，认为它是从把 algiros(费力的)+arithmos(数 字)组合起来派生而成的，但另一些人则不同意这种说法，认为这个词是从“喀 斯迪尔国王 Algor“派生而来的。最后，数学史学家发现了 algorism(算术)一词 的真实起源：它来源于著名的 Persian Textbook(波斯教科书)的作者的名 字 Abu Jafar Mohammed ibn M?sa al-Khowarizm （约公元前 825 年）-从字 面上看，这个名字的意思是“Jafar 的父亲，Mohammed 和 M?sa 的儿子， Khowarizm 的本地人“。Khow
4、arizm 是前苏联 XBA(基发) 的小城镇 。Al- Khowarizm 写了著名的书 Kitab al jabr wal-muqabala (复原和化简的规 则)；另一个词，“algebra“(代数)，是从他的书的标题引出来的，尽管这本 书实际上根本不是讲代数的。逐渐地，“algorism“的形式和意义就变得面目全非了。如牛津英语字典所说明 的，这个词是由于同 arithmetic(算术)相混淆而形成的错拼词。由 algorism 又变成 algorithm。一本早期的德文数学词典 Vollstandiges Mathematisches Lexicon (数学大全辞典) ，给出了 Al
5、gorithmus (算法)一词的如下定义： “在这个名称之下，组合了四种类型的算术计算的概念，即加法、乘法、减法、 除法“。拉顶短语 algorithmus infinitesimalis (无限小方法) ，在当时就用 来表示 Leibnitz(莱布尼兹)所发明的以无限小量进行计算的微积分方法。1950 年左右，algorithm 一词经常地同欧几里德算法(Euclids algorithm)联 系在一起。这个算法就是在欧几里德的几何原本(Euclids Elements ,第 VII 卷，命题 i 和 ii)中所阐述的求两个数的最大公约数的过程(即辗转相除法)。Abu Jafar Moha
6、mmed ibn M?sa al-KhowarizmBorn: about 780 in Baghdad (now in Iraq) Died: about 850伪代码的使用 Usage of Pseudocode 伪代码(Pseudocode)是一种算法描述语言。使用为代码的目的是为了使被描述 的算法可以容易地以任何一种编程语言(Pascal, C, Java, etc)实现。因此， 伪代码必须结构清晰，代码简单，可读性好，并且类似自然语言。下面介绍一种类 Pascal 语言的伪代码的语法规则。伪代码的语法规则 在伪代码中，每一条指令占一行(else if 例外，)，指令后不跟任何符号 （
7、Pascal 和 C 中语句要以分号结尾）； 书写上的“缩进“表示程序中的分支程序结构。这种缩进风格也适用于 if-then- else 语句。用缩进取代传统 Pascal 中的 begin 和 end 语句来表示程序的块结 构可以大大提高代码的清晰性；同一模块的语句有相同的缩进量，次一级模块 的语句相对与其父级模块的语句缩进； 例如：line 1 line 2 sub line 1 sub line 2 sub sub line 1 sub sub line 2 sub line 3 line 3而在 Pascal 中这种关系用 begin 和 end 的嵌套来表示，line 1 line
8、2 begin sub line 1 sub line 2 begin sub sub line 1 sub sub line 2 end; sub line 3 end; line 3 在 C 中这种关系用 和 的嵌套来表示，line 1 line 2 sub line 1 sub line 2 sub sub line 1 sub sub line 2 sub line 3 line 3在伪代码中，通常用连续的数字或字母来标示同一即模块中的连续语句，有时 也可省略标号。 例如：1. line 1 2. line 2 a. sub line 1 b. sub line 2 1. sub su
9、b line 1 2. sub sub line 2 c. sub line 3 3. line 3 符号后的内容表示注释； 在伪代码中，变量名和保留字不区分大小写，这一点和 Pascal 相同，与 C 或 C+不同； 在伪代码中，变量不需声明，但变量局部于特定过程，不能不加显示的说明就 使用全局变量； 赋值语句用符号表示，xexp 表示将 exp 的值赋给 x，其中 x 是一个变量， exp 是一个与 x 同类型的变量或表达式（该表达式的结果与 x 同类型）；多重 赋值 ije 是将表达式 e 的值赋给变量 i 和 j，这种表示与 je 和 ie 等 价。 例如：xy x20*(y+1) x
10、y30以上语句用 Pascal 分别表示为：x := y; x := 20*(y+1); x := 30; y := 30;以上语句用 C 分别表示为：x = y; x = 20*(y+1); x = y = 30;选择语句用 if-then-else 来表示，并且这种 if-then-else 可以嵌套，与 Pascal 中的 if-then-else 没有什么区别。 例如: if (Condition1) then Block 1 else if (Condition2) then Block 2 else Block 3 循环语句有三种：while 循环、repeat-until 循环和
11、 for 循环，其语法均与 Pascal 类似，只是用缩进代替 begin - end； 例如：1. x 0 2. y 0 3. z 0 4. while x = 0 ); z = x * y; y /= 2; 数组元素的存取有数组名后跟“下标“表示。例如 Aj指示数组 A 的第 j 个元 素。符号“ “用来指示数组中值的范围。 例如：A1j表示含元素 A1, A2, , Aj的子数组；复合数据用对象(Object)来表示，对象由属性(attribute)和域(field)构成。 域的存取是由域名后接由方括号括住的对象名表示。 例如：数组可被看作是一个对象，其属性有 length，表示其中元素
12、的个数，则 lengthA就表示数组 A 中的元素的个数。在表示数组元素和对象属性时都要用 方括号，一般来说从上下文可以看出其含义。用于表示一个数组或对象的变量被看作是指向表示数组或对象的数据的一个指 针。对于某个对象 x 的所有域 f，赋值 yx 就使 fy=fx，更进一步，若有 fx3，则不仅有 fx=3，同时有 fy=3，换言之，在赋值 yx 后，x 和 y 指向同一个对象。有时，一个指针不指向任何对象，这时我们赋给他 nil。函数和过程语法与 Pascal 类似。 函数值利用 “return (函数返回值)“ 语句来返回，调用方法与 Pascal 类似； 过程用 “call 过程名“语
13、句来调用；例如： 1. x t + 10 2. y sin(x) 3. call CalValue(x,y)参数用按值传递方式传给一个过程：被调用过程接受参数的一份副本，若他对 某个参数赋值，则这种变化对发出调用的过程是不可见的。当传递一个对象时， 只是拷贝指向该对象的指针，而不拷贝其各个域。在最初学习伪代码的过程中会遇到很多的困难，之所以在学习计 算机与语言前开程序设计基础也正是由于此。关键在学思想，如何设 计出一个好的算法，在开始学的时候要敢于写，不写是不行的。光看 别人写永远是别人的，要自己尝试，开始还是比较简单的，主要是思 想简单，主要克服从流程图到伪代码和从伪代码到流程图之间的转化，
14、 要熟记模型和基本语句，只要多加练习，是一定可以学好的，我简单 的把一些基本问题归纳如下，以下是配的一些练习题，难以搭配。 1 1 数字问题与几何图形问题：数字问题与几何图形问题：1.输入整数 n,输出由 2n+1 行 2n+1 列组成的以下(n=2)的图案。2.输入整数 n(=3)位数字的数，它等于每个数字的 n 次幂之和。例如， 153 是一个水仙花数，153=13+53+33。试编写一个程序求小于 999 的所有水仙花 数。6. 编写程序解百鸡问题：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。 百钱买百鸡。问鸡翁、鸡母和鸡雏各几何？7.编写一个程序，输入一个整数，逐位地输出整数的十进
15、制数，要求位与位之 间有一个空格符分隔。8.编写程序，列表输出整数 110 的平方和立方值。9.编写一个程序，输入 3 个实数，判断这些值能否作为一个三角形的三条边的 长，如果能构成三角形，要求输出三角形的面积。10.输入正整数 n，输出 n 行 n 列星号字符组成的三角形图案。以下是 n 等于 4 的图案。11.输入正整数 n，输出由 n 行 2n-1 列星号字符组成的三角形图案。以下是 n 等于 3 的图案。12.输入正整数你 n,输出 n 行 2n-1 列的空心三角形图案。以下是 n 等于 4 的图 案。13.输入正整数 n,输出 n 行 n 列的空心四边形图案。以下是 n 等于 5 的图案。14.编写程序，按下面的公式计算自然对数底 e 的值。e=1+1/1!+1/2!+1/3!+1/5!+15.编写程序，按如下公式计算圆周率 的近似值。=4-4/3+4/5-4/7+4/9-4/11+16.编写输入正实数 x，求平方不超过 x 的最大整数 n,并输出。17.回文整数是指正读和反读相同的整数，编写一个程序，输入一个整数，判断 它是否是回文整数。17.
