《程序设计与问题求解.ppt》由会员分享，可在线阅读，更多相关《程序设计与问题求解.ppt（75页珍藏版）》请在金锄头文库上搜索。
1、程序设计与问题求解程序设计与问题求解第第1章章 程序设计概述程序设计概述缪裕青缪裕青2011.9.20程序设计与问题求解I本章主要内容本章主要内容问题求解与程序设计问题求解与程序设计算法及其描述方法算法及其描述方法程序设计语言的故事程序设计语言的故事C/C+C/C+语言程序组成语言程序组成程序设计方法程序设计方法程序风格程序风格Visual C+Visual C+开发环境与上机指导开发环境与上机指导2程序设计与问题求解I问题求解与程序设计问题求解与程序设计问题求解问题求解w例：求1+2+100的和。 解:(1)分析分析问题特征。连续的100个整数求和。 (2)设计设计解决方案。100个数连加：
2、1+2+100采用等差数列求和公式计算：(1+100)*100/2拥有高斯的创造力,直接使用50*101 (3)优化优化解决方案。三种方案比较选择最好(优)的，计算量最小、计算速度最快。 (4)描述描述解决方案。可用数学算式50*101来描述。 (5)执行执行解决方案。计算50*101结果。分分析析设设计计优优化化描描述述执执行行3程序设计与问题求解I问题求解与程序设计问题求解与程序设计问题求解过程问题求解过程分分析析设设计计优优化化描描述述执执行行计算机做？计算机做？计算机做？计算机做？4程序设计与问题求解I问题求解与程序设计问题求解与程序设计计算机有计算机有智能吗？智能吗？5程序设计与问题
3、求解I问题求解与程序设计问题求解与程序设计计算机行业的梦想w让计算机（让计算机（Computer）能像人一样地）能像人一样地思考，与人自然交流，思考，与人自然交流，w人工智人工智能能AI （Artificial Intelligence）图灵（1912-1954）电子计算机理论和模型的奠基人w1946年诞生世界上第一台电子计算机年诞生世界上第一台电子计算机ENIACw1936年图灵发表论文年图灵发表论文“论可计算数及论可计算数及其在判定问题中的应用其在判定问题中的应用”w1966年年ACM设立设立“图灵奖图灵奖”6程序设计与问题求解I问题求解与程序设计问题求解与程序设计1997年，IBM公司研
4、制的深蓝超级计算机在一场“人机大战”中打败了国际象棋大师卡斯帕罗夫w被誉为被誉为“人工智能的一大胜利人工智能的一大胜利” 深蓝的主要研制者之一许峰雄博士：w胜利靠的只是不知疲倦地高速运算，并不是什么胜利靠的只是不知疲倦地高速运算，并不是什么智能智能 7程序设计与问题求解I问题求解与程序设计问题求解与程序设计计算机是用来延伸人能力的工具，具有高速运算的能力。我们的目标是控制计算机按照人的意愿去工作，执行解决方案。完成这一目标的手段就是“编程（Programming）”。8程序设计与问题求解I问问题题是是丰丰富富多多彩彩的的人具有思维人具有思维 人人计算机只认识计算机只认识0 0和和1 1计算机没
5、有思维计算机没有思维 计算机计算机 人和计算机通过程序进行沟通人和计算机通过程序进行沟通程序程序需要解决问题的人需要解决问题的人没有思维的计算机没有思维的计算机 问题求解与程序设计问题求解与程序设计9程序设计与问题求解I问题求解与程序设计问题求解与程序设计问题求解过程问题求解过程分分析析设设计计优优化化描描述述执执行行计算机可以做计算机可以做只能人做只能人做算法设计算法设计编写程序编写程序/算法实现算法实现问题问题思路思路算法算法程序程序程序设计程序设计10程序设计与问题求解I问题求解与程序设计问题求解与程序设计计算机组成计算机组成w硬件硬件：整个过程的执行者是硬件，但硬件是受软件控制的w软件
6、软件：编程，就是编写软件，使硬件按照人的意图工作电脑的“脑”体现在软件硬件受软件控制的执行者程序和数据执行结果11程序设计与问题求解I问题求解与程序设计问题求解与程序设计输入/输出设备存储器运算器控制器源程序和输入数据输出结果取出数据存入数据操作命令存取命令取出程序指令输入输出命令计算结果CPU计算机基本工作过程计算机基本工作过程“冯诺依曼机”结构 大脑记忆装置眼睛、耳朵、嘴、手12程序设计与问题求解I程序与编写程序程序与编写程序 程序：程序：能够实现特定功能的能够实现特定功能的指令序列指令序列，这些指令指，这些指令指示计算机完成特定的操作。示计算机完成特定的操作。 编写程序：编写程序：编写指
7、令序列的编写指令序列的过程过程。指令往往以某种。指令往往以某种程序设计语言程序设计语言的的语句语句形式给出。形式给出。问题求解与程序设计问题求解与程序设计13程序设计与问题求解I例：哥尼斯堡七桥问题 【问题问题】17世纪的东普鲁士有一座哥尼斯堡城（现在叫加里世纪的东普鲁士有一座哥尼斯堡城（现在叫加里宁格勒，在波罗的海南岸），普雷格尔河流过城中，在河中宁格勒，在波罗的海南岸），普雷格尔河流过城中，在河中有两座小岛，全城共有七座桥将有两座小岛，全城共有七座桥将4个城区连接起来，于是，产个城区连接起来，于是，产生了一个有趣的问题：一个人是否能在一次步行中穿越全部生了一个有趣的问题：一个人是否能在一次
8、步行中穿越全部的七座桥后回到起点，且每座桥只经过一次。的七座桥后回到起点，且每座桥只经过一次。算法及其描述方法算法及其描述方法14程序设计与问题求解I例：哥尼斯堡七桥问题 东区东区北区北区岛区岛区南区南区CADB 抽象抽象【想法想法抽象模型抽象模型】可以用可以用A、B、C、D表示表示4个城区，用个城区，用 7 条线表示条线表示 7 座桥，将七桥问题抽象为一个图模型。座桥，将七桥问题抽象为一个图模型。 算法及其描述方法算法及其描述方法15程序设计与问题求解I例：哥尼斯堡七桥问题 【想法想法基本思路基本思路】是否存在欧拉回路的判定规则是：是否存在欧拉回路的判定规则是：（1）如果通奇数桥的地方多于两
9、个，则不存在欧拉回路；）如果通奇数桥的地方多于两个，则不存在欧拉回路；（2）如果只有两个地方通奇数桥，可以从这两个地方之一出）如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；发，找到欧拉回路；（3）如果没有一个地方通奇数桥，则无论从哪里出发，都能）如果没有一个地方通奇数桥，则无论从哪里出发，都能找到欧拉回路。找到欧拉回路。 由上述判定规则得到求解七桥问题的基本思路：依次计算由上述判定规则得到求解七桥问题的基本思路：依次计算图中与每个节点相关联的边的个数（称为节点的度），根据度图中与每个节点相关联的边的个数（称为节点的度），根据度为奇数的节点个数判定是否存在欧拉回路。为奇数的节
10、点个数判定是否存在欧拉回路。 算法及其描述方法算法及其描述方法16程序设计与问题求解I算法及其描述方法算法及其描述方法例：哥尼斯堡七桥问题 【算法算法】设函数设函数EulerCircuit求解七桥问题，算法描述如下：求解七桥问题，算法描述如下：输入：二维数组输入：二维数组mat44功能：计算七桥问题中奇数桥的结点个数功能：计算七桥问题中奇数桥的结点个数输出：通奇数桥的结点个数输出：通奇数桥的结点个数countstep1:count 初始化为初始化为0;step2:下标下标i从从0到到n-1重复执行下列操作重复执行下列操作; step2.1:计算第计算第i行元素之和行元素之和degree; st
11、ep2.2:如果如果degree为奇数，则为奇数，则;countstep3:返回返回count17程序设计与问题求解I算法：算法：对特定问题求解步骤的一种描述。算法必须满足下列五个重要特性：1. 输入; 2. 输出; 3. 有穷性 ; 4. 确定性; 5. 可行性。 解决问题的方法解决问题的方法算算 法（法（y = f (x)） 有穷性：在合理时间内结束；有穷性：在合理时间内结束； 确定性：不存在二义性；确定性：不存在二义性； 可行性：机器可执行；可行性：机器可执行；输入输入输出输出算法及其特性算法及其特性算法及其描述方法算法及其描述方法 18程序设计与问题求解Iw描述算法：算法设计者在构思和
12、设计了一个算法之后，必须清楚准确地将所设计的求解步骤记录下来。 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； 步
13、骤步骤7：输出数据：输出数据f.不直观，书写繁琐不直观，书写繁琐20程序设计与问题求解IN开始输入n f=1;i=1ini=i+1；f=i*f 输出f结束Y图形符号名 称含 义起止框起止框表示算法的开始或表示算法的开始或结结束束处处理框理框表示表示处处理或运算等功能理或运算等功能输输入入/ /输输出框出框表示表示进进行行输输入入/ /输输出操作出操作判断框判断框根据根据给给定的条件是否定的条件是否满满足决定足决定执执行两条路径中的某一条路径行两条路径中的某一条路径控制流控制流表示算法表示算法执执行的路径，箭行的路径，箭头头代代表方向表方向算法及其描述方法算法及其描述方法算算法描述的方法法描述的
14、方法w程序流程图直观，流程线无约束直观，流程线无约束21程序设计与问题求解Iw程序流程图算法及其描述方法算法及其描述方法 规定只能使用三种基本结构规定只能使用三种基本结构AB条件表达式ABFT条件表达式ABTF顺序结构顺序结构选择结构选择结构循环结构循环结构算算法描述的方法法描述的方法22程序设计与问题求解IwN-S图算法及其描述方法算法及其描述方法 只能使用一些基本结构，不允许只能使用一些基本结构，不允许使用带箭头的流程线使用带箭头的流程线AB条件表达式A顺序结构顺序结构选择结构选择结构循环结构循环结构AB条件表达式TF算算法描述的方法法描述的方法23程序设计与问题求解IwPAD图算法及其描
15、述方法算法及其描述方法 只能使用一些基本结构，不允许只能使用一些基本结构，不允许使用带箭头的流程线使用带箭头的流程线顺序结构顺序结构选择结构选择结构循环结构循环结构ABAB条件表达式whileA算算法描述的方法法描述的方法24程序设计与问题求解Iw程序设计语言算法及其描述方法算法及其描述方法 int i,n;cinn;int f=1;for (i=1; i=n; i+) f=i*f;coutn结束结束 4.1 f=i*f; 4.2 i=i+1;5.输出输出f;介于自然语言和程序设计语言之间介于自然语言和程序设计语言之间算算法描述的方法法描述的方法26程序设计与问题求解I程序设计语言（Progr
16、amming Language）是人与计算机进行交流的语言计算机直接能读懂的语言w机器语言机器语言（Machine Code），也叫机器代码），也叫机器代码w一种纯粹的二进制语言一种纯粹的二进制语言程序设计语言的故事程序设计语言的故事27程序设计与问题求解I程序设计语言的故事程序设计语言的故事计算机为什么用二进制呢？为什么不用我们日常熟悉的十进制呢？w二进制在电器元件中容易实现二进制在电器元件中容易实现 w计算机进行二进制运算比进行十进制运算要简计算机进行二进制运算比进行十进制运算要简单得多单得多 45678+56789 10101+1101128程序设计与问题求解I程序设计语言的故事程序设计
17、语言的故事程序设计语言的发展程序设计语言的发展w机器语言(Machine Code)w汇编语言(Assemble Language)w面向过程的高级语言w面向对象的高级语言29程序设计与问题求解I程序设计语言的故事程序设计语言的故事机器语言编写的机器语言编写的1+1程序程序w执行效率高。执行效率高。w不同计算机使用不同的机器不同计算机使用不同的机器语言，程序不能通用。语言，程序不能通用。w在人类的自然语言和计算机在人类的自然语言和计算机编程语言之间存在着巨大的编程语言之间存在着巨大的鸿沟。鸿沟。汇编语言编写的汇编语言编写的1+1程序程序w不能直接识别和执行。不能直接识别和执行。w仍然依赖于机器
18、。仍然依赖于机器。w编编程程语语言言与与人人类类自自然然语语言言间间的的鸿鸿沟沟略略有有缩缩小小，但但仍仍与与人人类的思维相差甚远。类的思维相差甚远。101110000000000100000000000001010000000100000000MOV AX, 1ADD AX, 1汇编语言程序机器代码翻译程序30程序设计与问题求解I程序设计语言的故事程序设计语言的故事高级语言（面向过程的）wBASIC语言编写的语言编写的1+1程序程序wC语言编写的语言编写的1+1程序程序PRINT 1+1printf(%dn, 1+1);高级语言源程序目标目标程序翻译翻译程序高级语言源程序执行执行程序解释解释
19、程序31程序设计与问题求解I程序设计语言的故事程序设计语言的故事高级语言（面向对象的）wC+语言编写的语言编写的1+1程序程序cout“1+1=“ 1+1;面向对象语言源程序目标程序翻译程序32程序设计与问题求解I程序设计语言的故事程序设计语言的故事一种程序设计语言对应一种编译器程序员按照该语言的语法编写程序源代码，把自己的意图融入到代码中编译器读入源代码，把程序员的意图转换成可执行程序，供他人使用源程序目标程序编译程序33程序设计与问题求解I流行语言流行语言应用编程语言w机器语言机器语言w汇编语言汇编语言wBasicwPascalwCwC+wJavawC#专项编程语言wLotus Notes
20、wPower BuilderWeb编程语言wHTMLwXMLwPHPwASPwJSPwJavaScriptwVBScript其他wperlwpythonwVBA34程序设计与问题求解IC程序设计语言程序设计语言简称C语言wBCPL语言进化成语言进化成B语言，语言，B语言又进化为语言又进化为C语言语言是一种高级语言w高级语言并不是高级语言并不是“高级高级”，只是相对低级语言，在一，只是相对低级语言，在一个高的级别上进行编程个高的级别上进行编程历史悠久，战勋卓著w诞生于上世纪诞生于上世纪70年代初，成熟于年代初，成熟于80年代年代w“ANSI C”标准的发布是标准的发布是C语言成熟的标志语言成熟的
21、标志w很多重量级软件都是用很多重量级软件都是用C写的，如写的，如UNIX功能强大，无所不能w几乎没有不能用几乎没有不能用C写出来的软件，没有不支持写出来的软件，没有不支持C的系统的系统35程序设计与问题求解IC程序设计语言程序设计语言C语言被分类为高级语言，但实际上它是一种介于高级语言和低级语言之间的语言。很多流行语言、新生语言都借鉴了它的思想、语法w从从C+，到，到Java，再到，再到C#C+是对C语言的改进和扩充，完全兼容C的语法，除了保留C的优点外，还增加了面向对象的特性。C+既可以进行面向过程的程序设计，也可以用来进行面向对象的程序设计。36程序设计与问题求解IC语言的设计者语言的设计
22、者Dennis M. Ritchie37程序设计与问题求解IRitchie和和Thompson在开发在开发UNIX两人由于发明两人由于发明C和和UNIX而获得而获得1983年图灵奖年图灵奖38程序设计与问题求解IC/C+C/C+语言程序组成语言程序组成一个简单的C程序，主程序输出两个整数中的较大者39程序设计与问题求解IC/C+C/C+语言程序组成语言程序组成一个简单的C+程序，主程序输出两个整数中的较大者40程序设计与问题求解IC/C+C/C+语言程序组成语言程序组成C/C+程序可由程序可由一个或多个一个或多个文件组成，文件分为文件组成，文件分为头文件和源文件两种。头文件以头文件和源文件两种
23、。头文件以.h为后缀，源文为后缀，源文件以件以.c或或.cpp为后缀；为后缀；一般将函数的一般将函数的声明声明、类型、类型声明声明、类的、类的说明说明及全局及全局变量的变量的声明声明（包括宏定义）等部分放在（包括宏定义）等部分放在.h文件；文件；而将函数的而将函数的定义定义、类的、类的实现实现及类的及类的使用使用等形成为等形成为.c或或.cpp文件；文件；C+源程序可分为三个部分：源程序可分为三个部分： 编译预处理、程序主体和注释编译预处理、程序主体和注释C/C+程序有且仅有一个程序有且仅有一个main函数函数(主函数主函数)，程，程序序开始开始执行和执行和结束结束都在都在main函数。函数。
24、41程序设计与问题求解IC/C+C/C+语言程序组成语言程序组成一个简单的C+程序，主程序输出两个数的大小头文件源文件编译预处理程序主体注释主函数42程序设计与问题求解I程序设计方法程序设计方法面向过程的结构化程序设计面向过程的结构化程序设计面向对象的程序设计面向对象的程序设计43程序设计与问题求解I面向过程的结构化程序设计面向过程的结构化程序设计#includedouble a;void fun1() a=18; static int b=10; coutb=bendl;void fun2() static int c=20; couta=aendl; coutc=cendl; void m
25、ain() fun1(); fun2(); couta=aendl;函数函数主函数44程序设计与问题求解I程序设计方法程序设计方法面向过程的结构化程序设计面向过程的结构化程序设计w基本思想s利用过程或函数来抽象和模拟客观现实。w基本方法s自顶向下、逐步求精从抽象到细节s模块化设计将功能分解为：主模块（主函数）+若干个子模块（子函数）s程序结构的规范性每一模块内部均是由：顺序、选择和循环三种基本结构组成。45程序设计与问题求解I结构化程序设计结构化程序设计最突出特征最突出特征w大任务分解为若干个小任务 程序功能通过调用一个个模块完成。w思想简单容易实现 符合人求解问题的思维习惯。最重要的概念是函
26、数，结构化程序设计主要围绕最重要的概念是函数，结构化程序设计主要围绕功能划分功能划分与与函数函数的定义和调用展开的。的定义和调用展开的。46程序设计与问题求解I面向对象的程序设计面向对象的程序设计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
27、,12,2005); /圆点访问成员函数圆点访问成员函数today.Display(); /圆点访问成员函数圆点访问成员函数类对象47程序设计与问题求解I程序设计方法程序设计方法面向对象的程序设计面向对象的程序设计w基本思想s使用面向对象的观点来描述模仿并处理现实问题。w基本方法s将客观事物的属性和行为抽象成数据和操作数据的函数，并把它们组合（封装）成一个不可分割的整体（对象）。s对象与对象之间通过消息进行通讯。48程序设计与问题求解I面向对象的程序设计面向对象的程序设计对象示例：一个对象示例：一个“学生学生”对象的例子对象的例子w对象名对象名：学生：学生w对象的属性对象的属性：s学号：学号：
28、123456s姓名：令狐冲姓名：令狐冲s专业：计算机技术专业：计算机技术w行为：行为：s修改学号、姓名、专业等等修改学号、姓名、专业等等49程序设计与问题求解I面向对象的程序设计面向对象的程序设计最突出特征最突出特征w抽象性、封装性 程序模块间的关系更为简单，程序模块的独立性、数据的安全性有了良好的保障。w继承性和多态性 可以大大提高程序的可重用性，使得软件的开发和维护都更为方便。最重要的概念是类和对象，面向对象的程序设计最重要的概念是类和对象，面向对象的程序设计就是围绕就是围绕类类的定义和类的使用展开的。的定义和类的使用展开的。50程序设计与问题求解I程序风格程序风格#includeint
29、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,&x,&y);printf(%dn,a(x,y);下面下面C程序完成什么功能？程序完成什么功能？51程序设计与问题求解I程序风格程序风格良好的程序风格：良好的程序风格：s命名规则命名规则s注释注释s缩进缩进s适当空行、空格适当空行、空格s适当打印提示适当打印提示目的是增加程序的可读性目的是增加程序的可读性52程序设计与问题求解IVisual C+开发环境与上机指导开发环境与上机指导程序实现过程：程序实现
30、过程：编辑编辑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+项目（项目
31、（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
32、）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本章小结本章小结问题求解与程序设计问题求解与程序设计算法及其描述方法算法及其描述方法程序设计语言的故事程序设计语言的故事C/C+C/C+语言程序组成语言程序组成程序设计方法程序设计方法程序风格程序风格Visual C+Visual C+开发环境与上机指导开发环境与上机指导74程序设计与问题求解I作业作业1书上自学内容书上自学内容书上程序设计举例书上程序设计举例书上编程提示书上编程提示上机熟悉上机熟悉VCVC开发环境开发环境75
