程序设计与问题求解.ppt

《程序设计与问题求解.ppt》由会员分享，可在线阅读，更多相关《程序设计与问题求解.ppt（75页珍藏版）》请在三一办公上搜索。

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

2、101结果。,分析,设计,优化,描述,执行,4,问题求解与程序设计,问题求解过程,计算机做？,计算机做？,5,问题求解与程序设计,计算机有智能吗？,6,问题求解与程序设计,计算机行业的梦想让计算机（Computer）能像人一样地思考，与人自然交流，人工智能AI（Artificial Intelligence）图灵（1912-1954）电子计算机理论和模型的奠基人1946年诞生世界上第一台电子计算机ENIAC1936年图灵发表论文“论可计算数及其在判定问题中的应用”1966年ACM设立“图灵奖”,7,问题求解与程序设计,1997年，IBM公司研制的深蓝超级计算机在一场“人机大战”中打败了国际象棋

3、大师卡斯帕罗夫被誉为“人工智能的一大胜利”深蓝的主要研制者之一许峰雄博士：胜利靠的只是不知疲倦地高速运算，并不是什么智能,8,问题求解与程序设计,计算机是用来延伸人能力的工具，具有高速运算的能力。我们的目标是控制计算机按照人的意愿去工作，执行解决方案。完成这一目标的手段就是“编程（Programming）”。,9,人和计算机通过程序进行沟通,需要解决问题的人没有思维的计算机,问题求解与程序设计,10,问题求解与程序设计,问题求解过程,计算机可以做,只能人做,算法设计,编写程序/算法实现,程序设计,11,问题求解与程序设计,计算机组成硬件：整个过程的执行者是硬件，但硬件是受软件控制的软件：编程，

4、就是编写软件，使硬件按照人的意图工作,电脑的“脑”体现在软件硬件受软件控制的执行者,12,问题求解与程序设计,计算机基本工作过程“冯诺依曼机”结构,大脑,记忆装置,眼睛、耳朵、嘴、手,13,程序与编写程序,程序：能够实现特定功能的指令序列，这些指令指示计算机完成特定的操作。编写程序：编写指令序列的过程。指令往往以某种程序设计语言的语句形式给出。,问题求解与程序设计,14,例：哥尼斯堡七桥问题,【问题】17世纪的东普鲁士有一座哥尼斯堡城（现在叫加里宁格勒，在波罗的海南岸），普雷格尔河流过城中，在河中有两座小岛，全城共有七座桥将4个城区连接起来，于是，产生了一个有趣的问题：一个人是否能在一次步行中

5、穿越全部的七座桥后回到起点，且每座桥只经过一次。,算法及其描述方法,15,例：哥尼斯堡七桥问题,【想法抽象模型】可以用A、B、C、D表示4个城区，用 7 条线表示 7 座桥，将七桥问题抽象为一个图模型。,算法及其描述方法,16,例：哥尼斯堡七桥问题,【想法基本思路】是否存在欧拉回路的判定规则是：（1）如果通奇数桥的地方多于两个，则不存在欧拉回路；（2）如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；（3）如果没有一个地方通奇数桥，则无论从哪里出发，都能找到欧拉回路。由上述判定规则得到求解七桥问题的基本思路：依次计算图中与每个节点相关联的边的个数（称为节点的度），根据度为奇数的

6、节点个数判定是否存在欧拉回路。,算法及其描述方法,17,算法及其描述方法,例：哥尼斯堡七桥问题,【算法】设函数EulerCircuit求解七桥问题，算法描述如下：输入：二维数组mat44功能：计算七桥问题中奇数桥的结点个数输出：通奇数桥的结点个数count,step1:count 初始化为0;step2:下标i从0到n-1重复执行下列操作;step2.1:计算第i行元素之和degree;step2.2:如果degree为奇数，则;countstep3:返回count,18,算法：对特定问题求解步骤的一种描述。算法必须满足下列五个重要特性：1.输入;2.输出;3.有穷性;4.确定性;5.可行性。

7、,解决问题的方法,算法及其特性,算法及其描述方法,19,描述算法：算法设计者在构思和设计了一个算法之后，必须清楚准确地将所设计的求解步骤记录下来。使用算法：算法使用者知道如何调用算法。,算法描述,算法及其描述方法,求阶乘算法,20,自然语言,算法描述的方法,算法及其描述方法,步骤1：输入数据n;步骤2：将1保存到f中；步骤3：将1保存到i中；步骤4：若i大于n，则f为最后结果，算法执行步骤7；否则执行步骤5步骤5：i加1，将i*f的值放在f中；步骤6：重新执行步骤4；步骤7：输出数据f.,不直观，书写繁琐,21,算法及其描述方法,算法描述的方法,程序流程图,直观，流程线无约束,22,程序流程图

8、,算法及其描述方法,规定只能使用三种基本结构,顺序结构,选择结构,循环结构,算法描述的方法,23,N-S图,算法及其描述方法,只能使用一些基本结构，不允许使用带箭头的流程线,顺序结构,选择结构,循环结构,算法描述的方法,24,PAD图,算法及其描述方法,只能使用一些基本结构，不允许使用带箭头的流程线,顺序结构,选择结构,循环结构,算法描述的方法,25,程序设计语言,算法及其描述方法,int i,n;cinn;int f=1;for(i=1;i=n;i+)f=i*f;coutf;,很具体，语法要求严格,算法描述的方法,26,伪代码,算法及其描述方法,1.输入n;2.f=1;3.i=1;4.循环直

9、到in结束 4.1 f=i*f;4.2 i=i+1;5.输出f;,介于自然语言和程序设计语言之间,算法描述的方法,27,程序设计语言（Programming Language）是人与计算机进行交流的语言计算机直接能读懂的语言机器语言（Machine Code），也叫机器代码一种纯粹的二进制语言,程序设计语言的故事,28,程序设计语言的故事,计算机为什么用二进制呢？为什么不用我们日常熟悉的十进制呢？二进制在电器元件中容易实现 计算机进行二进制运算比进行十进制运算要简单得多,45678+56789,10101+11011,29,程序设计语言的故事,程序设计语言的发展机器语言(Machine Cod

10、e)汇编语言(Assemble Language)面向过程的高级语言面向对象的高级语言,30,程序设计语言的故事,机器语言编写的1+1程序执行效率高。不同计算机使用不同的机器语言，程序不能通用。在人类的自然语言和计算机编程语言之间存在着巨大的鸿沟。汇编语言编写的1+1程序不能直接识别和执行。仍然依赖于机器。编程语言与人类自然语言间的鸿沟略有缩小，但仍与人类的思维相差甚远。,101110000000000100000000000001010000000100000000,MOV AX,1ADD AX,1,31,程序设计语言的故事,高级语言（面向过程的）BASIC语言编写的1+1程序C语言编写的1

11、+1程序,PRINT 1+1,printf(%dn,1+1);,32,程序设计语言的故事,高级语言（面向对象的）C+语言编写的1+1程序,cout“1+1=“1+1;,33,程序设计语言的故事,一种程序设计语言对应一种编译器程序员按照该语言的语法编写程序源代码，把自己的意图融入到代码中编译器读入源代码，把程序员的意图转换成可执行程序，供他人使用,34,流行语言,应用编程语言机器语言汇编语言BasicPascalCC+JavaC#专项编程语言Lotus NotesPower Builder,Web编程语言HTMLXMLPHPASPJSPJavaScriptVBScript其他perlpython

12、VBA,35,C程序设计语言,简称C语言BCPL语言进化成B语言，B语言又进化为C语言是一种高级语言高级语言并不是“高级”，只是相对低级语言，在一个高的级别上进行编程历史悠久，战勋卓著诞生于上世纪70年代初，成熟于80年代“ANSI C”标准的发布是C语言成熟的标志很多重量级软件都是用C写的，如UNIX功能强大，无所不能几乎没有不能用C写出来的软件，没有不支持C的系统,36,C程序设计语言,C语言被分类为高级语言，但实际上它是一种介于高级语言和低级语言之间的语言。很多流行语言、新生语言都借鉴了它的思想、语法从C+，到Java，再到C#C+是对C语言的改进和扩充，完全兼容C的语法，除了保留C的优

13、点外，还增加了面向对象的特性。C+既可以进行面向过程的程序设计，也可以用来进行面向对象的程序设计。,37,C语言的设计者Dennis M.Ritchie,38,Ritchie和Thompson在开发UNIX,两人由于发明C和UNIX而获得1983年图灵奖,39,C/C+语言程序组成,一个简单的C程序，主程序输出两个整数中的较大者,40,C/C+语言程序组成,一个简单的C+程序，主程序输出两个整数中的较大者,41,C/C+语言程序组成,C/C+程序可由一个或多个文件组成，文件分为头文件和源文件两种。头文件以.h为后缀，源文件以.c或.cpp为后缀；一般将函数的声明、类型声明、类的说明及全局变量的

14、声明（包括宏定义）等部分放在.h文件；而将函数的定义、类的实现及类的使用等形成为.c或.cpp文件；C+源程序可分为三个部分：编译预处理、程序主体和注释C/C+程序有且仅有一个main函数(主函数)，程序开始执行和结束都在main函数。,42,C/C+语言程序组成,一个简单的C+程序，主程序输出两个数的大小,头文件,源文件,编译预处理,程序主体,注释,主函数,43,程序设计方法,面向过程的结构化程序设计面向对象的程序设计,44,面向过程的结构化程序设计,#includedouble a;void fun1()a=18;static int b=10;coutb=bendl;void fun2(

15、)static int c=20;couta=aendl;coutc=cendl;void main()fun1();fun2();couta=aendl;,45,程序设计方法,面向过程的结构化程序设计基本思想利用过程或函数来抽象和模拟客观现实。基本方法自顶向下、逐步求精从抽象到细节模块化设计将功能分解为：主模块（主函数）+若干个子模块（子函数）程序结构的规范性每一模块内部均是由：顺序、选择和循环三种基本结构组成。,46,结构化程序设计,最突出特征大任务分解为若干个小任务 程序功能通过调用一个个模块完成。思想简单容易实现 符合人求解问题的思维习惯。最重要的概念是函数，结构化程序设计主要围绕功能

16、划分与函数的定义和调用展开的。,47,面向对象的程序设计,class Datepublic:void Setvalue(int m,int d,int y)month=m;date=d;year=y;void Display()coutmonth-date-yearendl;private:int month;int date;int year;void main()Date today;coutToday is:endl;today.Setvalue(18,12,2005);/圆点访问成员函数today.Display();/圆点访问成员函数,48,程序设计方法,面向对象的程序设计基本思想使

17、用面向对象的观点来描述模仿并处理现实问题。基本方法将客观事物的属性和行为抽象成数据和操作数据的函数，并把它们组合（封装）成一个不可分割的整体（对象）。对象与对象之间通过消息进行通讯。,49,面向对象的程序设计,对象示例：一个“学生”对象的例子对象名：学生对象的属性：学号：123456姓名：令狐冲专业：计算机技术行为：修改学号、姓名、专业等等,50,面向对象的程序设计,最突出特征抽象性、封装性 程序模块间的关系更为简单，程序模块的独立性、数据的安全性有了良好的保障。继承性和多态性 可以大大提高程序的可重用性，使得软件的开发和维护都更为方便。最重要的概念是类和对象，面向对象的程序设计就是围绕类的定

18、义和类的使用展开的。,51,程序风格,#includeint 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,下面C程序完成什么功能？,52,程序风格,良好的程序风格：命名规则注释缩进适当空行、空格适当打印提示,目的是增加程序的可读性,53,Visual C+开发环境与上机指导,程序实现过程：编辑将源程序输入到计算机中，生成后缀为.cpp的磁盘文件。编译将程序的源代码转换为机器语言代码。连接将多个源程序文件以及库中的某些文件连在一起，生成一个后缀为exe的可执

19、行文件。运行调试,54,编辑源程序,进入Visual C+6.0开发环境（1）,55,编辑源程序,进入Visual C+6.0开发环境（2）,56,编辑源程序,创建一个Visual C+项目（1）,57,编辑源程序,创建一个Visual C+项目（2）,58,编辑源程序,创建一个Visual C+项目（3）,59,编辑源程序,创建一个Visual C+项目（4）,60,编辑源程序,建立并编辑Visual C+源程序（1）,61,编辑源程序,建立并编辑Visual C+源程序（2）,62,编辑源程序,建立并编辑Visual C+源程序（3）,63,编辑源程序,建立并编辑Visual C+源程序（4）,64,编辑源程序,建立并编辑Visual C+源程序（5）,65,编辑源程序,建立并编辑Visual C+源程序（6）,66,编译源程序,67,连接程序,68,运行程序（1）,69,运行程序（2）,70,运行程序（3）,71,调试程序（1）,按F9可设置、去除断点,72,调试程序（2）,F5进入开始调试,73,调试程序（3）,74,本章小结,问题求解与程序设计算法及其描述方法程序设计语言的故事C/C+语言程序组成程序设计方法程序风格Visual C+开发环境与上机指导,75,作业1,书上自学内容书上程序设计举例书上编程提示上机熟悉VC开发环境,