1.3 算法案例 第一课时.

Presentation on theme: "1.3 算法案例 第一课时."— Presentation transcript:

1 1.3 算法案例 第一课时

2 2.“求两个正整数的最大公约数”是数学中的一个基础性问题，它有各种解决办法，我们以此为案例，对该问题的算法作一些探究.
问题提出 1.研究一个实际问题的算法，主要从算法步骤、程序框图和编写程序三方面展开.在程序框图中算法的基本逻辑结构有哪几种？在程序设计中基本的算法语句有哪几种？ 2.“求两个正整数的最大公约数”是数学中的一个基础性问题，它有各种解决办法，我们以此为案例，对该问题的算法作一些探究.

3 辗转相除法与 更相减损术

4 思考1:18与30的最大公约数是多少？你是怎样得到的？
知识探究（一）:辗转相除法 思考1:18与30的最大公约数是多少？你是怎样得到的？ 先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数.

5 思考2:对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难
思考2:对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难.注意到8251=6105×1+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？

6 思考3:又6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等
思考3:又6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等.重复上述操作，你能得到8251与6105这两个数的最大公约数吗？ 8251=6105×1+2146， 6105=2146×2+1813， 2146=1813×1+333， 1813=333×5+148， 333=148×2+37， 148=37×4+0.

7 思考4:上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法
思考4:上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？ 第一步，给定两个正整数m，n(m>n). 第二步，计算m除以n所得的余数r. 第三步，m=n，n=r. 第四步，若r=0，则m，n的最大公约数等 于m；否则，返回第二步.

8 思考5:该算法的程序框图如何表示？ 开始 输入m，n 否 求m除以n的余数r m=n n=r r=0？ 是 输出m 结束

9 思考6:该程序框图对应的程序如何表述？ INPUT m，n DO r=m MODn m=n n=r LOOP UNTIL r=0
开始 输入m，n 求m除以n的余数r m=n n=r r=0？ 是 输出m 结束 否 INPUT m，n DO r=m MODn m=n n=r LOOP UNTIL r=0 PRINT m END

10 思考7:如果用当型循环结构构造算法，则用辗转相除法求两个正整数m，n的最大公约数的程序框图和程序分别如何表示？

11 INPUT m，n WHILE n>0 r=m MODn m=n n=r WEND PRINT m END 开始 n=r m=n
求m除以n的余数r n=r WEND 是 n>0？ PRINT m 否 输出m END 结束

12 知识探究（二）:更相减损术 思考1:设两个正整数m>n，若m-n=k，则m与n的最大公约数和n与k的最大公约数相等.反复利用这个原理，可求得98与63的最大公约数为多少？ 98-63=35， 63-35=28， 35-28=7， 28-7=21， 21-7=14， 14-7=7.

13 思考2:上述求两个正整数的最大公约数的方法称为更相减损术
思考2:上述求两个正整数的最大公约数的方法称为更相减损术.一般地，用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？ 第一步，给定两个正整数m，n(m>n). 第二步，计算m-n所得的差k. 第三步，比较n与k的大小，其中大者用m表 示，小者用n表示. 第四步，若m=n，则m，n的最大公约数等于 m；否则，返回第二步.

14 思考3:该算法的程序框图如何表示？ 开始 输入m，n 否 m≠n？ 是 k=m-n m=k 输出m n>k？ 是 结束 m=n n=k

15 思考4:该程序框图对应的程序如何表述？ INPUT m，n WHILE m<>n k=m-n IF n>k THEN
开始 输入m，n n>k？ m=n 是 输出m 结束 m≠n？ k=m-n 否 n=k m=k INPUT m，n WHILE m<>n k=m-n IF n>k THEN m=n n=k ELSE m=k END IF WEND PRINT m END

16 “更相减损术”在中国古代数学专著《九章算术》中记述为： 可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之.

17 1 分别用辗转相除法和更相减损术求168与93的最大公约数.
理论迁移 1 分别用辗转相除法和更相减损术求168与93的最大公约数. 辗转相除法：168=93×1+75， =75×1+18， =18×4+3， =3×6.

18 更相减损术:168-93=75， 93-75=18， 75-18=57， 57-18=39， 39-18=21， 21-18=3， 18-3=15， 15-3=12， 12-3=9， 9-3=6， 6-3=3.

19 2 求325，130，270三个数的最大公约数. 因为325=130×2+65，130=65×2，所以325与130的最大公约数是65. 因为270=65×4+10，65=10×6+5，10=5×2，所以65与270最大公约数是5. 故325，130，270三个数的最大公约数是5.

20 小结作业 1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数. 2. 更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.

21 1.3 算法案例 第二课时

22 2.对于求n次多项式的值，在我国古代数学中有一个优秀算法，即秦九韶算法，我们将对这个算法作些了解和探究.
问题提出 1.辗转相除法和更相减损术，是求两个正整数的最大公约数的优秀算法，我们将算法转化为程序后，就可以由计算机来执行运算，实现了古代数学与现代信息技术的完美结合. 2.对于求n次多项式的值，在我国古代数学中有一个优秀算法，即秦九韶算法，我们将对这个算法作些了解和探究.

23 秦九韶算法

24 知识探究(一):秦九韶算法的基本思想 思考1:对于多项式f(x)=x5+x4+x3+x2+x+1，求f(5)的值. 若先计算各项的值，然后再相加，那么一共要做多少次乘法运算和多少次加法运算？ =10次乘法运算， 5次加法运算.

25 思考2:在上述问题中，若先计算x2的值，然后依次计算x2·x，(x2·x)·x，((x2·x)·x)·x的值，这样每次都可以利用上一次计算的结果，再将这些数与x和1相加，那么一共做了多少次乘法运算和多少次加法运算？ 4次乘法运算，5次加法运算.

26 思考3:利用后一种算法求多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值，这个多项式应写成哪种形式？
f(x)=anxn+an-1xn-1+…+a1x+a =(anxn-1+an-1xn-2+…+a2x+a1)x+a0 =((anxn-2+an-1xn-3+…+a2)x+a1)x+a0 =… =(…((anx+an-1)x+an-2)x+…+a1)x+a0.

27 思考4:对于f(x)=(…((anx+an-1)x+ an-2)x+…+a1)x+a0，由内向外逐层计算一次多项式的值，其算法步骤如何？
第一步，计算v1=anx+an-1. 第二步，计算v2=v1x+an-2. 第三步，计算v3=v2x+an-3. … 第n步，计算vn=vn-1x+a0.

28 思考5:上述求多项式 f(x)=anxn+an-1xn-1+…+a1x+a0的值的方法称为秦九韶算法，利用该算法求f(x0)的值，一共需要多少次乘法运算，多少次加法运算？
思考6:在秦九韶算法中，记v0=an，那么第k步的算式是什么？ vk=vk-1x+an-k (k=1，2，…，n)

29 思考1:用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法？其算法步骤如何设计？
知识探究(二):秦九韶算法的程序设计 思考1:用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法？其算法步骤如何设计？ 第一步，输入多项式的次数n，最高次 项的系数an和x的值. 第二步，令v=an，i=n-1. 第三步，输入i次项的系数ai. 第四步，v=vx+ai，i=i-1. 第五步，判断i≥0是否成立.若是，则返回第 二步；否则，输出多项式的值v.

30 思考2:该算法的程序框图如何表示？ 开始 输入n，an，x的值 v=an i=n-1 i=i-1 v=vx+ai 输入ai 是 i≥0？ 否
结束

31 思考3:该程序框图对应的程序如何表述？ INPUT “n=”；n INPUT “an=”；a INPUT “x=”；x v=a i=n-1
开始 输入n，an，x的值 v=an v=vx+ai 输入ai i≥0？ i=n-1 i=i-1 结束 是 输出v 否 INPUT “n=”；n INPUT “an=”；a INPUT “x=”；x v=a i=n-1 WHILE i>=0 INPUT “ai=”；b v=v*x+b i=i-1 WEND PRINT y END

32 1 已知一个5次多项式为 用秦九韶算法求f(5)的值.
理论迁移 1 已知一个5次多项式为 用秦九韶算法求f(5)的值. f(x)=((((5x+2)x+3.5)x-2.6)x+1.7)x-0.8. v1=5×5+2=27； v2=27×5+3.5=138.5； v3=138.5×5-2.6=689.9； v4=689.9×5+1.7=3451.2； v5=3451.2×5-0.8= 所以f(5)= =

33 2 阅读下列程序，说明它解决的实际问题是什么？ INPUT “x=”；a n=0 y=0 WHLE n<5 y=y+(n+1)*a∧n
2 阅读下列程序，说明它解决的实际问题是什么？ INPUT “x=”；a n=0 y=0 WHLE n<5 y=y+(n+1)*a∧n n=n+1 WEND PRINT y END 求多项式 在x=a时的值.

34 小结作业 评价一个算法好坏的一个重要标志是运算的次数，如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理论算法.在多项式求值的各种算法中，秦九韶算法是一个优秀算法.

35 1.3 算法案例 第三课时

36 2.人们为了计数和运算方便，约定了各种进位制，这些进位制是什么概念，它们与十进制之间是怎样转化的？对此，我们从理论上作些了解和研究.
问题提出 1.辗转相除法和更相减损术，是求两个正整数的最大公约数的算法，秦九韶算法是求多项式的值的算法，将这些算法转化为程序，就可以由计算机来完成相关运算. 2.人们为了计数和运算方便，约定了各种进位制，这些进位制是什么概念，它们与十进制之间是怎样转化的？对此，我们从理论上作些了解和研究.

37 k进制化十进制

38 知识探究(一):进位制的概念 思考1:进位制是为了计数和运算方便而约定的记数系统，如逢十进一，就是十进制；每七天为一周，就是七进制；每十二个月为一年，就是十二进制，每六十秒为一分钟，每六十分钟为一个小时，就是六十进制；等等.一般地，“满k进一”就是k进制，其中k称为k进制的基数.那么k是一个什么范围内的数？

39 思考2:十进制使用0～9十个数字，那么二进制、五进制、七进制分别使用哪些数字？
思考3:在十进制中10表示十，在二进制中10表示2.一般地，若k是一个大于1的整数，则以k为基数的k进制数可以表示为一串数字连写在一起的形式： anan-1…a1a0(k). 其中各个数位上的数字an，an-1，…，a1，a0的取值范围如何？

40 思考4:十进制数4528表示的数可以写成4×103+5×102+2×101+8×100，依此类比，二进制数110011（2）,八进制数 7342（8）分别可以写成什么式子？
110011（2）=1×25+1×24+0×23+0×22+1×21+1×20 7342（8）=7×83+3×82+4×81+2×80.

41 思考5:一般地，如何将k进制数 anan-1…a1a0(k)写成各数位上的数字与基数k的幂的乘积之和的形式？
思考6:在二进制中，0+0，0+1，1+0，1+1的值分别是多少？

42 思考1:二进制数110011（2）化为十进制数是什么数？
知识探究(二):k进制化十进制的算法 思考1:二进制数110011（2）化为十进制数是什么数？ 110011（2）=1×25+1×24+0×23+0×22+1×21+1×20 = =51. 思考2:二进制数右数第i位数字ai化为十进制数是什么数？

43 第四步，判断i>n 是否成立.若是，则输 出b的值；否则，返回第三步.
第一步，输入a和n的值. 第二步，令b=0，i=1. 第三步， ，i=i+1. 第四步，判断i>n 是否成立.若是，则输 出b的值；否则，返回第三步.

44 思考4:按照上述思路，把k进制数 化为十进制数b的算法步骤如何设计？
第一步，输入a，k和n的值. 第二步，令b=0，i=1. 第三步， ，i=i+1. 第四步，判断i>n 是否成立.若是，则 输出b的值；否则，返回第三步.

45 思考5:上述把k进制数 化为十进制数b的算法的程序框图如何表示？
开始 思考5:上述把k进制数 化为十进制数b的算法的程序框图如何表示？ 输入a，k，n b=0 i=1 否 把a的右数第i位数字赋给t b=b+t·ki-1 i=i+1 i>n? 是 输出b 结束

46 INPUT a，k，n b=0 i=1 t=a MOD10 DO b=b+t*k∧（i-1） a=a/10 t=a MOD10 i=i+1
思考6:该程序框图对应的程序如何表述？ 开始 输入a，k，n b=0 i=1 把a的右数第i位数字赋给t b=b+t·ki-1 i=i+1 i>n? 结束 是 输出b 否 INPUT a，k，n b=0 i=1 t=a MOD10 DO b=b+t*k∧（i-1） a=a/10 t=a MOD10 i=i+1 LOOP UNTIL i>n PRINT b END

47 例1 将下列各进制数化为十进制数. （1）10303（4） ； （2）1234（5）.
理论迁移 例1 将下列各进制数化为十进制数. （1）10303（4） ； （2）1234（5）. 10303（4）=1×44+3×42+3×40=307. 1234（5）=1×53+2×52+3×51+4×50=194.

48 例2 已知10b1（2）=a02（3）,求数字a，b的值. 10b1（2）=1×23+b×2+1=2b+9. a02（3）=a×32+2=9a+2. 所以2b+9=9a+2，即9a-2b=7. 故a=1，b=1.

49 1. k进制数使用0～（k-1）共k个数字，但左侧第一个数位上的数字（首位数字）不为0.
小结作业 1. k进制数使用0～（k-1）共k个数字，但左侧第一个数位上的数字（首位数字）不为0. 2.用 表示k进制数，其中k称为基数，十进制数一般不标注基数. 3. 把k进制数化为十进制数的一般算式是：

50 1.3 算法案例 第四课时

51 1.“满几进一”就是几进制，k进制使用哪几个数字，k进制数化为十进制数的一般算式是什么？
问题提出 1.“满几进一”就是几进制，k进制使用哪几个数字，k进制数化为十进制数的一般算式是什么？

52 2. 利用k进制数化十进制数的一般算式，可以构造算法，设计程序，通过计算机就能把任何一个k进制数化为十进制数
2.利用k进制数化十进制数的一般算式，可以构造算法，设计程序，通过计算机就能把任何一个k进制数化为十进制数.在实际应用中，我们还需要把任意一个十进制数化为k进制数的算法，对此，我们作些理论上的探讨.

53 十进制化k进制

54 思考1:二进制数101101（2）化为十进制数是什么数？十进制数89化为二进制数是什么数？
知识探究(一):除k取余法 思考1:二进制数101101（2）化为十进制数是什么数？十进制数89化为二进制数是什么数？ 101101（2）= =45. 89=2×（2×（2×（2×（2×2+1）+1）+0）+0）+1 =1×26+0×25+1×24+1×23+0×22+0×21+1×20= （2）.

55 思考2:上述化十进制数为二进制数的算法叫做除2取余法，转化过程有些复杂，观察下面的算式你有什么发现吗？
1 5 11 22 44 89 余数

56 思考3:上述方法也可以推广为把十进制数化为k进制数的算法，称为除k取余法，那么十进制数191化为五进制数是什么数？
5 1 7 38 191 3 2 余数 191=1231（5）

57 思考4:若十进制数 a除以2所得的商是q0，余数是r0， 即a=2·q0+ r0；
q0除以2所得的商是q1，余数是r1， 即q0=2·q1+ r1； …… qn-1除以2所得的商是0，余数是rn， 即qn-1= rn， 那么十进制数a化为二进制数是什么数？ a=rnrn-1…r1r0(2)

58 思考1:根据上面的分析，将十进制数a化为二进制数的算法步骤如何设计？
知识探究(二):十进制化k进制的算法 思考1:根据上面的分析，将十进制数a化为二进制数的算法步骤如何设计？ 第一步，输入十进制数a的值. 第二步，求出a除以2所得的商q，余数r. 第三步，把所得的余数依次从右到左排列. 第四步，若q≠0，则a=q，返回第二步； 否则，输出全部余数r排列得到 的二进制数.

59 思考2:利用除k取余法，将十进制数a化为k进制数的算法步骤如何设计？
第二步，求出a除以k所得的商q，余数r. 第三步，把所得的余数依次从右到左排 列. 第四步，若q≠0，则a=q，返回第二步； 否则，输出全部余数r排列得到 的k进制数.

60 思考3:将除k取余法的算法步骤用程序框图如何表示？
开始 输入a，k 否 求a除以k的商q 求a除以k的余数r 把所得的余数依次从右到左排列 a=q q=0？ 输出全部余数r排 列得到的k进制数 是 结束

61 INPUT a，k b=0 i=0 DO q=a/k r=a MOD k b=b+r*10∧i i=i+1 a=q
思考4:该程序框图对应的程序如何表述？ INPUT a，k 开始 输入a，k 求a除以k的商q 求a除以k的余数r 把所得的余数依次从右到左排列 a=q q=0？ 结束 输出全部余数r排 列得到的k进制数 是 否 b=0 i=0 DO q=a/k r=a MOD k b=b+r*10∧i i=i+1 a=q LOOP UNTIL q=0 PRINT b END

62 例1 将十进制数458分别转化为四进制数和六进制数.
理论迁移 例1 将十进制数458分别转化为四进制数和六进制数. 4 1 7 28 114 458 2 3 余数 6 2 12 76 458 4 余数 458=13022（4）=2042（6）

63 例2 将五进制数3241（5）转化为七进制数. 30241（5）=3×54+2×52+4×5+1=1946.
7 5 39 278 1946 4 余数 30241（5）=5450（7）

64 1.利用除k取余法，可以把任何一个十进制数化为k进制数，并且操作简单、实用.
小结作业 1.利用除k取余法，可以把任何一个十进制数化为k进制数，并且操作简单、实用. 2.通过k进制数与十进制数的转化，我们也可以将一个k进制数转化为另一个不同基数的k进制数.