(
课件网) 3.3.2 编程解决问题 第三章 信息的加工与表达 一个游戏 在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上穿好了由大到小的６４片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片。一次只移动一片，不管在哪根针上，小片必在大片上面。当所有的金片都从梵天穿好的那根针上移到另外一概针上时，世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。 不管这个传说的可信度有多大，如果考虑一下把６４片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?运用数学中的递归的方法。不难证明f(n)=2^n-1。 n=64时， f(64)= 2^64-1=18446744073709551615 假如每秒钟一次，共需多长时间呢？一年大约有 31536926 秒，计算表明移完这些金片需要５８００多亿年，比地球寿命还要长，事实上，世界、梵塔、庙宇和众生都已经灰飞烟灭。 福州三中 编程解决问题的一般过程 两个概念 寻求问题求解的方法和确定具体的求解步骤 程序 指令序列和数据的集合 算法 狼菜羊过河 有一个牧羊人带着一头羊,一只狼和一颗大白菜准备过河,他找到一只很小的船,每次只能带一样东西过去,可是如果让狼与羊单独在一起,狼会吃羊,让羊与白菜单独在一起,羊会吃白菜，牧羊人应如何过河？ 过河的方案: 第一步：人和羊过河，人返回，留下羊； 第二步：人和狼过河，人和羊返回，留下狼； 第三步：人和菜过河，人返回，留下菜； 第四步：人和羊过河 三种算法的描述方式 算法的描述———用自然语言表达 用自然语言表达算法，就是把算法的各个步骤，依次用人们熟悉的自然语言表示出来。 优点：容易理解 缺点：书写较烦、不确定性、对复杂的问题难以表达准确、不能被计算机识别和执行 常用的“流程图”所用的基本符号 程序框 名称 功能 开始/结束 算法的开始和结束 输入/输出 输入和输出信息 处理 计算与赋值 判断 条件判断 流程线 算法中的流向 连接圈 表示算法流向出口或入口连接点 特征：有输入 确定性 有穷性 有输出 可行性 算法的描述 用自然语言描述算法 用流程图描述算法 用伪代码 二、程序设计语言分类 机器语言 汇编语言 高级程序设计语言 补充内容：参考P135 机器语言 机器语言就是计算机的指令系统 指令是使用二进制编码表示的 用机器语言编程序, 也就是直接使用二进制代码编写程序 优点： 可以直接被计算机执行 缺点： 记不住、难理解、效率低、不易维护 不同的机器语言程序，相互不兼容 现在已不直接用机器语言编制程序！ 例：机器语言程序 在MIPS计算机上求最大共约数（GCD）的机器程序（16进制表示） MISP计算机的每条机器指令均为32个二进位，用8个16进制数表示 汇编语言 用助记符号来表示机器指令中的操作符与操作数 优点： 操作数直接使用十进制 程序相对容易理解 缺点： 大型程序难以开发 依赖于具体计算机 将383传送到AX寄存器 将545传送到BX寄存器 将BX内容加AX内容，结果在BX中 将1055传送到AX寄存器 将AX内容减BX内容，结果在AX寄存器中 高级程序设计语言 目的：克服汇编语言的缺陷，提高编程和维护的效率 特点： 接近人们日常使用的自然语言（主要是英语）容易理解、记忆和使用 可在不同计算机上通用 对使用的符号、词汇、语法和语义等各种语言成分都有严格的规定 意义：使程序设计的难度降低，导致了计算机的发展进入新的阶段 高级程序设计语言的发展 50年代：Fortran，ALGOL 60年代：COBOL语言 70年代：Pascal 语言，C语言，BASIC语言 80年代： Ada语言，PROLOG语言，LISP语 ... ...
