程序设计与问题求解.ppt

《程序设计与问题求解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章程序设计概述缪裕青2011.9.20本章主要内容问题求解与程序设计算法及其描述方法程序设计语言的故事C/C++语言程序组成程序设计方法程序风格VisualC++开发环境与上机指导2问题求解与程序设计问题求解例：求1+2+…+100的和。解:(1)分析问题特征。连续的100个整数求和。(2)设计解决方案。100个数连加：1+2+…+100采用等差数列求和公式计算：(1+100)*100/2拥有高斯的创造力,直接使用50*101(3)优化解决方案。三种方案比较选择最好(优)的，计算量最小、计算速度最快。(4)描述解决方案。可用数学算式50*101来描

2、述。(5)执行解决方案。计算50*101结果。分析设计优化描述执行3问题求解与程序设计问题求解过程分析设计优化描述执行计算机做？计算机做？4问题求解与程序设计计算机有智能吗？5问题求解与程序设计计算机行业的梦想让计算机（Computer）能像人一样地思考，与人自然交流，人工智能AI（ArtificialIntelligence）图灵（1912-1954）——电子计算机理论和模型的奠基人1946年诞生世界上第一台电子计算机ENIAC1936年图灵发表论文“论可计算数及其在判定问题中的应用”1966年ACM设立“图灵奖”6问题求解与程序设计1997年，IB

3、M公司研制的深蓝超级计算机在一场“人机大战”中打败了国际象棋大师卡斯帕罗夫被誉为“人工智能的一大胜利”深蓝的主要研制者之一许峰雄博士：胜利靠的只是不知疲倦地高速运算，并不是什么智能7问题求解与程序设计计算机是用来延伸人能力的工具，具有高速运算的能力。我们的目标是控制计算机按照人的意愿去工作，执行解决方案。完成这一目标的手段就是“编程（Programming）”。8问题是丰富多彩的人具有思维人计算机只认识0和1计算机没有思维计算机人和计算机通过程序进行沟通程序需要解决问题的人没有思维的计算机问题求解与程序设计9问题求解与程序设计问题求解过程分析设计优

4、化描述执行计算机可以做只能人做算法设计编写程序/算法实现问题思路算法程序程序设计10问题求解与程序设计计算机组成硬件：整个过程的执行者是硬件，但硬件是受软件控制的软件：编程，就是编写软件，使硬件按照人的意图工作电脑的“脑”体现在——软件硬件——受软件控制的执行者程序和数据硬盘CPU内存执行结果11问题求解与程序设计输入/输出设备存储器运算器控制器源程序和输入数据输出结果取出数据存入数据操作命令存取命令取出程序指令输入输出命令计算结果CPU计算机基本工作过程“冯·诺依曼机”结构大脑记忆装置眼睛、耳朵、嘴、手12程序与编写程序程序：能够实现特定功能的指令序

5、列，这些指令指示计算机完成特定的操作。编写程序：编写指令序列的过程。指令往往以某种程序设计语言的语句形式给出。问题求解与程序设计13例：哥尼斯堡七桥问题【问题】17世纪的东普鲁士有一座哥尼斯堡城（现在叫加里宁格勒，在波罗的海南岸），普雷格尔河流过城中，在河中有两座小岛，全城共有七座桥将4个城区连接起来，于是，产生了一个有趣的问题：一个人是否能在一次步行中穿越全部的七座桥后回到起点，且每座桥只经过一次。算法及其描述方法14例：哥尼斯堡七桥问题东区北区岛区南区CADB抽象【想法——抽象模型】可以用A、B、C、D表示4个城区，用7条线表示7座桥，将七桥问题抽

6、象为一个图模型。算法及其描述方法15例：哥尼斯堡七桥问题【想法——基本思路】是否存在欧拉回路的判定规则是：（1）如果通奇数桥的地方多于两个，则不存在欧拉回路；（2）如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；（3）如果没有一个地方通奇数桥，则无论从哪里出发，都能找到欧拉回路。由上述判定规则得到求解七桥问题的基本思路：依次计算图中与每个节点相关联的边的个数（称为节点的度），根据度为奇数的节点个数判定是否存在欧拉回路。算法及其描述方法16算法及其描述方法例：哥尼斯堡七桥问题【算法】设函数EulerCircuit求解七桥问题，算法描述如

7、下：输入：二维数组mat[4][4]功能：计算七桥问题中奇数桥的结点个数输出：通奇数桥的结点个数countstep1:count初始化为0;step2:下标i从0到n-1重复执行下列操作;step2.1:计算第i行元素之和degree;step2.2:如果degree为奇数，则;countstep3:返回count17算法：对特定问题求解步骤的一种描述。算法必须满足下列五个重要特性：1.输入;2.输出;3.有穷性;4.确定性;5.可行性。解决问题的方法算法（y=f(x)）有穷性：在合理时间内结束；确定性：不存在二义性；可行性：机器可执行；…输入…输出算

8、法及其特性算法及其描述方法18描述算法：算法设计者在构思和设计了一个算法之后，必须清楚准确地将