《计算机基础与应用》教学课件-第4章-问题求解与算法.ppt

1、1本章学习目标本章学习目标n掌握计算机问题求解的一般步骤。掌握计算机问题求解的一般步骤。n了解程序、算法的概念。了解程序、算法的概念。n了解枚举法、迭代法、排序算法、查找算法、了解枚举法、迭代法、排序算法、查找算法、程序设计一般过程。程序设计一般过程。3 4.1 问题求解问题求解 4.2 程序与算法程序与算法 4.2.1 程序程序 4.2.2 算法的概念算法的概念 4.2.3 算法的表示算法的表示 4.3 算法设计的基本方法算法设计的基本方法 4.3.1 枚举法枚举法 4.3.2 迭代迭代 4.3.3 排序排序 4.3.4 查找查找 4.3.5 程序设计的一般过程程序设计的一般过程 4.3.6

2、 程序设计方法程序设计方法44.1 问题求解n科学探究的过程：提出问题、发现问题、解决问题n解决问题的科学方法：一般科学方法 专门科学方法n目前，计算成为一般科学方法 大量的问题都可以通过计算来解决n三大科学思维：理论思维、实验思维、计算思维5计算思维求解问题的过程：问题抽象 完全超越物理的时空观用符号来表示 自动化 机械地一步一步自动执行，即编写程序1.抽象 本义：从众多的事物中抽取出共同的、本质性的特征，而舍弃其非本质的特征 在计算机科学中：简化复杂的现实问题的最佳途径。形式化 采用严格的数学语言，具有精确的数学语义的方法。基于数学的方法，不同的形式化方法的数学基础是不同的 有以集合论和递

3、归函数为基础的，有以图论为基础的6 数学建模 通过计算得到的结果来解释实际问题，并接受实际的检验，来建立数学模型的全过程。实际事物的一种数学简化，常常是以某种意义上接近实际事 物的抽象形式存在的，但与真实的事物有着本质的区别。如：龙卷风模型、潮汐模型 形式化和数学建模都是基于数学的方法。2.自动化 抽象是自动化的前提和基础 计算机通过程序实现实现自动化 程序的核心是算法 常见的简单问题，自动化：设计算法和编写程序7【例9.1】猴子吃桃问题。猴子第一天摘了若干个桃子，当即吃了一半，还不解馋，又多吃了一个；第二天，吃剩下的桃子的一半，还不过瘾，又多吃了一个；以后每天都吃前一天剩下的一半多一个，到第

4、10天想再吃时，只剩下一个桃子了。问第一天共摘了多少个桃子？假定用xn表示第n天桃子的数量（1）抽象 采用逆向思维，发现数学的递推公式：89（2）自动化 设计算法和编写程序。算法设计 自然语言描述算法自然语言描述算法 置初态：x1，i10；如果i等于为1，则转；x(x+1)*2 ii-1 转 输出x的值；结束 伪代码描述算法伪代码描述算法 Begin x=1 i=10 While(i=1)x=(x+1)*2 i=i-1 Print x End 10 编写程序/用用C语语言言编写编写的的程序程序：#include int main()int x,i;x=1;i=10;while(i=1)x=(x

5、+1)*2;i=i-1;cout第一天共摘了第一天共摘了x个桃子个桃子endl;return 0;计算机求解问题的过程：抽象和自动化114.2 程序与算法12 4.1 问题求解问题求解 4.2 程序与算法程序与算法 4.2.1 程序程序 4.2.2 算法的概念算法的概念 4.2.3 算法的表示算法的表示 4.3 算法设计的基本方法算法设计的基本方法 4.3.1 枚举法枚举法 4.3.2 迭代迭代 4.3.3 排序排序 4.3.4 查找查找 4.3.5 程序设计的一般过程程序设计的一般过程 4.3.6 程序设计方法程序设计方法一、程序 【例4.2】下面是某一个学校颁奖大会的程序：主持人宣布颁奖会

6、开始，介绍出席颁奖会的领导 校长讲话 领导宣布获奖名单 领导颁奖 获奖代表发言 主持人宣布大会结 按一定的顺序安排的工作即操作序列 描述完成某项功能所涉及的对象和动作规则 计算机学科中,程序描述了计算机处理数据、解决问题的过程13n什么是程序？【例4.2】下面是某一个学校颁奖大会的程序：主持人宣布颁奖会开始，介绍出席颁奖会的领导 校长讲话 领导宣布获奖名单 领导颁奖 获奖代表发言 主持人宣布大会结 按一定的顺序安排的工作即操作序列 描述完成某项功能所涉及的对象和动作规则 计算机学科中,程序描述了计算机处理数据、解决问题的过程14【例4.3】教师节到了，要对教龄满30年的教职工发荣誉证书，要求从

7、存放教职工档案的“d:zg.dat”文件中，显示出教龄满30年的教职工的姓名和所在部门。C语言程序如下：#include stdafx.h#include int main()char xm80,char bm80;int jl;FILE*fp;fp=fopen(d:zg.dat,r);while(!feof(fp)fscanf(fp,%s,xm);fscanf(fp,%s,bm);fscanf(fp,%d,&jl);if(jl=30)cout姓名：xm所在部分：bm30且性别且性别为女？为女？从文件中读入一行从文件中读入一行truefalse当型循环3 3 算法的特点算法的特点有穷性有穷性

8、任意一个算法在执行有穷个计算步骤后任意一个算法在执行有穷个计算步骤后必须终止。必须终止。每一个计算步骤，必须是精确地定义、每一个计算步骤，必须是精确地定义、无二义性无二义性可行性可行性 有限多个步骤应该在一个合理的范围内有限多个步骤应该在一个合理的范围内进行进行输入输入 一般有一般有0 0个或多个输入，它们取自某一特定个或多个输入，它们取自某一特定的集合。的集合。输出输出 一般有若干个输出信息，是反映对输入数一般有若干个输出信息，是反映对输入数据加工后的结果。据加工后的结果。264 4 算法的分类算法的分类（1 1）数值计算算法）数值计算算法u 用于科学计算用于科学计算u 特点是少量的输入、输

9、出，复杂的运算。特点是少量的输入、输出，复杂的运算。u 例如：计算圆周率，积分例如：计算圆周率，积分（2 2）非数值计算算法）非数值计算算法u 对数据的管理对数据的管理u 特点是大量的输入、输出，简单的算术运算特点是大量的输入、输出，简单的算术运算 和大量的逻辑运算。和大量的逻辑运算。u 例如：排序例如：排序 查找替换查找替换 随着计算机技术的发展和应用面的普及，非数值计算算法随着计算机技术的发展和应用面的普及，非数值计算算法涉及面更广，研究的任务更重。涉及面更广，研究的任务更重。275 算法的表示算法的表示u自然语言自然语言u传统流程图传统流程图u伪代码伪代码u计算机语言计算机语言28利用求

10、圆周率公式利用求圆周率公式 计算圆周率计算圆周率1119171513114分析分析:对通项式：对通项式：t ti i=，i=1i=1，2 2，进行累加，直到某项进行累加，直到某项t ti i绝绝对值小于精度即对值小于精度即|t|10|t|=0.00000001)/当当前项还没有到达精度，继续求和当当前项还没有到达精度，继续求和pi=pi+t;/求和求和s=-1*s;/为下一项作准备，符号变化为下一项作准备，符号变化/i+;/t=s*1.0/(2*i-1);/下一项值下一项值coutsetprecision(8)pi*4endl;只有用计算只有用计算机语言编写机语言编写的程序才能的程序才能被计算

11、机执被计算机执行行必须严格遵循必须严格遵循所选择的编程所选择的编程语言的语法规语言的语法规则则344.3 4.3 算法设计的基本方算法设计的基本方法法36 4.1 问题求解问题求解 4.2 程序与算法程序与算法 4.2.1 程序程序 4.2.2 算法的概念算法的概念 4.2.3 算法的表示算法的表示 4.3 算法设计的基本方法算法设计的基本方法 4.3.1 枚举法枚举法 4.3.2 迭代迭代 4.3.3 排序排序 4.3.4 查找查找 4.3.5 程序设计的一般过程程序设计的一般过程 4.3.6 程序设计方法程序设计方法1.1.枚举法枚举法n亦称亦称穷举法穷举法或或试凑法试凑法。n例：计算机破

12、案例：计算机破案 张三在家中遇害，侦查中发现张三在家中遇害，侦查中发现A A、B B、C C、D D四人到四人到过现场。过现场。A A说：说：“我没有杀人。我没有杀人。”B B说：说：“C C是凶手。是凶手。”C C说：说：“杀人者是杀人者是D D”D D说：说：“C C在冤枉好人。在冤枉好人。”侦查员经过判断四人中有三人说的是真话，四人中侦查员经过判断四人中有三人说的是真话，四人中有且只有一人是凶手，凶手到底是谁？有且只有一人是凶手，凶手到底是谁？37分析分析 用用0 0表示不是凶手，表示不是凶手，1 1表示凶手，则每个人的表示凶手，则每个人的取值范围就是取值范围就是00，11 38算法算法

13、在每个人的取值范围在每个人的取值范围00，11的所有可能中进行搜索，的所有可能中进行搜索，如果表格的组合条件同时满足，即为凶手。如果表格的组合条件同时满足，即为凶手。相应的伪代码为：相应的伪代码为：For A=0 To 1For A=0 To 1 For B=0 TO 1 For B=0 TO 1 For C=0 To 1 For C=0 To 1 For D=0 To 1 For D=0 To 1 If(A=0)+(C=1)+(D=1)+(D=0)=3And(A+B+C+D=1)If(A=0)+(C=1)+(D=1)+(D=0)=3And(A+B+C+D=1)Print A,B,C,D/Pr

14、int A,B,C,D/输出的值是输出的值是1 1的为凶手，的为凶手，要同时满足要同时满足39总结总结n枚举法基本思想枚举法基本思想:采用搜索的方法，根据题目的部分条件确定答采用搜索的方法，根据题目的部分条件确定答案的大致搜索范围案的大致搜索范围在此范围内对所有可能的情况逐一验证在此范围内对所有可能的情况逐一验证若某个情况符合题目的条件，则为本题的一个若某个情况符合题目的条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条答案；若全部情况验证完后均不符合题目的条件，则问题无解。件，则问题无解。n枚举法是一种比较熬时的算法。枚举法是一种比较熬时的算法。为提高效率，根为提高效率，根据解决问

15、题的情况，尽量减少内循环层数或每层据解决问题的情况，尽量减少内循环层数或每层循环次数。循环次数。40思考题思考题:n百元买百鸡问题。假定小鸡每只百元买百鸡问题。假定小鸡每只0.50.5元元,公公鸡每只鸡每只2 2元，母鸡每只元，母鸡每只3 3元。现在有元。现在有100100元钱元钱要求买要求买100100只鸡，列出所有可能的购鸡方案。只鸡，列出所有可能的购鸡方案。搜索的范围搜索的范围?要满足的条件是什么？要满足的条件是什么？请尝试写出伪代码请尝试写出伪代码412.2.迭代法迭代法一般来说，迭代法又称递推法，是利用问题本身所具有的某种递推关系求解问题的一种方法。基本思想：从初值出发，归纳出新值与

16、旧值间直到最后值为止存在的关系，从而把一个复杂的计算过程转化为简单过程的多次重复，每次重复都从旧值的基础上递推出新值，并由新值代替旧值。42高次方程求根高次方程求根n求高次方程根：求高次方程根：的近似解，精度的近似解，精度为为1010-5-5 。迭代公式为：迭代公式为：n算法步骤为：算法步骤为：选择方程的近似根作为初值赋值给选择方程的近似根作为初值赋值给x1x1；将将x1x1的值保存于的值保存于x0 x0，通过迭代公式求得新近似根，通过迭代公式求得新近似根x1x1；若若x1x1与与x0 x0的差绝对值大于指定的精度的差绝对值大于指定的精度时，继续执行步骤；时，继续执行步骤；否则否则x1x1就是

17、方程的近似解就是方程的近似解。：初值的选择对计算有什么影响？初值的选择对计算有什么影响？433.3.排序排序n常用排序算法常用排序算法选择法选择法冒泡法冒泡法插入排序插入排序合并排序合并排序快速排序快速排序45(1)(1)选择法选择法将将N N个数按照从小到大的顺序排序个数按照从小到大的顺序排序原始数据原始数据 8 6 9 3 2 78 6 9 3 2 7过程演示过程演示算法思想算法思想:每次在无序数中找每次在无序数中找最小（递增）数的下标最小（递增）数的下标，然后存放在无序数的然后存放在无序数的第一个位置第一个位置。For i=0To n-2 /n个数进行个数进行n-1轮比较轮比较 mini

18、 /每一轮内，假定当前个最小每一轮内，假定当前个最小 For j=i+1 To n-1 If ajaj+1 /If ajaj+1 /若相邻两个次序不对若相邻两个次序不对 aj aj 与与aj+1aj+1元素交换元素交换 /则交换位置，小则交换位置，小数上浮，大数下沉数上浮，大数下沉For i=0 To n-2/n个数进行个数进行n-1轮比较轮比较 noswaptrue /数据不需交换数据不需交换,即已经有序即已经有序 For j=0 To n-2-i /每一轮内每一轮内 If ajaj+1 /若相邻两个次序不对若相邻两个次序不对 aj 与与aj+1元素交换元素交换 /则交换位置，小数上浮，则交

19、换位置，小数上浮，大数下沉大数下沉 noswapfalse/一旦交换过，一旦交换过，noswap设置为设置为flase If noswap 数据已经有序提前结束数据已经有序提前结束 /一轮比较结束，一轮比较结束，根据根据noswap值判断数据有序否值判断数据有序否 数据已经有序后数据已经有序后,后续的比较可省后续的比较可省略略4.4.查找查找48u已知已知姓名姓名,怎怎么查找某个学么查找某个学生生?u已知已知学号学号,怎怎么查找某个学么查找某个学生生?12512521251252高靖遥高靖遥男男交通运输类交通运输类12512541251254李一鸣李一鸣男男交通运输类交通运输类12512591

20、251259张晓敏张晓敏女女交通运输类交通运输类12512691251269施奕辰施奕辰男男交通运输类交通运输类12512701251270方尧方尧男男交通运输类交通运输类12512711251271应一丹应一丹女女交通运输类交通运输类12512731251273王子恒王子恒男男交通运输类交通运输类12512781251278黄彬黄彬男男交通运输类交通运输类12512811251281朱一鸣朱一鸣男男交通运输类交通运输类12512831251283陈钰陈钰女女交通运输类交通运输类12512851251285王羿童王羿童男男交通运输类交通运输类12512981251298邓能静邓能静女女交通运输

21、类交通运输类12513061251306王寒冰王寒冰男男交通运输类交通运输类12513141251314陈彦旭陈彦旭男男交通运输类交通运输类12513281251328温馨温馨女女交通运输类交通运输类12513291251329刘建兴刘建兴男男交通运输类交通运输类12513301251330彭洋彭洋男男交通运输类交通运输类(1)(1)顺序查找顺序查找u 适用于适用于无序序列无序序列，按顺序逐一比对。按顺序逐一比对。u 例：输入一个数例：输入一个数keykey，查找它是否，查找它是否在数列中，如在，在数列中，如在，输出是第几个数。输出是第几个数。49(2)(2)二分查找二分查找二分法查找只适合于

22、在二分法查找只适合于在已排好序已排好序的数组中进行。的数组中进行。待查区间的下界待查区间的下界lowlow为为1 1，上界，上界highhigh为为N N。求待查区间中间元素的下标求待查区间中间元素的下标 mid=(low+high)/2mid=(low+high)/2，x x和和amidamid比较。比较。若若x=amidx=amid，则查找完毕，结束程序；，则查找完毕，结束程序；若若xamidxamid，low=mid+1low=mid+1；若若xamidxhighlowhigh无查找区域，找不到无查找区域，找不到5051思考题思考题n利用二分法查找方法，设计人与计算机做利用二分法查找方法

23、，设计人与计算机做猜数游戏。由计算机随机产生一个猜数游戏。由计算机随机产生一个11，100100的任意整数的任意整数keykey，让用户猜这个数。，让用户猜这个数。n利用二分法的思想利用二分法的思想,该怎样解决该怎样解决?请画出流请画出流程图程图525.5.程序设计的一般过程程序设计的一般过程53分析问题确定数学模型程序编写、编辑、编译和连接算法设计运行和测试6.程序设计方法n结构化程序设计结构化程序设计n面向对象程序设计面向对象程序设计54结构化程序设计思想n最早由荷兰科学家最早由荷兰科学家E.W.DijkstraE.W.Dijkstra提出提出p任何程序都基于任何程序都基于顺序顺序、选择选

24、择、循环循环三种基本的三种基本的控制结构控制结构p程序具有模块化特征，每个程序模块具有程序具有模块化特征，每个程序模块具有惟一惟一的入口和出口的入口和出口p取消取消GOTOGOTO语句语句n结构化程序的结构简单清晰，可读性好，模结构化程序的结构简单清晰，可读性好，模块化强块化强。55结构化编程主要包括两个方面n提倡采用自顶向下、逐步细化的模块化程序设计原则n每个模块强调采用单入口单出口的三种基本控制结构（顺序、选择、循环），避免使用GOTO语句56主程序模块2模块3模块1模块11模块112 模块31模块32模块111模块311面向对象程序设计n8080年代初面向对象的程序设计年代初面向对象的程

25、序设计(Object(Object Oriented ProgrammingOriented Programming，简称，简称OOP)OOP)n用面向对象的方法解决问题，不再将问题分用面向对象的方法解决问题，不再将问题分解为过程，而是将问题解为过程，而是将问题分解为对象分解为对象。p对象：属性、方法和事件对象：属性、方法和事件n“对象消息对象消息”的面向对象的程序设计模式的面向对象的程序设计模式有取代有取代“数据结构算法数据结构算法”的面向过程的程的面向过程的程序设计模式的趋向。序设计模式的趋向。57两者区别n结构化的分解突出结构化的分解突出过程过程：p如何做如何做(How to do)(H

26、ow to do)？它强调代码的功能是如何得？它强调代码的功能是如何得以完成。以完成。n面向对象的分解突出真实世界和抽象的面向对象的分解突出真实世界和抽象的对象对象：p做什么做什么(What to do)(What to do)？它将大量的工作由相应的对？它将大量的工作由相应的对象来完成，程序员在应用程序中只需说明要求对象象来完成，程序员在应用程序中只需说明要求对象完成的任务。完成的任务。58面向对象程序设计益处 符合人们习惯的思维方法，便于分析复杂符合人们习惯的思维方法，便于分析复杂而多变化的问题；而多变化的问题；易于软件的维护和功能的增减；易于软件的维护和功能的增减；可重用性好，能用继承的方式减短程序开可重用性好，能用继承的方式减短程序开发所花的时间；发所花的时间；与可视化技术相结合，改善了工作界面和与可视化技术相结合，改善了工作界面和便于与用户交互。便于与用户交互。