算法的基本思想第一頁(yè)，共20頁(yè)。算法的基本思想第二頁(yè)，共20頁(yè)。【例1】在電視臺(tái)的某個(gè)娛樂(lè)節(jié)目中，要求參與者快速猜出物品的價(jià)格。主持人出示某件物品，參與者每次估算出一個(gè)價(jià)格，主持人只能回答高了、低了或者正確。在某次節(jié)目中，主持人出示了一臺(tái)價(jià)值在1000元以內(nèi)的隨身聽(tīng)，并開(kāi)始了競(jìng)猜。下面是主持人和參與者的一段對(duì)話：….如果你是參與者，你接下來(lái)會(huì)怎么猜？800元！高了400元！600元！低了高了參與者主持人：李詠第三頁(yè)，共20頁(yè)。例2：給定素?cái)?shù)表，設(shè)計(jì)算法，將936分解成素因數(shù)的乘積。判斷936是否為素?cái)?shù)：確定936的最小素因數(shù)：確定468的最小素因數(shù)：判斷468是否為素?cái)?shù)：判斷234是否為素?cái)?shù)：確定234的最小素因數(shù)：否2936＝468×2936＝234×22936＝117×23否2否2第四頁(yè)，共20頁(yè)。判斷117是否為素?cái)?shù)：否確定117的最小素因數(shù)：936＝39×23×33判斷39是否為素?cái)?shù)：否確定39的最小素因數(shù)：3936＝13×23×32判斷13是否為素?cái)?shù)：是結(jié)束分解結(jié)果為：936＝13×23×32936468234117392223133第五頁(yè)，共20頁(yè)。練習(xí)：將下列兩個(gè)數(shù)分解素因數(shù)

（1）840

（2）1764第六頁(yè)，共20頁(yè)。例3：設(shè)計(jì)一個(gè)算法，求840與1764的最大公因數(shù)。解：算法步驟如下：1.先將840進(jìn)行素因數(shù)分解：840=23×3×5×7；3.確定它們公共素因數(shù)：2,3,7；4.確定公共素因數(shù)的指數(shù)：公共素因數(shù)2，3,7的指數(shù)分別為2,1,1；2.先將1764進(jìn)行素因數(shù)分解:1764=22×32×72；5.最大公因數(shù)為：22×31×71=84第七頁(yè)，共20頁(yè)。寫算法的要求寫出的算法，必須能解決一類問(wèn)題（如求兩個(gè)正整數(shù)的最大公因數(shù)），并且能重復(fù)使用。算法過(guò)程要一步一步執(zhí)行，每一步執(zhí)行的操作必須明確，不能含混不清，而且在有限步驟內(nèi)能得出結(jié)果。算法要簡(jiǎn)潔，清晰可讀，不能搞得繁雜。算法不同于求解一個(gè)具體問(wèn)題的方法，是這種方法的高度概括。一個(gè)好的算法有如下要求：第八頁(yè)，共20頁(yè)。算法是什么算法可以理解為由基本運(yùn)算及規(guī)定的運(yùn)算順序構(gòu)成的一個(gè)完整的解題步驟，或看成是按要求設(shè)計(jì)好的有限的、確切的計(jì)算步驟，并且這樣的步驟能解決一類問(wèn)題?，F(xiàn)代意義上的“算法”通常是指可以用計(jì)算機(jī)來(lái)解決的某一類問(wèn)題的程序或步驟。第九頁(yè)，共20頁(yè)?！绊n信點(diǎn)兵”問(wèn)題第十頁(yè)，共20頁(yè)。第十一頁(yè)，共20頁(yè)。思考以下問(wèn)題的算法：一位商人有9枚銀元，其中有1枚略輕的是假銀元。你能用天平（不用砝碼）將假銀元找出來(lái)嗎？第十二頁(yè)，共20頁(yè)。第十三頁(yè)，共20頁(yè)。解:

2．先將兩組分別放在天平的兩邊。如果天平不平衡，那邊假銀元就放在輕的那一組；如果天平左右平衡，則假銀元就在末稱的第3組里。3．取出含假銀元的那一組，從中任取兩枚放在天平的兩邊。如果左右不平衡，則輕的那一邊就是假銀元；如果天平兩邊平衡，則末稱的那一枚就是假銀元。1.把銀元分成3組，每組3枚。第十四頁(yè)，共20頁(yè)。第十五頁(yè)，共20頁(yè)。說(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)描述算法第十六頁(yè)，共20頁(yè)。算法的特點(diǎn)：有限性：一個(gè)算法的步驟必須是有限的，必須在有限操作之后停止，不能是無(wú)限的.確定性：算法中的每一步應(yīng)該是確定的并且能有效地執(zhí)行且得到確定的結(jié)果，而不應(yīng)當(dāng)是模棱兩可.普遍性：一個(gè)算法通常設(shè)計(jì)成能解決一類問(wèn)題，不不唯一性：求解某一個(gè)問(wèn)題的解法不一定是唯一的，對(duì)于一個(gè)問(wèn)題可以有不同的算法.是僅僅解決一個(gè)單獨(dú)問(wèn)題的。第十七頁(yè)，共20頁(yè)。例四設(shè)函數(shù)f(x)的圖象是一條連續(xù)不斷的曲線，寫出用“二分法”求方程f(x)=0的一個(gè)近似解的算法.

第十八頁(yè)，共20頁(yè)。第一步，取函數(shù)f(x)，給定精確度d.第二步，確定區(qū)間[a，b]，滿足f(a)·f(b)<0.第五步，判斷[a,b]的長(zhǎng)度是否小于d或f(m)是否等于0.若是，則m是方程的近似解；否則，返回第三步.第三步，取區(qū)間中點(diǎn).