程序设计与问题求解.ppt

程序设计与问题求解 第1章 程序设计概述 缪裕青 2011.9.20 1 程序设计与问题求解I 本章主要内容 问题求解与程序设计 算法及其描述方法 程序设计语言的故事 C/C+语言程序组成 程序设计方法 程序风格 Visual C+开发环境与上机指导 2 程序设计与问题求解I 问题求解与程序设计 问题求解 w例：求1+2+100的和。 解:(1)分析问题特征。连续的100个整数求和。 (2)设计解决方案。 100个数连加：1+2+100 采用等差数列求和公式计算： (1+100)*100/2 拥有高斯的创造力,直接使用50*101 (3)优化解决方案。三种方案比较选择最好( 优)的，计算量最小、计算速度最快。 (4)描述解决方案。可用数学算式50*101来描 述。 (5)执行解决方案。计算50*101结果。 分 析 设 计 优 化 描 述 执 行 3 程序设计与问题求解I 问题求解与程序设计 问题求解过程 分 析 设 计 优 化 描 述 执 行 计算机做？计算机做？ 4 程序设计与问题求解I 问题求解与程序设计 计算机有 智能吗？ 5 程序设计与问题求解I 问题求解与程序设计 计算机行业的梦想 w让计算机（Computer）能像人 一样地思考，与人自然交流， w人工智能AI （Artificial Intelligence） 图灵（1912-1954）电子计算 机理论和模型的奠基人 w1946年诞生世界上第一台电子计 算机ENIAC w1936年图灵发表论文“论可计算 数及其在判定问题中的应用” w1966年ACM设立“图灵奖” 6 程序设计与问题求解I 问题求解与程序设计 1997年，IBM公司研制的深蓝超级计算机在 一场“人机大战”中打败了国际象棋大师卡斯 帕罗夫 w被誉为“人工智能的一大胜利” 深蓝的主要研制者之一许峰雄博士： w胜利靠的只是不知疲倦地高速运算，并不是 什么智能 7 程序设计与问题求解I 问题求解与程序设计 计算机是用来延伸人能力的工具，具有高 速运算的能力。 我们的目标是控制计算机按照人的意愿去 工作，执行解决方案。 完成这一目标的手段就是“编程（ Programming）”。 8 程序设计与问题求解I 问题是丰富多彩 的 人具有思维 人 计算机只认识0和1 计算机没有思维 计算机 人和计算机通过程序进行沟通 程序 需要解决问题的人没有思维的计算机 问题求解与程序设计 9 程序设计与问题求解I 问题求解与程序设计 问题求解过程 分 析 设 计 优 化 描 述 执 行 计算机可以做只能人做 算法设计编写程序/算法实现 问题思路算法程序 程序设计 10 程序设计与问题求解I 问题求解与程序设计 计算机组成 w硬件：整个过程的执行者是硬件，但硬件 是受软件控制的 w软件：编程，就是编写软件，使硬件按照 人的意图工作 电脑的“脑”体现在软件 硬件受软件控制的执行者 程序和数据 执行结果 11 程序设计与问题求解I 问题求解与程序设计 输入/输出 设备 存储器运算器 控制器 源程序 和输入数据 输出结果 取出数据 存入数据 操作命令存取命令 取出 程序指令 输入输出 命令 计算结果 CPU 计算机基本工作过程 “冯诺依曼机”结构 大脑 记忆 装置 眼睛、耳 朵、嘴、 手 12 程序设计与问题求解I 程序与编写程序 程序：能够实现特定功能的指令序列，这些指令指 示计算机完成特定的操作。 编写程序：编写指令序列的过程。指令往往以某种 程序设计语言的语句形式给出。 问题求解与程序设计 13 程序设计与问题求解I 例：哥尼斯堡七桥问题 【问题】17世纪的东普鲁士有一座哥尼斯堡城（现在叫加里 宁格勒，在波罗的海南岸），普雷格尔河流过城中，在河中 有两座小岛，全城共有七座桥将4个城区连接起来，于是，产 生了一个有趣的问题：一个人是否能在一次步行中穿越全部 的七座桥后回到起点，且每座桥只经过一次。 算法及其描述方法 14 程序设计与问题求解I 例：哥尼斯堡七桥问题 东区 北区 岛区 南区 C A D B 抽象 【想法抽象模型】可以用A、B、C、D表示4个城区，用 7 条线表示 7 座桥，将七桥问题抽象为一个图模型。 算法及其描述方法 15 程序设计与问题求解I 例：哥尼斯堡七桥问题 【想法基本思路】是否存在欧拉回路的判定规则是： （1）如果通奇数桥的地方多于两个，则不存在欧拉回路； （2）如果只有两个地方通奇数桥，可以从这两个地方之一出 发，找到欧拉回路； （3）如果没有一个地方通奇数桥，则无论从哪里出发，都能 找到欧拉回路。 由上述判定规则得到求解七桥问题的基本思路：依次计算 图中与每个节点相关联的边的个数（称为节点的度），根据度 为奇数的节点个数判定是否存在欧拉回路。 算法及其描述方法 16 程序设计与问题求解I 算法及其描述方法 例：哥尼斯堡七桥问题 【算法】设函数EulerCircuit求解七桥问题，算法描述如下： 输入：二维数组mat44 功能：计算七桥问题中奇数桥的结点个数 输出：通奇数桥的结点个数count step1:count 初始化为0; step2:下标i从0到n-1重复执行下列操作; step2.1:计算第i行元素之和degree; step2.2:如果degree为奇数，则;count step3:返回count 17 程序设计与问题求解I 算法：对特定问题求解步骤的一种描述。 算法必须满足下列五个重要特性： 1. 输入; 2. 输出; 3. 有穷性 ; 4. 确定性; 5. 可行性。 解决问题的方法 算 法（y = f (x)） 有穷性：在合理时间内结束； 确定性：不存在二义性； 可行性：机器可执行； 输入 输出 算法及其特性 算法及其描述方法 18 程序设计与问题求解I w描述算法：算法设计者在构思和设计 了一个算法之后，必须清楚准确地将所设 计的求解步骤记录下来。 w使用算法：算法使用者知道如何调用 算法。 算法描述 算法及其描述方法 nf=n! 求阶乘算法 19 程序设计与问题求解I w自然 语言 算法描述的方法 算法及其描述方法 步骤1：输入数据n; 步骤2：将1保存到f中； 步骤3：将1保存到i中； 步骤4：若i大于n，则f为最后结果，算法执行步骤7； 否则执行步骤5 步骤5：i加1，将i*f的值放在f中； 步骤6：重新执行步骤4； 步骤7：输出数据f. 不直观，书写繁琐 20 程序设计与问题求解I N 开始 输入n f=1;i=1 in i=i+1；f=i*f 输出f 结束 Y 图形 符号 名 称 含 义 起止框 表示算法的开始或结束 处理框 表示处理或运算等功能 输入/ 输出框 表示进行输入/输出操作 判断框 根据给定的条件是否满足决定 执行两条路径中的某一条路径 控制流 表示算法执行的路径，箭头代 表方向 算法及其描述方法 算法描述的方法 w程序流程图直观，流程线无约束 21 程序设计与问题求解I w程序流 程图 算法及其描述方法 规定只能使用三种基本结构 A B 条件表达式 AB FT 条件表达式 A B T F 顺序结构选择结构循环结构 算法描述的方法 22 程序设计与问题求解I wN-S 图 算法及其描述方法 只能使用一些基本结构，不允许 使用带箭头的流程线 A B 条件表达式 A 顺序结构选择结构循环结构 AB 条件表达式 TF 算法描述的方法 23 程序设计与问题求解I wPAD 图 算法及其描述方法 只能使用一些基本结构，不允许 使用带箭头的流程线 顺序结构选择结构循环结构 A B A B 条件表达式 whileA 算法描述的方法 24 程序设计与问题求解I w程序设计 语言 算法及其描述方法 int i,n; cinn; int f=1; for (i=1; in结束 4.1 f=i*f; 4.2 i=i+1; 5.输出f; 介于自然语言和程序设计语言之间 算法描述的方法 26 程序设计与问题求解I 程序设计语言（Programming Language） 是人与计算机进行交流的语言 计算机直接能读懂的语言 w机器语言（Machine Code），也叫机器 代码 w一种纯粹的二进制语言 程序设计语言的故事 27 程序设计与问题求解I 程序设计语言的故事 计算机为什么用二进制呢？ 为什么不用我们日常熟悉的十进制呢？ w二进制在电器元件中容易实现 w计算机进行二进制运算比进行十进制运算 要简单得多 45678 +56789 10101 +11011 28 程序设计与问题求解I 程序设计语言的故事 程序设计语言的发展 w机器语言(Machine Code) w汇编语言(Assemble Language) w面向过程的高级语言 w面向对象的高级语言 29 程序设计与问题求解I 程序设计语言的故事 机器语言编写的1+1程序 w执行效率高。 w不同计算机使用不同 的机器语言，程序不能通 用。 w在人类的自然语言和 计算机编程语言之间存在 着巨大的鸿沟。 汇编语言编写的1+1程序 w不能直接识别和执行 。 w仍然依赖于机器。 w编程语言与人类自然 语言间的鸿沟略有缩小， 但仍与人类的思维相差甚 远。 10111000 00000001 00000000 00000101 00000001 00000000 MOV AX, 1 ADD AX, 1 汇编语言程序机器代码 翻译程序 30 程序设计与问题求解I 程序设计语言的故事 高级语言（面向过程的） wBASIC语言编写的1+1程序 wC语言编写的1+1程序 PRINT 1+1 printf(“%dn“, 1+1); 高级语言源程序目标程序 翻译程序 高级语言源程序执行程序 解释程序 31 程序设计与问题求解I 程序设计语言的故事 高级语言（面向对象的） wC+语言编写的1+1程序 cout double a; void fun1() a=18; static int b=10; cout int a(int x, int y) if (x=y) return x; else return y; void main() int x,y; printf(“%dn“, a(5,8); scanf(“%d%d“, printf(“%dn“,a(x,y); 下面C程序完成什么功能？ 51 程序设计与问题求解I 程序风格 良好的程序风格 ： s命名规则 s注释 s缩进 s适当空行、空格 s适当打印提示 目的是增加程序的可读性 52 程序设计与问题求解I Visual C+开发环境与上机指导 程序实现过程： 编辑 w将源程序输入到计算机中，生成后缀为 .cpp的磁盘文件。 编译 w将程序的源代码转换为机器语言代码。 连接 w将多个源程序文件以及库中的某些文件连 在一起，生成一个后缀为exe的可执行文件。 运行调试 53 程序设计与问题求解I 编辑源程序 进入Visual C+6.0开发环境（1） 54 程序设计与问题求解I 编辑源程序 进入Visual C+6.0开发环境（2） 55 程序设计与问题求解I 编辑源程序 创建一个Visual C+项目（1） 56 程序设计与问题求解I 编辑源程序 创建一个Visual C+项目（2） 57 程序设计与问题求解I 编辑源程序 创建一个Visual C+项目（3） 58 程序设计与问题求解I 编辑源程序 创建一个Visual C+项目（4） 59 程序设计与问题求解I 编辑源程序 建立并编辑Visual C+源程序（1） 60 程序设计与问题求解I 编辑源程序 建立并编辑Visual C+源程序（2） 61 程序设计与问题求解I 编辑源程序 建立并编辑Visual C+源程序（3） 62 程序设计与问题求解I 编辑源程序 建立并编辑Visual C+源程序（4） 63 程序设计与问题求解I 编辑源程序 建立并编辑Visual C+源程序（5） 64 程序设计与问题求解I 编辑源程序 建立并编辑Visual C+源程序（6） 65 程序设计与问题求解I 编译源程序 66 程序设计与问题求解I 连接程序 67 程序设计与问题求解I 运行程序（1） 68 程序设计与问题