高一數(shù)學(xué) 算法的概念課件 新人教A版必修3

《高一數(shù)學(xué) 算法的概念課件 新人教A版必修3》由會(huì)員分享，可在線閱讀，更多相關(guān)《高一數(shù)學(xué) 算法的概念課件 新人教A版必修3（18頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1 什么是算法 算法（algorithm）一詞源于算術(shù)(algorism),算術(shù)方法的原義是一個(gè)由已知推求未知的運(yùn)算過程。后來，人們把它推廣到一般,指算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則,甚至把把進(jìn)行某一工作的方法和步驟也稱為算法。 例如，人們?cè)谟?jì)算過程中，先乘除，后加減，從內(nèi)到外去括號(hào)等規(guī)則，都是按部就班必須遵守的算法。人類最早關(guān)于算法的記錄存在于在兩河流域發(fā)現(xiàn)的公元前兩三千年的泥板書上，其中的一個(gè)典型例子就是計(jì)算利息何時(shí)能夠夠等于本金。算法早期發(fā)展中值得一提的另一個(gè)成果應(yīng)歸功于古希臘的歐幾里得，他提出的計(jì)算最大公約數(shù)的輾轉(zhuǎn)相除法（又稱歐幾里得算法）至今仍在使用。歐幾里得

2、是古代最有名望的學(xué)者之一，古希臘數(shù)學(xué)家，幾何學(xué)的鼻祖。公元前300年左右，他所著幾何原本13卷，是世界上最早公理化的數(shù)學(xué)著作。在幾何原本中他充分總結(jié)了前人的生產(chǎn)經(jīng)驗(yàn)和研究成果，從公理和公設(shè)出發(fā)，運(yùn)用演繹法，經(jīng)過邏輯推理和數(shù)學(xué)運(yùn)算，創(chuàng)立了著名的歐幾里得（簡(jiǎn)稱歐氏幾何）。 在幾何原本中，歐幾里得還闡述了關(guān)于求兩個(gè)整數(shù)的最大公約數(shù)的過程，這就是著名的歐幾里得算法輾轉(zhuǎn)相除法，其具體過程如下：設(shè)給定的兩個(gè)正整數(shù)為m和n，求它們的最大公約數(shù)的步驟為：（1）以m除以n，令所得的余數(shù)為r（r必小于n）；（2）若r0，則輸出結(jié)果n，算法結(jié)束；否則，繼續(xù)步驟（3)（3）令m=n，n=r,并返回步驟（1）繼續(xù)進(jìn)行。

3、中國(guó)古代數(shù)學(xué)研究中也有許多有關(guān)算法的成果。用我國(guó)傳統(tǒng)的開方術(shù)求高次方程的近似根，是算法上的一大成就。此外,在社會(huì)上得到廣泛使用的珠算口訣就可以看做是典型的算法,它把復(fù)雜的計(jì)算(例如除法)描述為一系列按口訣執(zhí)行的簡(jiǎn)單的算珠撥動(dòng)操作。中國(guó)古代數(shù)學(xué)以算法為主要特征，其中最具代表性的就是九章算術(shù)。九章算術(shù)是戰(zhàn)國(guó)、秦、漢時(shí)期數(shù)學(xué)發(fā)展的總結(jié)，就其數(shù)學(xué)成就來說，堪稱是世界數(shù)學(xué)名著。其內(nèi)容按類分章，以數(shù)學(xué)問題的形式出現(xiàn)，包括分?jǐn)?shù)四則運(yùn)算、開平方與開立方（包括二次方程數(shù)值解法）、盈不足術(shù)、各種面積和體積公式、線性方程組解法、正負(fù)數(shù)運(yùn)算的加減法則、勾股形解法（特別是勾股定理和求勾股數(shù)的方法）等。其中方程組解法和正

4、負(fù)數(shù)加減法則在世界數(shù)學(xué)發(fā)展上是遙遙領(lǐng)先的。就其特點(diǎn)來說，它形成了一個(gè)以籌算為中心，與古希臘數(shù)學(xué)完全不同的獨(dú)立體系。 在1114世紀(jì)約300年期間著名的數(shù)學(xué)家的著作中，如賈憲的黃帝九章算法細(xì)草，劉益的議古根源，秦九昭的數(shù)書九章，李治的測(cè)圓海鏡和益古演段，楊輝的詳解九章算法、日用算法和 楊輝算法中，算法的特點(diǎn)得到了進(jìn)一步的強(qiáng)化和發(fā)展（其中包括發(fā)展了一套求高次方程近似根的方法。1）能行性）能行性(effectiveness） 算法的能行性包括兩個(gè)方面：一是算法中的每算法的能行性包括兩個(gè)方面：一是算法中的每一個(gè)步驟必須是能實(shí)現(xiàn)的。例如，在算法中，不允許一個(gè)步驟必須是能實(shí)現(xiàn)的。例如，在算法中，不允許出現(xiàn)

5、分母為零的情況；在實(shí)數(shù)范圍內(nèi)不能求一個(gè)負(fù)數(shù)出現(xiàn)分母為零的情況；在實(shí)數(shù)范圍內(nèi)不能求一個(gè)負(fù)數(shù)的平方根等。二是算法執(zhí)行的結(jié)果要能達(dá)到預(yù)期的目的平方根等。二是算法執(zhí)行的結(jié)果要能達(dá)到預(yù)期的目的。通常，針對(duì)實(shí)際問題設(shè)計(jì)的算法，人們總是希望的。通常，針對(duì)實(shí)際問題設(shè)計(jì)的算法，人們總是希望能夠得到滿意的結(jié)果。能夠得到滿意的結(jié)果。 例如，某計(jì)算工具規(guī)定：大于例如，某計(jì)算工具規(guī)定：大于100的數(shù)認(rèn)為是比的數(shù)認(rèn)為是比1大很多，而小于大很多，而小于10的數(shù)不能認(rèn)為是比的數(shù)不能認(rèn)為是比1大很多；大很多；且在正常情況下出現(xiàn)的數(shù)或是大于且在正常情況下出現(xiàn)的數(shù)或是大于100,或是小于或是小于10.但指令但指令“輸入一個(gè)輸入一個(gè)

6、X，若，若x比比1大很多，則輸大很多，則輸出數(shù)字出數(shù)字1，否則輸出數(shù)字，否則輸出數(shù)字0”是不確定的。這是因是不確定的。這是因?yàn)?，在正常的輸入情況下，這一指令的執(zhí)行可以為，在正常的輸入情況下，這一指令的執(zhí)行可以得到正確的結(jié)果，但在異常情況下（輸入的得到正確的結(jié)果，但在異常情況下（輸入的x在在10與與100之間），這一指令執(zhí)行的結(jié)果就不確定之間），這一指令執(zhí)行的結(jié)果就不確定了了 1210 1210 12101210 1210 1210 算法的有窮性還應(yīng)包括合理的執(zhí)行時(shí)間的含義。如果一個(gè)算法的執(zhí)行時(shí)間是有窮的，但卻需要執(zhí)行千萬年顯然這就失去了算法的實(shí)用價(jià)值。例如，克萊姆(Cramer )規(guī)則是求解線

7、性代數(shù)方程組的一種數(shù)學(xué)方法，但不能以此為算法，這是因?yàn)椋m然總可以根據(jù)克萊姆規(guī)則設(shè)計(jì)出一個(gè)計(jì)算過程用于計(jì)算所有可能出現(xiàn)的行列式，但這樣的計(jì)算過程所需的時(shí)間實(shí)際上是不能容忍的。還例如，從理論上講，總可以寫出一個(gè)正確的弈棋程序，還例如，從理論上講，總可以寫出一個(gè)正確的弈棋程序，而且這也并不是一件很困難的工作。由于在一個(gè)棋盤上安而且這也并不是一件很困難的工作。由于在一個(gè)棋盤上安排棋子的方式總是有限的，而且，根據(jù)一定的規(guī)則在有排棋子的方式總是有限的，而且，根據(jù)一定的規(guī)則在有限次移動(dòng)棋子之后比賽一定結(jié)束。因此弈棋程序可以考限次移動(dòng)棋子之后比賽一定結(jié)束。因此弈棋程序可以考慮計(jì)算機(jī)每一次可能的移動(dòng)，它的對(duì)手

8、每一次可能的應(yīng)答，慮計(jì)算機(jī)每一次可能的移動(dòng)，它的對(duì)手每一次可能的應(yīng)答，以及計(jì)算機(jī)對(duì)這些移動(dòng)的可能應(yīng)答等等，直到每個(gè)可能的以及計(jì)算機(jī)對(duì)這些移動(dòng)的可能應(yīng)答等等，直到每個(gè)可能的移動(dòng)停止下來為止。此外，由于計(jì)算機(jī)可以知道每次移動(dòng)移動(dòng)停止下來為止。此外，由于計(jì)算機(jī)可以知道每次移動(dòng)的結(jié)果，因此總可以選擇一種最好的移動(dòng)方式。但即使如的結(jié)果，因此總可以選擇一種最好的移動(dòng)方式。但即使如此，這種弈棋程序還是不可能執(zhí)行，因?yàn)樗羞@些可能移此，這種弈棋程序還是不可能執(zhí)行，因?yàn)樗羞@些可能移動(dòng)的次數(shù)太多，所要花費(fèi)的時(shí)間不能容忍。由上述兩個(gè)例動(dòng)的次數(shù)太多，所要花費(fèi)的時(shí)間不能容忍。由上述兩個(gè)例子可以看出，雖然許多計(jì)算過程是

9、有限的但仍有可能無子可以看出，雖然許多計(jì)算過程是有限的但仍有可能無實(shí)用價(jià)值。實(shí)用價(jià)值。 （4）算法必須擁有足夠的情報(bào)）算法必須擁有足夠的情報(bào) 一個(gè)算法是否有效，還取決于為算法的執(zhí)行所一個(gè)算法是否有效，還取決于為算法的執(zhí)行所提供的情報(bào)是否足夠。例如，對(duì)于指令提供的情報(bào)是否足夠。例如，對(duì)于指令“如果小明是如果小明是學(xué)生，則輸出字母學(xué)生，則輸出字母Y，否則輸出，否則輸出N”。當(dāng)算法執(zhí)行過程。當(dāng)算法執(zhí)行過程中提供了小明一定不是學(xué)生的某種信息時(shí)，執(zhí)行的結(jié)中提供了小明一定不是學(xué)生的某種信息時(shí)，執(zhí)行的結(jié)果將輸出字母果將輸出字母N；當(dāng)提供的只是部分學(xué)生的名單，且?。划?dāng)提供的只是部分學(xué)生的名單，且小明恰在此名單之中，則執(zhí)行的結(jié)果將輸出字母明恰在此名單之中，則執(zhí)行的結(jié)果將輸出字母Y。但如。但如果在提供的部分學(xué)生的名單中找不到小明的名字則果在提供的部分學(xué)生的名單中找不到小明的名字則在執(zhí)行該指令時(shí)無法確定小明是否是學(xué)生。在執(zhí)行該指令時(shí)無法確定小明是否是學(xué)生。