高中数学1.4算法案例教学设计苏教版必修3

算法案例(3)教学目标（1）二分法主要是采用了循环结构处理问题要会分析类似的问题；（2）GoTo 语句的认识及其他语句的进一步熟悉；（3）能由流程图分析出期所含有的结构并用为代码表示出相应的算法．教学重点二分法的算法思想和算法表示．教学过程一、问题情境必修1中我们学习了二分法求方程的近似解，大家还能想起二分法的求解步骤吗？二、案例讲解：案例：写出用区间二分法求解方程310x x --=在区间[1,1.5]内的一个近似解（误差不超过0.001）的一个算法．（１）算法设计思想：如图，如果估计出方程()0f x =在某区间[,]a b 内有一个根*x ，就能用二分法搜索求得符合误差限制c 的近似解．（２）算法步骤可以表示为：1S 取[,]a b 的中点02a b x +=，间区间一分为二； 2S 若0()0f x =，则0x 就是方程的根，否则判断根*x 在0x 的左侧还是后侧；若0()()0f a f x >，则*0(,)x x b ∈，以0x 代替a ；若0()()0f a f x <，则*0(,)x a x ∈，以0x 代替b ；3S 若||a b c -<，计算终止，此时*0x x ≈，否则转1S ．（３）流程图：（4）伪代码1：R ea d a ，b ，c 02a b x +←While ||a b c -≥ And 30010x x --≠ If 3(1)a a --⨯300(1)x x --<0 Then0b x ←Else0a x ←End If02a b x +← End WhilePrint 0x伪代码2：10 Read ,,a b c20 0()2a b x +←30 3()1f a a a ←--40 3000()1f x x x ←-- 50 If 0()0f x = Then GoTo 12060 If 0()()0f a f x < Then70 0b x ←80 Else90 0a x ←100 End If110 If ||a b c -≥ Then GoTo 20120 Print 0x二分搜索的过程是一个多次重复的过程，故可以用循环结构来处理（代码1），课本解法是采用GoTo 语句实现的（代码2）。

2０17-2018版高中数学第一章算法初步１.4 算法案例学案苏教版必修3编辑整理:尊敬的读者朋友们:这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对,但是难免会有疏漏的地方,但是任然希望(２017－2０18版高中数学第一章算法初步 1.4 算法案例学案苏教版必修3）的内容能够给您的工作和学习带来便利。

同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。

本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅,最后祝您生活愉快业绩进步，以下为2017-2０１8版高中数学第一章算法初步 1.4 算法案例学案苏教版必修3的全部内容。

1。

４算法案例学习目标 1.理解解决“韩信点兵—孙子问题”的算法思想;2.理解辗转相除法与更相减损术的数学原理；3.能用伪代码实现二分法求方程的近似解．知识点一本节涉及的内置函数就像木工不必自己造锯一样,VＢ也把一些常用基础工具做成内置函数,以备使用者直接调用,下面是本节涉及的内置函数：函数功能例子Ｍod（a,b）得到a除以b的余数Moｄ（9,2)=1Val( ）将字符串转换为数值Ｉnt(x)表示不超过ｘ的最大整数Int(３.9)=３知识点二“韩信点兵一孙子问题”的数学本质思考“三三数之剩二”是什么意思?如何用代数式表示?梳理“韩信点兵-孙子问题”是求关于x,y,z的一次不定方程组_＿＿__________＿__的正整数解．知识点三辗转相除法与更相减损术的算法原理思考我们知道20４=８5×2+34。

为什么204与８５的最大公约数就是85与34的最大公约数？梳理一般地,有2种算法求两个正整数的最大公约数：(１）辗转相除法的运算步骤：第一步，给定___＿＿____＿___＿____．第二步,计算______＿＿＿_＿＿____＿_.第三步,_＿_______＿＿_.第四步，若r=0，则ｍ,n的最大公约数等于_＿＿___；否则,返回____＿__＿_＿.(2)更相减损术的运算步骤：第一步,任意给定两个正整数,判断它们是否都是__＿＿__．若是，用__＿_约简；若不是,执行_＿____＿_.第二步,以________的数减去___＿_＿_＿的数,接着把所得的差与＿＿___＿__的数比较，并以大数减小数,继续这个操作,直到所得的数＿＿____＿_为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.知识点四二分法的实现思考你还能回忆起二分法的作用和原理吗？梳理求方程f（x)=0在区间[a，b］上的近似解的步骤为:S1 取[a,b]的中点ｘ0=错误!(a+b），将区间一分为二.S2 若___＿____,则x０就是方程的根，否则判断根x＊在ｘ0的左侧还是右侧：若＿__＿________,则x*∈(x0，b)，以x0代替ａ;若＿_____＿＿_＿__,则x*∈（a,x0）,以ｘ0代替b。

如何依次检索正整数？ 该循环何时结束？
int(x)表示不超过x的最 大整数，例如int(2.7)=2， Int(2)=2，int(－2，7)＝－ 3.
一个正整数m什么时候满足方程？
如何用自然语言描述该算法？
mod(a，b)表示a除以b的余数.
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.顺序结构 :依次进行多个处理的结构称为 顺序结构.
2.顺序结构的流程图 顺序结构是最简单、最 基本的算法结构，语句与 语句之间，框与框之间是 按从上到下的顺序进行的. 它是由若干个处理步骤组 成的，这是任何一个算法 都离不开的基本结构.
语句A
语句B
选择结构也叫条件结构，是指在算法中通过对条件的 判断，根据条件是否成立而选择不同流向的算法结构．
B
Else
C
End If
当型语句:
A
直到型语句:
A p
Y N
While p
Do
p
N
Y
循环体
End while
循环体
Until p
End Do
伪代码中的:
(5)循环语句
(6)For语句: 当循环的次数已经确定，可用“For”语句表 示．
“For”语句伪代码格式： For I From “初值” To “终值” step “步长” …… End For
S←S+i
i←i＋1
A
N
A
N
i←i+1 i＜10 N 输出S 结束 Y
i>100
Y 输出S 结束

1.4 算法案例1．孙子剩余定理“韩信点兵—孙子问题”的算法最早出现在我国《算经十书》之一的《孙子算经》中．原文是：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二．问物几何？答曰：二十三．”自从《孙子算经》中提出这个“物不知数”问题之后，它便引起了人们很大的兴趣．南宋数学家秦九韶对此加以推广，又发现了一种新的解法，叫“大衍求一术”．这种解法后来传入欧洲，欧洲学者发现此解法和高斯的解法本质上是一致的，但比高斯早了500余年．所以，人们将这种问题的通用解法称为“孙子剩余定理”或“中国剩余定理”．预习交流1孙子剩余定理的实质是什么问题？提示：孙子剩余定理一般解决的是求总数问题，其实质就是利用求余的方法求不定方程(组)的整数解问题．辗转相除法与更相减损术有何区别与联系？提示：它们虽然来源于西、东方古代数学名著，但二者的算理却是相似的，都突出了“辗转”两字．两者的主要区别在于辗转相除法进行的是除法运算，即辗转相除；而更相减损术进行的是减法运算，即辗转相减．它们的步骤虽略有不同，但理论是一致的，都是一个不断地递推过程，两法相比，更相减损术思路更简单，计算更容易．预习交流3(1)下列说法中正确的个数为__________．①辗转相除法也叫欧几里得辗转相除法；②辗转相除法的基本步骤是用较大的数除以较小的数；③求最大公约数的方法，除辗转相除法之外，没有其他方法；④编写辗转相除法的程序时，要用到循环语句．(2)372与684的最大公约数是__________．(3)用辗转相除法求两个正整数a，b(a＞b)的最大公约数时，得到表达式a＝nb＋r(n∈N)，这里r的取值范围是__________．提示：(1)3 (2)12 (3)0≤r＜b一、孙子剩余定理的理解及应用有3个连续的自然数，其中最小的能被15整除，中间的能被17整除，最大的能被19整除，求满足要求的一组3个连续的自然数，画出流程图，并用伪代码表示算法．思路分析：本题其实就是求关于x ，y ，z 的不定方程组⎩⎪⎨⎪⎧m ＝15x ，m ＋1＝17y ，m ＋2＝19z的正整数解．解：流程图如图所示：伪代码如下：1．下列各式中正确的个数是________．①Mod(3,2)＝2；②Mod(3,2)＝1；③Mod(2,3)＝1；④Mod(105,7)＝0；⑤Mod(8,3)＝2. 答案：3解析：Mod(a ，b )的意义是a ÷b 所得的余数． ∵3＝2×1＋1，∴Mod(3,2)＝1. ∵2＝0×3＋2，∴Mod(2,3)＝2. ∵105＝15×7，∴Mod(105,7)＝0.∵8＝3×2＋2，∴Mod(8,3)＝2.∴②④⑤正确．2．已知一个班的学生人数在30至56之间，现按3人一排，多出1人；按5人一排，多出3人；按7人一排，多出1人，则该班级人数为________．答案：43解析：设此班有m 人，问题转化为解关于x ，y ，z 的不定方程组⎩⎪⎨⎪⎧3x ＋1＝m ，5y ＋3＝m ，7z ＋1＝m .又m ∈(30,56)，可得m 的值为43.1．Int(x )表示不超过x 的最大整数．2．解不定方程的思想在算法中有着广泛的应用，特别是求不定方程的整数解，常规解法就是试值的方法．一般情况下，由于试值的次数比较多，工作量较大，此时我们可以编写程序，由计算机代替人工单一重复的计算．二、求两数的最大公约数求两个正整数8 251和6 105的最大公约数．思路分析：解答本题首先明确8 251与6 105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，再根据已有的知识即可求出最大公约数．解：8 251＝6 105×1＋2 146，显然8 251与6 105的最大公约数也必是2 146的约数．同样，6 105与2 146的公约数也必是8 251的约数，所以8 251与6 105的最大公约数也是6 105与2 146的最大公约数．6 105＝2 146×2＋1 8132 146＝1 813×1＋3331 813＝333×5＋148333＝148×2＋37148＝37×4＋0则37为8 251与6 105的最大公约数．1．下列各组关于最大公约数的说法中不正确的序号是________．①16和12的最大公约数是4②78和36的最大公约数是6③85和357的最大公约数是34④105和315的最大公约数是105答案：③解析：85与357的最大公约数为17，而不是34.2．三个数48,120,90的最大公约数是________．答案：6解析：先求出48,120的最大公约数为24，再求出24,90的最大公约数为6,6就是这三个数的最大公约数．3．请用辗转相除法求1 734和816的最大公约数．解：辗转相除法的求解过程如下：第一步，1 734＝2×816＋102；第二步，816＝8×102＋0；因此，102是1 734和816的最大公约数．(1)辗转相除法适合求两个数的最大公约数．利用辗转相除法，直到余数为0时即可求出最大公约数．三个数的最大公约数分别是每个数的约数，因此也是任意两个数的最大公约数的约数．也就是说，三个数的最大公约数是其中任意两个数的最大公约数与第三个数的最大公约数．(2)对于求多个数的最大公约数，也可以用更相减损术．用更相减损术求两个数的最大公约数的步骤是用较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得数相等为止，则这个数(等数)就是所求的最大公约数．三、二分法求方程的近似解已知函数f(x)＝x2－5，画出求方程f(x)＝0在[2,3]上的一个近似解(误差不超过0.001)的流程图，并写出伪代码．思路分析：解答本题可先回忆一下二分法求近似解的步骤，由步骤画出流程图，然后再写出算法的伪代码．解：流程图如图所示：伪代码为：1．下面伪代码是求7的近似值的一个算法．(误差不超过0.001)其中横线处应填__________．答案：|a－b|＜0.001解析：根据循环结构的特点，当满足误差不超过0.001时结束．2．写出用二分法求方程x5－3x＋1＝0在(0,1)上的一个近似解的伪代码，精确到0.001. 解：伪代码为：给定误差c，用二分法求函数f(x)的零点x0的近似值的步骤如下：(1)确定区间[a，b]，验证f(a)f(b)＜0，给定误差值；(2)求区间(a，b)的中点x1；(3)计算f(x1)，若f(x1)＝0，则x1就是函数的零点；若f(a)f(x1)＜0，则令b＝x1(此时零点x0∈(a，x1))；若f(x1)f(b)＜0，则令a＝x1(此时零点x0∈(x1，b)) ；(4)判断，若|a－b|＜c，计算终止，此时，x0≈x1，否则重复步骤(2)～(4)．1．对于“韩信点兵—孙子问题”的方程组解的问题，以下理解正确的是__________．①只有一组正整数解②只有一组小于100的正整数解③可能没有正整数解④可能没有小于100的正整数解答案：②2．Mod(m，a)＝3的含义是__________．答案：m被a除后余33．用二分法求方程log2x＝3－x在区间[a，b]内的一个近似解(误差不超过0.001)时，利用循环语句“Do…End Do”编写伪代码，其循环的终止条件是________．答案：|a－b|＜0.0014．用辗转相除法求480和288的最大公约数时，需要做除法的次数是__________．答案：3解析：用辗转相除法求最大公约数的各步骤结果是(480,288)，(288,192)，(192,96)，此时相除余数为0，共进行了三次除法．5．用辗转相除法逐步列出求98和63的最大公约数的步骤．解：S1 98＝63×1＋35；S2 63＝35×1＋28；S3 35＝28×1＋7；S4 28＝7×4.∴最大公约数为7.11。