程序设计与问题求解第1章 程序设计概述缪裕青 2011.9.201程序设计与问题求解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例：哥尼斯堡七桥问题 东区北区岛区南区CADB抽象【想法抽象模型】可以用A、B、C、D表示4个城区，用 7 条线表示 7 座桥，将七桥问题抽象为一个图模型。 算法及其描述方法15程序设计与问题求解I例：哥尼斯堡七桥问题 【想法基本思路】是否存在欧拉回路的判定规则是： （1）如果通奇数桥的地方多于两个，则不存在欧拉回路； （2）如果只有两个地方通奇数桥，可以从这两个地方之一出 发，找到欧拉回路； （3）如果没有一个地方通奇数桥，则无论从哪里出发，都能 找到欧拉回路。由上述判定规则得到求解七桥问题的基本思路：依次计算 图中与每个节点相关联的边的个数（称为节点的度），根据度 为奇数的节点个数判定是否存在欧拉回路。 算法及其描述方法16程序设计与问题求解I 算法及其描述方法例：哥尼斯堡七桥问题 【算法】设函数EulerCircuit求解七桥问题，算法描述如下： 输入：二维数组mat44 功能：计算七桥问题中奇数桥的结点个数 输出：通奇数桥的结点个数countstep1:count 初始化为0; step2:下标i从0到n-1重复执行下列操作;step2.1:计算第i行元素之和degree;step2.2:如果degree为奇数，则;count step3:返回count17程序设计与问题求解I算法：对特定问题求解步骤的一种描述。算法必须满足下列五个重要特性：1. 输入; 2. 输出; 3. 有穷性 ; 4. 确定性; 5. 可行性。 解决问题的方法算 法（y = f (x)）有穷性：在合理时间内结束；确定性：不存在二义性；可行性：机器可执行；输入输出 算法及其特性算法及其描述方法 18程序设计与问题求解Iw描述算法：算法设计者在构思和设计 了一个算法之后，必须清楚准确地将所设 计的求解步骤记录下来。 w使用算法：算法使用者知道如何调用 算法。 算法描述算法及其描述方法 nf=n!求阶乘算法19程序设计与问题求解Iw自然 语言 算法描述的方法算法及其描述方法 步骤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程序设计与问题求解IN开始输入nf=1;i=1ini=i+1；f=i*f输出f结束Y图形 符号名 称含 义起止框表示算法的开始或结束处理框表示处理或运算等功能输入/ 输出框表示进行输入/输出操作判断框根据给定的条件是否满足决定 执行两条路径中的某一条路径控制流表示算法执行的路径，箭头代 表方向算法及其描述方法 算法描述的方法w程序流程图直观，流程线无约束21程序设计与问题求解Iw程序流 程图算法及其描述方法 规定只能使用三种基本结构AB条件表达式ABFT条件表达式ABTF顺序结构选择结构循环结构 算法描述的方法22程序设计与问题求解IwN-S 图算法及其描述方法 只能使用一些基本结构，不允许 使用带箭头的流程线AB条件表达式A顺序结构选择结构循环结构AB条件表达式TF 算法描述的方法23程序设计与问题求解IwPAD 图算法及其描述方法 只能使用一些基本结构，不允许 使用带箭头的流程线顺序结构选择结构循环结构ABAB条件表达式whileA 算法描述的方法24程序设计与问题求解Iw程序设计 语言算法及其描述方法 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 +5678910101 +1101128程序设计与问题求解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 00000000MOV AX, 1 ADD AX, 1汇编语言程序机器代码翻译程序30程序设计与问题求解I 程序设计语言的故事高级语言（面向过程的） wBASIC语言编写的1+1程序wC语言编写的1+1程序PRINT 1+1printf(“%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程序设计与问题求解I 运行程序（2）69程序设计与问题求解I 运行程序（3）70程序设计与问题求解I 调试程序（1）按F9可设置、去除断点71程序设计与问题求解I 调试程序（2）F5进入开始调试72程序设计与问题求解I 调试程序（3）73程序设计与问题求解I 本章小结