高中數(shù)學(xué)必修3第一章算法初步

高中數(shù)學(xué)必修3第一章算法初步第一頁，共45頁。算法知識結(jié)構(gòu)：基本概念算法基本結(jié)構(gòu)表示方法應(yīng)用自然語言程序框圖基本算法語句順序結(jié)構(gòu)條件結(jié)構(gòu)循環(huán)結(jié)構(gòu)輾轉(zhuǎn)相除法和更相減損數(shù)秦九韶算法進位制賦值語句條件語句循環(huán)語句輸入、輸出語句第一頁第二頁，共45頁。算法的定義：

通常指可以用計算機來解決的某一類問題的程序或步驟，這些程序或步驟必須是明確和有效的，而且能夠在有限步之內(nèi)完成。算法最重要的特征：1.有序性2.確定性3.有限性第二頁第三頁，共45頁。算法的基本特點1、有限性一個算法應(yīng)包括有限的操作步驟，能在執(zhí)行有窮的操作步驟之后結(jié)束。2、確定性算法的計算規(guī)則及相應(yīng)的計算步驟必須是唯一確定的，既不能含糊其詞，也不能有二義性。3、有序性算法中的每一個步驟都是有順序的,前一步是后一步的前提,只有執(zhí)行完前一步后,才能執(zhí)行后一步,有著很強邏輯性的步驟序列。第三頁第四頁，共45頁。

用程序框、流程線及文字說明來表示算法的圖形稱為程序框圖，它使算法步驟顯得直觀、清晰、簡明.終端框(起止框)

輸入、輸出框

處理框(執(zhí)行框)

判斷框

流程線○連接點二、程序框圖第四頁第五頁，共45頁。程序框圖又稱流程圖，是一種用規(guī)定的圖形，指向線及文字說明來準確、直觀地表示算法的圖形。程序框名稱功能終端框（起止框）表示一個算法的起始和結(jié)束輸入、輸出框表示算法的輸入和輸出的信息處理框（執(zhí)行框）賦值、計算判斷框判斷一個條件是否成立，用“是”、“否”或“Y”、“N”標明第五頁第六頁，共45頁。二、程序框圖1、順序結(jié)構(gòu)

2、條件結(jié)構(gòu)

3、循環(huán)結(jié)構(gòu)步驟n步驟n+1滿足條件？步驟A步驟B是否滿足條件？步驟A是否循環(huán)體滿足條件?否是循環(huán)體滿足條件?是否先做后判，否去循環(huán)先判后做，是去循環(huán)第六頁第七頁，共45頁。二、程序框圖1、順序結(jié)構(gòu)設(shè)計一算法,求和1+2+3+…+100，并畫出程序框圖。算法：第一步：取n=100；第二步：計算；第三步：輸出結(jié)果。開始結(jié)束輸入n=100s=(n+1)n/2輸出s第七頁第八頁，共45頁。二、程序框圖2、條件結(jié)構(gòu)算法：第一步：輸入x;第二步：如果x≥0；則輸出x；否則輸出－x。設(shè)計一個算法，求數(shù)x的絕對值，并畫出程序框圖。YN結(jié)束x≥0輸入x開始輸出x輸出-x算法分析：實數(shù)X的絕對值第八頁第九頁，共45頁。二、程序框圖3、循環(huán)結(jié)構(gòu)AP是否否

是AP（A）AP否是（C）是

否AP（B）（D）直到型循環(huán)結(jié)構(gòu)對應(yīng)的程序框圖是當型循環(huán)結(jié)構(gòu)對應(yīng)的程序框圖是直到型循環(huán)結(jié)構(gòu)當型循環(huán)結(jié)構(gòu)

AD第九頁第十頁，共45頁。

設(shè)計一個計算1+2+3+……+100的值的算法，并畫出程序框圖。算法：第一步：令i=1,s=0;第二步：s=s+i第三步：i=i+1；第四步：直到i＞100時,輸出S，結(jié)束算法，否則返回第二步。程序框圖如下：i>100?i=1開始輸出s結(jié)束否是s=0i=i+1s=s+i否

是循環(huán)體條件循環(huán)結(jié)構(gòu)直到型循環(huán)結(jié)構(gòu)第十頁第十一頁，共45頁。

設(shè)計一個計算1+2+3+……+100的值的算法，并畫出程序框圖。算法：第一步：令i=1,s=0;第二步：若i<=100成立，則執(zhí)行第三步；否則，輸出s，結(jié)束算法；第三步：s=s+i；第四步：i=i+1,返回第二步。i<=100?i=1開始輸出s結(jié)束否是s=0i=i+1s=s+i當型循環(huán)結(jié)構(gòu)程序框圖如下：循環(huán)體條件是否第十一頁第十二頁，共45頁。語句一般格式主要功能說明1.輸入語句2.輸出語句3.賦值語句INPUT“提示內(nèi)容”;變量PRINT“提示內(nèi)容”;表達式變量＝表達式可對程序中的變量賦值可輸出表達式的值，計算可對程序中的變量賦值，計算（1）提示內(nèi)容和它后面的“；”可以省略（2）一個語句可以給多個變量賦值，中間用“，”分隔（3）無計算功能（1）表達式可以是變量，計算公式，或系統(tǒng)信息（2）一個語句可以輸入多個表達式，中間用“，”分隔（3）有計算功能（1）“=”的右側(cè)必須是表達式，左側(cè)必須是變量（2）一個語句只能給一個變量賦（3）有計算功能三．五種基本算法語句第十二頁第十三頁，共45頁。（4）條件語句IF-THEN-ELSE格式

IF-THEN格式

IF

條件THEN語句1ELSE語句2ENDIF滿足條件？語句1語句2是否IF

條件THEN語句ENDIF滿足條件？語句是否第十三頁第十四頁，共45頁。（5）循環(huán)語句①WHILE語句②UNTIL語句WHILE

條件循環(huán)體WEND滿足條件？循環(huán)體是否DO循環(huán)體LOOPUNTIL條件滿足條件？循環(huán)體是否第十四頁第十五頁，共45頁。

成立AP不成立AP成立不成立While（當型）循環(huán)Until（直到型）循環(huán)兩種循環(huán)結(jié)構(gòu)有什么差別？先執(zhí)行循環(huán)體，然后再檢查條件是否成立，如果不成立就重復(fù)執(zhí)行循環(huán)體，直到條件成立退出循環(huán)。先判斷指定的條件是否為真，若條件為真，執(zhí)行循環(huán)條件，條件為假時退出循環(huán)。先執(zhí)行后判斷先判斷后執(zhí)行第十五頁第十六頁，共45頁。編寫程序,求和1+2+3+…+n。開始結(jié)束輸入ns=(n+1)n/2輸出sINPUTns=(n+1)n/2*PRINT“S=”;S程序語句：輸入語句賦值語句輸出語句順序結(jié)構(gòu)：END變量=表達式第十六頁第十七頁，共45頁。練：編寫一程序，求實數(shù)X的絕對值。條件結(jié)構(gòu)：開始輸入XX≥0輸出X輸出－X結(jié)束YNIFX>=0THENPRINTXELSEPRINT-XENDIF程序:INPUTXEND條件語句：第十七頁第十八頁，共45頁。i=1S=0WHILEi<=100S=S+ii=i+1WENDPRINTSEND當型循環(huán)語句當型循環(huán)語句練：設(shè)計一算法,求和1+2+3+…+100。循環(huán)體條件是否WHILE條件循環(huán)體WEND開始

結(jié)束

輸出S是否程序框圖：程序語句：當型循環(huán)結(jié)構(gòu)第十八頁第十九頁，共45頁。i=1S=0DOS=S+ii=i+1LOOPUNTIL

i>100PRINTSEND開始結(jié)束

輸出S直到型循環(huán)語句直到型循環(huán)語句否是否

是循環(huán)體條件DO循環(huán)體LOOPUNTIL

條件直到型循環(huán)結(jié)構(gòu)第十九頁第二十頁，共45頁。一、輾轉(zhuǎn)相除法（歐幾里得算法）1、定義：所謂輾轉(zhuǎn)相除法，就是對于給定的兩個數(shù)，用較大的數(shù)除以較小的數(shù)。若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則這時較小的數(shù)就是原來兩個數(shù)的最大公約數(shù)。第二十頁第二十一頁，共45頁。(1)、算法步驟：第一步：輸入兩個正整數(shù)

m,n(m>n).第二步：計算m除以n所得的余數(shù)r.第三步：m=n,n=r.第四步：若r＝0,則m,n的最大公約數(shù)等于m；否則轉(zhuǎn)到第二步.第五步：輸出最大公約數(shù)m.第二十一頁第二十二頁，共45頁。以求8251和6105的最大公約數(shù)的過程為例步驟：8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0顯然37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù)第二十二頁第二十三頁，共45頁。更相減損術(shù)

可半者半之，不可半者，副置分母、子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之。第一步：任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡；若不是則執(zhí)行第二步。第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的減數(shù)和差相等為止，則這個等數(shù)就是所求的最大公約數(shù)。（1）、《九章算術(shù)》中的更相減損術(shù)：1、背景介紹：（2）、現(xiàn)代數(shù)學(xué)中的更相減損術(shù)：第二十三頁第二十四頁，共45頁。2、定義：

所謂更相減損術(shù)，就是對于給定的兩個數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對數(shù)，再用較大的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等，此時相等的兩數(shù)便為原來兩個數(shù)的最大公約數(shù)。第二十四頁第二十五頁，共45頁。例:用更相減損術(shù)求98與63的最大公約數(shù).解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減98－63＝35

63－35＝28

35－28＝7

28－7＝2121－7＝2114－7＝7所以，98和63的最大公約數(shù)等于73、方法：第二十五頁第二十六頁，共45頁。比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別（1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。（2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到。第二十六頁第二十七頁，共45頁。1、用更相減損術(shù)求兩個正數(shù)84與72的最大公約數(shù)．

練習(xí)：思路分析：先約簡，再求21與18的最大公約數(shù),然后乘以兩次約簡的質(zhì)因數(shù)4。2、求324、243、135這三個數(shù)的最大公約數(shù)。思路分析：求三個數(shù)的最大公約數(shù)可以先求出兩個數(shù)的最大公約數(shù)，第三個數(shù)與前兩個數(shù)的最大公約數(shù)的最大公約數(shù)即為所求。第二十七頁第二十八頁，共45頁?！稊?shù)書九章》——秦九韶算法設(shè)是一個n次的多項式對該多項式按下面的方式進行改寫：第二十八頁第二十九頁，共45頁。要求多項式的值，應(yīng)該先算最內(nèi)層的一次多項式的值，即然后，由內(nèi)到外逐層計算一次多項式的值，即這種將求一個n次多項式f(x)的值轉(zhuǎn)化成求n個一次多項式的值的方法，稱為秦九韶算法。思考：在求多項式的值上，這是怎樣的一個轉(zhuǎn)化？第二十九頁第三十頁，共45頁。

通過一次式的反復(fù)計算，逐步得出高次多項式的值，對于一個n次多項式，只需做n次乘法和n次加法即可。秦九韶算法的特點：在秦九韶算法中反復(fù)執(zhí)行的步驟，可用循環(huán)結(jié)構(gòu)來實現(xiàn)。第三十頁第三十一頁，共45頁。例:用秦九韶算法求多項式 f(x)=2x5-5x4-4x3+3x2-6x+7當x=5時的值.解法一:首先將原多項式改寫成如下形式: f(x)=((((2x-5)x-4)x+3)x-6)x+7v0=2v1=v0x-5=2×5-5=5v2=v1x-4=5×5-4=21v3=v2x+3=21×5+3=108v4=v3x-6=108×5-6=534v5=v4x+7=534×5+7=2677所以,當x=5時,多項式的值是2677.然后由內(nèi)向外逐層計算一次多項式的值,即第三十一頁第三十二頁，共45頁。2-5-43-67x=5105252110510854053426702677所以,當x=5時,多項式的值是2677.原多項式的系數(shù)多項式的值.例.用秦九韶算法求多項式 f(x)=2x5-5x4-4x3+3x2-6x+7當x=5時的值.解法二:列表2第三十二頁第三十三頁，共45頁。一、進位制進位制是人們?yōu)榱擞嫈?shù)和運算方便而約定的記數(shù)系統(tǒng)。進位制是一種記數(shù)方式，用有限的數(shù)字在不同的位置表示不同的數(shù)值?？墒褂脭?shù)字符號的個數(shù)稱為基數(shù)，基數(shù)為n，即可稱n進位制，簡稱n進制。“滿幾進一”就是幾進制，幾進制的基數(shù)就是幾.基數(shù)：二進制、七進制、八進制、十二進制、六十進制等二進制只有0和1兩個數(shù)字，七進制用0~6七個數(shù)字十六進制有0~9十個數(shù)字及ABCDEF六個字母.第三十三頁第三十四頁，共45頁。

式中1處在百位，第一個3所在十位，第二個3所在個位，5和9分別處在十分位和百分位。十進制數(shù)是逢十進一的。

我們最常用最熟悉的就是十進制數(shù)，它的數(shù)值部分是十個不同的數(shù)字符號0，1，2，3，4，5，6，7，8，9來表示的。十進制：例如133.59，它可用一個多項式來表示：133.59=1*102+3*101+3*100+5*10-1+9*10-2第三十四頁第三十五頁，共45頁。

為了區(qū)分不同的進位制，常在數(shù)的右下角標明基數(shù)，十進制一般不標注基數(shù).例如十進制的133.59，寫成133.59(10)七進制的13，寫成13(7)；二進制的10，寫成10(2)

一般地，若k是一個大于1的整數(shù)，那么以k為基數(shù)的k進制可以表示為一串數(shù)字連寫在一起的形式：第三十五頁第三十六頁，共45頁。二進制與十進制的轉(zhuǎn)換1、二進制數(shù)轉(zhuǎn)化為十進制數(shù)例1：將二進制數(shù)110011(2)化成十進制數(shù)。解：根據(jù)進位制的定義可知所以，110011（2）=51．把其他進位制的數(shù)化為十進制數(shù)的公式是什么？第三十六頁第三十七頁，共45頁。方法：除2取余法，即用2連續(xù)去除89或所得的商，然后取余數(shù)。例、把89化為二進制數(shù)解：根據(jù)“逢二進一”的原則，有89＝2×44＋1＝2×

(2×22＋0)+1＝2×(2×(2×11＋0)+0)+1＝2×(2×(2×

(2×5＋1)+0)+0)+15＝2×2＋1＝2×（2×（2×（2×（22＋1）＋1）＋0）＋0）＋189＝1×26＋0×25＋1×24＋1×23＋0×22＋0×21＋1×20所以：89=1011001（2）＝2×（2×（2×（23＋2＋1）＋0）＋0）＋1＝2×（2×（24＋22＋2＋0）＋0）＋1＝2×（25＋23+22＋0＋0）＋1＝26＋24+23＋0＋0＋2089＝2×44＋144＝2×22＋022＝2×11＋011＝2×

5＋1＝2×(2×(2×(2×

(2×2＋1)+1)+0)+0)+1所以89＝2×（2×（2×（2×（2×2＋1）＋1）＋0）＋0）＋1十進制轉(zhuǎn)換為二進制第三十七頁第三十八頁，共45頁。注意：1.最后一步商為0，2.將上式各步所得的余數(shù)從下到上排列，得到：

89=1011001（2）另解（除2取余法的另一直觀寫法）：522212010余數(shù)11224489222201101練習(xí)將下面的十進制數(shù)化為二進制數(shù)？（1）10（2）20第三十八頁第三十九頁，共45頁。例：把89化為五進制數(shù)。解：根據(jù)除k取余法以5作為除數(shù)，相應(yīng)的除法算式為：所以，89=324（5）895175350423余數(shù)除k取余法：十進制數(shù)轉(zhuǎn)化為k進制數(shù)的方法

用k連續(xù)去除該