四种算法案例-高中数学常见题型解法归纳反馈训练（含答案）.doc

高中数学常见题型解法归纳及反馈检测第89讲： 四种算法案例【知识要点】算法案例有辗转相除法、更相减损术、秦九韶算法和进位制.一、 辗转相除法辗转相除法求两个数的最大公约数，其算法可以描述如下：① 输入两个正整数加和观；② 求余数I计算加除以斤，将所得余数存放到变量尸中；③ 更新被除数和余数：m = n , n = r ；④ 判断余数r是否为0.若余数为0,则输出结果；否则转向第②步继续循环执行如此循环，直到得到结果为止.例：利用辗转相除法求6105与2146的最大公约数6105=2146X2+1813 2146=1813X1+333 1813二333X5+148333二148X2+37 148=37X4+0 最后的除数37是6105与2146的最大公约数.二、 更相减损术我国早期也有解决求最大公约数问题的算法，就是更相减损术•在《九章算术》小记载了更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母•子之数，以少减多，更相减损，求其等也，以等数约之.解题步骤：以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止,则这个相等的数就是所求的最大公约数.例：用更相减损术求98与63的最大公约数98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7所以98和63的最大公约数是7.三、秦九韶算法秦九韶算法适用一般的多项式/（兀）=cinxn + an_}xn~} + an_2xn~2 + +的求值问题.用秦九韶算法求一般多项式/U）=色兀"+色_“"一，+色_2兀1 +…+吗兀+绳•当x = x0时的函数值，可把〃次多项式的求值问题转化成求舁个一次多项式的值的问题，即求V0 = an儿二％）兀+°灯 冬二忖+色_2叫二卩2兀+。

3…… 叫二忖丿+ °”这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现.用秦九韶算法求一般多项式/•（兀）=色兀”+色"2+色_2兀1+一 + 4兀+・当兀=“）时的函数值，需 要斤次乘法运算，〃次加法运算.四、进位制1、 概念进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值•可使用数字符号的个数称为基 数，基数为料，即可称比进位制，简称几进制•现在最常用的是十进制，通常使用10个阿拉伯数字0—9进 行记数.对于任何一个数，我们可以用不同的进位制来表示.比如：十进数57,可以用二进制表示为111001, 也可以用八进制表示为71、用十六进制表示为39,它们所代表的数值都是一样的.一般地，若比是一个大于1的整数，那么以R为基数的k进制可以表示为：勺…⑹ （°< an

1兀+)利用秦九韶算法要经过〃次乘法和农次加法•在利 用秦九韶算法计算时，必须把缺的项补充起来，缺的指数帚的项的系数为零即可，并按照降幕排列.【反馈检测3】用秦九韶算法计算多项式/(x) = 1 + 2x-3x3 + 2x4当x = -1时的值时，岭的结果为A. -4B. -1C. 5D. 6算法案例四进位制解题步骤1、 非十进制数转换为十进制数比较简单，只要计算下面的式子值即可：anan ,••…恥0伙）=an xkn + an { xkn^ + + % xk + 给；2、 把十进制数转换为£进制数，一般利用“除£取余法”.3、 非十进制之间的转换，先把它转换成十进制，再把十进制转换成英他进制.A. 120（4）B・叫）C. 200⑷D. 202 ⑷【例4】将二进制数11100（2）转化为四进制数，正确的是（）【解析】先转化为十进制，再将十进制转化为十进制11100⑵=Ox2° + Ox2】+1X2丄+1X 2日+1X2“ = 28㈣、则运用带余除法4[28余数4]7 04]1 3【点评】非十进制之间的转换，先把它转换成十进制，再把十进制转换成其他进制.【反馈检测4】若六进制数10肪（6）（£为正整数）化为十进制数为239,则£= 高中数学常见题型解法川纳及反馈检测第89讲:四种算法案例参考答案【反馈检测1答案】13【反馈检测1详细解析】4 5 5=390 X1+6 5 390=6 5 X 6•••390, 455的最犬公约数是65546=455X1-^1455书 IX 5故455, 546的最犬公约数为91又65, 91的最犬公约数为13三个数390, 455, 546的最犬公约数是13.【反馈检测2答案】51【反馈检测2详细解析】由更相减损术知459-357 = 102;357-102 = 255;255-102 = 153;153-102 = 51;102-51 = 51,所以最大公约数为51.【反馈检测3答案】C【反馈检测3详细解析】/(%) = 1 + 2兀一3兀彳+ 2x4 = 2十一3兀彳+ OxF + 2兀+1=(((2x 一 3)x + 0)x + 2)x +1x = —1 吋，=2x-3 = -5 ； v2 = VjX + O = —5x(—1)+0=5 .故选C.【反馈检测4答案】3【反馈检测4详细解析】由题⑴肪⑹= 1x63+0x62+jIx6,+5x60 =239, 221 + 6£ = 239,k = 3。