网校教育资源平台

2017_2018版高中数学第一章算法初步1.4算法案例学案苏教版必修3

评价文档:
文档评论: 0

相关文档推荐

2017_2018学年高中数学第3章概率3.2古典概型教学案苏教版必修3
免费
2017_2018学年高中数学第2章统计2.4线性回归方程教学案苏教版必修3
免费
2017_2018学年高中数学第1章算法初步1.3基本算法语句1.3.3条件语句教学案苏教版必修3
免费
2017_2018学年高中数学复习课一算法初步教学案苏教版必修3
免费
2017_2018学年高中数学第1章算法初步1.4算法案例教学案苏教版必修3
免费
2017_2018学年高中数学第2章统计2.1抽样方法2.1.1简单随机抽样教学案苏教版必修3
免费
2017_2018学年高中数学第2章统计2.2总体分布的估计2.2.1_2.2.2频率分布表频率分布直方图与折线图教学案苏教版必修3
免费
2017_2018学年高中数学第3章概率3.4互斥事件教学案苏教版必修3
免费
2017_2018学年高中数学第1章算法初步1.2流程图1.2.2选择结构教学案苏教版必修3
免费
2017_2018学年高中数学第1章算法初步1.1算法的含义教学案苏教版必修3
免费
2017_2018学年高中数学第1章算法初步1.3基本算法语句1.3.4循环语句教学案苏教版必修3
免费
2017_2018学年高中数学复习课二统计教学案苏教版必修3
免费
2017_2018学年高中数学第2章统计2.1抽样方法2.1.22.1.3系统抽样分层抽样教学案苏教版必修3
免费
2017_2018学年高中数学第3章概率3.3几何概型教学案苏教版必修3
免费
2017_2018学年高中数学第2章统计2.2总体分布的估计2.2.3茎叶图教学案苏教版必修3
免费
2017_2018学年高中数学第2章统计2.3总体特征数的估计2.3.2方差与标准差教学案苏教版必修3
免费
2017_2018学年高中数学第3章概率3.1随机事件及其概率3.1.1_3.1.2随机现象随机事件的概率教学案苏教版必修3
免费
2017_2018学年高中数学第1章算法初步1.2流程图1.2.1顺序结构教学案苏教版必修3
免费
2017_2018学年高中数学复习课三概率教学案苏教版必修3
免费
2017_2018学年高中数学第2章统计2.3总体特征数的估计2.3.1平均数及其估计教学案苏教版必修3
免费

高中数学审核员

中国现代教育网
分享到:
0积分 下载
                  中国现代教育网     www.30edu.com  全国最大教师交流平台

                               1.4 算法案例

学习目标     1.理解解决“韩信点兵—孙子问题”的算法思想;2.理解辗转相除法与更相减
损术的数学原理;3.能用伪代码实现二分法求方程的近似解.


知识点一 本节涉及的内置函数
就像木工不必自己造锯一样,VB            也把一些常用基础工具做成内置函数,以备使用者直接调
用,下面是本节涉及的内置函数:
               函数                  功能                    例子
             Mod(a,b)       得到   a 除以  b 的余数         Mod(9,2)=1

              Val( )        将字符串转换为数值
              Int(x)      表示不超过      x 的最大整数         Int(3.9)=3

知识点二 “韩信点兵一孙子问题”的数学本质
思考 “三三数之剩二”是什么意思?如何用代数式表示?


  
梳理 “韩信点兵—孙子问题”是求关于                 x,y,z   的一次不定方程组________________的正
整数解.
知识点三 辗转相除法与更相减损术的算法原理
思考 我们知道       204=85×2+34.为什么      204 与 85 的最大公约数就是       85 与 34 的最大公约
数?


 
梳理 一般地,有        2 种算法求两个正整数的最大公约数:
(1)辗转相除法的运算步骤:
第一步,给定__________________.
第二步,计算__________________.
第三步,____________.
第四步,若     r=0,则   m,n  的最大公约数等于______;
否则,返回__________.
(2)更相减损术的运算步骤:
第一步,任意给定两个正整数,判断它们是否都是______.若是,用____约简;若不是,执
                  中国现代教育网     www.30edu.com  全国最大教师交流平台

行________.
第二步,以________的数减去________的数,接着把所得的差与________的数比较,并以大
数减小数,继续这个操作,直到所得的数________为止,则这个数(等数)或这个数与约简的
数的乘积就是所求的最大公约数.
知识点四 二分法的实现

思考 你还能回忆起二分法的作用和原理吗?


 
梳理 求方程      f(x)=0 在区间[a,b]上的近似解的步骤为:
                     1

S1 取[a,b]的中点      x0=2(a+b),将区间一分为二.

                                            *
S2 若________,则    x0 就是方程的根,否则判断根          x 在  x0 的左侧还是右侧:

                   *
若____________,则   x ∈(x0,b),以   x0 代替 a;

                   *
若____________,则   x ∈(a,x0),以   x0 代替 b.
S3 若|a-b|b)的最大公约数的
一个算法吗?并画出流程图,编写伪代码.


 
反思与感悟 利用辗转相除法求给定的两个数的最大公约数,即利用带余除法,用数对中较
大的数除以较小的数,若余数不为零,则将余数和较小的数构成新的数对,再利用带余除法,
直到大数被小数除尽,则这时的较小数就是原来两个数的最大公约数.
跟踪训练    2 用辗转相除法和更相减损术求              261 和 319 的最大公约数.


 
类型三 求方程       f(x)=0 近似解的算法
例 3 画出用区间二分法求方程            x3-x-1=0   在区间[1,1.5]上的一个近似解(误差不超过
0.001)的一个算法流程图并编写伪代码.


 
反思与感悟 在此算法中用到了条件语句和循环语句,所以用“Do”是因为要执行再判断是
否满足条件,因为不知循环次数,所以也不宜用“For”语句.
跟踪训练    3 改造例    3 中伪代码,用来求        f(x)=ln  x+2x-1  在区间[a,b]上的一个近似解
(误差不超过     c).


 


1.m 是一正整数,对两个正整数            a,b,若   a-b  是 m 的倍数,则称模       m 同余,用符号
a≡b(Modm)表示.则     a≡5(Mod27)中,a   的取值最小为________.
2.用更相减损术求        36 与 134 的最大公约数,第一步应为__________________________.
3.求方程    x=5y+3(其中    y 为自然数)的所有小于         100 的 x 的正整数解,用伪代码表示.
                  中国现代教育网     www.30edu.com  全国最大教师交流平台


 
4.求两个正数      8 251 和 6 105 的最大公约数.


 


1.求两个正整数的最大公约数时,用辗转相除法进行设计的关键是:将“辗转”的过程用
循环语句表示.
为了避免求循环次数(对两个具体的正整数,循环次数可以求出,但会使程序更为复杂),最
好使用“While”语句.
2.用二分法求方程近似解,必须先判断方程在给定区间上是否有解.
3.二分法的过程是一个多次重复的过程,故可用循环结构处理.
4.二分法过程中需要对中点(端点)处函数值的符号进行判定,故实现算法需用选择结构,
即用条件语句进行分支选择.
                  中国现代教育网     www.30edu.com  全国最大教师交流平台


                                   答案精析

问题导学
知识点二
思考 “三三数之剩二”意思是一堆东西,三个三个地分组,余二个.
设这堆东西数目为        m,则  m=3x+2,其中     x 指组数.

梳理 Error!
知识点三
思考 设    204 与 85 的最大公约数为      a,则   a 能整除  204,故能整除      85×2+34.又因为     a 也
是 85 的约数,故     a 能整除   85×2,所以    a 必能整除   34,即   a 是 34 的约数,从而是      85 与
34 的最大公约数,显然,204         与 85 的公约数问题转化成了          85 与 34 的公约数问题,问题难
度降低了.
梳理 (1)两个正整数        m,n(m>n)
m 除以  n 所得的余数    r m←n,n←r
m 第二步
(2)偶数 2 第二步 较大 较小
较小 相等
知识点四
思考 二分法是用来求方程近似解的,其原理是先确定一个解所在的大致区间,然后借助零
点存在定理,不断缩小这个区间.

梳理 f(x0)=0 f(a)f(x0)>0

             *
f(a)f(x0)<0 x ≈x0 S1
题型探究
例 1 解 流程图为


伪代码为
                  中国现代教育网     www.30edu.com  全国最大教师交流平台

m←2
While Mod(m,3)≠2 or
  Mod(m,5)≠3 or
  Mod(m,7)≠2
 m←m+1

End While
Print m

跟踪训练    1 解 算法的伪代码如下:

m←2
While Mod(m,5)≠2 or
  Mod(m,7)≠3 or
  Mod(m,9)≠4
 m←m+1

End While
Print m

例 2 解 算法如下:
S1 输入两个正整数        a,b;
S2 若  Mod(a,b)≠0,那么转      S3,否则转    S6;
S3 r←Mod(a,b);
S4 a←b;
S5 b←r,转    S2;
S6 输出   b.
流程图如图:
                  中国现代教育网     www.30edu.com  全国最大教师交流平台

伪代码如下:
Read a,b
While      Moda,

b≠0
 r←Moda,b

 a←b
 b←r
End While
Print b

跟踪训练    2 解 辗转相除法:
319÷261=1(余   58),
261÷58=4(余   29),
58÷29=2(余   0),
所以  319 与 261 的最大公约数为      29.
更相减损术:
319-261=58,
261-58=203,
203-58=145,
145-58=87,
87-58=29,
58-29=29,
29-29=0,
所以  319 与 261 的最大公约数是      29.
例 3 解 流程图如图:
                  中国现代教育网     www.30edu.com  全国最大教师交流平台


伪代码如图:

a←1
b←1.5
c←0.001
Do
      (a  b)
 x0←
        2
fa←a3-a-1

            3
 fx0←    x0 -x0-1

 If   fx0=0      Then 
Exit Do

 If     fafx0<0 
Then

   b←x0
 Else

    a←x0
 End If
Until |a-b|
	
0积分下载