§1.3.1算法案例
————辗转相除法与更相减损术
学习目标
1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。
2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。
重点难点
重点：理解辗转相除法与更相减损术求最大公约数的方法。
难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言。
学法指导
1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数.
2. 更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.
问题探究
知识探究（一）:辗转相除法
思考1:18与30的最大公约数是多少？你是怎样得到的？
思考2:对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难.注意到8251=6105×1+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？
思考3:又6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等.重复上述操作，你能得到8251与6105这两个数的最大公约数吗？
思考4:上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？
第一步，给定两个正整数m，n(m>n).
第二步，
第三步，
第四步，
思考5:该算法的程序框图如何表示？
思考6:该程序框图对应的程序如何表述？
思考7:如果用当型循环结构构造算法，则用辗转相除法求两个正整数m，n的最大公约数的程序框图和程序分别如何表示？
知识探究（二）:更相减损术
思考1:设两个正整数m>n，若m-n=k，则m与n的最大公约数和n与k的最大公约数相等.反复利用这个原理，可求得98与63的最大公约数为多少？
思考2:上述求两个正整数的最大公约数的方法称为更相减损术.一般地，用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？
第一步，给定两个正整数m，n(m>n).
第二步，
第三步，
第四步，
思考3:该算法的程序框图如何表示？
思考4:该程序框图对应的程序如何表述？
知识探究（三）:辗转相除法与更相减损术的区别
（1）都是求最大公约数的方法，计算上辗转相除法以 为主，更相减损术以 为主，计算次数上辗转相除法计算次数相对 ，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是 则得到，而更相减损术则以 相等而得到
理论迁移
例1 分别用辗转相除法和更相减损术求168与93的最大公约数.
辗转相除法：
更相减损术:
例2 求325，130，270三个数的最大公约数.
目标检测
1、在对16和12求最大公约数时，整个操作如下：（16，12）→（4，12）→（4，8）→（4，4），由此可以看出12和16的最大公约数是（ ）
A. 4 B. 12
C. 16 D. 8
2、下列各组关于最大公约数的说法中不正确的是（ ）
A.16和12的最大公约数是4
B.78和36的最大公约数是6
C.85和357的最大公约数是34
D.105和315的最大公约数是105
3、算法
Ｓ１ 输入，ｘ，ｙ
Ｓ２ ｍ＝ｍａｘ{ｘ，ｙ}
Ｓ３ ｎ＝ｍｉｎ{ｘ，ｙ}
Ｓ４ 若ｍ／ｎ＝[ｍ／ｎ]（[ｘ]表示ｘ的整数部分）
则输出ｎ，否则执行Ｓ５
Ｓ５ ｒ＝ｍ－[ｍ／ｎ]＊ｎ
Ｓ６ ｍ＝ｎ
Ｓ７ ｎ＝ｒ
Ｓ８ 执行Ｓ４
Ｓ９ 输出ｎ
上述算法的含义是 。
4、用辗转相除法求840与1785的最大公约数.
5、用更相减损术求612与468的最大公约数
6、分析算法，编出程序，求两个整数ｘ（ｘ≥０）和ｙ（ｙ＞０）的整数商和余数（规定只能用加法和减法运算）。
纠错矫正
总结反思
※自我评价（ ）
A、课前自主学习认真，学案完成很好；
你真棒，继续坚持。
B、课前自主学习一般，学案完成良好；
下次争取做的更好。
C、课前自主学习较差，学案空白较多；
注意学习方法，提高学习效率。
§1.3.2算法案例
————秦九韶算法
学习目标
1.了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质。
2.理解数学算法与计算机算法的区别，理解计算机对数学的辅助作用。
重点难点
重点：理解秦九韶算法的思想。
难点：用循环结构表示算法的步骤。
学法指导
评价一个算法好坏的一个重要标志是运算的次数，如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理论算法.在多项式求值的各种算法中，秦九韶算法是一个优秀算法.
问题探究
知识探究(一):秦九韶算法的基本思想
思考1:对于多项式，求的值. 若先计算各项的值，然后再相加，那么一共要做多少次乘法运算和多少次加法运算？
思考2:在上述问题中，若先计算的值，然后依次计算，，的值，这样每次都可以利用上一次计算的结果，那么一共做了多少次乘法运算和多少次加法运算？
小结：第二种做法和第一种做法相比，乘法的运算次数减少了，因而能提高运算效率。而且对于计算机来说，做一次乘法运算所需的时间比做一次加法运算需要的时间要长得多，因此第二种算法能更快的得到结果。
思考3:利用后一种算法求多项式的值，这个多项式应写成哪种形式？
思考4:对于由内向外逐层计算一次多项式的值，其算法步骤如何？
第一步，计算.
第二步，
第三步，
…
第步，计算
思考5:上述求多项式 的值的方法称为秦九韶算法，利用该算法求的值，一共需要多少次乘法运算，多少次加法运算？
思考6:在秦九韶算法中，记那么第步的算式是什么？
知识探究(二):秦九韶算法的程序设计
思考1:用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法？其算法步骤如何设计？
第一步，
第二步，
第三步，
第四步，
第五步，
思考2:该算法的程序框图如何表示？
思考3:该程序框图对应的程序如何表述？
理论迁移
例1 已知一个5次多项式为
用秦九韶算法求的值.
例2 阅读下列程序，说明它解决的实际问题是什么？
INPUT “x=”；a
n=0
y=0
WHLE n<5
y=y+(n+1)*a∧n
n=n+1
WEND
PRINT y
END
目标检测
1、利用秦九韶算法求多项式在的值时，在运算中下列哪个值用不到（ ）
A.164 B.3767
C.86652 D.85169
2、利用秦九韶算法计算多项式
当=4的值的时候，需要做乘法和加法的次数分别为（ ）
A.6，6 B.5，6
C.5，5 D.6，5
3、利用秦九韶算法求多项式在的值，写出详细步骤。
4、下图的框图是一古代数学家的一个算法的程序框图，它输出的结果s表示（ ）
A.的值
B.的值
C.的值
D.以上都不对
5、已知n次多项式
如果在一种算法中，计算（k＝2，3，4，…，n）的值需要k－1次乘法，
（1）计算的值需要9次运算（6次乘法，3次加法），那么计算的值需要多少次运算？
（2）若采取秦九韶算法：
（k＝0， 1，2，…，n－1），计算的值只需6次运算，那么计算的值共需要多少次运算？
（3）若采取秦九韶算法，设ai=i+1，i=0，1，…，n，求P5（2）（写出采取秦九韶算法的计算过程）
纠错矫正
总结反思
资料：秦九韶的生平
秦九韶(1202～1261年)，字道古，南宋普州安岳(今四川省安岳县)人。
?秦九韶的突出数学成就表现为四个方面：
（1）“大衍求一术”。 ?
? 即为一次同余式组解法。西方解决同类问题的理论是高斯于1801年建立的，比秦九韶晚了554年。他还把这种理论用于解决商功、利息、粟米、建筑等问题。?
?(2)线性方程组解法。
?他在《数书九章》中解决了许多相当于线性方程组的问题，其中数字相当大，计算也很复杂。他在“均货推本”题草中，井然有序地写出厂解题过程，这种解法与高斯消元法本质相当，但比高斯早约600年。
(3)高次方程数值解法。
他集秦汉以来“开方术”之大成，运用贾宪的“增乘开方法”，解决于数字高次方程有理数根和无理数根的近似值计算问题。他所设计的演算程序被称为“秦九韶方法”。 西方同类问题的探究始于19世纪，他比意大利的鲁菲尼、英国的霍纳要早五、六百年。
(4)“三斜求积”。
他在《数书九章》中，依据分别为12、14、15的三边求出了相应的三角形面积，其方法具有一般性。这与西方的海伦公式是等价的。
※自我评价（ ）
A、课前自主学习认真，学案完成很好；
你真棒，继续坚持。
B、课前自主学习一般，学案完成良好；
下次争取做的更好。
C、课前自主学习较差，学案空白较多；
注意学习方法，提高学习效率。
1. 3算法案例
【教学目标】：
1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。
2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。
【教学重难点】：
重点：理解辗转相除法与更相减损术求最大公约数的方法。
难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言。
【教学过程】：
情境导入：
1.教师首先提出问题：在初中，我们已经学过求最大公约数的知识，你能求出18与30的公约数吗？
2.接着教师进一步提出问题，我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数？这就是我们这一堂课所要探讨的内容。
新知探究：
1.辗转相除法
例1 求两个正数8251和6105的最大公约数。
（分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数）
解：8251＝6105×1＋2146
显然8251的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。
6105＝2146×2＋1813
2146＝1813×1＋333
1813＝333×5＋148
333＝148×2＋37
148＝37×4＋0
则37为8251与6105的最大公约数。
以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。利用辗转相除法求最大公约数的步骤如下：
第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；
第二步：若r0＝0，则n为m，n的最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1；
第三步：若r1＝0，则r1为m，n的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2；
……
依次计算直至rn＝0，此时所得到的rn-1即为所求的最大公约数。
练习：利用辗转相除法求两数4081与20723的最大公约数（答案：53）
2.更相减损术
我国早期也有解决求最大公约数问题的算法，就是更相减损术。
更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母·子之数，以少减多，更相减损，求其等也，以等数约之。
翻译出来为：
第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。
第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。
例2 用更相减损术求98与63的最大公约数.
解：由于63不是偶数，把98和63以大数减小数，并辗转相减，即：98－63＝35
63－35＝28
35－28＝7
28－7＝21
21－7＝14
14－7＝7
所以，98与63的最大公约数是7。
练习：用更相减损术求两个正数84与72的最大公约数。（答案：12）
比较辗转相除法与更相减损术的区别：
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到
3. 秦九韶算法
秦九韶计算多项式的方法
令，则有，
其中.这样，我们便可由依次求出；
显然，用秦九韶算法求n次多项式的值时只需要做n次乘法和n次加法运算
4.进位制
进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值.可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制.现在最常用的是十进制，通常使用10个阿拉伯数字0-9进行记数.
对于任何一个数，我们可以用不同的进位制来表示.比如：十进数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的.
表示各种进位制数一般在数字右下脚加注来表示,如111001(2)表示二进制数,34(5)表示5进制数.
（1）.k进制转换为十进制的方法：
，
（2）.十进制转化为k进制数b的步骤为：
第一步，将给定的十进制整数除以基数k，余数便是等值的k进制的最低位；
第二步，将上一步的商再除以基数k，余数便是等值的k进制数的次低位；
第三步，重复第二步，直到最后所得的商等于0为止，各次所得的余数，便是k进制各位的数，最后一次余数是最高位，即除k取余法.
要点诠释：
1、在k进制中，具有k个数字符号.如二进制有0，1两个数字.
2、在k进制中，由低位向高位是按“逢k进一”的规则进行计数.
3、非k进制数之间的转化一般应先转化成十进制，再将这个十进制数转化为另一种进制的数，有的也可以相互转化.
【反馈测评】：
1．求324、243、135这三个数的最大公约数。
求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大公约数的最大公约数即为所求。
2．用更相减损术求98与63的最大公约数
解：由于63不是偶数，把98和63以大数减小数，并辗转相减
98－63＝35
63－35＝28
35－28＝7
28－7＝21
21－7＝21
14－7＝7
所以，98和63的最大公约数等于7
3．已知一个五次多项式为用秦九韶算法求这个多项式当x = 5的值。
解：将多项式变形：按由里到外的顺序，依此计算一次多项式当x = 5时的值：
，，，
，所以，当x = 5时，多项式的值等于17255.2
4．将二进制数110011(2)化成十进制数
解：根据进位制的定义可知
所以，110011（2）=51。
【板书设计】：
1.3算法案例
课前预习学案
一、预习目标
1、理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。
2、理解秦九韶算法的思想。
二、预习内容
什么是进位制？最常见的进位制是什么？除此之外还有哪些常见的进位制？请举例说明．
三、提出疑惑
思考：辗转相除法中的关键步骤是哪种逻辑结构？
课内探究学案
学习目标
1. 会用辗转相除法与更相减损术求最大公约数的方法。
2. 会利用秦九韶算法求多项式的值。
3．各进位制之间能灵活转化。
二、学习重难点：
重点：辗转相除法与更相减损术求最大公约数的方法和秦九韶算法求多项式的值。
难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言。
学习过程
辗转相除法思路：可以利用除法将大数化小,找两数的最大公约数.(适于两数较大时)
(1)用较大的数m除以较小的数n得到一个商和一个余数；
(2)若＝0,则n为m,n的最大公约数；若≠0,则用除数n除以余数得到一个
和一个余数；(3)若＝0,则为m,n的最大公约数;若≠0,则用除数除以余数得到一个商和一个余数；……依次计算直至＝0，此时所得到的即为所求的最大公约数.
例题1：求两个正数1424和801的最大公约数.
①以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法.
②由上述步骤可以看出，辗转相除法中的除法是一个反复执行的步骤，且执行次数由余数 是否等于0来决定,所以可把它看成一循环体,写出辗转相除法完整的程序框图和程序语言.
教学更相减损术：我国早期也有求最大公约数问题的算法，就是更相减损术. 在《九章算 术》中有更相减损术求最大公约数的步骤：可半者半之，不可半者，副置 分母?子之数，以少减多，更相减损，求其等也，以等数约之.
翻译为：(1) 任意给出两个正数；判断它们是否都是偶数. 若是，用2约简；若不是，执 行第二步.
(2) 以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小
数. 继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最
大公约数.
例题2. 用更相减损术求91和49的最大公约数.
秦九韶算法：
（1）设计求多项式当x=5时的值的算法，并写出程序。
（2）有没有更高效的算法？能否探求更好的算法，来解决任意多项式的求解问题？
引导学生把多项式变形为：
并提问：从内到外，如果把每一个括号都看成一个常数，那么变形后的式子中有哪些“一次式”？x的系数依次是什么？
用秦九韶算法求多项式的值，与多项式组成有直接关系吗？用秦九韶算法计算上述多项式的值，需要多少次乘法运算和多少次加法运算？秦九韶算法适用于一般的多项式的求值问题吗？
怎样用程序框图表示秦九韶算法？观察秦九韶算法的数学模型，计算时要用到的值，若令，我们可以得到下面的递推公式：
这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现。请画出程序框图。
例题3．已知一个五次多项式为用秦九韶算法求这个多项式当x = 5的值。
进位制：
我们了解十进制吗？所谓的十进制，它是如何构成的？其它进位制的数又是如何的呢？
进位制是人们为了计数和运算方便而约定的记数系统。进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制。
例题4．将二进制数110011(2)化成十进制数
精讲点拨：
1．求两个正数8251和2146;228和1995;5280和12155的最大公约数.
2． 求两个正数8251和2146的最大公约数.
3.用秦九韶算法计算多项式
在x=-4时的值时,V3的值为 ：
反思总结：
比较辗转相除法与更相减损术的区别
(1)都是求 的方法，计算上辗转相除法以 法为主，更相减损术以 法为主，计算次数上 法计算次数相对较少，特别当两个数字 时计算次数的区别较明显．
(2)从结果体现形式来看，辗转相除法体现结果是以 则得到，而更相减损术
则以 而得到．
(3)通过对秦九韶算法的学习，你对算法本身有哪些进一步认识？
(4)秦九韶算法在计算一个n次多项式的值时，只要做____次乘法运算和____次加法运算。
课后练习与提高
1、用“辗转相除法”求得459和357的最大公约数是：
A．3 B．9 C．17 D．51
2、将数转化为十进制数为：
A. 524 B. 774 C. 256 D. 260
3、用秦九韶算法计算多项式
当时的值时,需要做乘法和加法的次数分别是：
A. 6 , 6 B. 5 , 6
C. 5 , 5 D. 6 ，5
参考答案:1D 2B 3A
课件27张PPT。新知自解最大公约数两个正整数m、nm除以n所得余数rm＝n，n＝rm第二步两个正整数最大公约数偶数用2约简第二步较大较小较小相等一元n次多项式(anxn－1＋an－1xn－2＋…＋a1)x＋a0(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0v2x＋an－3vn－1x＋a0n个一次多项式计数运算方便k进制k除k取余法答案： D答案： D3.二进制数1 101(2)化成五进制数为 Ｗ.答案： 23(5)课堂探究答案： C答案： B答案： A
谢谢观看！学业分层测评(八) 算法案例
(建议用时：45分钟)
[学业达标]
一、选择题
1．关于进位制说法错误的是( )
A．进位制是人们为了计数和运算方便而约定的记数系统
B．二进制就是满二进一，十进制就是满十进一
C．满几进一，就是几进制，几进制的基数就是几
D．为了区分不同的进位制，必须在数的右下角标注基数
【解析】 一般情况下，不同的进位制须在数的右下角标注基数，但十进制可以不用标注，所以不是必须在数的右下角标注基数，所以D错误．
【答案】 D
2．下列四个数中，数值最小的是( )
A．25(10) B．54(4)
C．10 110(2) D．10 111(2)
【解析】 统一成十进制，B中54(4)＝5×41＋4＝24，C中10 110(2)＝1×24＋1×22＋2＝22，D中，10 111(2)＝23.
【答案】 C
3．用更相减损术求1 515和600的最大公约数时，需要做减法次数是( )
A．15 B．14
C．13 D．12
【解析】 1 515－600＝915，915－600＝315，600－315＝285，315－285＝30，285－30＝255，255－30＝225，225－30＝195，195－30＝165，165－30＝135，135－30＝105，105－30＝75，75－30＝45，45－30＝15，30－15＝15.
∴1 515与600的最大公约数是15.则共做14次减法．
【答案】 B
4．计算机中常用的十六进制是逢16进1的计数制，采用数字0～9和字母A～F共16个计数符号，这些符号与十进制数的对应关系如下表：
十六进制
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
十进制
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
例如，用十六进制表示：E＋D＝1B，则A×B等于( )
A．6E B．72
C．5F D．B0
【解析】 A×B用十进制表示10×11＝110，而110＝6×16＋14，所以用16进制表示6E.
【答案】 A
5．以下各数有可能是五进制数的是( )
A．15 B．106
C．731 D．21 340
【解析】 五进制数中各个数字均是小于5的自然数，故选D.
【答案】 D
二、填空题
6．用更相减损术求36与134的最大公约数，第一步应为________．
【解析】 ∵36与134都是偶数，∴第一步应为：先除以2，得到18与67.
【答案】 先除以2，得到18与67
7．用秦九韶算法求f(x)＝2x3＋x－3当x＝3时的值v2＝________．
【解析】 f(x)＝((2x＋0)x＋1)x－3，
v0＝2；
v1＝2×3＋0＝6；
v2＝6×3＋1＝19.
【答案】 19
8．将八进制数127(8)化成二进制数为________．
【解析】 先将八进制数127(8)化为十进制数：127(8)＝1×82＋2×81＋7×80＝64＋16＋7＝87，
再将十进制数87化成二进制数：
∴87＝1010111(2)，
∴127(8)＝1010111(2)．
【答案】 1010111(2)
三、解答题
9．用更相减损术求288与153的最大公约数．
【解】 288－153＝135，153－135＝18，135－18＝117，117－18＝99，99－18＝81，81－18＝63，63－18＝45，45－18＝27，27－18＝9，18－9＝9.
因此288与153的最大公约数为9.
10．用秦九韶算法计算多项式f(x)＝x6－12x5＋60x4－160x3＋240x2－192x＋64，当x＝2时的值．
【解】 将f(x)改写为
f(x)＝(((((x－12)x＋60)x－160)x＋240)x－192)x＋64，
由内向外依次计算一次多项式当x＝2时的值，
v0＝1，
v1＝1×2－12＝－10，
v2＝－10×2＋60＝40，
v3＝40×2－160＝－80，
v4＝－80×2＋240＝80，
v5＝80×2－192＝－32，
v6＝－32×2＋64＝0.
所以f(2)＝0，即x＝2时，原多项式的值为0.
[能力提升]
1．下面一段程序的目的是( )
INPUT m，n
WHILF m<>n
IF m>n THEN
m＝m－n
ELSE
n＝n－m
END IF
WEND
PRINT m
END
A．求m，n的最小公倍数 B．求m，n的最大公约数
C．求m被n除的商 D．求n除以m的余数
【解析】 本程序当m，n不相等时，总是用较大的数减去较小的数，直到相等时跳出循环，显然是“更相减损术”．故选B.
【答案】 B
2．若k进制数123(k)与十进制数38相等，则k＝________．
【解析】 由k进制数123可知k≥4.下面可用验证法：若k＝4，则38(10)＝212(4)，不合题意；若k＝5，则38(10)＝123(5)成立，所以k＝5.
或者123(k)＝1×k2＋2×k＋3＝k2＋2k＋3，∴k2＋2k＋3＝38，k2＋2k－35＝0，k＝5(k＝－7＜0舍去)．
【答案】 5
3．若二进制数10b1(2)和三进制数a02(3)相等，求正整数a，b. 【导学号：28750022】
【解】 ∵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，2}，b∈{0，1}，
∴当a＝1时，b＝1符合题意；
当a＝2时，b＝不符合题意．
∴a＝1，b＝1.
4．用秦九韶算法求多项式f(x)＝8x7＋5x6＋3x4＋2x＋1，当x＝2时的值．
【解】 根据秦九韶算法，把多项式改写成如下形式：
f(x)＝8x7＋5x6＋0·x5＋3·x4＋0·x3＋0·x2＋2x＋1
＝((((((8x＋5)x＋0)x＋3)x＋0)x＋0)x＋2)x＋1.
而x＝2，所以有
v0＝8，
v1＝8×2＋5＝21，
v2＝21×2＋0＝42，
v3＝42×2＋3＝87，
v4＝87×2＋0＝174，
v5＝174×2＋0＝348，
v6＝348×2＋2＝698，
v7＝698×2＋1＝1 397.
所以当x＝2时，多项式的值为1 397.
课件26张PPT。第一章 算法初步§1.3 算法案例（一）1.理解辗转相除法与更相减损术中的数学原理，并能根据这些原理进行算法分析；
2.了解秦九韶算法及利用它提高计算效率的本质；
3.对简单的案例能设计程序框图并写出算法程序.问题导学题型探究达标检测学习目标知识点一 求两个数的最大公约数的算法答案问题导学 新知探究 点点落实思考 注意到8 251＝6 105×1＋2 146，那么8 251与6 105这两个数的公约数和6 105与2 146的公约数有什么关系？答案 显然8 251与6 105的公约数也必是2 146的约数，同样6 105与2 146的公约数也必是8 251的约数，所以8 251与6 105的最大公约数也是6 105与2 146的最大公约数.一般地，求两个数的最大公约数有2种算法：
1.辗转相除法
(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的 的古老而有效的算法.
(2)辗转相除法的算法步骤
第一步，给定 .
第二步，计算 .
第三步， .
第四步，若r＝0，则m，n的最大公约数等于 ；
否则，返回 .答案最大公约数两个正整数m，n(m>n)m除以n所得的余数rm＝n，n＝rm第二步2.更相减损术的运算步骤
第一步，任意给定两个正整数，判断它们是否都是 .若是，用 约简；若不是，执行 .
第二步，以 的数减去 的数，接着把所得的差与 的数比较，并以大数减小数，继续这个操作，直到所得的数 为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.答案偶数2第二步较大较小较小相等答案知识点二 求n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0的值的算法思考 衡量一个算法是否优秀的重要参数是速度.把多项式f(x)＝x5＋x4＋x3＋x2＋x＋1变形为f(x)＝((((x＋1)x＋1)x＋1)x＋1)x＋1，然后求当x＝5时的值，为什么比常规逐项计算省时？答案 从里往外计算，充分利用已有成果，可减少重复计算.秦九韶算法的一般步骤：
把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如下形式：
(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0，求多项式的值时，首先计算
一次多项式的值，即v1＝ ，然后由内向外逐层计算一次多项式的值，即最内层括号内anx＋an－1v2＝ ，
v3＝ ，
…
vn＝ ，
这样，求n次多项式f(x)的值就转化为求 的值.答案返回v1x＋an－2v2x＋an－3vn－1x＋a0n个一次多项式类型一 辗转相除法的现代实现解析答案反思与感悟例1 试设计用辗转相除法可以求两个正整数m，n的最大公约数的程序框图和程序. 题型探究 重点难点 个个击破解析答案解 (1)算法：
第一步，给定两个正整数m，n(m>n).
第二步，计算m除以n所得的余数r.
第三步，m＝n，n＝r.
第四步，若r＝0，则m，n的最大公约数等于m；否则，返回第二步.
(2)程序框图：反思与感悟(3)程序：INPUT m，n
DO
r＝m MOD n
m＝n
n＝r
LOOP UNTIL r＝0
PRINT m
END反思与感悟利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数.反思与感悟跟踪训练1 用辗转相除法求261和319的最大公约数.解析答案解 辗转相除法：
319÷261＝1(余58)，
261÷58＝4(余29)，
58÷29＝2(余0)，
所以319与261的最大公约数为29.类型二 更相减损术解析答案反思与感悟例2 试用程序框图和程序表述更相减损术.解 程序框图：程序：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反思与感悟利用更相减损术求两个正整数的最大公约数的一般步骤是首先判断两个正整数是否都是偶数.若是，用2约简，也可以不除以2，直接求最大公约数，这样不影响最后结果.跟踪训练2 用更相减损术求261和319的最大公约数.解 319－261＝58,261－58＝203，
203－58＝145,145－58＝87，
87－58＝29,58－29＝29，
29－29＝0，
所以319与261的最大公约数是29.解析答案类型三 秦九韶算法的基本思想解析答案反思与感悟例3 已知一个5次多项式为f(x)＝4x5＋2x4＋3.5x3－2.6x2＋1.7x－0.8，用秦九韶算法求这个多项式当x＝5时的值.解 将f(x)改写为
f(x)＝((((4x＋2)x＋3.5)x－2.6)x＋1.7)x－0.8，
由内向外依次计算一次多项式当x＝5时的值：
v0＝4；v1＝4×5＋2＝22；
v2＝22×5＋3.5＝113.5；
v3＝113.5×5－2.6＝564.9；
v4＝564.9×5＋1.7＝2 826.2；
v5＝2 826.2×5－0.8＝14 130.2.
∴当x＝5时，多项式的值等于14 130.2.反思与感悟反思与感悟秦九韶算法之所以优秀，一是其对所有多项式求值都适用，二是充分利用已有计算成果，效率更高.跟踪训练3 用秦九韶算法求多项式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x当x＝3时的值.解 f(x)＝((((((7x＋6)x＋5)x＋4)x＋3)x＋2)x＋1)x，
所以有v0＝7，
v1＝7×3＋6＝27，
v2＝27×3＋5＝86，
v3＝86×3＋4＝262，
v4＝262×3＋3＝789，
v5＝789×3＋2＝2 369，
v6＝2 369×3＋1＝7 108，
v7＝7 108×3＝21 324.
故当x＝3时，多项式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x的值为21 324.解析答案返回1.下列说法中正确的个数为( )
①辗转相除法也叫欧几里得算法；
②辗转相除法的基本步骤是用较大的数除以较小的数；
③求最大公约数的方法，除辗转相除法之外，没有其他方法；
④编写辗转相除法的程序时，要用到循环语句.
A.1 B.2 C.3 D.4C达标检测 12345解析 ①、②、④正确，③错误.解析答案2.关于利用更相减损术求156和72的最大公约数，下列说法正确的是( )
A.都是偶数必须约简
B.可以约简，也可以不约简
C.第一步作差为156－72＝84，第二步作差为72－84＝－12
D.以上皆不正确12345B答案3.用辗转相除法求210与98的最大公约数需作除法的次数为( )
A.1 B.2 C.3 D.412345B答案4.用更相减损术求147和42的最大公约数是( )
A.6 B.7 C.21 D.42C12345答案123455.用秦九韶算法计算多项式f(x)＝6x6＋5x5＋4x4＋3x3＋2x2＋x＋7在x＝0.4时的值时，需做加法和乘法的次数的和为( )
A.10 B.9 C.12 D.8C解析 f(x)＝(((((6x＋5)x＋4)x＋3)x＋2)x＋1)x＋7，
∴加法6次，乘法6次，
∴6＋6＝12次，故选C.解析答案规律与方法1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数.
2.更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.返回§1.3 算法案例
课时目标 通过三种算法案例：辗转相除法与更相减损术，秦九韶算法，进位制，进一步体会算法的思想，提高算法设计水平，体会中国古代数学对世界的贡献．
1．辗转相除法
(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法．
(2)辗转相除法的算法步骤
第一步，给定两个正整数m，n.
第二步，计算m除以n所得的余数r.
第三步，m＝n，n＝r.
第四步，若r＝0，则m、n的最大公约数等于m；否则，返回第二步．
2．更相减损术
第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．
第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．
3．秦九韶算法
把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如下形式：
(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0，
求多项式的值时，首先计算最内层括号内一次多项式的值，即v1＝anx＋an－1，然后由内向外逐层计算一次多项式的值，即
v2＝v1x＋an－2，
v3＝v2x＋an－3，
…
vn＝vn－1x＋a0
这样，求n次多项式f(x)的值就转化为求n个一次多项式的值．
4．进位制
进位制是人们为了计数和运算方便而约定的记数系统，“满k进一”就是k进制，k进制的基数是k.
把十进制转化为k进制数时，通常用除k取余法．
一、选择题
1．下列说法中正确的个数为( )
(1)辗转相除法也叫欧几里得算法；
(2)辗转相除法的基本步骤是用较大的数除以较小的数；
(3)求最大公约数的方法，除辗转相除法之外，没有其他方法；
(4)编写辗转相除法的程序时，要用到循环语句．
A．1 B．2 C．3 D．4
答案 C
解析 (1)、(2)、(4)正确，(3)错误．
2．用更相减损术求294和84的最大公约数时，需做减法的次数是( )
A．2 B．3 C．4 D．5
答案 C
解析 由于294和84都是偶数，
所以用2约简：
294÷2＝147，
84÷2＝42，
又由于147不是偶数，
所以147－42＝105，
105－42＝63，
63－42＝21，
42－21＝21，
故需做4次减法，故选C.
3．1 037和425的最大公约数是( )
A．51 B．17 C．9 D．3
答案 B
解析 ∵1 037＝425×2＋187，
425＝187×2＋51，
187＝51×3＋34，
51＝34×1＋17，
34＝17×2，
即1 037和425的最大公约数是17.
4．用秦九韶算法计算多项式f(x)＝6x6＋5x5＋4x4＋3x3＋2x2＋x＋7在x＝0.4时的值时，需做加法和乘法的次数的和为( )
A．10 B．9 C．12 D．8
答案 C
解析 f(x)＝(((((6x＋5)x＋4)x＋3)x＋2)x＋1)x＋7
∴加法6次，乘法6次，
∴6＋6＝12(次)，故选C.
5．已知f(x)＝x5＋2x3＋3x2＋x＋1，应用秦九韶算法计算x＝3时的值时，v3的值为( )
A．27 B．11 C．109 D．36
答案 D
解析 将函数式化成如下形式．
f(x)＝(((x＋0)x＋2)x＋3)x＋1)x＋1
由内向外依次计算：
v0＝1，
v1＝1×3＋0＝3，
v2＝3×3＋2＝11，
v3＝11×3＋3＝36，
v4＝36×3＋1＝109，
v5＝109×3＋1＝328.
6．下列有可能是4进制数的是( )
A．5 123 B．6 542 C．3 103 D．4 312
答案 C
解析 4进制数每位上的数字一定小于4，故选C.
二、填空题
7．辗转相除法程序中有一空请填上．
答案 a MOD b
解析 MOD用来表示a除以b的余数．
8．更相减损术程序中有两空请填上．
答案 a＝b b＝r
9．已知三个数12(16)，25(7)，33(4)，将它们按由小到大的顺序排列为________．
答案 33(4)<12(16)<25(7)
解析 将三个数都化为十进制数．
12(16)＝1×16＋2＝18，
25(7)＝2×7＋5＝19，
33(4)＝3×4＋3＝15，
∴33(4)<12(16)<25(7)．
三、解答题
10．用两种方法求210与98的最大公约数．
解 用辗转相除法：
210＝98×2＋14，
98＝14×7.
∴210与98的最大公约数为14.
用更相减损术：
∵210与98都是偶数，用2约简得
105和49，
105－49＝56,56－49＝7，
49－7＝42,42－7＝35，
35－7＝28,28－7＝21，
21－7＝14,14－7＝7.
∴210与98的最大公约数为2×7＝14.
11．用秦九韶算法计算多项式f(x)＝x6－12x5＋60x4－160x3＋240x2－192x＋64当x＝2时的值．
解 将f(x)改写为
f(x)＝(((((x－12)x＋60)x－160)x＋240)x－192)x＋64
由内向外依次计算一次多项式当x＝2时的值
v0＝1，
v1＝1×2－12＝－10，
v2＝－10×2＋60＝40，
v3＝40×2－160＝－80，
v4＝－80×2＋240＝80，
v5＝80×2－192＝－32，
v6＝－32×2＋64＝0.
∴f(2)＝0，即x＝2时，原多项式的值为0.
能力提升
12．把111化为五进制数．
解
∴111化为五进制数为421(5)．
13．把10 231(5)化为四进制数．
解 先化成十进制数．
10 231(5)＝1×54＋0×53＋2×52＋3×51＋1
＝625＋50＋15＋1
＝691
再化为四进制数
∴10 231(5)＝22 303(4).
1．辗转相除法与更相减损术的区别和联系
(1)都是求最大公约数的方法．
(2)二者的实质都是递归的过程．
(3)二者都要用循环结构来实现．
2．秦九韶算法的特点
秦九韶算法的特点在于把求一个n次多项式的值转化为求n个一次多项式的值，即把求f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0的值转化为求递推公式：
这样可以最多计算n次乘法和n次加法即可得多项式的值，和直接代入多项式相比减少了乘法的运算次数，提高了运算效率．
3．十进制与其他进制的转化
(1)将k进制转化为十进制的方法：先把k进制数写成各位上的数字与k的幂的乘积的形
式，再按十进制的运算规则计算．
(2)将十进制化成k进制的方法：用除k取余法，用k连续去除十进制数所得的商，直到商为零为止，然后将各步所得的余数倒序写出，即为相应的k进制数．
