第二章 算法初步第一節 算法的基本思想一 算法概念所謂算法可理解為由基本運算及規定的運算順序所構成的完整的解題步驟，或看成按照要求設計好的有限的確切的計算序列，并且這樣的步驟或序列能夠解決一類問題。 算法作為一個名詞，我們雖沒有深刻接觸過這個概念，但算法在我們的學習和日常生活中卻已經是無處不在了。如我們在小學學過的四則運算法則：先乘除后加減從里往外脫括弧以及乘法口訣，洗衣機的使用說明書，中國象棋的棋譜，國際象棋的棋譜等都是算法的具體體現。因此，處理任何問題都需要算法，從廣義上說，算法就是做某一件事的步驟或程序。在數學上，現代意義上的“算法”通常是指可以用計算機來解決的某一類問題的程序或步驟，這些程序或步驟必須是明確和有效的，而且能夠在有限步之內完成.。算法一般是機械的，有時要進行大量重復的計算，只要按部就班的去做總能算出結果，通常把算法過程稱為“數學機械化”。 二 算法的要求應當注意的是，我們現在所學習的算法是不同于求解一個具體問題的方法，它的要求是：寫出的算法，必須能解決一類問題，并且能重復使用；算法過程能一步一步執行，每一步執行的操作，必須確切，不能含糊不清，而且在有限步后能得出結果。對于上述的算法要求，可細分如下：(1)、有窮性：一個算法的步驟序列是有限的，必須在有限操作之后停止，不能是無限的。這一點是十分重要的，是成功完成任務的必要條件，特別在算法的循環結構中，一定要考慮好何時終止，轉入下一步操作。(2)、確定性：算法中的每一步應該是確定的并且能有效地執行，且能得到確定的結果，而不應是模棱兩可。(3)、通用性：算法應該適用于求解一類問題，而不是只是用來解決一個具體的問題。這樣在解決具體問題時，可以先針對具體問題涉及算法，在設計的過程中，或在設計完成后，考慮如何修改或推廣該算法可以解決類似的問題，已達到通用性的要求。(4)、能行性：算法中每一部的運算和操作必須是相當基本的，也即它們原則上是能夠精確地執行的。所謂基本和能實現是相對的，如：讓計算機計算12345是可以做到的，但讓計算機去執行“倒一杯水”“替我理發”等則是做不到的。(5) 有輸入有輸出 算法有零個或多個輸入，還要有一個或多個輸出。三 算法的表達描述表達描述算法可以有不同的方式，常用的有自然語言、程序框圖、程序設計語言、為代碼等。自然語言 它是指用漢語、英語或數學語言描述算法。優點是通徐易懂，黨算法中的操作不重復且都是按順序執行時，比較容易描述，如果算法中包含判斷和轉向，并且操作步驟較多時，此時描述起來就不那么直觀清晰了。程序框圖 就是用規定的圖形符號來描述算法。用程序框圖描述算法，它逆補了自然語言描述算法時有時顯得庸長且易產生歧義的不足，它具有直觀結構清晰、條理分明、便于檢查修改與交流等優點。程序設計語言 算法最終要通過程序的形式編寫出來，并在計算機上執行，程序設計語言分為低級語言和高級語言，低級語言包括機器語言和匯編語言，機器語言是計算機唯一能夠識別的語言，匯編語言是一種符號語言。高級語言也叫算法語言，其表達方式接近于自然語言，容易被人們掌握和書寫。四 概念應用靈活運用算法的概念和算法的基本思想和方法，可以寫出一此簡單問題的算法，我們常見的算法問題主要有兩類：第一類 數值性計算問題如：解方程（或方程組），解不等式（或不等式組），套用公式判斷性的問題，累加，累乘等一類問題的算法描述，對這類問題的解決我們可通過建立相應的數學模型，或通過固有的公式或計算方法來進行算法的設計與描述，同時要求所涉及的算法要步驟清晰和條理。例1、寫出解方程x22x30的一個算法。解：算法1：第一步：移項，得x22x30； 第二步：式兩邊同加1并配方，得（x1）24； 第三步：式兩邊開方，得x12； 第四步：解得x3或x1。算法2：第一步：計算方程的判別式并判斷其符號2243160；第二步：將a1，b2，c3代入求根公式x，得x13，x21點評：求解某個問題的算法不同于求解一個具體問題的方法，因此在設計算法時一定要做到以下幾點：（1）寫出的算法必須能解決一類問題，并且能夠重復使用；（2）要使算法盡量簡單、步驟盡量少；（3）要保證算法正確，且計算機能夠執行。而在本題中出現了兩種不同的算法，比較兩種算法發現，算法2更簡單，步驟少，所以利用公式解決問題是最理想、合算的算法，因此我們在今后設計算法的過程時，首先要考慮利用公式。第二類 非數值性計算問題解決對于象排序、查找、變量變換、文字處理等非數值性計算問題，要先建立過程模型，通過模型來進行算法的設計與描述。例2、有藍和黑兩個墨水瓶，但現在卻錯把藍墨水裝在了黑墨水瓶中，黑墨水錯裝在了藍墨水瓶中，要求將其互換，請你設計算法解決這一問題。分析：由于兩個墨水瓶中的墨水不能直接交換，故可以考慮通過引入第三個空墨水瓶的辦法進行交換。解：算法步驟如下：第一步：取一只空的墨水瓶，設其為白色；第二步：將黑墨水瓶中的藍墨水裝入白瓶中；第三步：將藍墨水瓶中的黑墨水裝入黑瓶中；第四步：將白瓶中的藍墨水裝入藍瓶中；第五步：交換結束。點評：在本體中我們首先建立過程模型