《《算法的基本思想》課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《算法的基本思想》課件.ppt（17頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、1算法的基本思想,課題引入,,作為家里的一員，在平時分擔(dān)一些力所能及的事是我們應(yīng)盡的義務(wù)，你每天都幫家里做事嗎？你會燒開水嗎？請寫出你在家中燒開水的過程,1、往壺內(nèi)注水； 2、點火加熱； 3觀察：如果水開，則停止燒火，否則繼續(xù)燒火； 4、如果水未開，重復(fù)“3”直至水開。,總結(jié)： “1”其實大部分事情都是按照一定的程序執(zhí)行，因此要理清事情的每一步?！?”判斷水是否燒開與是否繼續(xù)燒火的過程是一個反饋與判斷過程，因此有必要不斷重復(fù)過程“3”,事實上，我們完成任何事，都要有一個步驟，合理安排步驟，會達到事半功倍的效果。在我們數(shù)學(xué)的意義來講，在解決某些問題時，需要設(shè)計出一系列可操作或可計算的步驟，通過實

2、施這些步驟來解決問題，我們通常把這些步驟稱為解決問題的一種算法。這種描述不是算法的定義，但反映了算法的基本思想。,中國古代數(shù)學(xué)以算法為主要特征， 這可以從中國古代數(shù)學(xué)家的著作中 看出端倪，其中最具代表性的就是 九章算術(shù)，就其成就來說堪稱 是世界數(shù)學(xué)名著，其內(nèi)容按類分章, 以數(shù)學(xué)問題的形式出現(xiàn)，包括分?jǐn)?shù) 四則運算，開平方和開立方(包括二次方程數(shù)值的解法)，盈不足術(shù)，各種面積和體積的計算公式，線性方程組解法，正負(fù)數(shù)運算的加減法法則，勾股形解法等。另外還有賈憲的黃帝九章算法細(xì)草、劉益議古根源、秦九韶的數(shù)書九章，楊輝的詳解九章算法和楊輝算法等。,隨著計算科學(xué)和信息技術(shù)的飛速發(fā)展，算法的思想已經(jīng)滲透到社

3、會的方方面。在以前的學(xué)習(xí)中，雖然沒有出現(xiàn)算法這個名詞，但實際上在數(shù)學(xué)教學(xué)中已經(jīng)滲透了大量的算法思想，如四則運算的過程、求解方程的步驟等等。完成這些工作都需要一系列程序化的步驟，這就是算法的思想。,【例1】在中央電視臺的幸運52節(jié)目中，要求參與者快速猜出物品的價格。主持人出示某件物品，參與者每次估算出一個價格，主持人只能回答高了、低了或者正確。在某次節(jié)目中，主持人出示了一臺價值在1000元以內(nèi)的隨身聽，并開始了競猜。下面是主持人和參與者的一段對話：,.,如果你是參與者，你接下來會怎么猜？,800元！,高了,400元！,600元！,低了,高了,參與者,主持人：李詠,例2 兩個大人和兩個小孩一起渡河

4、，渡口只有一條小船每次只能渡1 個大人或兩個小孩，他們四人都會劃 船，但都不會游泳試問他們怎樣渡過河去？請寫出一個渡河方案。,S1 兩個小孩同船過河去；,S2 一個小孩劃船回來；,S3 一個大人劃船過河去；,S4 對岸的小孩劃船回來；,S5 兩個小孩同船渡過河去；,S6 一個小孩劃船回來；,S7 余下的一個大人獨自劃船渡過河去； 對岸的小孩劃船回來；,S8 兩個小孩再同時劃船渡過河去。,智力大比拼,在給定素數(shù)表的條件下，請你設(shè)計一個算法，將936分成素因數(shù)的乘積.,解 算法步驟如下： 判斷936是否為素數(shù)：否。 確定936的最小素因數(shù)：2。936=2*468 判斷468是

5、否為素數(shù)：否。 確定468的最小素因數(shù)：2。936=2*2*234。 判斷234是否為素數(shù)：否。 確定234的最小素因數(shù)：2。936=2*2*2*117。 判斷117是否為素數(shù)：否。 確定117的最小素因數(shù)：3。936=2*2*2*3*39。 判斷39是否為素數(shù)：否。 確定39的最小素因數(shù)：3。936=2*2*2*3*3*13。 判斷13 是否為素數(shù)：13是素數(shù)，所以分解結(jié)束。 分解結(jié)果是：936=2*2*2*3*3*13,實際操作,寫算法的要求,算法不同于求解一個具體問題的方法，是這種方法的高度概括。一個好的算法有如下要求： 寫出的算法，

6、必須能解決一類問題（如一元二次方程求根公式），并且能重復(fù)使用。 算法過程要能一步一步執(zhí)行，每一步執(zhí)行的操作，必須確切，不能含混不清，而且在有限步能得出結(jié)果。 算法要簡潔，要清晰可讀，不能弄搞繁雜，以以致于易程序化。,思考以下問題的算法：,一位商人有9枚銀元，其中有1枚略輕的是假銀元。你能用天平（不用砝碼）將假銀元找出來嗎？,解: 1.把銀元分成3組，每組3枚。,2先將兩組分別放在天平的兩邊。如果天平不平衡，那邊假銀元就放在輕的那一組；如果天平左右平衡，則假銀元就在末稱的第3組里。,3取出含假銀元的那一組，從中任取兩枚放在天平的兩邊。如果左右不平衡，則輕的那一邊就是假銀元；如果天平兩邊平衡，則末

7、稱的那一枚就是假銀元。,算法是什么,算法可以理解為由基本運算及規(guī)定的運算順序構(gòu)成的完整的解題步驟，或看成按要求設(shè)計好的有限的、確切的計算序列，并且這樣的步驟或序列能解決一類問題。,現(xiàn)代意義上的“算法”通常是指可以用計算機來解決的某一類問題的程序或步驟。,求方程 在0,5上的近似解，精確到0.05,分析：,如何求方程的根？我們可以參考p9192,解法1,（1）移項，得,（2）兩邊同時加1并配方得：,（3）兩邊同時開放得：x=3或x=-1,（4）取x=3,解法2,1因為f(0)=-3,f(5)=12,f(0).f(5)0.05,2取0,5的中點2.5；計算f(2.5)=-1.75,則f

8、(5)f(2.5)0.01,3取2.5,5的中點3.75，計算f(3.75)=3.5625,則f(2.5)f(3.5625)0.05,4取2.5,3.5625的中點3.03125，則f(3.03125)=0.12598,則f(3.03125)f(2.5)0.05,5取2.5,3.03125的中點2.765625，則f(2.765625)=-0.88257,精度：3.03125-2.7656250.26570.05,6取2.765625,3.03125的中點2.8984，f(2.8984)=-0.340,則f(2.8984)f(3.03125)0.05,7取2.8984,3.03125的中點2.

9、9648，則f(2.96)=-0.140,則f(3.03125)f(2.9648)0.01,8取2.9648,3.031的中點3.009，則f(3.009)=0.008,則f(3.009)f(2.965)<0,精度：3.009-2.9650.045<0.05,9取3.009,2.965的中點2.99，則x=2.99,說明：,1算法實際上就是解決某一類問題的步驟和方法，在解決問題時形成的規(guī)律性的東西，按照算法描述的規(guī)則與步驟，一步一步地去做，最終便能解決問題。,2算法的基本思想就是我們分析問題時的想法。由于想法不同思考的角度不同，著手點不一樣，同一問題存在不同的算法，算法有優(yōu)劣之分。,3從熟悉的問題出發(fā)，體會算法的程序化思想，學(xué)會用自然語言來描述算法,算法的特征,有窮性： 一個算法應(yīng)包含有限的操作步驟而不能是 無限的。,確定性：算法中每一個步驟應(yīng)當(dāng)是確定的，而不應(yīng)當(dāng) 是含糊的、模棱兩可的。,有效性：算法中每一個步驟應(yīng)當(dāng)能有效地執(zhí)行，并得到 確定的結(jié)果。,輸 入: 有零個或多個輸入。,輸 出: 有一個或多個輸出。,習(xí)題,5寫出過A(2,1)、B(1,0) 、C(2,-1)三點的外接圓 的一個算法。,2二次函數(shù)頂點為A(1,-41)、且過B(0,-3)， 寫出二次函數(shù)f(x)解析式的一個算法。,1寫出解方程x2- x-1=0的一個算法。,