算法設計與分析 課件 1.2.1-算法分析準則 - 正確性_第1頁
算法設計與分析 課件 1.2.1-算法分析準則 - 正確性_第2頁
算法設計與分析 課件 1.2.1-算法分析準則 - 正確性_第3頁
算法設計與分析 課件 1.2.1-算法分析準則 - 正確性_第4頁
算法設計與分析 課件 1.2.1-算法分析準則 - 正確性_第5頁
已閱讀5頁，還剩3頁未讀， 繼續免費閱讀

下載本文檔

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

文檔簡介

信息工程大學算法設計與分析算法分析—正確性國家級實驗教學示范中心計算機學科組規劃教材算法設計與分析Python案例詳解微課視頻版正確性對算法的任何有效（合法）輸入，算法能在有限時間內，給出問題的正確結果。證明步驟

1.建立一個給出算法輸入后算法產生什么樣的結果的命題。2.證明算法中使用的各種方法是正確的。3.證明命題是正確的。正確性

1.

j=1;2.whilej≤nandL[j]≠xdo3.j=j+1;4.ifj>nthenj=0;5.

output(j)

命題1：如果L是一個具有n項的表，若表中有一個等于X的項，那么這個算法以將j置成表中等于X的項的下標而結束；否則，若表中沒有等于X的項，則這個算法將j置成0而結束。命題2：給定一個具有n項（n≥0）的數組L，并且給定X，當X在L之中時，順序搜索算法將j置成X在L中第一次出現處的下標而結束，否則算法將j置成0而結束。正確性缺點：一是沒有說明當x在表中多次出現時的結果；二是沒有指明算法在n為何值時工作。

1.

j:=1;2.whilej≤nandL[j]≠xdo3.j:=j+1;4.ifj>nthenj:=0;5.output(j)

命題3：對于1≤k≤n+1,假若算法第k次地執行第2行中的測試，則下列條件成立：1.j=k而且對1≤i＜k,L(i)≠X。2.若k≤n而且L(k)=X，則算法將在執行了第2行中的測試和第4行以后結束，此時j仍然等于k。3.若k=n+1，則算法將在執行了第2行中的測試和第4行以后結束，此時j=0。數學歸納法證明的思路：1.證明k=1時，命題3成立；2.假設k<n+1時，命題3成立；3.證明k+1時，命題3成立命題3：對于1≤k≤n+1,假若算法第k次地執行第2行中的測試，則下列條件成立：1.j=k而且對1≤i＜k,L(i)≠X。2.若k≤n而且L(k)=X，則算法將在執行了第2行中的測試和第4行以后結束，此時j仍然等于k。3.若k=n+1，則算法將在執行了第2行中的測試和第4行以后結束，此時j=0。證明一個算法的正確性，首先需要建立（），并常用（）進行證明。A：給出輸入后算法將要產生什么結果的命題B：解決問題的方法C：數學歸納法D：反證法測試正確性是如何證明的；

溫馨提示

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

評論

0/150

提交評論