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

1、1计算机基础与应用第章问题求解与算法 本章学习目标掌握计算机问题求解的一般步骤。了解程序、算法的概念。了解枚举法、迭代法、排序算法、查找算法、程序设计一般过程。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 程序设计方法44.1 问题求解科学探究的过程：提出问题、发现问题、解决问题解决问题的科学方法： 一般科学方法 专门科学方法目前，计算成为一般科学方法 大量的问题都可以通过计算来解决三大科

2、学思维：理论思维、实验思维、计算思维5计算思维求解问题的过程： 问题抽象 完全超越物理的时空观用符号来表示 自动化 机械地一步一步自动执行，即编写程序1. 抽象 本义：从众多的事物中抽取出共同的、本质性的特征， 而舍弃其非本质的特征 在计算机科学中：简化复杂的现实问题的最佳途径。 形式化 采用严格的数学语言，具有精确的数学语义的方法。 基于数学的方法，不同的形式化方法的数学基础是不同的 有以集合论和递归函数为基础的，有以图论为基础的6 数学建模 通过计算得到的结果来解释实际问题，并接受实际的检验， 来建立数学模型的全过程。 实际事物的一种数学简化，常常是以某种意义上接近实际事 物的抽象形式存在

3、的，但与真实的事物有着本质的区别。 如：龙卷风模型、潮汐模型 形式化和数学建模都是基于数学的方法。2.自动化 抽象是自动化的前提和基础 计算机通过程序实现实现自动化 程序的核心是算法 常见的简单问题，自动化：设计算法和编写程序7【例9.1】猴子吃桃问题。猴子第一天摘了若干个桃子，当即吃了一半，还不解馋，又多吃了一个；第二天，吃剩下的桃子的一半，还不过瘾，又多吃了一个；以后每天都吃前一天剩下的一半多一个，到第10天想再吃时，只剩下一个桃子了。问第一天共摘了多少个桃子？假定用xn表示第n天桃子的数量（1）抽象 采用逆向思维，发现数学的递推公式：89（2）自动化 设计算法和编写程序。 算法设计 自然

4、语言描述算法 置初态：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+1)*2; i = i-1; cout第一天共摘了x个桃子endl; return 0;计算机求解问题的过程：抽象和自动化114.2 程序与算法12 4.1 问题求解 4.2 程序与算法 4.

5、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】下面是某一个学校颁奖大会的程序： 主持人宣布颁奖会开始，介绍出席颁奖会的领导 校长讲话 领导宣布获奖名单 领导颁奖 获奖代表发言 主持人宣布大会结 按一定的顺序安排的工作即操作序列 描述完成某项功能所涉及的对象和动作规则 计算机学科中,程序描述了计算机处理数据、解决问题的过程13什么是程序？ 【例4.2】下面是某一个学校颁奖大会的程序： 主持人宣布颁奖会开

6、始，介绍出席颁奖会的领导 校长讲话 领导宣布获奖名单 领导颁奖 获奖代表发言 主持人宣布大会结 按一定的顺序安排的工作即操作序列 描述完成某项功能所涉及的对象和动作规则 计算机学科中,程序描述了计算机处理数据、解决问题的过程14【例4.3】教师节到了，要对教龄满30年的教职工发荣誉证书， 要求从存放教职工档案的 “d:zg.dat” 文件中， 显示出教龄满30年的教职工的姓名和所在部门。 C语言程序如下： #include stdafx.h #include int main( ) char xm80, char bm80; int jl; FILE *fp; fp=fopen(d:zg.da

7、t,r); while(!feof(fp) fscanf(fp,%s,xm); fscanf(fp,%s,bm); fscanf(fp,%d,&jl); if (jl = 30) cout姓名：xm所在部分：bm30且性别为女？从文件中读入一行truefalse当型循环3 算法的特点有穷性 任意一个算法在执行有穷个计算步骤后必须终止。每一个计算步骤，必须是精确地定义、无二义性可行性 有限多个步骤应该在一个合理的范围内进行输入 一般有0个或多个输入，它们取自某一特定的集合。输出 一般有若干个输出信息，是反映对输入数据加工后的结果。264 算法的分类（1）数值计算算法 用于科学计算 特点是少量的输

8、入、输出，复杂的运算。 例如：计算圆周率，积分（2）非数值计算算法 对数据的管理 特点是大量的输入、输出，简单的算术运算 和大量的逻辑运算。 例如：排序 查找替换 随着计算机技术的发展和应用面的普及，非数值计算算法涉及面更广，研究的任务更重。275 算法的表示自然语言传统流程图伪代码计算机语言28利用求圆周率公式 计算圆周率分析:对通项式：ti= ，i=1，2， ，进行累加，直到某项ti绝对值小于精度即|t|=0.00000001) /当当前项还没有到达精度，继续求和pi=pi+ t; /求和s=-1*s; /为下一项作准备，符号变化/i+; /t=s*1.0/(2*i-1); /下一项值co

9、utsetprecision(8)pi*4endl;只有用计算机语言编写的程序才能被计算机执行必须严格遵循所选择的编程语言的语法规则344.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.枚举法亦称穷举法或试凑法。例：计算机破案 张三在家中遇害，侦查中发现A、B、C、D四人到过现场。A说：“我没有杀人。”B说：“C是凶手。”C说：“杀人者是D”D说：“

10、C在冤枉好人。”侦查员经过判断四人中有三人说的是真话，四人中有且只有一人是凶手，凶手到底是谁？37分析 用0表示不是凶手，1表示凶手，则每个人的取值范围就是0，138算法在每个人的取值范围0，1的所有可能中进行搜索，如果表格的组合条件同时满足，即为凶手。相应的伪代码为：For A=0 To 1 For B=0 TO 1 For C=0 To 1 For D=0 To 1 If(A=0)+(C=1)+(D=1)+(D=0)=3And(A+B+C+D=1) Print A,B,C,D / 输出的值是1的为凶手，要同时满足39总结枚举法基本思想:采用搜索的方法，根据题目的部分条件确定答案的大致搜索范

11、围在此范围内对所有可能的情况逐一验证若某个情况符合题目的条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解。枚举法是一种比较熬时的算法。为提高效率，根据解决问题的情况，尽量减少内循环层数或每层循环次数。40思考题:百元买百鸡问题。假定小鸡每只0.5元,公鸡每只2元，母鸡每只3元。现在有100元钱要求买100只鸡，列出所有可能的购鸡方案。搜索的范围?要满足的条件是什么？请尝试写出伪代码412.迭代法一般来说，迭代法又称递推法，是利用问题本身所具有的某种递推关系求解问题的一种方法。基本思想：从初值出发，归纳出新值与旧值间直到最后值为止存在的关系，从而把一个复杂的计算过程转化

12、为简单过程的多次重复，每次重复都从旧值的基础上递推出新值，并由新值代替旧值。 42高次方程求根求高次方程根： 的近似解，精度为10-5 。 迭代公式为：算法步骤为： 选择方程的近似根作为初值赋值给x1； 将x1的值保存于x0，通过迭代公式求得新近似根x1； 若x1与x0的差绝对值大于指定的精度时，继续执行步骤； 否则x1就是方程的近似解。：初值的选择对计算有什么影响？433.排序常用排序算法选择法冒泡法插入排序合并排序快速排序45(1)选择法将N个数按照从小到大的顺序排序原始数据 8 6 9 3 2 7过程演示算法思想:每次在无序数中找最小（递增）数的下标，然后存放在无序数的第一个位置。For

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

14、根据noswap值判断数据有序否 数据已经有序后,后续的比较可省略4.查找48已知姓名,怎么查找某个学生?已知学号,怎么查找某个学生?1251252高靖遥男交通运输类1251254李一鸣男交通运输类1251259张晓敏女交通运输类1251269施奕辰男交通运输类1251270方尧男交通运输类1251271应一丹女交通运输类1251273王子恒男交通运输类1251278黄彬男交通运输类1251281朱一鸣男交通运输类1251283陈钰女交通运输类1251285王羿童男交通运输类1251298邓能静女交通运输类1251306王寒冰男交通运输类1251314陈彦旭男交通运输类1251328温馨女交通

15、运输类1251329刘建兴男交通运输类1251330彭洋男交通运输类(1)顺序查找 适用于无序序列，按顺序逐一比对。 例：输入一个数key，查找它是否在数列中，如在，输出是第几个数。49(2)二分查找二分法查找只适合于在已排好序的数组中进行。 待查区间的下界low为1，上界high为N。 求待查区间中间元素的下标 mid = (low+high)/2，x和amid比较。 若x=amid，则查找完毕，结束程序； 若xamid，low = mid+1； 若xhigh无查找区域，找不到5051思考题利用二分法查找方法，设计人与计算机做猜数游戏。由计算机随机产生一个1，100的任意整数key，让用户猜

16、这个数。利用二分法的思想,该怎样解决?请画出流程图525.程序设计的一般过程53分析问题确定数学模型程序编写、编辑、编译和连接算法设计运行和测试6. 程序设计方法结构化程序设计面向对象程序设计54结构化程序设计思想最早由荷兰科学家E.W.Dijkstra提出任何程序都基于顺序、选择、循环三种基本的控制结构程序具有模块化特征，每个程序模块具有惟一的入口和出口取消GOTO语句结构化程序的结构简单清晰，可读性好，模块化强。55结构化编程主要包括两个方面提倡采用自顶向下、逐步细化的模块化程序设计原则每个模块强调采用单入口单出口的三种基本控制结构（顺序、选择、循环），避免使用GOTO语句56主程序模块2模块3模块1模块11模块112模块31模块32模块111模块311面向对象程序设计80年代初面向对象的程序设计(Object Oriented Programming，简称OOP)用面向对象的方法解决问题，不再将问题分解为过程，而是将问题分解为对象。对象：属性、方法和事件“对象消息”的面向对象的程序设计模式