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)辗转相除法的运算步骤： 第一步，给定 . 第二步，计算 . 第三步， . 第四步，
3、若r0，则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|0 f(a)f(x0)b)的最大公约数的一个算法吗？并画出流程图，编写伪代码.,类型二 辗转相除法的现代实现,解答,算法如下： S1 输入两个正整数a，b； S2 若Mod(a，b)0，那么转S3，否则转S6； S3 rMod(a，b)； S4 ab； S5 br，转S2； S6 输出b. 流
5、程图如图：,伪代码如下：,利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数.,反思与感悟,跟踪训练2 用辗转相除法和更相减损术求261和319的最大公约数.,解答,辗转相除法： 3192611(余58)， 261584(余29)， 58292(余0)， 所以319与261的最大公约数为29. 更相减损术： 31926158， 26158203， 20358145，,1455887， 875829， 582929， 29290， 所以3
6、19与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是一正整数，对两个正整数a，b，若ab是m的倍数，则称模m同余，用符号
7、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.求两个正整数的最大公约数时，用辗转相除法进行设计的关键是：将“辗转”的过程用循环语句表示. 为了避免求循环次数(对两个具体的正整数，循环次数可以求出，但会使程序更为复杂)，最好使用“While”语句. 2.用二分法求方程近似解，必须先判断方程在给定区间上是否有解. 3.二分法的过程是一个多次重复的过程，故可用循环结构处理. 4.二分法过程中需要对中点(端点)处函数值的符号进行判定，故实现算法需用选择结构，即用条件语句进行分支选择.,本课结束,