1、.,1,算法的基本思想,焦作師專附中 孫紅霞,2014.05,！本章在高考中的地位,課題引入,作為家里的一員，在平時分擔一些力所能及的事是我們應(yīng)盡的義務(wù)，你每天都幫家里做事嗎？你會煮餃子嗎？請寫出你在家中煮餃子的過程,1、往鍋里注水； 2、點火加熱，等水沸騰后，放入餃子； 3、觀察，當餃子浮起來后繼續(xù)加水； 4、重復步驟3至少兩次。,總結(jié)： “1”其實大部分事情都是按照一定的程序執(zhí)行，因此要理清事情的每一步?！?”類似于這樣按照順序執(zhí)行一系列步驟，最后完成任務(wù)的解決問題的思想，就是算法的基本思想。,事實上，我們完成任何事，都要有一個步驟，合理安排步驟，會達到事半功倍的效果。在我們數(shù)學上的意義來

2、講：在解決某些問題時，需要設(shè)計出一系列可操作或可計算的步驟，通過實施這些步驟來解決問題，我們通常把這些步驟稱為解決問題的一種算法。這種描述不是算法的定義，但反映了算法的基本思想。,引：在中央電視臺的幸運52節(jié)目中，要求參與者快速猜出物品的價格。主持人出示某件物品，參與者每次估算出一個價格，主持人只能回答高了、低了或者正確。在某次節(jié)目中，主持人出示了一臺價值在1000元以內(nèi)的隨身聽，并開始了競猜。下面是主持人和參與者的一段對話：,.,如果你是參與者，你接下來會怎么猜？,800元！,高了,400元！,600元！,低了,高了,參與者,主持人：李詠,2班提問 確定,1班提問 確定,3班提問 確定,【例

3、1】一個同學想一個0到30之間的一個數(shù)，另一個同學負責猜，第一個同學只需要給出“高了” ，“低了” ，“正確”的提示。,2班提問 確定,1班提問 確定,3班提問 確定,我們寫的這個過程能不能稱為是一個算法呢？,算法是要解決一類問題而不是一個問題，所以我們這樣寫出來的不能稱為一個算法。把它一般化就成為一個算法。而且從第一步到最后一步做到環(huán)環(huán)相扣，分工明確。,算法特征：普遍性、邏輯性,方法：已知數(shù)字在一個范圍內(nèi)（030）,1.報出首次T1； 2.根據(jù)回答確定下一個區(qū)間： （1）若T1低于數(shù)字P，則下一個區(qū)間為（T1，30）； （2）若T1高于數(shù)字P，則價格區(qū)間為（0，T1）； （3）若T1等于數(shù)字

4、P，則游戲結(jié)束. 3.若沒結(jié)束，則報出上面確定的新區(qū)間的中點T2. 按照這種方法，繼續(xù)判斷，直到游戲結(jié)束 .,例二 思考以下問題的算法：,一位商人有9枚銀元，其中有1枚略輕的是假銀元。你能用天平（不用砝碼）將假銀元找出來嗎？,解: 1.把銀元分成3組，每組3枚。,2先將兩組分別放在天平的兩邊。如果天平不平衡，那邊假銀元就放在輕的那一組；如果天平左右平衡，則假銀元就在末稱的第3組里。,3取出含假銀元的那一組，從中任取兩枚放在天平的兩邊。如果左右不平衡，則輕的那一邊就是假銀元；如果天平兩邊平衡，則末稱的那一枚就是假銀元。,2班提問 確定,1班提問 確定,3班提問 確定,算法特征：不唯一性,在解決這

5、個問題時我們共有幾個方法，是不是每種方法都能把假銀元找出來呢,兩個大人和兩個小孩一起渡河，渡口只有一條小船每次只能渡1 個大人或兩個小孩，他們四人都會劃 船，但都不會游泳試問他們怎樣渡過河去？請寫出一個渡河方案。,智力大比拼,S1 兩個小孩同船過河去；,S2 一個小孩劃船回來；,S3 一個大人劃船過去,S4 對岸的小孩劃船回來；,S5 兩個小孩同船過河去；,S6 一個小孩劃船回來；,S7 余下的一個大人獨自劃船渡過河去；,S8對岸的小孩劃船回來；,S9 兩個小孩再同時劃船渡過河去。,算法特征：有限性、確定性,在解決這個問題時我們的步驟有點多，但是我們最終也把事情做完了。,說明：,1算法實際上就

6、是解決某一類問題的步驟和方法，在解決問題時形成的規(guī)律性的東西，按照算法描述的規(guī)則與步驟，一步一步地去做，最終便能解決問題。,2算法的基本思想就是我們分析問題時的想法。由于想法不同思考的角度不同，著手點不一樣，同一問題存在不同的算法，算法有優(yōu)劣之分。,3從熟悉的問題出發(fā)，體會算法的程序化思想，學會用自然語言來描述算法,算法的特征,普遍性：必須能解決一類問題，并且能重復使用,邏輯性：算法具有正確性和順序性，并且每一步都具 有確切的含義，從而組成一個很強邏輯性的序列,有限性: 一個算法在執(zhí)行有限的步驟后，結(jié)束且有正 確的輸出,不唯一性: 求解某一問題的算法不唯一,3班提問 確定,1班提問 確定,2班

7、提問 確定,確定性：算法的每一步計算都必須有確定的結(jié)果， 不能模棱兩可,應(yīng)用練習,下列關(guān)于算法的說法，正確的有（ ） 求解某一類問題的算法是唯一的； 算法必須在有限步驟操作之后停止； 算法的每一步操作必須是明確的，不能有歧義 或模糊； 算法執(zhí)行后一定產(chǎn)生確定的結(jié)果；, ,例1：在給定素數(shù)表的條件下，請你設(shè)計一個算法，將936分成素因數(shù)的乘積.,回歸,3班提問 確定,2班提問 確定,1班提問 確定,4 6 8,9 3 6,2 3 4,2,2,2,1 1 7,3,3,3 9,1 3,短除法可以使這個過程更清晰.,解：判斷936是否為素數(shù)：否。 確定936的最小素因數(shù)：2。936=2*468 判斷4

8、68是否為素數(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,算法步驟如下：,例二：設(shè)計算法，求840與1764的最大公因數(shù).,解：第一步，將840分解質(zhì)因數(shù)：840=233 5 7;,第二步，將1764分解質(zhì)因數(shù)：1764=22372

9、;,第三步，確定它們的公共質(zhì)因數(shù)：2、3、7;,第四步，確定公共質(zhì)因數(shù)的指數(shù)：2、1、1;,第五步，最大公因數(shù)為：2237= 84.,例三：設(shè)計算法，求方程x2-2x-30的解？,解析 求一元二次方程的根的問題，解法較多，可有配方法、判別式法。本題用判別式法寫出算法。,算法： 1.計算方程的根的判別式 b2-4ac與0的關(guān)系 2.若0，將a,b,c的值代入求根公式x= -b b2-4ac 2a 得解。 3.若0，則方程無解。,例四：設(shè)函數(shù)f(x)的圖象是一條連續(xù)不斷的曲線，寫出用“二分法”求方程 f(x)=0的一個近似解的算法.,第一步，取函數(shù)f(x)，給定精確度d.,第二步，確定區(qū)間a，b，滿足f(a)f(b)0.,第五步，判斷a,b的區(qū)間長度是否小于d或f(m)是否等于0. 若是，則m是方程的近似解；否則，返回第三步.,第三步，取區(qū)間中點.,第四步，若f(a)f(m)0