高中数学 第一章 算法初步 1.3算法案例学案 新人教a版必修3

《高中数学 第一章 算法初步 1.3算法案例学案 新人教a版必修3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1．3　算法案例1．问题导航(1)什么叫辗转相除法？(2)什么叫更相减损术？(3)辗转相除法与更相减损术的区别是什么？(4)什么是秦九韶算法？(5)学习了十进制，知道十进制是使用0～9十个数字，那么二进制、五进制、七进制分别使用哪些数字？2．例题导读通过对例1的学习，学会用更相减损术求最大公约数；通过对例2的学习，学会用秦九韶算法求多项式的值；通过对例3的学习，学会如何将二进制化为十进制；通过对例4的学习，学会如何将k进制化为十进制；通过对例5的学习，学会如何将十进制化为二进制；通过对例6的学习，学会十进制化为k进制的方法：即“除k取余法”(k∈N，2≤k≤9)．1．辗转相除法与更相减损术(1

2、)辗转相除法：又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法．(2)更相减损术：我国古代数学专著《九章算术》中介绍的一种求两个正整数的最大公约数的算法．2．秦九韶算法功能它是一种用于计算一元n次多项式的值的方法改写后的形式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0＝(anxn－1＋an－1xn－2＋…＋a1)x＋a0＝((anxn－2＋an－1xn－3＋…＋a2)x＋a1)x＋a0＝…＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0计算方法从括号最内层开始，由内向外逐层计算v1＝anx＋an－1，v2＝v1x＋an－2，v3＝v2x＋an－3，v

3、n＝vn－1x＋a0，…这样，求n次多项式f(x)的值就转化为求n个一次多项式的值.　　3.进位制(1)进位制进位制是人们为了计数和运算方便而约定的记数系统，“满几进一”就是几进制，几进制的基数就是几．(2)其他进位制与十进制间的转化①其他进位制化成十进制其他进位制的数化成十进制时，表示成不同位上数字与基数的幂的乘积之和的形式．②十进制化成k进制的方法——“除k取余法”．1．用更相减损术求294和84的最大公约数时，需做减法运算的次数是(　　)A．2　　　　　　　　　B．3C．4D．5解析：选C.294－84＝210，210－84＝126，126－84＝42，84－42＝42，共做4次减法运算

4、．2．用秦九韶算法计算多项式f(x)＝3x6＋4x5＋5x4＋6x3＋7x2＋8x＋1当x＝0.4时的值时，需要做乘法和加法的次数分别是(　　)A．6，6B．5，6C．5，5D．6，5答案：A3．完成下列进位制之间的转化．(1)1034(7)＝________(10)；(2)119(10)＝________(6)．解析：(1)1034(7)＝1×73＋0×72＋3×7＋4×70＝368.(2)∴119(10)＝315(6)．答案：(1)368　(2)3154．当所给的多项式按x的降幂排列“缺项”时，用秦九韶算法改写多项式时，应注意什么？解：所缺的项写成系数为零的形式，即写成0·xn的形式．1．

5、对于任何一个数，我们可以用不同的进位制来表示．2．表示各种进位制数一般在数字右下角加注来表示，如111001(2)表示二进制数，34(5)表示5进制数．3．电子计算机一般都使用二进制．4．利用除k取余法，可以把任何一个十进制数化为k进制数，并且操作简单、实用．5．通过k进制数与十进制数的转化，我们也可以将一个k进制数转化为另一个不同基数的M进制数．6．利用秦九韶算法可以减少计算次数提高计算效率．　　　　　　　求最大公约数用辗转相除法求612与468的最大公约数，并用更相减损术检验所得结果．(链接教材P36例1)[解]　用辗转相除法：612＝468×1＋144，468＝144×3＋36，144＝

6、36×4，即612和468的最大公约数是36.用更相减损术检验：612和468为偶数，两次用2约简得153和117，153－117＝36，117－36＝81，81－36＝45，45－36＝9，36－9＝27，27－9＝18，18－9＝9，所以612和468的最大公约数为9×2×2＝36.方法归纳(1)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．(2)利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶

7、数．若是，用2约简，也可以不除以2，直接求最大公约数，这样不影响最后结果．1．(1)1624与899的最大公约数是________．解析：1624＝899×1＋725，899＝725×1＋174，725＝174×4＋29，174＝29×6，故1624与899的最大公约数是29.答案：29(2)用辗转相除法求80和36的最大公约数，并用更相减损术检验所得结果．解：辗转相除法：80＝36×2＋8，36