2022年2022年计算机程序设计基础学习 .pdf

《2022年2022年计算机程序设计基础学习 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年计算机程序设计基础学习 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、作中解决一些问题，提高工作效率。图 13.1 就是一段用Visual C+ 编写的程序代码。图 13.1 Visual C+程序代码13.2 设计程序的过程我们用实际的例子来说明设计一个程序的过程。中国古代的算经中有个著名的“ 百钱百鸡” 问题：公鸡5 文钱一只，母鸡3 文钱一只，小鸡一文钱三只；现在要用100 文钱正好买100 只鸡， 问公鸡、 母鸡和小鸡应该各买多少只？这个问题用代数的方法很难求解，逐个数去试又很费时间。但是，如果我们利用计算机程序去分析这个问题，很快就可以得到结果。怎样用计算机程序解决这个问题呢？13.2.1 描述问题我们已经知道了“ 百钱百鸡 ” 问题，但对于计算机来说

3、，问题本身并不清晰。哪些是输入的参数，输入参数的约束和条件是什么？输出什么？需要对这个问题做一些整理和抽象，将问题描述为一些可以用来解决问题的要素（专业的术语叫做建立数学模型）。一般来说，表达清晰的问题描述应该具备以下三个特征：1. 能说明问题域的相关假设2. 列出已知条件和约束3. 具体说明解决什么问题例如，对于 “ 百钱百鸡 ” 问题，我们可以做下面的问题描述：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 1. 假设：用未

4、知数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 值。“ 百钱百鸡 ” 这个问题的描述相对要容易一些。在某些实际应用中，例如某些企业业务流程，问题描述要复杂的多，需要一定的经验、技巧和抽象能力。13.2.

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

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

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

8、精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - 后变为 3，再和 x 相乘，结果仍放入x，x 现在等于1 2 3；.；继续上述过程，直到最终 x 等于 1 2 3 . 100，算法可以描述为：步骤 1：将 1 放入 x；步骤 2：将 2 放入 i；步骤 3：计算 i 乘以 x，结果放入x；步骤 4：i 自己的值加1，结果放回i；步骤 5： 如果 i 小于等于 100， 转入步骤 3 继续计算；否则，算法结束，x的值就是 1 2 3 . 100的值。可以

9、看出， 虽然这种算法的速度和前面的算法不相上下，但描述非常简捷，如果写成计算机代码， 10 行就足够了。另外，这种算法的灵活性很好。比如现在要改算1 2 3 . 50，只需要将步骤5 的 “ 如果i 小于等于100” 改为 “ 如果i 小于等于50” 即可；如果要改算1 3 5 7 .99，只需要将步骤4 的“i自己的值加1” 改为 “i自己的值加2” 即可。“ 百钱百鸡 ” 这个问题可以用穷举算法来解决。根据问题描述，公鸡和母鸡的可能个数都在1至 100 之间（实际上范围可以更小，这里为简单起见按照100 讲述），小鸡的可能个数都在 3 至 100 之间。如果我们把公鸡、母鸡和小鸡个数的每种

10、可能都试一下，看看哪种个数搭配正好花完100 文钱，那么一定可以找到所有可能的答案。这就好比你忘记了密码箱的密码，无奈只好逐个去试。如果密码是三位的，每位可能是0 9，那么你需要试最多10 10 101000 次。 同样，如果去试公鸡、 母鸡和小鸡的个数， 需要 100100 33 330000次，显然这个次数对于人工尝试是痛苦的。但是，计算机如果做这个工作就太简单了，计算机的速度快，且不知疲倦，百万次的计算不到1 秒即可以完成。这样，“ 百钱百鸡 ” 的算法可以描述为：步骤 1：将 1 放入 x；步骤 2：将 1 放入 y；步骤 3：将 3 放入 z；步骤 4：检查5x+3y+z/3 和 x

11、+y+z ，如果二者均等于100，则打印输出x、y 和 z；步骤 5：z 的值加 3，结果放回z（因为 z 只可能是3 的倍数）；步骤 6：如果 z 小于等于100，转入步骤4 继续检查；否则继续下面的步骤；步骤 7：y 的值加 1，结果放回y；步骤 8：如果 y 小于等于100，则转入步骤3 继续；否则继续下面的步骤；步骤 9：x 的值加 1，结果放回x；步骤 10：如果 x 小于等于 100 ，则转入步骤2 继续；否则算法结束。注意在上述步骤中，x 和 y 等于 1，z 变化时，步骤4 被执行了33 次； x 等于 1，y 和 z 变化时，步骤4 被执行了10033 次。整个算法中步骤4

12、执行了 10010033330000 次。2算法的表示为了表示一个算法，可以用不同的方法，常用的算法表示方法有传统流程图、N-S 流程图和伪代码。（1）传统流程图传统流程图使用一些符号和图框表示计算机算法。如表13.1 所示，这些常用的流程图符号是 ANSI 规定的，已经被世界各国的软件提供商普遍采用。表 13.1 常用流程图符号名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - 流程图符号含义开始或结束输入或输出判断处理和计算连接

13、点流程线表 13.1 中菱形框的作用是对框内的条件进行判断，根据判断的结果决定走哪个分支。菱形框有一个入口，两个出口。两个出口旁边一个写Y（或 T），代表逻辑真；另一个写N（或F），代表逻辑假，如图13.2 所示。矩形框代表要进行的赋值、处理和计算等。流程线代表算法步骤的走向，注意不要忘记箭头。流程图较大时， 可以拆分为多个子流程图，用连接点（中间加标号）连接。“ 百钱百鸡 ” 问题用传统流程图表示如图13.3 所示。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页

14、 - - - - - - - - - 传统流程图的特点是直观形象，易于理解，可以很清楚的反映出算法各框之间的逻辑关系。但当算法比较复杂时，传统流程图的表达并不理想，目前正逐步被其他表示方法代替。但传统流程图作为一种形象的方法在许多场合还被使用，读者应该熟练掌握。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - （2）流程图用传统流程图表示的算法最大的缺点是使用步骤跳转。当算法简单时尚好理解；当算法复杂时，流程跳来跳去，使人难以理解

15、，也难于发现算法中的问题。60 年代末期，出现了“ 结构化程序设计 ” 理论，解决了这个问题。“ 结构化程序设计” 的基本思路是：强调算法的清晰和可读性。算法由一些基本结构组成。基本结构具有一个入口，一个出口。基本结构之间不允许跳转，步骤移动限制在一个基本结构内。N-S 流程图也称盒图，形状象一个多层的盒子，非常适合表达结构化算法。它抛弃了传统流程图的流程线， 结构紧凑。整个算法是一个大的矩形框，框中包括若干个代表基本结构（顺序、分支和循环）的小矩形框，矩形框之间不存在跳转。N-S 流程图用矩形表示顺序、分支和循环，如图13.4 所示：图 13.4 ?N-S流程图的矩形图 13.4 （a）表示

16、算法执行完A 后，顺序执行B；图 13.4 （b）表示检查某个条件，条件成立则执行 A，否则执行B；图 13.4（ c）和图 13.4（d）表示只要条件成立，A 就重复执行，直到条件不成立才结束循环。A 或 B 可以是一个算法步骤，也可以是一组步骤，或者是另外一种结构。这些基本结构互相嵌套，相互堆积，形成复杂的算法结构。理论上可以表示任何算法结构。例如， “ 百钱百鸡 ” 问题用 N-S 流程图表示图13.5 所示。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页

17、- - - - - - - - - N-S 流程图最大的优点是实现了程序的结构化，便于人们通过流程图理解算法，即使算法比较复杂和庞大，通过N-S 流程图建立、修改和维护算法也比传统流程图方便。（3）伪代码伪代码是一种介于自然语言和计算机程序之间的描述算法。它和实际的程序结构非常类似，但不使用特定的程序语言的语法，而是使用人们比较容易理解的自然语言。伪代码没有固定的语法规则，形式比较自由，只要便于理解，清晰易懂就可以了。伪代码可以使用英文或中文，也可以混合使用，一般是英文的关键字加中文的说明。“ 百钱百鸡 ” 问题用伪代码表示如下：BEGIN （算法开始）1 - x do 1 - y do 3

18、- z do if (5x+3y+z/3=100 且 x+y+z100) 打印输出 x, y, z endif z+3 - z while(z y 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - while(y x while(x=100) END（算法结束）伪代码的书写格式比较自由，可以很容易的表达出程序员的设计思路。另外， 伪代码没有图形，比较容易编辑和修改，因此，实践中熟练的软件专业人员一般使用伪代码比较多。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -