《《算法的基本思想》課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《算法的基本思想》課件.ppt（17頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、1算法的基本思想,課題引入,,作為家里的一員，在平時(shí)分擔(dān)一些力所能及的事是我們應(yīng)盡的義務(wù)，你每天都幫家里做事嗎？你會(huì)燒開(kāi)水嗎？請(qǐng)寫出你在家中燒開(kāi)水的過(guò)程,1、往壺內(nèi)注水； 2、點(diǎn)火加熱； 3觀察：如果水開(kāi)，則停止燒火，否則繼續(xù)燒火； 4、如果水未開(kāi)，重復(fù)“3”直至水開(kāi)。,總結(jié)： “1”其實(shí)大部分事情都是按照一定的程序執(zhí)行，因此要理清事情的每一步?！?”判斷水是否燒開(kāi)與是否繼續(xù)燒火的過(guò)程是一個(gè)反饋與判斷過(guò)程，因此有必要不斷重復(fù)過(guò)程“3”,事實(shí)上，我們完成任何事，都要有一個(gè)步驟，合理安排步驟，會(huì)達(dá)到事半功倍的效果。在我們數(shù)學(xué)的意義來(lái)講，在解決某些問(wèn)題時(shí)，需要設(shè)計(jì)出一系列可操作或可計(jì)算的步驟，通過(guò)實(shí)
2、施這些步驟來(lái)解決問(wèn)題，我們通常把這些步驟稱為解決問(wèn)題的一種算法。這種描述不是算法的定義，但反映了算法的基本思想。,中國(guó)古代數(shù)學(xué)以算法為主要特征， 這可以從中國(guó)古代數(shù)學(xué)家的著作中 看出端倪，其中最具代表性的就是 九章算術(shù)，就其成就來(lái)說(shuō)堪稱 是世界數(shù)學(xué)名著，其內(nèi)容按類分章, 以數(shù)學(xué)問(wèn)題的形式出現(xiàn)，包括分?jǐn)?shù) 四則運(yùn)算，開(kāi)平方和開(kāi)立方(包括二次方程數(shù)值的解法)，盈不足術(shù)，各種面積和體積的計(jì)算公式，線性方程組解法，正負(fù)數(shù)運(yùn)算的加減法法則，勾股形解法等。另外還有賈憲的黃帝九章算法細(xì)草、劉益議古根源、秦九韶的數(shù)書(shū)九章，楊輝的詳解九章算法和楊輝算法等。,隨著計(jì)算科學(xué)和信息技術(shù)的飛速發(fā)展，算法的思想已經(jīng)滲透到社
3、會(huì)的方方面。在以前的學(xué)習(xí)中，雖然沒(méi)有出現(xiàn)算法這個(gè)名詞，但實(shí)際上在數(shù)學(xué)教學(xué)中已經(jīng)滲透了大量的算法思想，如四則運(yùn)算的過(guò)程、求解方程的步驟等等。完成這些工作都需要一系列程序化的步驟，這就是算法的思想。,【例1】在中央電視臺(tái)的幸運(yùn)52節(jié)目中，要求參與者快速猜出物品的價(jià)格。主持人出示某件物品，參與者每次估算出一個(gè)價(jià)格，主持人只能回答高了、低了或者正確。在某次節(jié)目中，主持人出示了一臺(tái)價(jià)值在1000元以內(nèi)的隨身聽(tīng)，并開(kāi)始了競(jìng)猜。下面是主持人和參與者的一段對(duì)話：,.,如果你是參與者，你接下來(lái)會(huì)怎么猜？,800元！,高了,400元！,600元！,低了,高了,參與者,主持人：李詠,例2 兩個(gè)大人和兩個(gè)小孩一起渡河
4、，渡口只有一條小船每次只能渡1 個(gè)大人或兩個(gè)小孩，他們四人都會(huì)劃 船，但都不會(huì)游泳試問(wèn)他們?cè)鯓佣蛇^(guò)河去？請(qǐng)寫出一個(gè)渡河方案。,S1 兩個(gè)小孩同船過(guò)河去；,S2 一個(gè)小孩劃船回來(lái)；,S3 一個(gè)大人劃船過(guò)河去；,S4 對(duì)岸的小孩劃船回來(lái)；,S5 兩個(gè)小孩同船渡過(guò)河去；,S6 一個(gè)小孩劃船回來(lái)；,S7 余下的一個(gè)大人獨(dú)自劃船渡過(guò)河去； 對(duì)岸的小孩劃船回來(lái)；,S8 兩個(gè)小孩再同時(shí)劃船渡過(guò)河去。,智力大比拼,在給定素?cái)?shù)表的條件下，請(qǐng)你設(shè)計(jì)一個(gè)算法，將936分成素因數(shù)的乘積.,解 算法步驟如下： 判斷936是否為素?cái)?shù)：否。 確定936的最小素因數(shù)：2。936=2*468 判斷468是
5、否為素?cái)?shù)：否。 確定468的最小素因數(shù)：2。936=2*2*234。 判斷234是否為素?cái)?shù)：否。 確定234的最小素因數(shù)：2。936=2*2*2*117。 判斷117是否為素?cái)?shù)：否。 確定117的最小素因數(shù)：3。936=2*2*2*3*39。 判斷39是否為素?cái)?shù)：否。 確定39的最小素因數(shù)：3。936=2*2*2*3*3*13。 判斷13 是否為素?cái)?shù)：13是素?cái)?shù)，所以分解結(jié)束。 分解結(jié)果是：936=2*2*2*3*3*13,實(shí)際操作,寫算法的要求,算法不同于求解一個(gè)具體問(wèn)題的方法，是這種方法的高度概括。一個(gè)好的算法有如下要求： 寫出的算法，
6、必須能解決一類問(wèn)題（如一元二次方程求根公式），并且能重復(fù)使用。 算法過(guò)程要能一步一步執(zhí)行，每一步執(zhí)行的操作，必須確切，不能含混不清，而且在有限步能得出結(jié)果。 算法要簡(jiǎn)潔，要清晰可讀，不能弄搞繁雜，以以致于易程序化。,思考以下問(wèn)題的算法：,一位商人有9枚銀元，其中有1枚略輕的是假銀元。你能用天平（不用砝碼）將假銀元找出來(lái)嗎？,解: 1.把銀元分成3組，每組3枚。,2先將兩組分別放在天平的兩邊。如果天平不平衡，那邊假銀元就放在輕的那一組；如果天平左右平衡，則假銀元就在末稱的第3組里。,3取出含假銀元的那一組，從中任取兩枚放在天平的兩邊。如果左右不平衡，則輕的那一邊就是假銀元；如果天平兩邊平衡，則末
7、稱的那一枚就是假銀元。,算法是什么,算法可以理解為由基本運(yùn)算及規(guī)定的運(yùn)算順序構(gòu)成的完整的解題步驟，或看成按要求設(shè)計(jì)好的有限的、確切的計(jì)算序列，并且這樣的步驟或序列能解決一類問(wèn)題。,現(xiàn)代意義上的“算法”通常是指可以用計(jì)算機(jī)來(lái)解決的某一類問(wèn)題的程序或步驟。,求方程 在0,5上的近似解，精確到0.05,分析：,如何求方程的根？我們可以參考p9192,解法1,（1）移項(xiàng)，得,（2）兩邊同時(shí)加1并配方得：,（3）兩邊同時(shí)開(kāi)放得：x=3或x=-1,（4）取x=3,解法2,1因?yàn)閒(0)=-3,f(5)=12,f(0).f(5)0.05,2取0,5的中點(diǎn)2.5；計(jì)算f(2.5)=-1.75,則f
8、(5)f(2.5)0.01,3取2.5,5的中點(diǎn)3.75，計(jì)算f(3.75)=3.5625,則f(2.5)f(3.5625)0.05,4取2.5,3.5625的中點(diǎn)3.03125，則f(3.03125)=0.12598,則f(3.03125)f(2.5)0.05,5取2.5,3.03125的中點(diǎn)2.765625，則f(2.765625)=-0.88257,精度：3.03125-2.7656250.26570.05,6取2.765625,3.03125的中點(diǎn)2.8984，f(2.8984)=-0.340,則f(2.8984)f(3.03125)0.05,7取2.8984,3.03125的中點(diǎn)2.
9、9648，則f(2.96)=-0.140,則f(3.03125)f(2.9648)0.01,8取2.9648,3.031的中點(diǎn)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的中點(diǎn)2.99，則x=2.99,說(shuō)明：,1算法實(shí)際上就是解決某一類問(wèn)題的步驟和方法，在解決問(wèn)題時(shí)形成的規(guī)律性的東西，按照算法描述的規(guī)則與步驟，一步一步地去做，最終便能解決問(wèn)題。,2算法的基本思想就是我們分析問(wèn)題時(shí)的想法。由于想法不同思考的角度不同，著手點(diǎn)不一樣，同一問(wèn)題存在不同的算法，算法有優(yōu)劣之分。,3從熟悉的問(wèn)題出發(fā)，體會(huì)算法的程序化思想，學(xué)會(huì)用自然語(yǔ)言來(lái)描述算法,算法的特征,有窮性： 一個(gè)算法應(yīng)包含有限的操作步驟而不能是 無(wú)限的。,確定性：算法中每一個(gè)步驟應(yīng)當(dāng)是確定的，而不應(yīng)當(dāng) 是含糊的、模棱兩可的。,有效性：算法中每一個(gè)步驟應(yīng)當(dāng)能有效地執(zhí)行，并得到 確定的結(jié)果。,輸 入: 有零個(gè)或多個(gè)輸入。,輸 出: 有一個(gè)或多個(gè)輸出。,習(xí)題,5寫出過(guò)A(2,1)、B(1,0) 、C(2,-1)三點(diǎn)的外接圓 的一個(gè)算法。,2二次函數(shù)頂點(diǎn)為A(1,-41)、且過(guò)B(0,-3)， 寫出二次函數(shù)f(x)解析式的一個(gè)算法。,1寫出解方程x2- x-1=0的一個(gè)算法。,
《算法的基本思想》課件.ppt
