《13算法案例》(优秀经典公开课比赛课件).ppt

1、算算 法法 案案 例例(1)学习目标1.会用辗转相除法与更相减损术求两个数的最大公约数(易错易混点)2.会用秦九韶算法求多项式的值(难点)3.会在不同进位制间进行相互转化(重点)1.回顾算法的三种表述：回顾算法的三种表述：自然语言自然语言程序框图程序框图程序语言程序语言（三种逻辑结构）（三种逻辑结构）（五种基本语句）（五种基本语句）2.思考：思考：小学学过的求两个数最大公约数的方法小学学过的求两个数最大公约数的方法 先用两个公有的质因数连续去除，一直先用两个公有的质因数连续去除，一直 除到所得的商是互质数为止，然后把所除到所得的商是互质数为止，然后把所有的除数连乘起来有的除数连乘起来.辗转相除

2、法（欧几里得算法）辗转相除法（欧几里得算法）观察用辗转相除法求观察用辗转相除法求8251和和6105的最的最大公约数的过程大公约数的过程 第一步第一步 用两数中较大的数除以较小的数，用两数中较大的数除以较小的数，求得商和余数求得商和余数8251=61051+2146结论：结论：8251和和6105的公约数就是的公约数就是6105和和2146的公约数，求的公约数，求8251和和6105的最的最大公约数，只要求出大公约数，只要求出6105和和2146的公约的公约数就可以了。数就可以了。第二步第二步 对对6105和和2146重复第一步的做法重复第一步的做法6105=21462+1813同理同理610

3、5和和2146的最的最大公约数也是大公约数也是2146和和1813的最大公约数。的最大公约数。完整的过程完整的过程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0例例2 用辗转相除法求用辗转相除法求225和和135的最大公约数的最大公约数225=1351+90135=901+4590=452显然显然37是是148和和37的最大公的最大公约数，也就是约数，也就是8251和和6105的最大公约数的最大公约数 显然显然45是是90和和45的最大公约数，也就是的最大公约数，也就是225和和13

4、5的最大公约数的最大公约数 思考思考1：从上面的两个例子可以看出计算：从上面的两个例子可以看出计算的规律是什么？的规律是什么？1 1、辗转相除法（欧几里得算法）、辗转相除法（欧几里得算法）（1）算理：所谓辗转相除法，就是对于给定）算理：所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大尽，则这时较小的数就是原来两个数的最大公约数。公约数。辗转相除法是一个

5、反复执行直到余数等辗转相除法是一个反复执行直到余数等于于0停止的步骤，这实际上是一个循环结构。停止的步骤，这实际上是一个循环结构。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m=n q r用程序框图表示出右边的过程用程序框图表示出右边的过程r=m MOD nm=nn=rr=0?是否（2 2）算法步骤）算法步骤第一步：输入两个正整数第一步：输入两个正整数m,n(mn).第二步：计算第二步：计算m除以除以n所得的余数所得的余数r.第三步：第三步：m=n,n=r.第四步：若第四步：若r0

6、,则则m,n的最大公约数等于的最大公约数等于m；否则转到第二步否则转到第二步.第五步：输出最大公约数第五步：输出最大公约数m.（3 3）程序框图）程序框图（4 4）程序）程序INPUT“m,n=“;m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND开始开始输入输入m,n r=m MOD n m=nr=0?是是否否 n=r 输出输出m结束结束九章算术九章算术更相减损术更相减损术 第一步：第一步：任意给定两个正整数；判断他们是任意给定两个正整数；判断他们是否都是偶数。若是，则用否都是偶数。若是，则用2约简；若不是则约简；若不是则执行第二步。执行第二步。第

7、二步：第二步：以较大的数减较小的数，接着把所以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。止，则这个等数就是所求的最大公约数。2、更相减损术、更相减损术（1）算理）算理：所谓更相减损术，就是对于：所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步用较大的数减去较小的数，

8、反复执行此步骤直到差数和较小的数相等，此时相等的骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。两数便为原来两个数的最大公约数。例例3 3 用更相减损术求用更相减损术求9898与与6363的最大公约数的最大公约数解：由于解：由于6363不是偶数，把不是偶数，把9898和和6363以大数减以大数减小数，并辗转相减小数，并辗转相减 989863633535636335352828353528287 728287 7212121217 7212114147 77 7所以，所以，9898和和6363的的最大公约数等于最大公约数等于7 7 用更相减损术求两个正数用更相减损术求两个正数

9、8484与与7272的的最大公约数最大公约数 练习：练习：12（2）算法步骤）算法步骤第一步：输入两个正整数第一步：输入两个正整数a,b(ab);第二步：若第二步：若a不等于不等于b,则执行第三步；否则转则执行第三步；否则转到第五步；到第五步；第三步：把第三步：把a-b的差赋予的差赋予r;第四步：如果第四步：如果br,那么把那么把b赋给赋给a,把把r赋给赋给b;否否则把则把r赋给赋给a，执行第二步；，执行第二步；第五步：输出最大公约数第五步：输出最大公约数b.（3 3）程序框图）程序框图（4 4）程序）程序INPUT “a,b=“;a,bWHILE ab r=a-b IF br THEN a=

10、b b=r ELSE a=r END IFWENDPRINT bEND开始开始输入输入a,bab?是是否否 输出输出b结束结束 b=ra=br=a-brb?a=r否否是是例例4、求、求324、243、135这三个数的最大这三个数的最大公约数。公约数。思路分析：求三个数的最大公约数可以先求出两个思路分析：求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大公约数的最大公约数，第三个数与前两个数的最大公约数的最大公约数即为所求。数的最大公约数即为所求。27比较辗转相除法与更相减损术的区别比较辗转相除法与更相减损术的区别（1 1）都是求最大公约数的方法，计算上辗）都是求最大公约

11、数的方法，计算上辗转相除法以除法为主，更相减损术以减法为转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次少，特别当两个数字大小区别较大时计算次数的区别较明显。数的区别较明显。（2 2）从结果体现形式来看，辗转相除法体）从结果体现形式来看，辗转相除法体现结果是以相除余数为现结果是以相除余数为0 0则得到，而更相减损则得到，而更相减损术则以减数与差相等而得到术则以减数与差相等而得到小结小结算算 法法 案案 例例(2)1、求两个数的最大公约数的两种方法分别是、求两个数的最大公约数的两种方法分别是（

12、）和（）和（）。）。2、两个数、两个数21672，8127的最大公约数是的最大公约数是 （）A、2709 B、2606 C、2703 D、2706案例2、秦九韶算法怎样求多项式怎样求多项式f(x)=xf(x)=x5 5+x+x4 4+x+x3 3+x+x2 2+x+1+x+1当当x=5x=5时的值呢？时的值呢？计算多项式计算多项式()=当当x=5的值的值算法算法1：因为因为()=所以所以(5)=55555=3125625125255=3906算法算法2：(5)=55555=5(5555)=5(5(555 )=5(5(5(5+5+)+)+)+=5(5(5(5(5+)+)+)+)+算法算法1：因为

13、因为()=所以所以(5)=55555=3125625125255=3906算法算法2：(5)=55555=5(5555)=5(5(555 )=5(5(5(5+5+)+)+)+=5(5(5(5(5+)+)+)+)+共做了共做了1+2+3+4=10次乘法运算，次乘法运算，5次加法运算次加法运算共做了共做了4次乘法运算，次乘法运算，5次加法运算。次加法运算。数书九章数书九章秦九韶算法秦九韶算法0111)(axaxaxaxfnnnn设设)(xf是一个是一个n 次的多项式次的多项式对该多项式按下面的方式进行改写：对该多项式按下面的方式进行改写：0111)(axaxaxaxfnnnn01211)(axax

14、axannnn012312)(axaxaxaxannnn0121)(axaxaxaxannn这是怎样的一种改写方式？最后的结果是什么？0121)()(axaxaxaxaxfnnn要求多项式的值，应该先算最内层的一次多项式的要求多项式的值，应该先算最内层的一次多项式的值，即值，即11nnaxav然后，由内到外逐层计算一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即212naxvv323naxvv01axvvnn最后的一最后的一项是什么？项是什么？这种将求一个这种将求一个n次多项式次多项式f(x)的值转化成求的值转化成求n个一次多项式的值的方法，称为个一次多项式的值的方法，称为秦九韶算法

15、秦九韶算法。算法步骤：算法步骤：第一步：输入多项式次数第一步：输入多项式次数n、最高次项、最高次项的系数的系数an和和x的值的值.第二步：将第二步：将v的值初始化为的值初始化为an，将，将i的值的值初始化为初始化为1.第三步：输入第三步：输入i次项的系数次项的系数an-i.第四步：第四步：v=vx+an-i,i=i+1.第五步：判断第五步：判断i是否小于或等于是否小于或等于n，若是，若是，则返回第三步；否则，输出多项式的值则返回第三步；否则，输出多项式的值v。程序框图：程序框图：这是一个在这是一个在秦九韶秦九韶算法中反复执行的算法中反复执行的步骤，因此可用循步骤，因此可用循环结构来实现。环结构

16、来实现。输入输入an-i开始开始输入输入n,an,xi=n?输出输出v结束结束v=vx+an-ii=i+1YNi=1V=an ),(nkaxvvavknkkn2110特点：特点：通过一次式的反复计算，逐步得出通过一次式的反复计算，逐步得出高次多项式的值，对于一个高次多项式的值，对于一个n次多项式，只次多项式，只需做需做n次乘法和次乘法和n次加法即可。次加法即可。例例2 已知一个五次多项式为已知一个五次多项式为8.07.16.25.325)(2345xxxxxxf用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x=5的值。的值。解：解：将多项式变形：将多项式变形：8.0)7.1)6.2)5.

17、3)25()(xxxxxxf按由里到外的顺序，依此计算一次多项式当按由里到外的顺序，依此计算一次多项式当x=5时的值：时的值：272551v50v5.1385.35272v9.6896.255.1383v2.34517.159.6894v2.172558.052.34515v所以，当所以，当x=5时，多项式的值等于时，多项式的值等于17255.2你从中看到了怎样的规律？怎么用程序框图来描述呢？程序框图：开始输入f(x)的系数：a0,a1,a2,a3,a4a5输入x0n5?输出v结束v=vx0+a5-nn=n+1YN n=1 v=a5 ),(nkaxvvavknkkn2110这是一个在这是一个在

18、秦九韶算法中秦九韶算法中反复执行的步骤，因此可反复执行的步骤，因此可用循环结构来实现。用循环结构来实现。练习、已知多项式练习、已知多项式f(x)=x5+5x4+10 x3+10 x2+5x+1用用秦九韶算法求这个多项式当秦九韶算法求这个多项式当x=-2时的值时的值的过程中，求的过程中，求41vv与算法案例(3)1 1、什么是进位制？、什么是进位制？2 2、最常见的进位制是什么？除此之外还有哪、最常见的进位制是什么？除此之外还有哪些常见的进位制？请举例说明些常见的进位制？请举例说明进位制是人们为了计数和运算方便而约定的记数系统。进位制是人们为了计数和运算方便而约定的记数系统。进位制是一种记数方式

19、，用有限的进位制是一种记数方式，用有限的数字数字在不同的位在不同的位置表示不同的数值。可使用数字符号的个数称为基置表示不同的数值。可使用数字符号的个数称为基数，基数为数，基数为n n，即可称，即可称n n进位制，简称进位制，简称n n进制。进制。半斤半斤=八两八两 我们常见的数字都是十进制的,比如一般的数值计算，但是并不是生活中的每一种数字都是十进制的.古人有半斤八两之说，就是十六进制与十进制的转换.比如时间和角度的单位用六十进位制,计算“一打”数值时是12进制的。电子计算机用的是二进制 3 3、我们了解十进制吗？所谓的十进制，它是如何构成的？、我们了解十进制吗？所谓的十进制，它是如何构成的？

20、十进制由两个部分构成十进制由两个部分构成例如：例如：3721其它进位制的数又是如何的呢？其它进位制的数又是如何的呢？第一、它有第一、它有0 09 9十个数字；十个数字；第二、它有第二、它有“数位数位”，即，即从右往左从右往左为个位、为个位、十位、百位、千位等等。十位、百位、千位等等。(用用10个数字来记数，称基数为个数字来记数，称基数为10)01231011021071037213表示有：表示有：1个个1，2个十，个十，7个百即个百即7个个10的平的平方，方，3个千即个千即3个个10的立方的立方十进制：十进制：“满十进一满十进一”二、二、二进制二进制二进制是用二进制是用0 0、1 1两个数字来

21、描述的如两个数字来描述的如1100111001二进制的表示方法二进制的表示方法区分的写法：区分的写法：1100111001（2 2）或者或者(11001)(11001)2 201234(2)212020212111001八进制呢？八进制呢？如如73427342(8)(8)k k进制呢？进制呢？a an na an-1n-1a an-2n-2a a1(k)1(k)？三、二进制与十进制的转换三、二进制与十进制的转换1 1、二进制数转化为十进制数、二进制数转化为十进制数例例1 1 将二进制数将二进制数110011110011(2)(2)化成十进制数化成十进制数解：解：根据进位制的定义可知根据进位制的

22、定义可知012345)2(21212020212111001112116132151所以，所以，110011110011（2 2）=51=51将下面的二进制数化为十进制数？将下面的二进制数化为十进制数？（1）11（2）110练习练习注意：注意：1.1.最后一步商为最后一步商为0 0，2.2.将上式各步所得的余数将上式各步所得的余数从下到上排列从下到上排列，得到：，得到：89=101100189=1011001（2 2）2 2、十进制转换为二进制、十进制转换为二进制例例2 2 把把8989化为二进制数化为二进制数5 52 22 22 21 12 20 01 10 0余数余数11112222444

23、489892 22 22 22 20 01 11 10 01 1练习练习将下面的十进制数化为二进制数？将下面的十进制数化为二进制数？（1 1）1010（2 2）2020例例3 3 把把8989化为五进制数化为五进制数3 3、十进制转换为其它进制、十进制转换为其它进制解：解：根据根据除除k k取余法取余法以以5 5作为除数，相应的除法算式为：作为除数，相应的除法算式为：所以，所以，89=32489=324（5 5）89895 517175 53 35 50 04 42 23 3余数余数练习：练习：完成下列进位制之间的转化：完成下列进位制之间的转化：（1）10231（4）=（10）；（2）235（7）=（10）；（3）137（10）=（6）；（4）1231（5）=（7）；（5）213（4）=（3）；（6）1010111（2）=（4）。1进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基数为k，即可称k进位制，简称k进制。k进制需要使用k个数字；2十进制与二进制之间转换的方法；先把这个k进制数写成用各位上的数字与k的幂的乘积之和的形式，再按照十进制数的运算规则计算出结果。小结小结 3十进制数转化为k进制数的方法：（除除k取余法取余法）用k连续去除该十进制数或所得的商，直到商为零为止，然后把每次所得的余数倒着排成一个数，就是相应的k进制数。