素材：2012屆高中數(shù)學(xué)2.1算法的基本思想素材北師大必修3.doc

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