《數(shù)學(xué)算法概念》PPT課件.ppt

數(shù)學(xué)必修 3 第一章 算法初步 1.1算法與程序框圖 1.1.1算法的概念（ 1） 2011年 11月 14日 算法作為一個名詞，在中學(xué)課本中并沒有出現(xiàn)過，沒有學(xué)習(xí)過 什么叫算法這個概念。但是我們對算法并不陌生，從小學(xué)就開 始接觸算法，熟悉許多問題的算法。如，數(shù)的四則運算要先乘 除后加減，從里往外脫括弧，豎式筆算等都是算法，還有乘法 口訣、珠算口訣更是算法的具體體現(xiàn)。生活中，菜譜是菜肴的 算法，洗衣機的說明書是操作洗衣機的算法，歌譜是歌曲的算 法， 在數(shù)學(xué)中，我們主要研究用計算機實現(xiàn)的算法，即按照某 種機械程序步驟一定可以得到結(jié)果的解決問題的程序。 從小學(xué) 到高中我們所學(xué)的算法很多是與計算有關(guān)的問題。比如解方程 的算法、函數(shù)求值的算法、作圖的算法，等等。 在數(shù)學(xué)課上的算法，數(shù)學(xué)課上的計算機課，與計算機課上的數(shù) 學(xué)不一樣，主要是利用計算機解決與數(shù)學(xué)有關(guān)的算術(shù)問題，利 用計算機解決一起我們所學(xué)過的數(shù)學(xué)問題。 計算工具：古代 算盤 現(xiàn)代：計算機 20世紀(jì)最偉大的發(fā)明：計算機，計算機是強大的實現(xiàn)各種算 法的工具。 下面通過幾個具體的生活實例體會算法的含義。 1.把蘋果裝入冰箱里分幾步？ 第一步： 把冰箱門打開。 第二步： 把蘋果放進(jìn)冰箱。 第三步： 把冰箱門關(guān)上。 2.在家中燒開水的過程分幾步？ 第一步：打開壺蓋加水蓋上蓋子 第二步：壺放在火上開火 第三步：水開后關(guān)火。 小結(jié)： 這是生活中的算法，做這件事是 有先后順序的，邏輯性的，打亂順序就不 能完成任務(wù)，分三步完成步驟缺一不可， 步驟是有限的，每步的結(jié)果是明確的，每 步都有通用性，人們只要按照該步驟執(zhí)行 可完成任務(wù)。誰家燒開水都會按這個順序 完成的，只要按以上步驟做都可以完成這 一類問題，但他們不能用計算機來操作。 這是生活中的例子， 下面我們重要學(xué)習(xí)數(shù)學(xué)中的算法。 知識探究（一）：算法的概念 在初中，對于解二元一次方程組你學(xué)過 哪些方法？ 用加減消元法解二元一次方程組 x-2y=-1 2x+y=1 的具體步驟是什么？ 加減消元法和代入消元法 + 2，得 5x=1 . 15x 解，得 . 1 5 x - 2，得 5y 3 . 解，得 . 3 5 y 第一步， 第二步， 第三步， 第四步， 第五步， 得到方程組的解為 . 1 5 3 5 x y = = yx yx 12 12 代入消元法： yx yx 12 12 解：第一步： - 2得 5y=3； 第二步：解得 5 3 y 5 3 y 5 1x 第三步：將 代入，得 小結(jié)：解二元一次方程組的過程 1.步驟有一定的順序性，打亂順序不能 完成任務(wù) 2.步驟完整性缺一不可 3.步驟有限性 4.每步結(jié)果明確 5.步驟通用性，任何人只要按照步驟執(zhí) 行就可以完成這類任務(wù) 參照上述思路，一般地，解方程 組 的基 本步驟是什么？ 1 1 1a x b y c 2 2 2a x b y c 1 2 2 1 0a b a b（ ） 2b 1b 第一步， - ，得 . 1 2 2 1 2 1 1 2()a b a b x b c b c 第二步，解 ，得 . 2 1 1 2 1 2 2 1 b c b cx a b a b 第三步， - ，得 . 1 a 2a 1 2 2 1 1 2 2 1()a b a b y a c a c 第四步，解 ，得 . 1 2 2 1 1 2 2 1 a c a cy a b a b 第五步，得到方程組的解為 2 1 1 2 1 2 2 1 1 2 2 1 1 2 2 1 b c b c x a b a b a c a c y a b a b 解： 第 一 步 ： a 1 - a 2 ， 得 ： 12211221 cacaybaba 第二步：解得 1221 1221 baba caca y ； 第三步：將 1221 1221 baba caca y 代入，得 11 1 c b y x a 在數(shù)學(xué)中，算法通常是按照一定規(guī)則 解決某 一類 問題的 明確 和 有限 的步驟。 一、算法的定義 現(xiàn)在算法通?？梢跃帉懗捎嬎銠C程序 讓計算機執(zhí)行并解決問題。 二、對算法定義的理解 1 在數(shù)學(xué)中 ，只針對數(shù)學(xué)中的問題 2一定的規(guī)則： 設(shè)計算法的依據(jù)， 即不同的數(shù)學(xué)結(jié)論或方法不同的 規(guī)則得到的算法是不同的算法。 3某一類問題 ：通用性有時也可把某 一具體問題的步驟看成算法 4明確和有限： 步驟最顯著特征就是順 序，每一步都是明確的，在有限步內(nèi)完成 不能無限執(zhí)行。 三、算法的特征 1有限性 （一個算法的步驟序列是有限 性的，必須在有限操作后停止不能無限） 2確定性 （算法中的每一步都是確定的， 并且能有效的執(zhí)行且得到確定的結(jié)果，而不 應(yīng)是摸棱兩可） 3有序性 （前后順序缺一不可） 4不惟一性 （對于一個問題有不同的算法） 5通用性 1自然語言 四、算法的表現(xiàn)形式 2。程序框圖 3。程序語句 五、設(shè)計算法的格式 step S1: S2:. . . . Sn:. 第一步： . 第二步： . . 第幾步： . 知識探究（二） :算法的步驟設(shè)計 如果讓計算機判斷 7是否為質(zhì)數(shù)，如何設(shè)計 算法步驟？ 第一步，用 2除 7，得到余數(shù) 1,所以 2不能整除 7. 第四步，用 5除 7，得到余數(shù) 2,所以 5不能整除 7. 第五步，用 6除 7，得到余數(shù) 1,所以 6不能整除 7. 第二步，用 3除 7，得到余數(shù) 1,所以 3不能整除 7. 第三步，用 4除 7，得到余數(shù) 3,所以 4不能整除 7. 因此， 7是質(zhì)數(shù) . 如果讓計算機判斷 35是否為質(zhì)數(shù)，如何設(shè)計 算法步驟？ 第一步，用 2除 35，得到余數(shù) 1,所以 2不能整除 35. 第二步，用 3除 35，得到余數(shù) 2,所以 3不能整除 35. 第三步，用 4除 35，得到余數(shù) 3,所以 4不能整除 35. 第四步，用 5除 35，得到余數(shù) 0,所以 5能整除 35. 因此， 35不是質(zhì)數(shù) . 整數(shù) 89是否為質(zhì)數(shù)？如果讓計算機判斷 89是否為質(zhì)數(shù)，按照上述算法需要設(shè)計 多少個步驟？ 第一步，用 2除 89，得到余數(shù) 1,所以 2不能整除 89. 第二步，用 3除 89，得到余數(shù) 2,所以 3不能整除 89. 第三步，用 4除 89，得到余數(shù) 1,所以 4不能整除 89. 第八十七步，用 88除 89，得到余數(shù) 1,所以 88不能 整除 89. 因此， 89是質(zhì)數(shù) . 用 2 88逐一去除 89求余數(shù)，需要 87個步驟， 這些步驟基本是重復(fù)操作，我們可以按下面 的思路改進(jìn)這個算法，減少算法的步驟 . （ 1）用 i表示 2 88中的任意一個整數(shù)，并從 2開始取數(shù)； （ 2）用 i除 89，得到余數(shù) r. 若 r=0，則 89不 是質(zhì)數(shù)；若 r0 ，將 i用 i+1替代，再執(zhí)行同 樣的操作； （ 3）這個操作一直進(jìn)行到 i取 88為止 . 你能按照這個思路，設(shè)計一個“判斷 89是否 為質(zhì)數(shù)”的算法步驟嗎？ 用 i除 89，得到余數(shù) r； 令 i=2； 若 r=0，則 89不是質(zhì)數(shù)，結(jié)束算 法；若 r0 ，將 i用 i+1替代； 判斷“ i88” 是否成立？若是， 則 89是質(zhì)數(shù)，結(jié)束算法；否則， 返回第二步 . 第一步， 第四步， 第三步， 第二步， 算法設(shè)計 : 一般地，判斷一個大于 2的整數(shù)是否為質(zhì)數(shù) 的算法步驟如何設(shè)計？ 第一步，給定一個大于 2的整數(shù) n； 第二步，令 i=2； 第三步，用 i除 n，得到余數(shù) r； 第四步，判斷“ r=0” 是否成立 .若是，則 n 不是質(zhì)數(shù)，結(jié)束算法；否則，將 i 的值增加 1，仍用 i表示； 第五步，判斷“ i(n-1)” 是否成立，若是， 則 n是質(zhì)數(shù)，結(jié)束算法；否則，返回 第三步 . 例： 寫出解方程 x2 2x 3 0的一個 算法。 解：算法 1： 第一步：移項，得 x2 2x 3； 第二步：式兩邊同加 1得 x2 2x+1 4 第三步：兩邊配方，得（ x 1） 2 4 第四步：式兩邊開方，得 x 1 2 第五步：解得 x 3或 x 1。 算法 2： 第一步：計算方程的判別式判斷其符號 22 4 3 16 0； a acbb 2 42 第二步：將 a 1， b 2， c 3 代入求根公式 x 得 x1 3， x2 1 下面設(shè)計一個求一般的一元二次方程 ax2 bx c 0的根的算法如下： 第一步：輸入 a,b,c 第二步：計算 b2 4ac； 第三步：若 0；則輸出方程無實根； 第四步：若 0；計算并輸出方程根 x1,2 a acbb 2 42 數(shù)值性計算： 解方程、解不等式、 套用公式判斷性問題累加累乘 算法問題分為： 數(shù)值性計算和非數(shù)值性計算 非數(shù)值性計算； 文字處理、排序、 變量交換 例： 寫出一個求整數(shù) a、 b、 c最大值的算法 解 ： S1 ： max=a S2 ：如果 bmax，則 max=b S3 ：如果 cmax，則 max=c S4： max就是 a、 b、 c的最大值。 例 用二分法設(shè)計一個求方程 的近似根的算法 . 022 x 設(shè)所求近似根與精確解的差的絕對值 不超過 0.005 第一步：令 22 xxf . 因為 02,01 ff ， 所以設(shè) x 1 =1 ， x 2 = 2. 第二步：令 2 21 xx m ，判斷 f （ m ）是否為 0. 若是， 則 m 為所求；若否，則繼續(xù)判斷 mfxf 1 大于 0 還是小于 0. 第三步：若 01 mfxf ，則 x 1 =m ；否則， 令 x 2 = m . 第四步 判斷 005.0 21 xx 是否成立？若 是，則 x 1 、 x 2 之間的任意值均為滿足條件的 近似根；若否，則返回第二步 . 練習(xí) 、 有藍(lán)和黑兩個墨水瓶，但現(xiàn)在卻錯把藍(lán)墨水 裝在了黑墨水瓶中，黑墨水錯裝在了藍(lán)墨水 瓶中，要求將其互換，請你設(shè)計算法解決這 一問題。 由于兩個墨水瓶中的墨水不能直接交換， 故可以考慮通過引入第三個空墨水瓶的 辦法進(jìn)行交換。 解：算法步驟如下： 第一步：取一只空的墨水瓶，設(shè)其為白色； 第二步：將黑墨水瓶中的藍(lán)墨水裝入白瓶中； 第三步：將藍(lán)墨水瓶中的黑墨水裝入黑瓶中； 第四步：將白瓶中的藍(lán)墨水裝入藍(lán)瓶中； 第五步：交換結(jié)束。 算法是建立在解法基礎(chǔ)上的操作過程，算 法不一定要有運算結(jié)果，問題答案可以由 計算機解決設(shè)計一個解決某類問題的算 法的核心內(nèi)容是設(shè)計算法的步驟，它沒有 一個固定的模式，但有以下幾個基本要求： (1)符合運算規(guī)則，計算機能操作； (2)每個步驟都有一個明確的計算任務(wù)； (3)對重復(fù)操作步驟作返回處理； (4)步驟個數(shù)盡可能少； (5)每個步驟的語言描述要準(zhǔn)確、簡明 .