高中数学 第一章 算法初步 1.doc

§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．1B．2C．3D．4答案C解析(1)、(2)、(4)正确，(3)错误．2．用更相减损术求294和84的最大公约数时，需做减法的次数是()A．2B．3C．4D．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．1037和425的最大公约数是()A．51B．17C．9D．3答案B解析∵1037＝425×2＋187，425＝187×2＋51，187＝51×3＋34，51＝34×1＋17，34＝17×2，即1037和425的最大公约数是17.4．用秦九韶算法计算多项式f(x)＝6x6＋5x5＋4x4＋3x3＋2x2＋x＋7在x＝0.4时的值时，需做加法和乘法的次数的和为()A．10B．9C．12D．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．27B．11C．109D．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．5123B．6542C．3103D．4312答案C解析4进制数每位上的数字一定小于4，故选C.二、填空题7．辗转相除法程序中有一空请填上．eq\x(\a\al(INPUT“a，b＝”；a，b,DO,r＝,a＝b,b＝r,LOOPUNTILr＝0,PRINTa,END))答案aMODb解析MOD用来表示a除以b的余数．8．更相减损术程序中有两空请填上．eq\x(\a\al(INPUTa，b,WHILEa<>b,r＝a－b,IFb>rTHEN,,,ELSE,a＝r,ENDIF,WEND,PRINTb,END))答案a＝bb＝r9．已知三个数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