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