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

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