2017_18版高中数学第一章算法初步1.4算法案例课件苏教版必修.pptx

1、第1章算法初步,1.4算法案例,学习目标 1.理解解决“韩信点兵孙子问题”的算法思想； 2.理解辗转相除法与更相减损术的数学原理； 3.能用伪代码实现二分法求方程的近似解.,题型探究,问题导学,内容索引,当堂训练,问题导学,知识点一本节涉及的内置函数,就像木工不必自己造锯一样，VB也把一些常用基础工具做成内置函数，以备使用者直接调用，下面是本节涉及的内置函数：,思考,知识点二“韩信点兵一孙子问题”的数学本质,“三三数之剩二”是什么意思？如何用代数式表示？,“三三数之剩二”意思是一堆东西，三个三个地分组，余二个. 设这堆东西数目为m，则m3x2，其中x指组数.,答案,梳理,“韩信点兵孙子问题”是

2、求关于x，y，z的一次不定方程组_ 的正整数解.,思考,知识点三辗转相除法与更相减损术的算法原理,我们知道20485234.为什么204与85的最大公约数就是85与34的最大公约数？,设204与85的最大公约数为a，则a能整除204，故能整除85234.又因为a也是85的约数，故a能整除852，所以a必能整除34，即a是34的约数，从而是85与34的最大公约数，显然，204与85的公约数问题转化成了85与34的公约数问题，问题难度降低了.,答案,梳理,一般地，有2种算法求两个正整数的最大公约数： (1)辗转相除法的运算步骤： 第一步，给定 . 第二步，计算 . 第三步， . 第四步，若r0，则

3、m，n的最大公约数等于 ； 否则，返回 .,第二步,两个正整数m，n(mn),m除以n所得的余数r,mn，nr,m,(2)更相减损术的运算步骤： 第一步，任意给定两个正整数，判断它们是否都是 .若是，用 约简；若不是，执行 . 第二步，以 的数减去 的数，接着把所得的差与 的数比较，并以大数减小数，继续这个操作，直到所得的数 为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.,相等,偶数,2,第二步,较大,较小,较小,思考,知识点四二分法的实现,你还能回忆起二分法的作用和原理吗？,二分法是用来求方程近似解的，其原理是先确定一个解所在的大致区间，然后借助零点存在定理，不断缩小这

4、个区间.,答案,梳理,求方程f(x)0在区间a，b上的近似解的步骤为： S1取a，b的中点x0 (ab)，将区间一分为二. S2若 ，则x0就是方程的根，否则判断根x*在x0的左侧还是右侧： 若 ，则x*(x0，b)，以x0代替a； 若 ，则x*(a，x0)，以x0代替b. S3若|ab|c，计算终止，此时 ，否则转 .,S1,f(x0)0 f(a)f(x0)0 f(a)f(x0)0,x*x0,题型探究,类型一“韩信点兵孙子问题”,例1韩信是秦末汉初的著名军事家.据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场，刘邦问韩信有什么办法，不要逐个报数，就能知道场上士兵的人数. 韩信先令士兵排成3列纵队

5、进行操练，结果有2人多余；接着他立刻下令将队形改为5列纵队，这一改，又多出3人；随后他又下令改为7列纵队，这一次又剩下2人无法成整列.结果在场的人哈哈大笑，韩信看此情形，立刻报告共有士兵2 333人.众人都愣了，不知韩信用什么办法这么快清点出准确人数的.,这个故事却引出一个著名的数学问题，即闻名世界的“孙子问题”.最早出现在我国算经十书之一的孙子算经中.原文是：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二.问物几何？答曰：二十三.”所以人们将这种问题的通用解法称为“孙子剩余定理”或“中国剩余定理”. 设有物m个，则其本质为由方程组 求m的正整数解. 试为此问题编写流程图和伪代码.

6、,解答,流程图为,伪代码为,此算法的本质是从最小2开始，逐个实验是否满足方程组，对人而言是个笨法，但很适合计算机，以上程序求出的是m的最小值.,反思与感悟,跟踪训练1有一堆围棋子，五个五个地数，最后余下2个；七个七个地数，最后余下3个；九个九个地数，最后余下4个.请用伪代码表示“求出这堆棋子至少有多少个”的一种算法.,算法的伪代码如下：,解答,例2你能根据“欧几里得辗转相除法”设计一种求两个正整数a，b(ab)的最大公约数的一个算法吗？并画出流程图，编写伪代码.,类型二辗转相除法的现代实现,解答,算法如下： S1输入两个正整数a，b； S2若Mod(a，b)0，那么转S3，否则转S6； S3r

7、Mod(a，b)； S4ab； S5br，转S2； S6输出b. 流程图如图：,伪代码如下：,利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数.,反思与感悟,跟踪训练2用辗转相除法和更相减损术求261和319的最大公约数.,解答,辗转相除法： 3192611(余58)， 261584(余29)， 58292(余0)， 所以319与261的最大公约数为29. 更相减损术： 31926158， 26158203， 20358145，,14

8、55887， 875829， 582929， 29290， 所以319与261的最大公约数是29.,类型三求方程 f(x)0近似解的算法,例3画出用区间二分法求方程x3x10在区间1，1.5上的一个近似解(误差不超过0.001)的一个算法流程图并编写伪代码.,解答,流程图如图：,伪代码如图：,在此算法中用到了条件语句和循环语句，所以用“Do”是因为要执行再判断是否满足条件，因为不知循环次数，所以也不宜用“For”语句.,反思与感悟,跟踪训练3改造例3中伪代码，用来求f(x)ln x2x1在区间a，b上的一个近似解(误差不超过c).,解析,伪代码如图：,当堂训练,2,3,4,1,1.m是一正整数

9、，对两个正整数a，b，若ab是m的倍数，则称模m同余，用符号ab(Modm)表示.则a5(Mod27)中，a的取值最小为_.,答案,32,2.用更相减损术求36与134的最大公约数，第一步应为_.,36与134都是偶数， 第一步应为：先除以2，得到18与67.,先除以2，得到18与67,2,3,4,1,答案,解析,3.求方程x5y3(其中y为自然数)的所有小于100的x的正整数解，用伪代码表示.,算法的伪代码如图：,解答,2,3,4,1,4.求两个正数8 251和6 105的最大公约数.,8 2516 10512 146； 6 1052 14621 813； 2 1461 8131333； 1 8133335148； 333148237； 1483740； 则37为8 251与6 105的最大公约数.,解答,2,3,4,1,规律与方法,1.求两个正整数的最大公约数时，用辗转相除法进行设计的关键是：将“辗转”的过程用循环语句表示. 为了避免求循环次数(对两个具体的正整数，循环次数可以求出