高中數(shù)學《算法案例分析》學案1北師大版必修3

1、算法部分章質量檢測本章知識結構算法程序框圖算法語句輾轉相除法與更相減損術排序進位制秦九韶算法一、知識點剖析1算法的定義和特點掌握要點：算法定義：在數(shù)學中指按照一定規(guī)則解決某一類問題的明確和有限的步驟。算法特點：有窮性：一個算法的步驟是有限的，它應在有限步操作之后停止。確定性，算法的每一步操作必須是明確的，不能有歧義或模糊且算法執(zhí)行后一定產(chǎn)生確定的結果，不能模棱兩可?？尚行裕核惴◤某跏疾襟E開始，分為若干明確的步驟，每一個步驟只能有一個明確的后繼步驟，前一步是后一步的前提,只有執(zhí)行完前一步才能進行下一步，并且每一步都要準確無誤才能解決問題。不惟一性：求解某一類問題的算法是不惟一的，對于一個問題可以

2、有不同的算法。普遍性，很多具體的問題都可以設計合理的算法解決。易混易錯 ： （1）算法一般是機械的，有時要進行大量重復的運算，只要按部就班的做總能算出結果，通常把算法過程稱為“數(shù)學機械化”， “數(shù)學機械化”的最大優(yōu)點是它可以讓計算機來完成。（2）實際上，處理任何問題都需要算法。如，郵購物品有其相應的手續(xù)。購買飛機票也有一定的手續(xù)等。 （3）求解某個問題的算法不惟一。2 （1）程序框圖表示算法步驟的一些常用的圖形和符號圖形符號名稱功能終端框（起止框）程序的開始和結束，輸入、輸出框表示數(shù)據(jù)的輸入或結果的輸出處理框賦值 , 計算判斷框判斷某一條件是否成立，成立時在出口處標明：“是”或“yes ” ；

3、 不成立時在出口處標明“否”或”no ”流程線連接程序框連接點連接程序框圖的兩部分易混易錯： 在所給的上述符號之中只有判斷框有一個入口和兩個出口，它是唯一有兩個退出點的符號。（2）三種基本邏輯結構順序結構條件結構循環(huán)結構順序結構 ：順序結構是最簡單的算法結構，語句與語句之間，框與框之間是按從上到下的順序進行的。這是任何一個算法都離不開的基本結構。條件結構： 在一個算法中，經(jīng)常會遇到一些條件的判斷，算法的流程根據(jù)條件是否成立會有不同的流向，條件結構就是處理這種過程的結構。易混易錯 ： 在條件結構中無論條件是否成立，都只能執(zhí)行兩框之一，兩框不可能同時執(zhí)行，也不可能兩框都不執(zhí)行。循環(huán)結構： 算法結構

4、中經(jīng)常會遇到從某處開始，按照一定條件反復執(zhí)行某些步驟的情況，這就是循環(huán)結構，反復執(zhí)行的步驟成為循環(huán)體。循環(huán)結構分為兩種：當性循環(huán)結構和直到性循環(huán)結構。當性循環(huán)結構：在每次執(zhí)行循環(huán)體前，對條件進行判斷，當條件滿足時，執(zhí)行循環(huán)體，否則終止循環(huán)?！跋扰袛唷敝钡叫匝h(huán)結構：在執(zhí)行了一次循環(huán)體后，對條件進行判斷，如果條件不滿足就繼續(xù)執(zhí)行循環(huán)體，直到條件滿足時終止循環(huán)?！跋妊h(huán)”注意： 循環(huán)結構中一定包含著條件結構。3基本算法語句（1）輸入語句輸入語句的一般形式是：input “提示內容”；變量輸入語句的作用是實現(xiàn)算法的輸入信息功能“提示內容”提示用戶輸入什么樣的信息輸入語句可以給變量提供初值提示內容與變

5、量之間用分號隔開，若輸入多個變量，變量之間用逗號隔開。例如： input “提示內容1，提示內容2，提示內容3，”；變量 1，變量 2，變量（2）輸出語句輸出語句的一般形式是：print “提示內容”；表達式輸出語句的作用是實現(xiàn)算法的輸出結果功能?！疤崾緝热荨碧崾居脩糨斎胧裁礃拥男畔?，如print “s=；s 是提示輸出的結果是s的值print語句可以在屏幕上出現(xiàn)常量、變量以及系統(tǒng)信息。注意 ：任何求解問題的算法，都要把求解問題的結果輸出。（3）賦值語句賦值語句是最基本的語句賦值語句的一般格式為：變量=表達式“ =”叫做賦值號。易混易錯 :賦值號做變只能是變量而不能使表達式。賦值號的左右兩邊不

6、能調換。不能利用賦值語句進行代數(shù)式的演算（如化簡、因式分解、解方程等）。賦值號與數(shù)學中的符號意義不同。注意 : 輸入語句、輸出語句、賦值語句基本上對應程序框圖中的順序結構；一個算法有0 個或者多個輸入，有一個或多個輸出；輸出語句和賦值語句具有運算功能而輸入語句不具有運算功能。（4）條件語句共分為兩種形式 if-then-else 格式(1) 當計算機執(zhí)行上述語句時，首先對if 后的條件進行判斷，如果條件符合，就執(zhí)行then后的語句 1，否則執(zhí)行else后的語句 2。其對應的程序框圖為：（如上右圖） if-then 格式計算機執(zhí)行這種形式的條件語句時，也是首先對if 后的條件進行判斷，如果條件符

7、合，就執(zhí)行 then后的語句，如果條件不符合，則直接結束該條件語句，轉而執(zhí)行其他語句。其對應的程序框圖為： （如上右圖）條件語句的作用：在程序執(zhí)行過程中，根據(jù)判斷是否滿足約定的條件而決定是否需要轉換到何處去。需要計算機按條件進行分析、比較、判斷，并按判斷后的不同情況進行不同的處理。（5）循環(huán)語句算法中的循環(huán)結構是由循環(huán)語句來實現(xiàn)的。對應于程序框圖中的兩種循環(huán)結構。一般程序設計語言中也有當型（while型）和直到型（until型）兩種語句結構。即while語句和 until語句。while語句的一般格式是：if 條件then語句 1 else 滿足條件？語句 1 語句 2 是否if 條件then

8、語句滿足條件？語句是否while 條件循環(huán)體滿足條件？循環(huán)體是否其中循環(huán)體是由計算機反復執(zhí)行的一組語句構成的。whlie后面的“條件”是用于控制計算機執(zhí)行循環(huán)體或跳出循環(huán)體的。當計算機遇到while語句時，先判斷條件的真假，如果條件符合，就執(zhí)行while與 wend 之間的循環(huán)體；然后再檢查上述條件，如果條件仍符合，再次執(zhí)行循環(huán)體，這個過程反復進行，直到某一次條件不符合為止。這時，計算機將不執(zhí)行循環(huán)體，直接跳到wend 語句后，接著執(zhí)行 wend 之后的語句。因此，當型循環(huán)有時也稱為“前測試型”循環(huán)。其對應的程序結構框圖為： （如上右圖）until語句的一般格式是：其對應的程序結構框圖為：（如

9、上右圖）從 until型循環(huán)結構分析，計算機執(zhí)行該語句時，先執(zhí)行一次循環(huán)體，然后進行條件的判斷，如果條件不滿足，繼續(xù)返回執(zhí)行循環(huán)體，然后再進行條件的判斷，這個過程反復進行，直到某一次條件滿足時，不再執(zhí)行循環(huán)體，跳到loop until語句后執(zhí)行其他語句，是先執(zhí)行循環(huán)體后進行條件判斷的循環(huán)語句。區(qū)別：在while語句中，是當條件滿足時執(zhí)行循環(huán)體，而在until 語句中，是當條件不滿足時執(zhí)行循環(huán)體。4算法案例輾轉相除法算法：第一步：用較大的數(shù)m除以較小的數(shù)n 得到一個商q0和一個余數(shù)r0；第二步：若r00，則 n 為 m ，n 的最大公約數(shù)；若r00，則用除數(shù)n 除以余數(shù) r0得到一個商q1和一個

10、余數(shù)r1；第三步：若r10，則 r1為 m ，n 的最大公約數(shù)；若r10，則用除數(shù)r0除以余數(shù) r1得到一個商q2和一個余數(shù)r2；do循環(huán)體loop until 條件滿足條件？循環(huán)體是否依次計算直至rn0，此時所得到的rn1即為所求的最大公約數(shù)。程序框圖輸入兩個正整數(shù) m，nmn?r=m mod nr=0?m=nn=r結束開始x=nn=mm=x輸出 n否是否是程序：input “m= ” ;m input “n=” ;n if mn then x=m m=n n=x end if r=m mod n while r0 r=m mod n m=n n=r wend print m end 更相減

11、損術更相減損術求最大公約數(shù)的步驟如下：可半者半之，不可半者，副置分母子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之。翻譯出來為：第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用2 約簡；若不是，執(zhí)行第二步。第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）就是所求的最大公約數(shù)。（1） 輾轉相除法與更相減損術區(qū)別聯(lián)系都是求最大公約數(shù)的方法，計算上輾轉相除法以除法為主，更相減損術以減法為主，計算次數(shù)上輾轉相除法計算次數(shù)相對較少，特別當兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。從結果體現(xiàn)形式來看，輾轉相除法體

12、現(xiàn)結果是以相除余數(shù)為0 則得到， 而更相減損術則以減數(shù)與差相等而得到(2) 秦九韶算法與排序掌握 秦九韶 算法的原理=an vk=vk-1+an-k (k=1,2,3, n) (3) 進位制進位制是一種記數(shù)方式，用有限的數(shù)字在不同的位置表示不同的數(shù)值?？墒褂脭?shù)字符號的個數(shù)稱為基數(shù)，基數(shù)為n，即可稱n 進位制，簡稱n 進制?，F(xiàn)在最常用的是十進制，通常使用10 個阿拉伯數(shù)字0-9 進行記數(shù)。易混易錯： 表示各種進位制數(shù)一般在數(shù)字右下腳加注來表示, 如 111001(2)表示二進制數(shù) ,34(5)表示 5 進制數(shù) . 二、典型例題剖析1判斷某一事情是否為算法方法歸納：（1） 判斷某一問題是否為算法要

13、把握算法的五個特征：有窮性確定性可行性不惟一性普遍性例 1下列關于算法的說法中正確的個數(shù)有( ) 求解某一類問題的算法是唯一的算法必須在有限步操作之后停止算法的每一步操作必須是明確的，不能有歧義或模糊算法執(zhí)行后一定產(chǎn)生確定的結果a. 1 b. 2 c. 3 d. 4 主要過程：由算法的五個特征可以解得只有是錯誤的，解答某一類問題的算法時不惟一的。強調內容 ：把握好算法的五個特征。2就某一問題畫出程序框圖并寫出算法方法歸納：（1）畫程序框圖時一定要明確圖中各個符號的作用并能正確使用三種基本邏輯結構。 （ 2）用程序設計語言描述算法時一定要注意有些符號與框圖之中書寫的不同。例 2設計算法求1009

14、91431321211的值 . 要求畫出程序框圖，寫出用基本語句編寫的程序. 主要過程：強調內容 ： 解答此題目是一定要注意循環(huán)終止的條件是i99 而不是 i100, 因為這個數(shù)列共有99項3討論法畫程序框圖寫程序方法歸納：先通過解決數(shù)學題的思想進行討論，再畫圖寫程序。例3、畫出解關于x的不等式ax+b99?輸出 s 結束input a,b if a= 0 then if b0 then print 無解else print x 為全體實數(shù)else if a 0 then print bxaelse print bxai=1 s=0 do s=s+1/(i*(i+1)i=i+1 loop un

15、til i99 print s 方法歸納：先通過解決數(shù)學題的思想進行討論，再畫圖寫程序例 4、某城市現(xiàn)有人口總數(shù)為100 萬人，如果年自然增長率為1.2%，試解答下列問題：（1）寫出該城市人口數(shù)y（萬人）與年份x（年）的函數(shù)關系式；（2）用程序表示計算10 年以后該城市人口總數(shù)的算法；（3）用流程圖表示計算大約多少年以后該城市人口將達到120 萬人的算法。主要過程：（1）xy012.1100（2) 程序如下：s=100 i=1.2 x=0 while s120 s=s*i x=x+1 wend print x end 5求高次多項式的值方法歸納 ：能夠熟練利用秦九韶算法原理求高次多項式的值v0

16、=anvk=v1k+akn (k=1,2,3, n) 用秦九韶算法計算543254321fxxxxxx開始結束s=100 i=1.2 x=0 s=s*i x= x +1 sbaca=b輸出 aa=cyynn第 1 題c2500， 2550 d2550，2500 鞏固練習1、給出一個算法的流程圖（如圖），若sin,cos ,tan ,(,)42abc，則輸出結果a為（）a、sin b、cos c 、tan d 、不確定2x=5 y=6 print x+y=11 end 上面程序運行時輸出的結果是( ) a.xy=11 b.11 c.x+y=11 d. 出錯信息3. 如果下邊程序執(zhí)行后輸出的結果是

17、990，那么在程序中until 后面的“條件”應為( ) a. i10 b. i8 c. i=9 d. i9 4. 如右圖所示的程序是用來( ) a計算 310 的值 b計算93的值c計算103的值 d計算 123 10 的值5. 計算機中常用十六進制，采用數(shù)字09 和字母 af 共 16 個計數(shù)符號與十進制得對應關系如下表：i=11 s=1 do s=s*i i=i1 loop until “ 條件 ” （第3程序： s=1 i=1 while i=10 s=3*s i=i+1 wend 16 進制0 1 2 3 4 5 6 7 8 9 a b c d e f 10 進制0 1 2 3 4

18、5 6 7 8 9 10 11 12 13 14 15 例如用十六進制表示有d+e 1b，則 a b=( ) a 6e b 7c c 5f d b0 二、填空題6. 若六進數(shù)63 502m化為十進數(shù)為4934，則m= 7.二進制數(shù)111.11轉換成十進制數(shù)是_. 8. 右邊程序輸出的n 的值是 _. j=1 n=0 while j20(或者 i10) 10. 4,4,f(x)=2*x4+3*x3+5*x-4 三、 11 37 輸入兩個正整數(shù) m，nmn?r=m mod nr=0?m=nn=r結束開始x=nn=mm=x輸出 n否是否是23 解 ：由 表達 式規(guī) 律可知，輸入的n 必須為偶數(shù)。程序框圖為：n n y y 輸入xy=1xxy=