算法初步算法與程序框圖1算法的概念精選課件

1、 第一章 算法初步1.1 算法與程序框圖1.1.1 算法的概念高中新課程數(shù)學(xué)必修第1頁，共79頁。問題提出1.用計(jì)算機(jī)解二元一次方程組 .exe2.在上述解二元一次方程組的過程中，計(jì)算機(jī)是按照一定的指令來工作的，其中最基礎(chǔ)的數(shù)學(xué)理論就是算法，本節(jié)課我們就來學(xué)習(xí): 第2頁，共79頁。算法的概念第3頁，共79頁。知識(shí)探究（一）：算法的概念思考1:在初中，對(duì)于解二元一次方程組你學(xué)過哪些方法？ 思考2：用加減消元法解二元一次方程組 x-2y=-1 2x+y=1 的具體步驟是什么？加減消元法和代入消元法思考2:用加減消元法解二元一次方程組 的具體步驟是什么？第4頁，共79頁。 +2，得 5x=1 . 解

2、，得 . -2，得 5y3 . 解，得 .第一步，第二步，第三步，第四步，第五步， 得到方程組的解為 . 第5頁，共79頁。思考3:參照上述思路，一般地，解方程組 的基本步驟是什么？第6頁，共79頁。第一步， - ，得 . 第二步，解 ，得 . 第三步， - ，得 . 第四步，解 ，得 . 第五步，得到方程組的解為 第7頁，共79頁。思考4:根據(jù)上述分析，用加減消元法解二元一次方程組，可以分為五個(gè)步驟進(jìn)行，這五個(gè)步驟就構(gòu)成了解二元一次方程組的一個(gè)“算法”.我們再根據(jù)這一算法編制計(jì)算機(jī)程序，就可以讓計(jì)算機(jī)來解二元一次方程組.那么解二元一次方程組的算法包括哪些內(nèi)容？ 第8頁，共79頁。思考5:一般

3、地，算法是由按照一定規(guī)則解決某一類問題的基本步驟組成的.你認(rèn)為：(1)這些步驟的個(gè)數(shù)是有限的還是無限 的？(2)每個(gè)步驟是否有明確的計(jì)算任務(wù)？第9頁，共79頁。思考6:有人對(duì)哥德巴赫猜想“任何大于4的偶數(shù)都能寫成兩個(gè)質(zhì)數(shù)之和”設(shè)計(jì)了如下操作步驟：第一步，檢驗(yàn)6=3+3，第二步，檢驗(yàn)8=3+5，第三步，檢驗(yàn)10=5+5， 利用計(jì)算機(jī)無窮地進(jìn)行下去！請(qǐng)問：這是一個(gè)算法嗎？第10頁，共79頁。思考7:根據(jù)上述分析，你能歸納出算法的概念嗎？ 在數(shù)學(xué)中，按照一定規(guī)則解決某一類問題的明確和有限的步驟稱為算法. 第11頁，共79頁。知識(shí)探究（二）:算法的步驟設(shè)計(jì)思考1:如果讓計(jì)算機(jī)判斷7是否為質(zhì)數(shù)，如何設(shè)計(jì)

4、算法步驟？ 第一步，用2除7，得到余數(shù)1,所以2不能整除7.第四步，用5除7，得到余數(shù)2,所以5不能整除7. 第五步，用6除7，得到余數(shù)1,所以6不能整除7. 第二步，用3除7，得到余數(shù)1,所以3不能整除7.第三步，用4除7，得到余數(shù)3,所以4不能整除7. 因此，7是質(zhì)數(shù).第12頁，共79頁。思考2:如果讓計(jì)算機(jī)判斷35是否為質(zhì)數(shù)，如何設(shè)計(jì)算法步驟？ 第一步，用2除35，得到余數(shù)1,所以2不能整除35.第二步，用3除35，得到余數(shù)2,所以3不能整除35.第三步，用4除35，得到余數(shù)3,所以4不能整除35. 第四步，用5除35，得到余數(shù)0,所以5能整除35.因此，35不是質(zhì)數(shù).第13頁，共79頁

5、。思考3:整數(shù)89是否為質(zhì)數(shù)？如果讓計(jì)算機(jī)判斷89是否為質(zhì)數(shù)，按照上述算法需要設(shè)計(jì)多少個(gè)步驟？ 第一步，用2除89，得到余數(shù)1,所以2不能整除89.第二步，用3除89，得到余數(shù)2,所以3不能整除89.第三步，用4除89，得到余數(shù)1,所以4不能整除89. 第八十七步，用88除89，得到余數(shù)1,所以88不能 整除89.因此，89是質(zhì)數(shù).第14頁，共79頁。思考4:用288逐一去除89求余數(shù)，需要87個(gè)步驟，這些步驟基本是重復(fù)操作，我們可以按下面的思路改進(jìn)這個(gè)算法，減少算法的步驟.（1）用i表示288中的任意一個(gè)整數(shù)，并從2開始取數(shù)；（2）用i除89，得到余數(shù)r. 若r=0，則89不是質(zhì)數(shù)；若r0，

6、將i用i+1替代，再執(zhí)行同樣的操作； （3）這個(gè)操作一直進(jìn)行到i取88為止.你能按照這個(gè)思路，設(shè)計(jì)一個(gè)“判斷89是否為質(zhì)數(shù)”的算法步驟嗎？第15頁，共79頁。用i除89，得到余數(shù)r； 令i=2； 若r=0，則89不是質(zhì)數(shù)，結(jié)束算法；若r0，將i用i+1替代； 判斷“i88”是否成立？若是，則89是質(zhì)數(shù)，結(jié)束算法；否則，返回第二步. 第一步， 第四步， 第三步， 第二步， 算法設(shè)計(jì):第16頁，共79頁。思考5:一般地，判斷一個(gè)大于2的整數(shù)是否為質(zhì)數(shù)的算法步驟如何設(shè)計(jì)？ 第一步，給定一個(gè)大于2的整數(shù)n； 第二步，令i=2； 第三步，用i除n，得到余數(shù)r； 第四步，判斷“r=0”是否成立.若是，則n

7、 不是質(zhì)數(shù)，結(jié)束算法；否則，將i 的值增加1，仍用i表示； 第五步，判斷“i(n-1)”是否成立，若是， 則n是質(zhì)數(shù)，結(jié)束算法；否則，返回 第三步. 第17頁，共79頁。理論遷移 例 設(shè)函數(shù)f(x)的圖象是一條連續(xù)不斷的曲線，寫出用“二分法”求方程 f(x)=0的一個(gè)近似解的算法. 第18頁，共79頁。第一步，取函數(shù)f(x)，給定精確度d. 第二步，確定區(qū)間a，b，滿足f(a)f(b)0. 第五步，判斷a,b的長度是否小于d或f(m)是否等于0. 若是，則m是方程的近似解；否則，返回第三步.第三步，取區(qū)間中點(diǎn) .第四步，若f(a)f(m)2）是否為質(zhì)數(shù)”的算法步驟如何？第一步，給定一個(gè)大于2的

8、整數(shù)n； 第二步，令i=2； 第三步，用i除n，得到余數(shù)r； 第四步，判斷“r=0”是否成立.若是，則n 不是質(zhì)數(shù)，結(jié)束算法；否則，將i 的值增加1，仍用i表示； 第五步，判斷“i(n-1)”是否成立，若是， 則n是質(zhì)數(shù)，結(jié)束算法；否則，返回 第三步. 第26頁，共79頁。思考2:我們將上述算法用下面的圖形表示：開始r=0？輸出“n是質(zhì)數(shù)”輸出“n不是質(zhì)數(shù)”求n除以i的余數(shù)i=2輸入ni的值增加1，仍用i表示in-1或r=0？是是結(jié)束否否第27頁，共79頁。上述表示算法的圖形稱為算法的程序框圖又稱流程圖，其中的多邊形叫做程序框，帶方向箭頭的線叫做流程線，你能指出程序框圖的含義嗎？ 用程序框、流

9、程線及文字說明來表示算法的圖形. 第28頁，共79頁。思考3:在上述程序框圖中，有4種程序框，2種流程線，它們分別有何特定的名稱和功能？ 開始r=0？輸出“n不是質(zhì)數(shù)”求n除以i的余數(shù)i=2輸入ni的值增加1，仍用i表示in-1或r=0？是是結(jié)束否否輸出“n是質(zhì)數(shù)”第29頁，共79頁。圖形符號(hào) 名 稱 功 能 終端框 （起止框） 輸入、輸出框 處理框 （執(zhí)行框） 判斷框 流程線 表示一個(gè)算法的起始和結(jié)束 表示一個(gè)算法輸入和輸出的信息 賦值、計(jì)算 判斷某一條件是否成立，成立時(shí)在出口處標(biāo)明“是”或“Y”；不成立時(shí)標(biāo)明“否”或“N” 連接程序框，表示算法步驟的執(zhí)行順序 第30頁，共79頁。思考4:在

10、邏輯結(jié)構(gòu)上，“判斷整數(shù)n（n2）是否為質(zhì)數(shù)”的程序框圖由幾部分組成？開始r=0？輸出“n不是質(zhì)數(shù)”求n除以i的余數(shù)i=2輸入ni的值增加1，仍用i表示in-1或r=0？是是結(jié)束否否輸出“n是質(zhì)數(shù)”第31頁，共79頁。知識(shí)探究（二）：算法的順序結(jié)構(gòu)思考1:任何一個(gè)算法各步驟之間都有明確的順序性，在算法的程序框圖中，由若干個(gè)依次執(zhí)行的步驟組成的邏輯結(jié)構(gòu)，稱為順序結(jié)構(gòu)，用程序框圖可以表示為：步驟n步驟n+1在順序結(jié)構(gòu)中可能會(huì)用到哪幾種程序框和流程線？?第32頁，共79頁。思考2:若一個(gè)三角形的三條邊長分別為a，b，c，令 ，則三角形的面積 .你能利用這個(gè)公式設(shè)計(jì)一個(gè)計(jì)算三角形面積的算法步驟嗎？第一步

11、，輸入三角形三條邊的邊長 a，b，c. 第二步，計(jì)算 . 第三步，計(jì)算 .第四步，輸出S. 第33頁，共79頁。思考3:上述算法的程序框圖如何表示？開始結(jié)束輸出S輸入a，b，c第34頁，共79頁。 例1 一個(gè)籠子里裝有雞和兔共m只，且雞和兔共n只腳，設(shè)計(jì)一個(gè)計(jì)算雞和兔各有多少只的算法，并畫出程序框圖表示.理論遷移算法分析： 第一步，輸入m，n.第二步，計(jì)算雞的只數(shù) .第三步，計(jì)算兔的只數(shù)y=m-x.第四步，輸出x，y.第35頁，共79頁。開始結(jié)束輸出x，y輸入m，ny= m-x程序框圖： 第36頁，共79頁。 例2 已知下圖是“求一個(gè)正奇數(shù)的平方加5的值”的程序框圖，若輸出的數(shù)是30，求輸入的

12、數(shù)n的值.開始結(jié)束輸入正整數(shù)n輸出yy=x2+5x=2n-1第37頁，共79頁。順序結(jié)構(gòu)的程序框圖的基本特征：小結(jié)作業(yè)（2）各程序框從上到下用流程線依次連接.（1）必須有兩個(gè)起止框，穿插輸入、輸出框和處理框，沒有判斷框.（3）處理框按計(jì)算機(jī)執(zhí)行順序沿流程線依次排列.第38頁，共79頁。作業(yè):P20習(xí)題1.1B組：1.第39頁，共79頁。1.1.2 程序框圖與算法 的基本邏輯結(jié)構(gòu) 第二課時(shí)第40頁，共79頁。問題提出 1.用程序框、流程線及文字說明來表示算法的圖形稱為程序框圖，它使算法步驟顯得直觀、清晰、簡明.其中程序框有哪幾種基本圖形？它們表示的功能分別如何？ 終端框 （起止框） 輸入、輸出框

13、 處理框 （執(zhí)行框） 判斷框 流程線 第41頁，共79頁。 2.順序結(jié)構(gòu)是任何一個(gè)算法都離不開的基本邏輯結(jié)構(gòu)，在一些算法中，有些步驟只有在一定條件下才會(huì)被執(zhí)行，有些步驟在一定條件下會(huì)被重復(fù)執(zhí)行，這需要我們對(duì)算法的邏輯結(jié)構(gòu)作進(jìn)一步探究.第42頁，共79頁。條件結(jié)構(gòu)與循環(huán)結(jié)構(gòu)第43頁，共79頁。知識(shí)探究（一）：算法的條件結(jié)構(gòu)思考1:在某些問題的算法中，有些步驟只有在一定條件下才會(huì)被執(zhí)行，算法的流程因條件是否成立而變化.在算法的程序框圖中，由若干個(gè)在一定條件下才會(huì)被執(zhí)行的步驟組成的邏輯結(jié)構(gòu)，稱為條件結(jié)構(gòu)，用程序框圖可以表示為下面兩種形式：第44頁，共79頁。滿足條件？步驟A步驟B是否滿足條件？步驟A

14、是否你如何理解這兩種程序框圖的共性和個(gè)性？ 第45頁，共79頁。思考2:判斷“以任意給定的3個(gè)正實(shí)數(shù)為三條邊邊長的三角形是否存在”的算法步驟如何設(shè)計(jì)？第二步，判斷a+bc，b+ca，c+ab是否同時(shí)成立.若是，則存在這樣的三角形；否則，不存在這樣的三角形.第一步，輸入三個(gè)正實(shí)數(shù)a，b，c.思考3:你能畫出這個(gè)算法的程序框圖嗎？ 第46頁，共79頁。開始輸入a，b，ca+bc，b+ca，c+ab是否同時(shí)成立？是存在這樣的三角形結(jié)束否不存在這樣的三角形第47頁，共79頁。知識(shí)探究（二）：算法的循環(huán)結(jié)構(gòu)思考1:在算法的程序框圖中，由按照一定的條件反復(fù)執(zhí)行的某些步驟組成的邏輯結(jié)構(gòu)，稱為循環(huán)結(jié)構(gòu)，反復(fù)執(zhí)

15、行的步驟稱為循環(huán)體，那么循環(huán)結(jié)構(gòu)中一定包含條件結(jié)構(gòu)嗎？ 第48頁，共79頁。思考2:某些循環(huán)結(jié)構(gòu)用程序框圖可以表示為： 循環(huán)體滿足條件？是否 這種循環(huán)結(jié)構(gòu)稱為直到型循環(huán)結(jié)構(gòu)，你能指出直到型循環(huán)結(jié)構(gòu)的特征嗎？ 在執(zhí)行了一次循環(huán)體后，對(duì)條件進(jìn)行判斷，如果條件不滿足，就繼續(xù)執(zhí)行循環(huán)體，直到條件滿足時(shí)終止循環(huán).第49頁，共79頁。思考3:還有一些循環(huán)結(jié)構(gòu)用程序框圖可以表示為：循環(huán)體滿足條件？是否這種循環(huán)結(jié)構(gòu)稱為當(dāng)型循環(huán)結(jié)構(gòu)，你能指出當(dāng)型循環(huán)結(jié)構(gòu)的特征嗎？在每次執(zhí)行循環(huán)體前，對(duì)條件進(jìn)行判斷，如果條件滿足，就執(zhí)行循環(huán)體，否則終止循環(huán).第50頁，共79頁。思考4:計(jì)算1+2+3+100的值可按如下過程進(jìn)行：

16、第1步，0+1=1.第2步，1+2=3.第3步，3+3=6.第4步，6+4=10. 第100步，4950+100=5050. 我們用一個(gè)累加變量S表示每一步的計(jì)算結(jié)果，即把S+i的結(jié)果仍記為S，從而把第i步表示為S=S+i，其中S的初始值為0，i依次取1，2，100，通過重復(fù)操作，上述問題的算法如何設(shè)計(jì)？第51頁，共79頁。 第四步，判斷i100是否成立.若是，則輸出S，結(jié)束算法；否則，返回第二步.第一步，令i=1，S=0.第二步，計(jì)算S+i，仍用S表示.第三步，計(jì)算i+1，仍用i表示.第52頁，共79頁。思考5:用直到型循環(huán)結(jié)構(gòu)，上述算法的程序框圖如何表示？開始i=1i100？是輸出S結(jié)束S

17、=0i=i+1S=S+i否第53頁，共79頁。思考6:用當(dāng)型循環(huán)結(jié)構(gòu)，上述算法的程序框圖如何表示？開始i=1結(jié)束輸出S否是S=0S=S+ii100？i=i+1第54頁，共79頁。 例 設(shè)計(jì)一個(gè)求解一元二次方程ax2+bx+c=0的算法，并畫出程序框圖表示. 理論遷移算法分析：第一步，輸入三個(gè)系數(shù)a，b，c.第二步，計(jì)算=b2-4ac.第三步，判斷0是否成立.若是，則計(jì) 算 ；否則，輸出“方程沒有 實(shí)數(shù)根”，結(jié)束算法.第四步，判斷=0是否成立.若是，則輸出 x1=x2=p，否則，計(jì)算x1=p+q，x2=p-q， 并輸出x1，x2. 第55頁，共79頁。程序框圖：開始輸入a，b，c= b2-4ac

18、0？=0？否x1=p+q輸出x1，x2結(jié)束否是x2=p-q輸出x1=x2=p是輸出“方程沒有實(shí)數(shù)根”第56頁，共79頁。（3）條件結(jié)構(gòu)和循環(huán)結(jié)構(gòu)的程序框圖各有兩種形式，相互對(duì)立統(tǒng)一.條件結(jié)構(gòu)和循環(huán)結(jié)構(gòu)的基本特征：小結(jié)作業(yè)（1）程序框圖中必須有兩個(gè)起止框，穿插輸入、輸出框和處理框，一定有判斷框.（2）循環(huán)結(jié)構(gòu)中包含條件結(jié)構(gòu)，條件結(jié)構(gòu)中不含循環(huán)結(jié)構(gòu).第57頁，共79頁。作業(yè)：P20習(xí)題1.1A組：2，3.第58頁，共79頁。1.1.2 程序框圖與算法 的基本邏輯結(jié)構(gòu) 第三課時(shí)第59頁，共79頁。問題提出 1.算法的基本邏輯結(jié)構(gòu)有哪幾種？用程序框圖分別如何表示？ 步驟n步驟n+1順序結(jié)構(gòu)第60頁，共

19、79頁。條件結(jié)構(gòu)滿足條件？步驟A步驟B是否(1)滿足條件？步驟A是否(2)第61頁，共79頁。循環(huán)結(jié)構(gòu)循環(huán)體滿足條件？是否直到型循環(huán)體滿足條件？是否當(dāng)型第62頁，共79頁。 2.在學(xué)習(xí)上，我們要求對(duì)實(shí)際問題能用自然語言設(shè)計(jì)一個(gè)算法，再根據(jù)算法的邏輯結(jié)構(gòu)畫出程序框圖，同時(shí)，還要能夠正確閱讀、理解程序框圖所描述的算法的含義，這需要我們對(duì)程序框圖的畫法有進(jìn)一步的理解和認(rèn)識(shí).第63頁，共79頁。程序框圖的畫法第64頁，共79頁。知識(shí)探究（一）：多重條件結(jié)構(gòu)的程序框圖思考1:解關(guān)于x的方程ax+b=0的算法步驟如何設(shè)計(jì)？第三步，判斷b是否為0.若是，則輸出“方程的解為任意實(shí)數(shù)”；否則，輸出“方程無實(shí)數(shù)解”.第一步，輸入實(shí)數(shù)a，b.第二步，判斷a是否為0.若是，執(zhí)行第三步；否則，計(jì)算 ，并輸出x，結(jié)束算法.第65頁，共79頁。思考2:該算法的程序框圖如何表示？ 開始輸入a，ba=0？是b=0？輸出x結(jié)束輸出“方程的解為任意實(shí)數(shù)”是輸出“方程無實(shí)數(shù)根”否否第66頁，共79頁。思考3：你能畫出求分段函數(shù)的值的程序框圖嗎？思考3：你能畫出求分段函數(shù) 的值的程序框圖嗎？開始輸入xx1？輸出y結(jié)束x0？否是y=x+2是y=3x-1否y=1-x第67頁，共79頁。思考1：用“二分法”求方程 的近似解的算法如何設(shè)計(jì)