13算法案例（1）

1、1.3 算法案例教學(xué)目標(biāo)1、理解掌握輾轉(zhuǎn)相除法、更相減損術(shù)、秦九韶算法以及進(jìn)位制的含義，了解他們的計(jì)算過程。2、提高學(xué)生的數(shù)學(xué)邏輯思維能力，發(fā)展有條理的思考與數(shù)學(xué)表達(dá)能力。3、了解古代著名的算法，培養(yǎng)學(xué)生的民族自豪感與愛國(guó)情懷，激發(fā)學(xué)生學(xué)習(xí)的熱情。教學(xué)重難點(diǎn)重點(diǎn)：輾轉(zhuǎn)相除法、更相減損術(shù)、秦九韶算法以及進(jìn)位制的算法思想，輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別與聯(lián)系。難點(diǎn)：1、如何選擇輾轉(zhuǎn)相除法與更相減損術(shù)。 2、理解秦九韶算法的先進(jìn)性。 3、理解進(jìn)位制的概念，不同進(jìn)位制之間的轉(zhuǎn)換。教學(xué)過程一、復(fù)習(xí)引入問題：求18與30的最大公約數(shù)通過該例來(lái)回憶小學(xué)求最大公約數(shù)的方法，進(jìn)而引入輾轉(zhuǎn)相除法與更相減損術(shù)，以體現(xiàn)

2、這兩種算法的優(yōu)越性。學(xué)生：2 18 30 3 9 15 3 5所以18與30的最大公約數(shù)是2*3=6教師：若兩個(gè)數(shù)的公共因子不容易發(fā)現(xiàn)，又如何求它們的最大公約數(shù)？二、新課講解例如：求8251與6105的最大公約數(shù)分析：如果使用上述方法求最大公約數(shù)比較困難，因?yàn)槲覀兒茈y發(fā)現(xiàn)這兩個(gè)數(shù)字的公共因子，下面我們介紹一種古老而有效的算法輾轉(zhuǎn)相除法。這種算法是由歐幾里得在公元前300年左右首先提出來(lái)的，因而又叫歐幾里得算法。所謂輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)數(shù)，用較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則這時(shí)的較小的數(shù)就是原來(lái)兩個(gè)數(shù)的最大公約

3、數(shù)。用這一思想求解8251與6105的最大公約數(shù)8251=6105*1+21466105=2146*2+18132146=1813*1+3331813=333*5+148333=148*2+37148=37*4所以8251與6105的最大公約數(shù)是37.說(shuō)明：這里學(xué)生可能要產(chǎn)生疑問：為什么37是8251與6105的最大公約數(shù)？教師稍做解釋。比如由等式8251=6105*1+2146可知，8251與6105的公約數(shù)和6105與2146的公約數(shù)相同，從而最大公約數(shù)相同，這樣求8251與6105的最大公約數(shù)就轉(zhuǎn)化為求6105與2146的最大公約數(shù)，如此繼續(xù)下去，除到可以整除為止，即得最大公約數(shù)。輾轉(zhuǎn)相

4、除法用的是除法，我們也可以用減法來(lái)求兩個(gè)數(shù)的最大公約數(shù)，這就是更相減損術(shù)。學(xué)生閱讀課本36頁(yè)更相減損術(shù)有關(guān)內(nèi)容。所謂更相減損術(shù)，第一步，任意給定兩個(gè)正整數(shù)，判斷它們是否都是偶數(shù)。若是，用2約簡(jiǎn)；若不是，執(zhí)行第二步。第二步，以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，則這個(gè)數(shù)或這個(gè)數(shù)與約簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù)。下面用一個(gè)例子說(shuō)明這個(gè)算法。例1 用更相減損術(shù)求18與30的最大公約數(shù)解：18與30都是偶數(shù)，先除以2，得到9與15， 15-9=6 9-6=3 6-3=3 直到2個(gè)小的數(shù)相等為止，因?yàn)殚_始18與30同時(shí)除以了2，所以

5、最后用這兩個(gè)相等的數(shù)字乘以2即3*2=6,6才是18與30的最大公約數(shù)。例2 用輾轉(zhuǎn)相除法與更相減損術(shù)求98與63的最大公約數(shù)解：輾轉(zhuǎn)相除法 更相減損術(shù) 98=63*1+35 98-63=35 63=35*1+28 63-35=28 35=28*1+7 35-28=7 28=4*7 28-7=21 最大公約數(shù)為7 21-7=14 14-7=7 最大公約數(shù)為7對(duì)比兩種方法，前者的步驟更少，后者的步驟多，如果用更相減損術(shù)求例1，要用14步，所以在解題中選取哪種方法較為重要。案例2 秦九韶算法例：求多項(xiàng)式當(dāng)時(shí)的值學(xué)生自然而然直接將代入中，但是這樣我們要做10次乘法運(yùn)算，5次加法運(yùn)算，有沒有更有效的算

6、法呢？我國(guó)南宋時(shí)期的數(shù)學(xué)家秦九韶在數(shù)書九章中提出了下面的算法。（計(jì)算時(shí)由內(nèi)到外）所以，當(dāng)時(shí)，多項(xiàng)式的值等于7031這個(gè)算法實(shí)際上是通過提取公因式將高次降低為低次，這樣我們只需要算5次乘法，5次加法。從這里我們可以看出，要算多少次乘法與最高次項(xiàng)的次數(shù)相同，要算多少次加法與加號(hào)的個(gè)數(shù)相同。課本38頁(yè)的思考題，因?yàn)樽罡叽雾?xiàng)的次數(shù)為n，所以需要n次乘法運(yùn)算，因?yàn)橛衝個(gè)加號(hào)，所以需要n次加法運(yùn)算。案例3 進(jìn)位制1、我們平時(shí)最熟悉的進(jìn)位制是十進(jìn)制，十進(jìn)制的數(shù)字由0-9這十個(gè)數(shù)字組成，教師：除了十進(jìn)制，我們生活中還會(huì)出現(xiàn)什么進(jìn)制？學(xué)生：每個(gè)星期從星期一到星期天再?gòu)男瞧谝坏叫瞧谔?，這是七進(jìn)制教師：七進(jìn)制由那些

7、數(shù)字組成？學(xué)生：0-6教師：在計(jì)算機(jī)中用的都是二進(jìn)制，二進(jìn)制由那些數(shù)字組成？學(xué)生：0,1從這幾個(gè)我們生活中的例子，你能發(fā)現(xiàn)幾進(jìn)制（這個(gè)幾叫做基數(shù)）的基數(shù)與它所構(gòu)成的數(shù)字間有什么聯(lián)系嗎？學(xué)生發(fā)現(xiàn):十進(jìn)制就是0-9，七進(jìn)制就是0-7，二進(jìn)制就是0-1，都是從0開始，到的數(shù)比基數(shù)小1.老師：那么五進(jìn)制由什么數(shù)字組成？學(xué)生：0-4大于10的進(jìn)制借助ABCDEF.這些字母來(lái)表示。比如固學(xué)案2、進(jìn)位制的轉(zhuǎn)換3721讀作三千七百二十一，3表示3個(gè)1千，7表示7個(gè)1百，2表示2個(gè)十，一表示1，所以，同理，這些都是十進(jìn)制到十進(jìn)制的計(jì)算，那么由二進(jìn)制到十進(jìn)制怎么轉(zhuǎn)換呢？隨堂練習(xí)：課本48頁(yè)習(xí)題1.3A組第3題（1

8、）、（3）這些都是由k進(jìn)制轉(zhuǎn)換到十進(jìn)制，那么十進(jìn)制如何轉(zhuǎn)換到k進(jìn)制呢？這里我們采用除k取余法，例如：把89化為二進(jìn)制數(shù)。分析：根據(jù)二進(jìn)制數(shù)“滿二進(jìn)一”的原則，可以用2連續(xù)去除89或所得商，然后取余數(shù)。解：2 89 余數(shù)2 44 12 22 02 11 02 5 12 2 12 1 0 0 1也可以用除法算式表示 把上式中各步所得的余數(shù)從下到上排列，得到這就是除k取余法，用來(lái)將十進(jìn)制的數(shù)轉(zhuǎn)換為k進(jìn)制的數(shù)，要注意最后的余數(shù)從下到上排列。三、課堂練習(xí)課本45頁(yè)練習(xí)1、2、3四、課堂小結(jié)本節(jié)課學(xué)習(xí)了幾種古老的算法輾轉(zhuǎn)相除法和更相減損術(shù)，這兩種方法都可以求數(shù)字比較大并且較難發(fā)現(xiàn)公共因子的數(shù)的最大公約數(shù)；秦九韶算法，可