算法與程序設計基礎-文庫吧
2025-05-13 00:32 本頁面
【正文】 序，而且也直接反映了算法的設計是否符合結構化原則。描述算法的工具通常有傳統(tǒng)流程圖、 NS 結構化流程圖 、算法描述語言等。一個算法一般都可以用順序、選擇、循環(huán) 3 種基本控制結構組合而成。 例 ： 有黑和藍兩個墨水瓶，但卻錯把黑墨水裝在了藍墨水瓶子里，而藍墨水錯裝在黑墨水瓶子里，要求將其互換。 這是一個非數(shù)值運算問題。因為兩個瓶子的墨水不能直接交換，所以，解決這一類問題的關鍵是需要 借助 第三個墨水瓶。設第三個墨水瓶為白色，其交換步驟如下： ①將黑瓶中的藍墨水裝入白瓶中； ②將藍瓶中的黑墨水裝入黑瓶中； ③將白瓶中的藍墨水裝入藍瓶中； ④交換結束。 例 計算函數(shù) f(x)的值。函數(shù) f(x)為： ??? ?? ??? axbax axabxxf ??? ???)(其中， a， b 為常數(shù)。 本題是一個數(shù)值運算問題。其中 f(x)代表要計算的函數(shù)值，有兩個不同的表達式，根據 x 的取值決定采用哪一個算式。根據計算機具有邏輯判斷的基本功能，用計算機算法描述如下： ①將 a， b 和 x的值輸入到計算機； ②判斷 x 是否 ≤ a？如果條件成立，執(zhí)行第③步，否則執(zhí)行第④步； ③按表達式 bx＋ a，計算出結果存放到 f 中，然后執(zhí)行第⑤步； ④按表達式 ax＋ b，計算出結果存放到 f 中，然后執(zhí)行第⑤步； ⑤輸出 f 的值； ⑥算法結束。 由上述兩個簡單的例子可以看出，一個算法由若干操作步 驟構成，并且，任何簡單或復雜的算法都是由基本功能操作和控制結構這兩個要素組成。算法的控制結構決定了算法的執(zhí)行順序。 計算機解題的過程實際上是實現(xiàn)計算機算法的過程； 計算機算法不同于人工處理 大學計算機基礎 4 的方法，下面 列舉出 工程上常用的幾種算法設計，在實際應用時，各種方法之間往往存在著一定的聯(lián)系。 (1)列舉法 列舉法的基本思想是根據提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗哪些是需要的，哪些是不需要的。 求解不定方程的問題常用此法。 列舉法是計算機基礎算法之一。 列舉法的特點是算法比較簡單， 但當列舉的可能情況較多時，執(zhí)行列舉算法的工作量將會很大。因此，在用列舉法設計算法時，使方案優(yōu)化、盡量減少運算工作量是應該重點 注意 的問題。 列舉原理是計算機應用領域中十分重要的原理；因為許多實際問題若采用人工列舉是不可思議的，但由于計算機的運算速度快并擅長重復操作，計算機便可以輕而易舉地進行大量列舉；因此，列舉法雖然笨拙、原始、運算量大，但在 許多實際問題 中（如查找、搜索等問題）局部使用列舉法還是十分有效的 。 (2)歸納法 歸納法的基本思想是通過列舉少量的特殊情況，經過分析找出一般的關系。從本質上講，歸納法就是 通過觀察一些簡單而特殊的情況，最后總結出一般性的結論。 歸納是一種抽象，即從一個實際問題的特殊現(xiàn)象中總結出一般關系；但由于在歸納的過程中不可能對所有的因素進行一一列舉，因此，最后由歸納得到的結論不是完全可靠的，還需要進一步加以必要的證明。 (3)遞推 遞推是指從已知的初始條件出發(fā)，逐次推出所要求的中間結果和最后結果。其中初始條件或者問題本身已經給定，或者通過對問題的分析與化簡而確定。遞推本質上也屬于歸納法，工程上許多遞推關系式實際上是通過對實際問題的分析與歸納而得到的，因此，遞推關系式往往是歸納的結果。 遞 推 算法經常用于數(shù)值計算；但 對于數(shù)值型的遞推算法必須要注意數(shù)值計算的穩(wěn)定性問題 ，因為計算機中數(shù)值的表示往往是有界的，而數(shù)學意義上數(shù)值是無界的 。 (4)遞歸 人們在解決一些復雜問題時，為了降低問題的復雜程度 (如問題的規(guī)模等 )，一般總是將問題逐層分解，最后歸結為一些最簡單的問題。這種將問題逐層分解的過程，實際上并沒有對問題進行求解，而只是當解決了最后那些最簡單的問題后，再沿著原來分解的逆過程逐步進行綜合，這就是遞歸的基本思想。 遞歸分為直接遞歸與間接遞歸兩種。 例如有算法 P 和 Q， 如果 P 顯式地調用自己則稱為直接遞歸， 如果 P 先調用 Q，而 Q 又調用 P 則稱為間接遞歸。 (5)減半遞推技術 實際問題的復雜程度往往與問題的規(guī)模有著密切的聯(lián)系，因此，利用分治法解決這類實際問題非常有效。工程上常用的分治法是減半遞推技術。 所謂“減半”是指將問題的規(guī)模減半，而問題的性質不變；所謂“遞推”是指重復“減半”的過程。 第 5 章 算法與程序設計基礎 5 例 設方程 f(x)=0 在區(qū)間【 a,b】上有實根，且 f(a)與 f(b)異號。利用二分法求其在區(qū)間【 a,b】上的一個實根 。 減半遞推 過程如下： 首先取給定區(qū)間的中點 c=(a+b)/2；然后判斷 f(c)是否為 0，若為 0，則 c 就是 根，結束；否則根據以下原則將原區(qū)間減半： 若 f(a)*f(c)0，則取原區(qū)間的前半部分； 若 f(b)*f(c)0，則取原區(qū)間的后半部分。 最后判定減半后的區(qū)間長度是否已經很??；若是很小 ，則取 (a+b)/2 為根的近似值，否則重復上述減半過程。（很小的概念取決于計算機的精度） (6)回溯法 在工程上，有些實際問題很難歸納出一組簡單的遞推公式或直觀的求解步驟，并且也不能進行無限的列舉。對于這類問題，一種有效的方法是＂試＂。通過對問題的分析，找出一個解決問題的線索，然后沿著這個線索逐步試探，若試探成功，就得到問 題的解，若試探失敗，就逐步回退，換別的路線再逐步試探。 常用于處理復雜數(shù)據結構。 算法復雜度 算法的復雜度包括時間復雜度和空間復雜度。 所謂 算法的時間復雜度是指執(zhí)行算法所需要的計算工作量。 算法所執(zhí)行的基本運算次數(shù) 與計算機硬件、軟件因素 無 關 。 算法所執(zhí)行的基本運算次數(shù)與問題的規(guī)模有關。對于一個固定的規(guī)模，算法所執(zhí)行的基本運算次數(shù)還可能與特定的輸入有關。
醫(yī)療健康相關推薦
鄂ICP備17016276號-1