计算机程序设计基础学习

《计算机程序设计基础学习》由会员分享，可在线阅读，更多相关《计算机程序设计基础学习（8页珍藏版）》请在金锄头文库上搜索。

1、13.1 计算机程序的概念所谓计算机程序，就是一些编写的代码或指令，这些代码或指令可以驱动计算机，完成某些 特定的工作。编写计算机程序的人员称为程序员。我们熟悉的一些软件系统，例如Windows, MS Office等等，其中最重要的组成部分就是计算机程序，大家用到的纷繁复杂的各种功能, 都是由若干程序的片断组成，这些计算机程序是许多优秀程序员的智慧结晶。有些读者或许会想，我并不打算成为一个专业的程序员，也不会去编写大型的软件，计算机 程序对我有什么用呢？实际上，计算机技术已经渗透到各种领域，我们在日常生活和工作中 总会遇到一些计算机程序可以解决的问题。掌握一些计算机程序的基础知识，便于在实际

2、工 作中解决一些问题，提高工作效率。图13.1就是一段用Visual C+编写的程序代码。/ Hello.cpp : Defines the entry point for the console application.ttinclude MstdaFx.hMint nain(int argc, char* argu) printf(Hello World*nM);return 霑；图13.1 Visual C+程序代码13.2 设计程序的过程我们用实际的例子来说明设计一个程序的过程。中国古代的算经中有个著名的“百钱百 鸡”问题：公鸡5文钱一只，母鸡3文钱一只，小鸡一文钱三只；现在要用100

3、文钱正好买 100 只鸡，问公鸡、母鸡和小鸡应该各买多少只？这个问题用代数的方法很难求解，逐个数 去试又很费时间。但是，如果我们利用计算机程序去分析这个问题，很快就可以得到结果 怎样用计算机程序解决这个问题呢？13.2.1 描述问题我们已经知道了“百钱百鸡”问题，但对于计算机来说，问题本身并不清晰。哪些是输入的参 数，输入参数的约束和条件是什么？输出什么？需要对这个问题做一些整理和抽象，将问题 描述为一些可以用来解决问题的要素(专业的术语叫做建立数学模型)。一般来说，表达清 晰的问题描述应该具备以下三个特征：1. 能说明问题域的相关假设2. 列出已知条件和约束3. 具体说明解决什么问题例如，对

4、于“百钱百鸡”问题，我们可以做下面的问题描述：1. 假设：用未知数x代表公鸡的个数，y代表母鸡的个数，z代表小鸡的个数。2. 已知条件：x、y和z都只能是正整数；买每只公鸡需5文钱，x只公鸡共需 要5x文钱；买每只母鸡需3文钱，y只公鸡共需要3x文钱；三只小鸡一文钱，小 鸡个数为3的倍数，且大于等于3, z只小鸡共需要z/3文钱；3. 解决问题：x+y+z=100且5x+3y+z/3=100时，x、y和z所有可能的值。4. 输出：所有可以解决问题的 x、 y、 z 值。“百钱百鸡”这个问题的描述相对要容易一些。在某些实际应用中，例如某些企业业务流程， 问题描述要复杂的多，需要一定的经验、技巧和

5、抽象能力。13.2.2 设计算法问题描述清楚后，就可以设计适当的计算机算法去解决问题。1计算机算法的概念所谓计算机算法，就是计算机能执行的、为解决某个问题所采取的方法和步骤。计算机是一 种由指令驱动的机器，只能机械地执行指令。它本身不会思考，也不会理解任何问题。要使 计算机能解决问题，必须首先为如何解决问题设计一个算法，然后再根据算法编写程序。 算法是抽象的解题方法，是问题求解过程的精确描述。算法有以下五个主要特征：有效性：算法的每一个步骤都必须可行并能达到预期目的。确定性：算法的每一个步骤都是明确定义的，不允许有多义性。 有穷性：算法必须在有限的时间内执行完，即必须在有限个步骤后中止。足够的

6、信息：算法有足够的输入信息（条件）。必定的输出：必须给用户提供解决问题的答案。另外，一个问题可以有多种算法来解决，不同的算法可能导致程序效率的优劣。例如，如果 要计算1+2+3+.+100，可以将1 和2相加，然后将它们的和与3相加，依次类推。但也可 以采用算法：1+2+3+.+100=（1+100）+ （2+99） +.+（50+51）=101x50=5050，显而 易见后者比前者的计算速度要快得多。在设计算法时，还要注意充分利用计算机的特点，使算法尽量简练并具有较好的通用性。例如，要计算1x2x3x.x100的值，可以使用算法：步骤1：计算1x2，得结果1x2=2；步骤2： 上个步骤的结果

7、乘以3,得结果2x3 = 6；步骤3： 上个步骤的结果乘以4,得结果6x4=24；步骤99：第98个步骤的结果乘以100，得到最终结果。这个算法可以得到正确结果，计算机运算速度极快，可以在极短时间内完成计算。但是，该 算法过于繁琐，如果上述算法写出计算机程序，至少需要 99 行代码。而且，如果要改算 1x2x3x.x50或1x2x3x.x300时，算法和程序还需要大规模的改动。可以用另一种算法完成上述运算。设定两个变量x和i，x表示被乘数，i表示乘数。开始将 1放在x中，2放在i中，计算i和x的积后，将结果再放入x，x现在等于1x2； i自加1 后变为3,再和x相乘，结果仍放入x, x现在等于

8、1x2x3；继续上述过程，直到最 终x等于1x2x3x.x100，算法可以描述为：步骤 1 ：将 1 放入 x； 步骤2：将2 放入 i； 步骤3：计算i乘以x,结果放入x； 步骤4： i自己的值加1,结果放回i； 步骤5：如果i小于等于100，转入步骤3继续计算;否则，算法结束,x的值就是1x2x3x.x100 的值。可以看出，虽然这种算法的速度和前面的算法不相上下，但描述非常简捷，如果写成计算机 代码，10行就足够了。另外，这种算法的灵活性很好。比如现在要改算1x2x3x.x50,只 需要将步骤 5 的“如果 i 小于等于 100”改为“如果 i 小于等于 50”即可；如果要改算 1x3x

9、5x7x.x99,只需要将步骤4的“i自己的值加T改为“i自己的值加2”即可。“百钱百鸡”这个问题可以用穷举算法来解决。根据问题描述，公鸡和母鸡的可能个数都在1 至 100 之间（实际上范围可以更小，这里为简单起见按照1 00 讲述），小鸡的可能个数都 在 3 至 100 之间。如果我们把公鸡、母鸡和小鸡个数的每种可能都试一下，看看哪种个数 搭配正好花完 100 文钱，那么一定可以找到所有可能的答案。这就好比你忘记了密码箱的 密码，无奈只好逐个去试。如果密码是三位的，每位可能是09，那么你需要试最多10x10x10 = 1000次。同样，如果去试公鸡、母鸡和小鸡的个数，需要100x100x33

10、=330000 次，显然这个次数对于人工尝试是痛苦的。但是，计算机如果做这个工作就太简单了，计算 机的速度快，且不知疲倦，百万次的计算不到1 秒即可以完成。这样， “百钱百鸡”的算法可 以描述为：步骤 1 ：将 1 放入 x；步骤 2：将 1 放入 y；步骤 3：将 3 放入 z；步骤4：检查5x+3y+z/3和x+y+z,如果二者均等于100,则打印输出x、y和z；步骤5： z的值加3,结果放回z （因为z只可能是3的倍数）；步骤 6：如果 z 小于等于 100，转入步骤 4 继续检查；否则继续下面的步骤；步骤7： y的值加1,结果放回y；步骤8：如果y小于等于100,则转入步骤3继续；否则

11、继续下面的步骤；步骤 9： x 的值加 1，结果放回 x；步骤 10：如果 x 小于等于 100，则转入步骤 2 继续；否则算法结束。注意在上述步骤中， x 和 y 等于 1， z 变化时，步骤 4 被执行了 33 次； x 等于 1， y 和 z 变 化时，步骤 4 被执行了 100x33 次。整个算法中步骤 4 执行了 100x100x33=330000 次。2算法的表示为了表示一个算法，可以用不同的方法，常用的算法表示方法有传统流程图、N-S流程图和 伪代码。（ 1 ）传统流程图传统流程图使用一些符号和图框表示计算机算法。如表13.1 所示，这些常用的流程图符号 是 ANSI 规定的，已

12、经被世界各国的软件提供商普遍采用。表 13.1 常用流程图符号流程图符号含义CD开始或结束/ /输入或输出O判断处理和计算连接点T T.流程线表 13.1 中菱形框的作用是对框内的条件进行判断，根据判断的结果决定走哪个分支。菱形 框有一个入口，两个出口。两个出口旁边一个写Y （或T）,代表逻辑真；另一个写N （或 F）,代表逻辑假，如图13.2所示。矩形框代表要进行的赋值、处理和计算等。流程线代 表算法步骤的走向，注意不要忘记箭头。流程图较大时，可以拆分为多个子流程图，用连接 点（中间加标号）连接。“百钱百鸡”问题用传统流程图表示如图13.3所示。传统流程图的特点是直观形象，易于理解，可以很清

13、楚的反映出算法各框之间的逻辑关系。 但当算法比较复杂时，传统流程图的表达并不理想，目前正逐步被其他表示方法代替。但传 统流程图作为一种形象的方法在许多场合还被使用，读者应该熟练掌握。(2)流程图 用传统流程图表示的算法最大的缺点是使用步骤跳转。当算法简单时尚好理解；当算法复杂 时，流程跳来跳去，使人难以理解，也难于发现算法中的问题。60 年代末期，出现了“结构 化程序设计”理论，解决了这个问题。“结构化程序设计”的基本思路是：强调算法的清晰和可读性。算法由一些基本结构组成。 基本结构具有一个入口，一个出口。 基本结构之间不允许跳转，步骤移动限制在一个基本结构内。N-S 流程图也称盒图，形状象一

14、个多层的盒子，非常适合表达结构化算法。它抛弃了传统流 程图的流程线，结构紧凑。整个算法是一个大的矩形框，框中包括若干个代表基本结构(顺 序、分支和循环)的小矩形框，矩形框之间不存在跳转。N-S 流程图用矩形表示顺序、分支和循环，如图13.4所示：图 13.4 ?N-S 流程图的矩形图13.4 (a)表示算法执行完A后，顺序执行B；图13.4 (b)表示检查某个条件，条件成 立则执行A,否则执行B；图13.4 (c)和图13.4 (d)表示只要条件成立，A就重复执行, 直到条件不成立才结束循环。A或B可以是一个算法步骤，也可以是一组步骤，或者是另外一种结构。这些基本结构互 相嵌套，相互堆积，形成

15、复杂的算法结构。理论上可以表示任何算法结构。例如，“百钱百鸡”问题用N-S流程图表示图13.5所示。N-S 流程图最大的优点是实现了程序的结构化，便于人们通过流程图理解算法，即使算法比 较复杂和庞大，通过N-S流程图建立、修改和维护算法也比传统流程图方便。(3)伪代码 伪代码是一种介于自然语言和计算机程序之间的描述算法。它和实际的程序结构非常类似 但不使用特定的程序语言的语法，而是使用人们比较容易理解的自然语言。伪代码没有固定的语法规则，形式比较自由，只要便于理解，清晰易懂就可以了。伪代码可 以使用英文或中文，也可以混合使用，一般是英文的关键字加中文的说明。“百钱百鸡”问题用伪代码表示如下：BEGIN (算法开始)1 - xdo1 - ydo3 - zdoif (5x+3y+z/3=100 且 x+y+z= 100)打印输出 x, y, zendifz+3 - zwhile(z ywhile(y xwhile(x=100)END (算法结束)伪代码的书写格式比较自由，可以很容易的表达出程序员的设计思路。另外，伪代码没有图 形，