（整理版）幾種常見的算法案例分析_第1頁
（整理版）幾種常見的算法案例分析_第2頁
（整理版）幾種常見的算法案例分析_第3頁
全文預覽已結束

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、幾種常見的算法案例分析算法不僅是數學及其應用的重要的組成局部，也是計算機科學的重要根底，其中算法的重要思想在幾種常見的算法例案中得以較好的表達。本文從幾種常見算法案例出發，來探究一下算法的內涵。一、 輾轉相除法所謂輾轉相除法，就是對于給定的兩個數，用較大的數除以較小的數，假設余數不為零，那么將余數和較小的數構成新的一對數，繼續上面的除法，直到大數被小數除盡，那么這時的較小的數就是原來兩個數的最大公約數。例1 寫出求兩個正數的最大公約數的一個算法。算法設計：第一步：輸入兩個正整數； 第二步：把的余數賦予； 第三步：如果，那么把賦予，把賦予，轉到第二步；否那么轉到第四步； 第四步：輸入最大公約數。

2、 程序框圖下列圖所示： yn開始 輸入 r=mod(a,b)a=bb=rr=0輸出結束用偽代碼表示：input“a=,b=；a,b do r=mod(a,b) a=b b=r loop until r=0 print b end二、 更相減損術所謂更相減術，就是對于給定的兩個數，以其中較大的數減去較小的數，然后將差和較小的數構成一對新數，再用較大的數減去較小的數，反復執行此步驟，直到差數和較小的數相等，此時相等的兩個數就是原兩個數的最大公約數。在我國古代的<<九章算術>>中有這樣的描述“約分術曰：可半者半之，不可半者會置分母分子之數，以少減多，更相損減，求其等也，以等數

3、約之。意思是說如果分母、分子都是偶數，那么先除以2；如果不全是偶數，便將分子與分母互減，以少減多，直到得出最大公約數為止，用最大公約數約分子與分母，便可使分數最簡。如果兩個數都是偶數，也不除以2，直接求最大公約數。這是一種多么奇妙的方法啊，我們古代人在許多方面都比西方先進，這是值得我們自豪的。以上題為例，算法可以這樣來設計：第一步：輸入兩個正整數；第二步：假設不等于，那么執行第三步；否那么執行第五步；第三步：把的差賦予；第四步：如果，那么把的值賦予，否那么把的值賦予，執行第二步；第五步：輸出最大公約數。程序框圖如圖(2)所示：用偽代碼表示：input a,bwhile a<>b r

4、=a-b if b>r then a=b b=r else a=r end if wendprint bend 三、 秦九韶算法例2、寫出，求多項式的值的一個算法。算法1：input “x；x p= print “p；p end 算法2：input “x；x p= print “p；p end 比擬上述兩種算法，我們可以看出算法2是較為方便的，這種算法就是“秦九韶算法。其特點是：通過一次式的反復計算，逐步得出高次多項式的值，對于一個次多項式，只要做次乘法和次加法即可。例3、試描述給定的值，求多項式值的算法。分析：我們先看給定一個定值，求5次多項式函數值的例子。首先可以把多項式一步一步的改寫： 上面分層計算：第一步：計算最內層的值，把的值賦給一個變量；第二步：計算的值，可以改寫為四、 直接插入排序法五、 冒泡排序法希望同學們通過對上

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論