当前位置:首页 >> 数学 >> §1

§1


第二章

算法初步

§1 算法的基本思想

复习
1.算法的含义
通过一系列步骤解决一个问题的方法就称为一个算法.

2.算法的要求
算法不同于求解一个具体问题的方法,是这种方法的 高度概括。一个好的算法有如下要求: ①写出的算法,必须能解决一类问题(如求两个数的最大

公 因数),并且能重复使用。 ②算法过程要能一步一步执行,每一步执行的操作,必须确 切,不能含混不清,而且在有限步能得出结果。

③算法要简洁,要清晰可读,不能弄搞繁杂,以以致于易程 序化。

3.算法的特征
(1)有穷性,算法可以在有穷步内执行完; (2)确定性,算法的每一步应该是确定的并能被有效地执行的确定 结果; (3)顺序性,算法从初始步骤开始,前一步是后一步的前提; (4)不唯一性,求解一个问题的算法不是唯一的,可以有不同的算 法; (5)普遍性,很多问题都可以设计合理的算法去解决。

例4 “韩信点兵”问题.韩信是汉高祖刘邦手下的大将,他英勇善战,
智谋超群,为建立汉朝立下了汗马功劳.据说他在点兵的时候,为了 保住军事机密,不让敌人知道自己部队的实力,采用下述点兵的方 法:先令士兵从1~3报数,结果最后一个士兵报2;再令士兵从1~5 报数,结果最后一个士兵报3;又令士兵从1~7报数,结果最后一个 士兵报4.这样,韩信很快就算出了自己部队的总人数.请设计一个算 法,求出士兵至少有多少人? 分析:从报数情况分析,总人数除以3余2;总人数除以5余3;总人数 除以7余4.算法的第一步是将所有的除以3余2的正整数找出来,按从小 到大排成一列.第二步是从第一步的数列中找出除以5余3的一列数,按 从小到大排成一列.最后在满足前两个条件的第二步数列中再找出除以 7余4的一列数,这列数中最小的数,即为我们所求的数.

解:具体算法步骤如下: (1)首先确定最小的满足除以3余2的正整数:2. (2)依次加3就得到所有除以3余2的正整数:2,5,8, 11,14,17,20,23,26,29,32,35,38,41,44,47, 50,53,56??

(3)在上列数中确定最小的满足除以5余3的正整数:8.
(4)然后依次加上15,得到8,23,38,53??,显然这 些数既满足除以3余2,又满足除以5余3.

(5)在第4步得到的一列数中,找出满足除以7余4的最小 数:53.这就是我们要求的数.

例5 思考以下问题的算法:
一位商人有9枚银元,其中有1枚略轻的是假银元。你 能用天平(不用砝码)将假银元找出来吗?

解:

1.把银元分成3组,每组3枚。 2.先将两组分别放在天平的两边。如果天 平不平衡,那边假银元就放在轻的那一组; 如果天平左右平衡,则假银元就在末称的 第3组里。 3.取出含假银元的那一组,从中任取两枚 放在天平的两边。如果左右不平衡,则轻 的那一边就是假银元;如果天平两边平衡 ,则末剩的那一枚就是假银元。

例6 在函数的应用部分,我们学习了用二分法求方程f(x)=0 分析: 的近似解.如图所示 y 二分法的基本思想是:将方程的有 解区间分为两个小区间,然后判断

解在哪个小区间;继续把有解的区
间一分为二进行判断,如此周而复 始,直到求出满足精度要求的近似 O

a
x* b x

解.

其算法步骤如下

5.判断新的有解区间长度是否大于精确度: (1)如果新的有解区间长度大于精确度,则在新的有解区间

的基础上重复上述步骤;
(2)如果新的有解区间长度小于或等于精确度,则这个有解 区间中的任意一个数均为方程的满足精度的近似解.

3.计算f(0.5)=-0.625;

6.计算f(0.75)=-0.015625;

9.计算f(0.875)=0.435 546 875; 10.由于f(0.75)f(0.875)<0,可得新的有解区间 [0.75,0.875],0.875-0.75=0.125>0.1;

12.计算f(0.8125)=0.196533203125; 13.

所以,区间[0.75,0.8125]中的任一数值,都可以
作为方程的近似解.

简化写法: 第一步:令f(x)=x3+x2-1,因为f(0)f(1)<0,所以设x1=0,x2=1.

第三步:若f(x1)f(m)>0,则令x1= m;否则,令x2= m. 第四步:判断|x1-x2|<0.1是否成立?若是,则x1,x2之间的中 间值为满足条件的近似解;若否,则返回第二步.

说明: 1算法实际上就是解决某一类问题的步骤和方法,在解 决问题时形成的规律性的东西,按照算法描述的规则 与步骤,一步一步地去做,最终便能解决问题。 2算法的基本思想就是我们分析问题时的想法。由于想 法不同思考的角度不同,着手点不一样,同一问题存在 不同的算法,算法有优劣之分。 3从熟悉的问题出发,体会算法的程序化思想,学会用 自然语言来描述算法

课堂练习
一个大油瓶装8kg油,还有两个空油瓶,一个能装5kg油,另 一个能装3kg油,请设计一个算法,将这8kg油评分成两份。
不妨设8kg的大油瓶为A,5kg和3kg的分别为B,C 1、从A往C 中倒3kg,将C装满,此时A中剩余5kg油 2、将C中的3kg油倒入B瓶 3、从A往C中倒3kg油 4、从C往B中倒2kg,即将B瓶装满 5、将B中的油全部倒入A

6、将C中的油全部倒入B
7、从A往C中倒油,将C瓶全部装满,此时A中油为4kg 8、将C中油全部倒入B,则B中油也为4kg

1、算法:算法是解决某类问题的一系列步骤或程序; 2、算法的基本思想:程序化思想; 3、算法的特征:

有穷性

确定性

顺序性

不唯一性

普遍性

课后作业:P83---练习-1 习题-1


更多相关文档:

§1 原子结构与性质基础知识

§1 一、原子核外电子排布及表示方法 原子结构与性质 李仲林 1.能层、能级及其最多容纳电子数的关系 能层:根据多电子原子的核外电子的能量不同,可以将核外电子...

§1.1.1

郑州高新区石佛中学学案 北师大版七年级数学(下册) 七年级数学上册§1.1.1《同底数幂的乘法》第 1 课时课型:新授课 时间:2 月 17 日主备人:黄国有 审核...

§1.1 归纳推理学案教师

、预习案 1、归纳推理的概念及特点: (1)概念:根据一类事物中 具有的某种属性,推断该类事 物中 都具有这种属性,我们把这种推理方式称为归纳推理。 (2)特点:...

§1 集合练习题

. § 1— 1 如果 a 是集合 A 的元素,就记作 如果 b 不是集合 B 的元素,就记作 用“(1) 0 (4)-2 (7) π 2 ?、 ? ” 填空: N﹡ ( 2) ...

§1、强筋壮骨 孕望完美未来

“棘手” 医药生物技术类 的专利审查意见 优秀文件奖 审查意见引用证 据分析 电学技术领域 优秀文件奖 孙 伟 第—部分 专利代理的职业特色 §1、强筋壮骨 孕望...

《§1.1 信息及其特征》教案设计+罗晓波

§1.1 信息及其特征》教案设计+罗晓波_其它课程_高中教育_教育专区。信息及其特征§1.1 信息及其特征梅河口市实验高中 罗晓波 一、教学目标 1.知识与技能:通过...

§1 极限的重要性质

3 ? x≤2 2<x ≤ 5 5<x 讨论 y = f(g(x) )的连续性,若有间断点并指出类型 §1 一元函数微分学中的基本概念及其联系(1)说明下列事实的几何意义(1...

§1.2.1基本逻辑联结词--且与或(学案)

§1.2.1基本逻辑联结词--且与或(学案)_数学_高中教育_教育专区。基本逻辑联结词--且与或与非 1.2.1 基本逻辑联结词--且与或(学案 002)制作人:李媛 ...

§1.柯西函数方程

§1.柯西函数方程_理学_高等教育_教育专区。§1.柯西函数方程 考虑二元函数方程: f : R ? R f ( x ? y) ? f ( x) ? f ( y) (1) 通常这类函数...

§1电工

§1电工_电力/水利_工程科技_专业资料。电工教程1习题说明: 本习题中,设置了部分错误答案(或无答案) 。请学员 在学习中注意查找! 一 单选题 1、在电路中,电源...
更多相关标签:
§怎么打 | 我的世界§1 | §怎么读 | 192.168.1.1 | 80后夫妻捐1亿 | 1号店 | 迟到1分被拒入场 | 1男39女毕业照 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com