nbhkdz.com冰点文库

苏教版必修三第1章 算法初步 1.4


1.4
课时目标

算法案例

通过三种算法案例:孙子剩余定理、辗转相除法、利用二分法求方程的近

似解,进一步体会算法的思想,提高逻辑思维能力和算法设计水平.

1. “孙子问题”是求关于 x, y, z 的一次不定方程组_______________________________. 2

.欧几里得辗转相除法求两个正整数 a,b 的最大公约数的步骤是:_____________ ________________________________________________________________________ ________________________________________________________________________. 3.利用“二分法”求方程 f(x)=0 在区间[a,b]上的近似解的步骤为: S1 ____________________________________________________________________; S2 若__________________________________________________________________ ________________________________________________________________________: 若__________________________________________________________________; 若__________________________________________________________________; S3 若__________________________________________________________________ ________________________________________________________________________.

一、填空题 1.对于下列等式:①Int(10.01)=10;②Int(-1)=-1;③Int(-5.2)=-5.其中正确的 有________个. 2.对下列不等式:①Mod(2,3)=3;②Mod(3,2)=2;③Mod(2,3)=1;④Mod(3,2)=1. 成立的有________(写出成立的等式的序号). 3.Int(0.35)=________,Int(-0.01)=________,Int(0)=________. 4.1 037 和 425 的最大公约数是________. 5. 如果 a, b 是整数, 且 a>b>0, r=Mod(a, b), 则 a 与 b 的最大公约数与下面的________ 相等.(填写正确答案的序号) ①r;②b;③b-r;④b 与 r 的最大公约数. 6.已知 a=333,b=24,则使得 a=bq+r(q,r 均为自然数,且 0≤r<b)成立的 q 和 r 的值分别为________. 7.下面的说法: ①若 f(a)f(b)<0(a≠b),则方程 f(x)=0 在区间(a,b)上一定有根; ②若 f(a)f(b)>0(a≠b),则方程 f(x)=0 在区间(a,b)上一定没有根. ③连续不间断的函数 y=f(x),若 f(a)f(b)<0(a≠b),则方程 f(x)=0 在区间(a,b)上只有一 个根. 其中不正确的说法有________个. 8.用二分法求方程 x2-2=0 的近似根(误差不超过 0.001)的一个算法补充完整: S1 令 f(x)=x2-2,因为 f(1)<0,f(2)>0,所以设 x1=1,x2=2; S2 令 m=____________,判断 f(m)是否为 0,若 f(m)=0,则 m 即为所求;若否,则 判断__________的符号; S3 若____________,则 x1←m;否则 x2←m; S4 判断____________<0.001 是否成立,若是,则 x1,x2 之间的任意值均为满足条件 的近似根,若否,________.

二、解答题 9.用辗转相除法求 204 与 85 的最大公约数.

10.设计求被 6 除余 4,被 10 除余 8,被 9 除余 4 的最小正整数的算法,画出流程图, 写出伪代码.

能力提升 11.读入 50 个正整数 a1,a2,?,a50,统计出其中奇数的个数,用伪代码表示解决这 个问题的算法.

1 12.在平面直角坐标系中作出函数 f(x)= 和 g(x)=lg x 的图象,根据图象判断方程 lg x x 1 = 的解的范围,再将用二分法求这个方程的近似解(误差不超过 0.001)的算法用伪代码 x 表示.

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

答案
知识梳理 m=3x+2 ? ? 1.?m=5y+3 ? ?m=7z+2 的正整数解 2.计算出 a÷ b 的余数 r,若 r=0,则 b 即为 a,b 的最大公

约数; 若 r≠0, 则把前面的除数 b 作为新的被除数, 把余数 r 作为新的除数, 继续运算, 1 直到余数为 0,此时的除数即为 a,b 的最大公约数 3.取[a,b]的中点 x0= (a+b),将 2 * 区间一分为二 f(x0)=0,则 x0 就是方程的根;否则判断根 x 在 x0 的左侧还是右侧 f(a)f(x0)>0,则 x*∈(x0,b),以 x0 代替 a f(a)f(x0)<0,则 x*∈(a,x0),以 x0 代替 b |a -b|<c,计算终止,此时 x*≈x0,否则转 S1 作业设计 1.2 解析 ①、②正确,③错误.因为 Int(x)表示的是不超过 x 的最大整数. 2.④ 解析 Mod(a,b)表示 a 除以 b 所得的余数,所以 Mod(2,3)=2,Mod(3,2)=1. 3.0 -1 0 4.17 解析 ∵1 037=425×2+187, 425=187×2+51, 187=51×3+34, 51=34×1+17, 34=17×2, ∴1 037 和 425 的最大公约数是 17. 5.④ 解析 根据辗转相除法的算法思想, 就是将较大的数的最大公约数转化为较小的数的最 大公约数. 6.13,21 解析 用 333 除以 24,商即为 q,余数就是 r. 7.3 ? ?-x+1, x≤0, 解析 ①的反例:f(x)=? ?-x-1, x>0, ? 区间:(-1,1).

②的反例:图象为 区间:(-1,2).



3 3 ③的反例:y=sin x,区间(- π, π). 2 2 x1+x2 8. f(x1)f(m) f(x1)f(m)>0 |x1-x2| 转 S2 2 9.解 S1 204÷ 85=2????34; S2 85÷ 34=2????17; S3 34÷ 17=2????0. 17 是 204 与 85 的最大公约数. 10.解 流程图:

伪代码: n←1 While Mod(n,6)≠4 or Mod(n,10) ≠8 or Mod(n,9)≠4 n←n+1 End While Print n 11.解 k←0 For i From 1 To 50 Read ai If Mod?ai,2?=1 Then k←k+1 End For Print k 12.解 图象为 1 设 h(x)= -lg x. x 1 1 ∵h(2)= -lg 2>0,h(3)= -lg 3<0, 2 3 ∴h(x)=0 在(2,3)内有解. 伪代码为: