1、基本結(jié)構(gòu)基本結(jié)構(gòu)流程圖流程圖順序結(jié)構(gòu)順序結(jié)構(gòu)變量與賦值變量與賦值循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)基本語句基本語句循環(huán)語句循環(huán)語句條件語句條件語句WHILE語句語句UNTIL語句語句IF-THEN語句語句語句適用結(jié)構(gòu)語句適用結(jié)構(gòu)算法算法條件結(jié)構(gòu)條件結(jié)構(gòu)案例案例1.輾轉(zhuǎn)相除法與更相減損術(shù)輾轉(zhuǎn)相除法與更相減損術(shù)在初中，我們已經(jīng)學(xué)過求最大公約數(shù)的知識，你能在初中，我們已經(jīng)學(xué)過求最大公約數(shù)的知識，你能求出求出18與與30的最大公約數(shù)嗎？的最大公約數(shù)嗎？ 218 30 3 9 15 3 5所以，所以，18和和30的最大公約數(shù)是：的最大公約數(shù)是：236互質(zhì)互質(zhì)因數(shù)因數(shù)但是，當(dāng)我們處理較大數(shù)（如：但是，當(dāng)我們處理較大數(shù)（如：

2、8251與與6105）的最）的最大公因數(shù)時，如果利用這種方法可能計算量比較大，大公因數(shù)時，如果利用這種方法可能計算量比較大，步驟比較多。下面我們介紹一種古老而有效的算步驟比較多。下面我們介紹一種古老而有效的算法法輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法這種算法是這種算法是歐幾里得歐幾里得公元前公元前300年左右首先提出的，因此又年左右首先提出的，因此又叫歐幾里得算法叫歐幾里得算法例例1 求兩個正數(shù)求兩個正數(shù)8251和和6105的最大公約數(shù)。的最大公約數(shù)。 分析：分析：8251與與6105兩數(shù)都比較大，而且沒有明顯的公約數(shù)，兩數(shù)都比較大，而且沒有明顯的公約數(shù)，如能把它們都變小一點，根據(jù)已有的知識即可求出最大公約數(shù)如

3、能把它們都變小一點，根據(jù)已有的知識即可求出最大公約數(shù) 解解8251610512146 顯然顯然8251和和6105的最大公約數(shù)也必是的最大公約數(shù)也必是2146的約數(shù)，的約數(shù)，同樣同樣6105與與2146的公約數(shù)也必是的公約數(shù)也必是8251的約數(shù)，所以的約數(shù)，所以8251與與6105的最大公約數(shù)也是的最大公約數(shù)也是6105與與2146的最大的最大公約數(shù)公約數(shù) 繼續(xù)下去，我們得到：繼續(xù)下去，我們得到：歐幾里得（公元前歐幾里得（公元前330-公元前公元前275）：古希）：古希臘數(shù)學(xué)家，雅典人臘數(shù)學(xué)家，雅典人歐幾里得是歐幾里得是柏拉圖柏拉圖的學(xué)生，長期在亞的學(xué)生，長期在亞歷山大里亞教書。歷山大里亞教書

4、。公元前公元前300年左右，代表作年左右，代表作幾何原本幾何原本13卷問世，創(chuàng)立了著名的卷問世，創(chuàng)立了著名的歐氏幾何歐氏幾何，至今，至今仍為中學(xué)生必學(xué)的一門基礎(chǔ)知識。歐幾里仍為中學(xué)生必學(xué)的一門基礎(chǔ)知識。歐幾里得對光學(xué)也有一定研究。得對光學(xué)也有一定研究。61056105214621462 21813181321462146181318131 1333333181318133333335 51481483333331481482 2373714814837374 40 0則則3737為為82518251與與61056105的最大公約數(shù)的最大公約數(shù) 這就是輾轉(zhuǎn)相除法，有除法的性質(zhì)可以知道，這就是輾轉(zhuǎn)

5、相除法，有除法的性質(zhì)可以知道，對于任意兩個正整數(shù)，上述除法步驟總可以對于任意兩個正整數(shù)，上述除法步驟總可以在有限步驟之后完成在有限步驟之后完成利用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下：利用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下： 第一步：第一步：用較大的數(shù)用較大的數(shù)m除以較小的數(shù)除以較小的數(shù)n得到一個商得到一個商q0和一個余和一個余數(shù)數(shù)r0； 第二步：第二步：若若r00，則，則n為為m，n的最大公約數(shù)；若的最大公約數(shù)；若r00，則用，則用除數(shù)除數(shù)n除以余數(shù)除以余數(shù)r0得到一個商得到一個商q1和一個余數(shù)和一個余數(shù)r1；第三步：第三步：若若r10，則，則r1為為m，n的最大公約數(shù)；若的最大公約數(shù)；若r10，

6、則，則用除數(shù)用除數(shù)r0除以余數(shù)除以余數(shù)r1得到一個商得到一個商q2和一個余數(shù)和一個余數(shù)r2第第n n步：依次計算直至步：依次計算直至r rn n0 0，此時所得到的，此時所得到的r rn n1 1即為所求的即為所求的最大公約數(shù)最大公約數(shù) r= m MOD nm=nn=rr=o?否否是是程序圖框程序圖框帶余除法帶余除法INPUT “請輸入請輸入m，n的值的值”；m，nIF mn THEN a=m m=n n=aEND IFDO r=m MOD N m=n n=rLOOP UNTIL r=0PRINT mEND作用是什么？作用是什么？為什么要用為什么要用直到型循環(huán)直到型循環(huán)結(jié)構(gòu)？結(jié)構(gòu)？1.1.利用

7、輾轉(zhuǎn)相除法求兩數(shù)利用輾轉(zhuǎn)相除法求兩數(shù)40814081與與2072320723的最大公約的最大公約數(shù)數(shù) ，寫出它的流程框圖和，寫出它的流程框圖和BASICBASIC程序程序更相減損術(shù)更相減損術(shù) 我國早期也有解決求最大公約數(shù)問題的算法我國早期也有解決求最大公約數(shù)問題的算法 九章算術(shù)九章算術(shù)（公元（公元50年年100年或更早年或更早 ）是中國古代數(shù)學(xué)專著，）是中國古代數(shù)學(xué)專著，承先秦數(shù)學(xué)發(fā)展的源流，進(jìn)入漢承先秦數(shù)學(xué)發(fā)展的源流，進(jìn)入漢朝后又經(jīng)許多學(xué)者的刪補(bǔ)才最后朝后又經(jīng)許多學(xué)者的刪補(bǔ)才最后成書，這大約是公元一世紀(jì)的下成書，這大約是公元一世紀(jì)的下半葉。它的出現(xiàn)，標(biāo)志著中國古半葉。它的出現(xiàn)，標(biāo)志著中國古代

8、數(shù)學(xué)體系的形成。代數(shù)學(xué)體系的形成。 歷代數(shù)學(xué)家把它尊為歷代數(shù)學(xué)家把它尊為“算經(jīng)之首算經(jīng)之首”這是世這是世界上最早的印刷本數(shù)學(xué)書。界上最早的印刷本數(shù)學(xué)書。 九章算術(shù)九章算術(shù)共收有共收有 246246個數(shù)學(xué)問題，分個數(shù)學(xué)問題，分為九章。分別是：方田、栗米、衰分、少廣、為九章。分別是：方田、栗米、衰分、少廣、商功、均輸、盈不足、方程、勾股。商功、均輸、盈不足、方程、勾股。 九章算術(shù)九章算術(shù)是世界上最早系統(tǒng)敘述了分是世界上最早系統(tǒng)敘述了分?jǐn)?shù)運(yùn)算的著作；其中盈不足的算法更是一項數(shù)運(yùn)算的著作；其中盈不足的算法更是一項令人驚奇的創(chuàng)造；令人驚奇的創(chuàng)造；“方程方程”章還在世界數(shù)學(xué)章還在世界數(shù)學(xué)史上首次闡述了負(fù)數(shù)

9、及其加減運(yùn)算法則。史上首次闡述了負(fù)數(shù)及其加減運(yùn)算法則。更相減損術(shù)求最大公約數(shù)的步驟如下：可半者半之，不可半更相減損術(shù)求最大公約數(shù)的步驟如下：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。以等數(shù)約之。翻譯出來為：翻譯出來為：第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用用2約簡；若不是，執(zhí)行第二步。約簡；若不是，執(zhí)行第二步。第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小

10、數(shù)。得的差比較，并以大數(shù)減小數(shù)。第三部：繼續(xù)第二步，直到所得的數(shù)相等為止，則這個數(shù)第三部：繼續(xù)第二步，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）就是所求的最大公約數(shù)（等數(shù)）就是所求的最大公約數(shù)例例2 2 用更相減損術(shù)求用更相減損術(shù)求9898與與6363的最大公約數(shù)的最大公約數(shù). . 解解 由于由于6363不是偶數(shù)，把不是偶數(shù)，把9898和和6363以大數(shù)減小數(shù)，以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減并輾轉(zhuǎn)相減 98-6398-63353563-3563-35282835-2835-287 728-728-7141414-714-77 7所以，所以，98與與63的最大公約數(shù)是的最大公約數(shù)是7 比較輾轉(zhuǎn)相除法與更相

11、減損術(shù)的區(qū)別比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別 （1）都是求最大公約數(shù)的方法，計算上）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法以以除法除法為為主，主，更相減損術(shù)更相減損術(shù)以以減法減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當(dāng)兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)數(shù)相對較少，特別當(dāng)兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。別較明顯。（2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到則得到，而更相減損術(shù)則以減數(shù)與差相等而得到一一. .用輾轉(zhuǎn)相除法求

12、下列各組數(shù)的最大公約數(shù)用輾轉(zhuǎn)相除法求下列各組數(shù)的最大公約數(shù)（1 1）225225，135 135 （2 2）9898，196 196 （3 3）7272，168168二：二：用更相減損法可否求上述用更相減損法可否求上述3組數(shù)的最大公約數(shù)？組數(shù)的最大公約數(shù)？三：三：利用輾轉(zhuǎn)相除法是否可以求兩數(shù)的最大公倍數(shù)？利用輾轉(zhuǎn)相除法是否可以求兩數(shù)的最大公倍數(shù)？ 案例案例2 秦九韶算法秦九韶算法案例二（秦九韶算法）怎樣求多項式案例二（秦九韶算法）怎樣求多項式1)(2354xxxxxxf當(dāng)當(dāng)x=5時的值？時的值？據(jù)我們的計算統(tǒng)計可以得出我們共需要據(jù)我們的計算統(tǒng)計可以得出我們共需要10次乘法運(yùn)次乘法運(yùn)算，算，5次

13、加法運(yùn)算次加法運(yùn)算 我們把多項式變形為：我們把多項式變形為： 再統(tǒng)計一下計算當(dāng)時的值時需要的計算次數(shù)，可以得再統(tǒng)計一下計算當(dāng)時的值時需要的計算次數(shù)，可以得出僅需出僅需4次乘法和次乘法和5次加法運(yùn)算即可得出結(jié)果。顯然少次加法運(yùn)算即可得出結(jié)果。顯然少了了6次乘法運(yùn)算。這種算法就叫次乘法運(yùn)算。這種算法就叫秦九韶算法秦九韶算法。1)1 (1 (1 ()(2xxxxxxf秦九韶（秦九韶（1202-1261年），年），字道古，安岳縣人。其父秦字道古，安岳縣人。其父秦季棲，進(jìn)士出身，官至工部季棲，進(jìn)士出身，官至工部郎中、秘書少監(jiān)。秦九韶性郎中、秘書少監(jiān)。秦九韶性敏慧，勤奮好學(xué)，幼年隨父敏慧，勤奮好學(xué)，幼年隨

14、父居中都（今北京），受到名居中都（今北京），受到名師指導(dǎo)，學(xué)習(xí)日益增進(jìn)。及師指導(dǎo)，學(xué)習(xí)日益增進(jìn)。及長，隨父遷湖州（今浙江吳長，隨父遷湖州（今浙江吳興縣），在西門外修建住房，興縣），在西門外修建住房，由秦九韶設(shè)計施工，堂分由秦九韶設(shè)計施工，堂分7間，間，后為列室，僅中堂后為列室，僅中堂1間，縱橫間，縱橫7丈，極其宏偉寬敞，顯示出丈，極其宏偉寬敞，顯示出他在建筑方面的才能他在建筑方面的才能 01210123120132211012211)()()()(aaxaxaxaaxaxaxaxaaxaxaxaxaaxaxaxaxaxfnnnnnnnnnnnnnnnnnnn把一個多項式把一個多項式012211

15、)(axaxaxaxaxfnnnnnn改寫為：改寫為：求多項式的值時，首先計算最內(nèi)層括號內(nèi)的一次多項式的求多項式的值時，首先計算最內(nèi)層括號內(nèi)的一次多項式的值，即：值，即：11nnaxav01323212avvaxvvaxvvnnnn再有內(nèi)向外逐層計算一次多項式的值，即：再有內(nèi)向外逐層計算一次多項式的值，即：這樣將求這樣將求n次多項式次多項式f(x)的值轉(zhuǎn)化為求的值轉(zhuǎn)化為求n個一次多項式的值。個一次多項式的值。例例3 3 設(shè)計利用秦九韶算法計算設(shè)計利用秦九韶算法計算5 5次多項式次多項式 0122334455)(axaxaxaxaxaxf當(dāng)當(dāng)0 xx 時的值的程序框圖以及時的值的程序框圖以及BA

16、SIC程序。程序。 ENDvPRINTWEND1nnax*vvav5nWHILEx;XINPUTa,a,a,a,a,a;aa)x( fINPUTn5050O543210n0 的的值值請請輸輸入入的的系系數(shù)數(shù)請請輸輸入入i=0WHILE i5INPUT aiWENDDOv=a5v=v*x0+a5-nn=n+1LOOP UNTIL n6END用秦九韶算法求這個多項式當(dāng)用秦九韶算法求這個多項式當(dāng) 時的值。時的值。8 . 07 . 16 . 25 . 325)(2345xxxxxxf5x3. 3. 已知一個已知一個5 5次多項式為次多項式為思考：思考：（1）例）例1計算時需要多少次乘法計算？多少次加法

17、計算時需要多少次乘法計算？多少次加法計算？計算？（2）在利用秦九韶算法計算）在利用秦九韶算法計算n次多項式當(dāng)時需要多次多項式當(dāng)時需要多少次乘法計算和多少次加法計算？少次乘法計算和多少次加法計算？案例案例3 進(jìn)位制進(jìn)位制 問題問題11我們常見的數(shù)字都是十進(jìn)制的我們常見的數(shù)字都是十進(jìn)制的, ,但是并不是生活中的每一種數(shù)字都是十進(jìn)制的但是并不是生活中的每一種數(shù)字都是十進(jìn)制的. .比如時間和角度的單位用六十進(jìn)位制比如時間和角度的單位用六十進(jìn)位制, ,電子計電子計算機(jī)用的是二進(jìn)制算機(jī)用的是二進(jìn)制. .那么什么是進(jìn)位制那么什么是進(jìn)位制? ?不同的不同的進(jìn)位制之間又有什么聯(lián)系呢進(jìn)位制之間又有什么聯(lián)系呢? ?

18、進(jìn)位制進(jìn)位制是人們?yōu)榱擞嫈?shù)和運(yùn)算的方便而是人們?yōu)榱擞嫈?shù)和運(yùn)算的方便而約定的一種記數(shù)系統(tǒng)，約定滿二進(jìn)一約定的一種記數(shù)系統(tǒng)，約定滿二進(jìn)一, ,就是二就是二進(jìn)制進(jìn)制; ;滿十進(jìn)一滿十進(jìn)一, ,就是十進(jìn)制就是十進(jìn)制; ;滿十六進(jìn)一滿十六進(jìn)一, ,就就是十六進(jìn)制是十六進(jìn)制; ;等等等等. . “滿幾進(jìn)一滿幾進(jìn)一”,就是就是幾進(jìn)制幾進(jìn)制,幾進(jìn)制的幾進(jìn)制的基數(shù)基數(shù)就是幾就是幾.可使用數(shù)字符號的個數(shù)稱為基數(shù)可使用數(shù)字符號的個數(shù)稱為基數(shù). .基數(shù)基數(shù)都是大于都是大于1 1的整數(shù)的整數(shù). . （1）二進(jìn)制可使用的數(shù)字有）二進(jìn)制可使用的數(shù)字有0和和1,基數(shù)是基數(shù)是2;（2）十進(jìn)制可使用的數(shù)字有）十進(jìn)制可使用的數(shù)字有

19、0,1,2,8,9等十個數(shù)字等十個數(shù)字,基數(shù)是基數(shù)是10;（3）十六進(jìn)制可使用的數(shù)字或符號有）十六進(jìn)制可使用的數(shù)字或符號有09等等10個數(shù)字個數(shù)字以及以及AF等等6個字母個字母(規(guī)定字母規(guī)定字母AF對應(yīng)對應(yīng)1015),十六進(jìn)十六進(jìn)制的基數(shù)是制的基數(shù)是16.注意注意: :為了區(qū)分不同的進(jìn)位制為了區(qū)分不同的進(jìn)位制, ,常在數(shù)字的右下腳標(biāo)常在數(shù)字的右下腳標(biāo)明基數(shù)明基數(shù), ,如如111001111001(2)(2)表示二進(jìn)制數(shù)表示二進(jìn)制數(shù),34,34(5)(5)表示表示5 5進(jìn)制數(shù)進(jìn)制數(shù). .十進(jìn)制數(shù)一般不標(biāo)注基數(shù)十進(jìn)制數(shù)一般不標(biāo)注基數(shù).問題問題2十進(jìn)制數(shù)十進(jìn)制數(shù)3721中的中的3表示表示3個千個千,

20、7表示表示7個百個百,2表示表示2個十個十,1表示表示1個一個一,從而它可以寫成下面的形式從而它可以寫成下面的形式:3721=3103+7102+2101+1100.想一想二進(jìn)制數(shù)想一想二進(jìn)制數(shù)1011(2)可以類似的寫成什么形式可以類似的寫成什么形式?1011(2)=123+022+121+120.3421(5)=353+452+251+150.C7A16(16)=12164+7163+10162 +1161+6160.一般地一般地,若若k是一個大于是一個大于1的整數(shù)的整數(shù),那么以那么以k為為基數(shù)的基數(shù)的k進(jìn)制數(shù)可以表示為一串?dāng)?shù)字連寫在一進(jìn)制數(shù)可以表示為一串?dāng)?shù)字連寫在一起的形式起的形式ana

21、n-1a1a0(k) (0ank,0an-1,a1,a0k)意思是意思是:(1):(1)第一個數(shù)字第一個數(shù)字a an n不能等于不能等于0;0;(2)(2)每一個數(shù)字每一個數(shù)字a an n,a,an-1n-1, ,a,a1 1,a,a0 0都須小于都須小于k.k.k進(jìn)制的數(shù)也可以表示成不同位上數(shù)字與進(jìn)制的數(shù)也可以表示成不同位上數(shù)字與基數(shù)基數(shù)k的冪的乘積之和的形式的冪的乘積之和的形式,即即anan-1a1a0(k)=ankn+an-1kn-1 +a1k1+a0k0 .注意這是一注意這是一個個n+1位數(shù)位數(shù).問題問題3二進(jìn)制只用二進(jìn)制只用0和和1兩個數(shù)字兩個數(shù)字,這這正好與電路的正好與電路的通通和

22、和斷斷兩種狀態(tài)相對應(yīng)兩種狀態(tài)相對應(yīng),因因此此計算機(jī)內(nèi)部都使用二進(jìn)制計算機(jī)內(nèi)部都使用二進(jìn)制.計算機(jī)在進(jìn)計算機(jī)在進(jìn)行數(shù)的運(yùn)算時行數(shù)的運(yùn)算時,先把接受到的數(shù)轉(zhuǎn)化成二先把接受到的數(shù)轉(zhuǎn)化成二進(jìn)制數(shù)進(jìn)行運(yùn)算進(jìn)制數(shù)進(jìn)行運(yùn)算,再把運(yùn)算結(jié)果轉(zhuǎn)化為十再把運(yùn)算結(jié)果轉(zhuǎn)化為十進(jìn)制數(shù)輸出進(jìn)制數(shù)輸出. 那么二進(jìn)制數(shù)與十進(jìn)制數(shù)之間是那么二進(jìn)制數(shù)與十進(jìn)制數(shù)之間是如何轉(zhuǎn)化的呢如何轉(zhuǎn)化的呢? ?例例1:把二進(jìn)制數(shù)把二進(jìn)制數(shù)110011(2)化為十進(jìn)制數(shù)化為十進(jìn)制數(shù).分析分析:先把二進(jìn)制數(shù)寫成不同位上數(shù)字與先把二進(jìn)制數(shù)寫成不同位上數(shù)字與2的冪的乘積之和的形式的冪的乘積之和的形式,再按照十進(jìn)制數(shù)的運(yùn)算再按照十進(jìn)制數(shù)的運(yùn)算規(guī)則計算出結(jié)果

23、規(guī)則計算出結(jié)果.解解:110011(2) =125+124+023+022+121+120 =132+116+12+1=51. k進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)的方法進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)的方法先把先把k進(jìn)制的數(shù)表示成不同位上數(shù)字進(jìn)制的數(shù)表示成不同位上數(shù)字與基數(shù)與基數(shù)k的冪的乘積之和的形式的冪的乘積之和的形式,即即anan-1a1a0(k)=ankn+an-1kn-1+a1k1+a0k0 .再按照十進(jìn)制數(shù)的運(yùn)算規(guī)則計算出結(jié)果再按照十進(jìn)制數(shù)的運(yùn)算規(guī)則計算出結(jié)果.例：例：10231（4）=_（10） 235（7）=_（10）301124例例2:把把89化為二進(jìn)制的數(shù)化為二進(jìn)制的數(shù).分析分析:把把89化為二進(jìn)制的數(shù)化為二進(jìn)制的數(shù),需想辦法將需想辦法將89先寫先寫成如下形式成如下形式89=an2n+an-12n-1+a121+a020 . 十進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)轉(zhuǎn)化為k進(jìn)制數(shù)的方法進(jìn)制數(shù)的方法89=442+1, =(222+0)2+1 =(112+0)2+0)2+1 =(52+1)2+0)2+0)2+1 =(22+1)2+1)2+0) 2+0)2+1 =(12)+0)2+1)2+1)2+0) 2+0)2+1=126+025+