算法的基本思想課件

隨著計算機科學(xué)和信息技術(shù)的飛速發(fā)展，計算機已經(jīng)被應(yīng)用到了我們生活的方方面面，那么計算機是怎樣工作的呢？這就要用到算法的思想。在以前的學(xué)習(xí)中，雖然沒有出現(xiàn)算法這個名詞，在數(shù)學(xué)學(xué)習(xí)中已經(jīng)學(xué)習(xí)到了大量的算法的思想，例如四則運算的過程，求解方程的步驟等等。完成這些工作都需要一系列程序化的步驟，這就是算法的思想。本章中，我們將介紹算法的基本思想、基本結(jié)構(gòu)和描述算法的基本語句。這對我們理解數(shù)學(xué)與計算機技術(shù)的關(guān)系是有很大幫助的。算法的基本思想隨著計算機科學(xué)和信息技術(shù)的飛速發(fā)展，計算機已經(jīng)被1算法的基本思想算法的基本思想算法的基本思想算法的基本思想2【例1】在電視臺的某個娛樂節(jié)目中，要求參與者快速猜出物品的價格。主持人出示某件物品，參與者每次估算出一個價格，主持人只能回答高了、低了或者正確。在某次節(jié)目中，主持人出示了一臺價值在1000元以內(nèi)的隨身聽，并開始了競猜。下面是主持人和參與者的一段對話：….如果你是參與者，你接下來會怎么猜？800元！高了400元！600元！低了高了參與者主持人：李詠算法的基本思想【例1】在電視臺的某個娛樂節(jié)目中，要求參與者快速猜出物品的價3例2：給定素數(shù)表，設(shè)計算法，將936分解成素因數(shù)的乘積。判斷936是否為素數(shù)：確定936的最小素因數(shù)：確定468的最小素因數(shù)：判斷468是否為素數(shù)：判斷234是否為素數(shù)：確定234的最小素因數(shù)：否2936＝468×2936＝234×22936＝117×23否2否2算法的基本思想例2：給定素數(shù)表，設(shè)計算法，將936分解成判斷936是否為素4判斷117是否為素數(shù)：否確定117的最小素因數(shù)：936＝39×23×33判斷39是否為素數(shù)：否確定39的最小素因數(shù)：3936＝13×23×32判斷13是否為素數(shù)：是結(jié)束分解結(jié)果為：936＝13×23×32936468234117392223133算法的基本思想判斷117是否為素數(shù)：否確定117的最小素因數(shù)：936＝395練習(xí)：將下列兩個數(shù)分解素因數(shù)

（1）840

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

2．先將兩組分別放在天平的兩邊。如果天平不平衡，那邊假銀元就放在輕的那一組；如果天平左右平衡，則假銀元就在末稱的第3組里。3．取出含假銀元的那一組，從中任取兩枚放在天平的兩邊。如果左右不平衡，則輕的那一邊就是假銀元；如果天平兩邊平衡，則末稱的那一枚就是假銀元。1.把銀元分成3組，每組3枚。算法的基本思想解:2．先將兩14算法的基本思想算法的基本思想15說明：1算法實際上就是解決某一類問題的步驟和方法，在解決問題時形成的規(guī)律性的東西，按照算法描述的規(guī)則與步驟，一步一步地去做，最終便能解決問題。2算法的基本思想就是我們分析問題時的想法。由于想法不同思考的角度不同，著手點不一樣，同一問題存在不同的算法，算法有優(yōu)劣之分。3從熟悉的問題出發(fā)，體會算法的程序化思想，學(xué)會用自然語言來描述算法算法的基本思想說明：1算法實際上就是解決某一類問題的步驟和方法，在解決問題16算法的特點：有限性：一個算法的步驟必須是有限的，必須在有限操作之后停止，不能是無限的.確定性：算法中的每一步應(yīng)該是確定的并且能有效地執(zhí)行且得到確定的結(jié)果，而不應(yīng)當(dāng)是模棱兩可.普遍性：一個算法通常設(shè)計成能解決一類問題，不不唯一性：求解某一個問題的解法不一定是唯一的，對于一個問題可以有不同的算法.是僅僅解決一個單獨問題的。算法的基本思想算法的特點：有限性：一個算法的步驟必須是有限的，必須在有17例四設(shè)函數(shù)f(x)的圖象是一條連續(xù)不斷的曲線，寫出用“二分法”求方程f(x)=0的一個近似解的算法.

算法的基本思想例四設(shè)函數(shù)f(x)的圖象是一條連續(xù)不斷的曲線，寫出用“二18第一步，取函數(shù)f(x)，給定精確度d.第二步，確定區(qū)間[a，b]，滿足f(a)·f(b)<0.第五步，判斷[a,b]的長度是否小于d或f(m)是否等于0.若是，則m是方程的近似解；否則，返回第三步.第三步，取區(qū)間中點.第四步，若f(a)·f(m)<0,則含零點的區(qū)間為[a,m],否則，含零點的區(qū)間為[m，b].

將新得到的含零點的區(qū)間仍記為[a,b];算法的基本思想第一步，取函數(shù)f(x)，給定精確度d.第二步，確定區(qū)間[a19隨著計算機科學(xué)和信息技術(shù)的飛速發(fā)展，計算機已經(jīng)被應(yīng)用到了我們生活的方方面面，那么計算機是怎樣工作的呢？這就要用到算法的思想。在以前的學(xué)習(xí)中，雖然沒有出現(xiàn)算法這個名詞，在數(shù)學(xué)學(xué)習(xí)中已經(jīng)學(xué)習(xí)到了大量的算法的思想，例如四則運算的過程，求解方程的步驟等等。完成這些工作都需要一系列程序化的步驟，這就是算法的思想。本章中，我們將介紹算法的基本思想、基本結(jié)構(gòu)和描述算法的基本語句。這對我們理解數(shù)學(xué)與計算機技術(shù)的關(guān)系是有很大幫助的。算法的基本思想隨著計算機科學(xué)和信息技術(shù)的飛速發(fā)展，計算機已經(jīng)被20算法的基本思想算法的基本思想算法的基本思想算法的基本思想21【例1】在電視臺的某個娛樂節(jié)目中，要求參與者快速猜出物品的價格。主持人出示某件物品，參與者每次估算出一個價格，主持人只能回答高了、低了或者正確。在某次節(jié)目中，主持人出示了一臺價值在1000元以內(nèi)的隨身聽，并開始了競猜。下面是主持人和參與者的一段對話：….如果你是參與者，你接下來會怎么猜？800元！高了400元！600元！低了高了參與者主持人：李詠算法的基本思想【例1】在電視臺的某個娛樂節(jié)目中，要求參與者快速猜出物品的價22例2：給定素數(shù)表，設(shè)計算法，將936分解成素因數(shù)的乘積。判斷936是否為素數(shù)：確定936的最小素因數(shù)：確定468的最小素因數(shù)：判斷468是否為素數(shù)：判斷234是否為素數(shù)：確定234的最小素因數(shù)：否2936＝468×2936＝234×22936＝117×23否2否2算法的基本思想例2：給定素數(shù)表，設(shè)計算法，將936分解成判斷936是否為素23判斷117是否為素數(shù)：否確定117的最小素因數(shù)：936＝39×23×33判斷39是否為素數(shù)：否確定39的最小素因數(shù)：3936＝13×23×32判斷13是否為素數(shù)：是結(jié)束分解結(jié)果為：936＝13×23×32936468234117392223133算法的基本思想判斷117是否為素數(shù)：否確定117的最小素因數(shù)：936＝3924練習(xí)：將下列兩個數(shù)分解素因數(shù)

（1）840

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

2．先將兩組分別放在天平的兩邊。如果天平不平衡，那邊假銀元就放在輕的那一組；如果天平左右平衡，則假銀元就在末稱的第3組里。3．取出含假銀元的那一組，從中任取兩枚放在天平的兩邊。如果左右不平衡，則輕的那一邊就是假銀元；如果天平兩邊平衡，則末稱的那一枚就是假銀元。1.把銀元分成3組，每組3枚。算法的基本思想解:2．先將兩33算法的基本思想算法的基本思想34說明：1算法實際上就是解決某一類問題的步驟和方法，在解決問題時形成的規(guī)律性的東西，按照算法描述的規(guī)則與步驟，一步一步地去做，最終便能解決問題。2算法的基本思想就是我們分析問題時的想法。由于想法不同思考的角度不同，著手點不一樣，同一問題存在不同的算法，算法有優(yōu)劣之分。3從熟悉的問題出發(fā)，體會算法的程序化思想，學(xué)會用自然語言來描述算法算法的基本思想說明：1算法實際上就是解決某一類問題的步驟和方法，在解決問題35算法的特點：有限性：一個算法的步驟必須是有限的，