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

,歡迎進(jìn)入數(shù)學(xué)課堂,算法,一.算法的基本概念,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)相除法（又稱歐幾里得算法）至今仍在使用。,歐幾里得是古代最有名望的學(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)立了著名的歐幾里得（簡稱歐氏幾何）。在《幾何原本》中，歐幾里得還闡述了關(guān)于求兩個(gè)整數(shù)的最大公約數(shù)的過程，這就是著名的歐幾里得算法——輾轉(zhuǎn)相除法，其具體過程如下：,設(shè)給定的兩個(gè)正整數(shù)為m和n，求它們的最大公約數(shù)的步驟為：,,,（1）以m除以n，令所得的余數(shù)為r（r必小于n）；,（2）若r＝0，則輸出結(jié)果n，算法結(jié)束；否則，繼續(xù)步驟（3),（3）令m=n，n=r,并返回步驟（1）繼續(xù)進(jìn)行。,中國古代數(shù)學(xué)研究中也有許多有關(guān)算法的成果。用我國傳統(tǒng)的開方術(shù)求高次方程的近似根，是算法上的一大成就。此外,在社會(huì)上得到廣泛使用的珠算口訣就可以看做是典型的算法,它把復(fù)雜的計(jì)算(例如除法)描述為一系列按口訣執(zhí)行的簡單的算珠撥動(dòng)操作。中國古代數(shù)學(xué)以算法為主要特征，其中最具代表性的就是《九章算術(shù)》。,《九章算術(shù)》是戰(zhàn)國、秦、漢時(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ù)的方法）等。其中方程組解法和正負(fù)數(shù)加減法則在世界數(shù)學(xué)發(fā)展上是遙遙領(lǐng)先的。就其特點(diǎn)來說，它形成了一個(gè)以籌算為中心，與古希臘數(shù)學(xué)完全不同的獨(dú)立體系。,在11~14世紀(jì)約300年期間著名的數(shù)學(xué)家的著作中，如賈憲的《黃帝九章算法細(xì)草》，劉益的《議古根源》，秦九昭的《數(shù)書九章》，李治的《測(cè)圓海鏡》和《益古演段》，楊輝的《詳解九章算法》、《日用算法》和《楊輝算法》中，算法的特點(diǎn)得到了進(jìn)一步的強(qiáng)化和發(fā)展（其中包括發(fā)展了一套求高次方程近似根的方法。,2。算法的一般特征算法實(shí)際上是一種抽象的解題方法，它具有動(dòng)態(tài)性。因此，算法的行為非常重要。作為一個(gè)算法，應(yīng)具有以下四個(gè)特征。,,1）能行性(effectiveness）算法的能行性包括兩個(gè)方面：一是算法中的每一個(gè)步驟必須是能實(shí)現(xiàn)的。例如，在算法中，不允許出現(xiàn)分母為零的情況；在實(shí)數(shù)范圍內(nèi)不能求一個(gè)負(fù)數(shù)的平方根等。二是算法執(zhí)行的結(jié)果要能達(dá)到預(yù)期的目的。通常，針對(duì)實(shí)際問題設(shè)計(jì)的算法，人們總是希望能夠得到滿意的結(jié)果。,（2）確定性(definiteness）算法的確定性，是指算法中的每一個(gè)步驟都必須是有明確定義的，不允許有模棱兩可的解釋，也不允許有多義性。這一特征也反映了算法與數(shù)學(xué)公式的明顯差異。在解決實(shí)際問題時(shí)，可能會(huì)出現(xiàn)這樣的情況：針對(duì)某種特特殊問題，數(shù)學(xué)公式是正確的，但按此數(shù)學(xué)公式設(shè)計(jì)的計(jì)算過程可能會(huì)使計(jì)算機(jī)系統(tǒng)無所適從，這是因?yàn)?，根?jù)數(shù)學(xué)公式設(shè)計(jì)的計(jì)算過程只考慮了正常使用的情況，而當(dāng)出現(xiàn)異常情況時(shí)，該計(jì)算過程就不能適應(yīng)了。,例如，某計(jì)算工具規(guī)定：大于100的數(shù)認(rèn)為是比1大很多，而小于10的數(shù)不能認(rèn)為是比1大很多；且在正常情況下出現(xiàn)的數(shù)或是大于100,或是小于10.但指令“輸入一個(gè)X，若x比1大很多，則輸出數(shù)字1，否則輸出數(shù)字0”是不確定的。這是因?yàn)?，在正常的輸入情況下，這一指令的執(zhí)行可以得到正確的結(jié)果，但在異常情況下（輸入的x在10與100之間），這一指令執(zhí)行的結(jié)果就不確定了．,例如，某計(jì)算工具具有七位有效數(shù)字（如FORTRAN中的單精度運(yùn)算）,在計(jì)算下列三個(gè)量A＝，B＝1，C＝的和時(shí)，如果采用不同的運(yùn)算順序，就會(huì)得到不同的結(jié)果，即A＋B＋C=＋1＋=0A＋C十B=＋＋1=1而在數(shù)學(xué)上，A+B+C與A+C+B是完全等價(jià)的。這可知，算法和計(jì)算公式是有差別的。,,3）有窮性(finiteness）算法的有窮性是指算法必須能在有限的時(shí)間內(nèi)執(zhí)行完，即算法必須能在執(zhí)行有限個(gè)步驟之后終止。數(shù)學(xué)中的無窮級(jí)數(shù)，在實(shí)際計(jì)算時(shí)只能取有限項(xiàng)，即計(jì)算無窮級(jí)數(shù)的過程只能是有窮的。因此，一個(gè)數(shù)的無窮級(jí)數(shù)的表示只是一種計(jì)算公式，而根據(jù)精度要求確定的計(jì)算過程才是有窮的算法。,算法的有窮性還應(yīng)包括合理的執(zhí)行時(shí)間的含義。如果一個(gè)算法的執(zhí)行時(shí)間是有窮的，但卻需要執(zhí)行千萬年．顯然這就失去了算法的實(shí)用價(jià)值。例如，克萊姆(Cramer)規(guī)則是求解線性代數(shù)方程組的一種數(shù)學(xué)方法，但不能以此為算法，這是因?yàn)?，雖然總可以根據(jù)克萊姆規(guī)則設(shè)計(jì)出一個(gè)計(jì)算過程用于計(jì)算所有可能出現(xiàn)的行列式，但這樣的計(jì)算過程所需的時(shí)間實(shí)際上是不能容忍的。,還例如，從理論上講，總可以寫出一個(gè)正確的弈棋程序，而且這也并不是一件很困難的工作。由于在一個(gè)棋盤上安排棋子的方式總是有限的，而且，根據(jù)一定的規(guī)則．在有限次移動(dòng)棋子之后比賽一定結(jié)束。因此．弈棋程序可以考慮計(jì)算機(jī)每一次可能的移動(dòng)，它的對(duì)手每一次可能的應(yīng)答，以及計(jì)算機(jī)對(duì)這些移動(dòng)的可能應(yīng)答等等，直到每個(gè)可能的移動(dòng)停止下來為止。此外，由于計(jì)算機(jī)可以知道每次移動(dòng)的結(jié)果，因此總可以選擇一種最好的移動(dòng)方式。但即使如此，這種弈棋程序還是不可能執(zhí)行，因?yàn)樗羞@些可能移動(dòng)的次數(shù)太多，所要花費(fèi)的時(shí)間不能容忍。由上述兩個(gè)例子可以看出，雖然許多計(jì)算過程是有限的．但仍有可能無實(shí)用價(jià)值。,（4）算法必須擁有足夠的情報(bào)一個(gè)算法是否有效，還取決于為算法的執(zhí)行所提供的情報(bào)是否足夠。例如，對(duì)于指令“如果小明是學(xué)生，則輸出字母Y，否則輸出N”。當(dāng)算法執(zhí)行過程中提供了小明一定不是學(xué)生的某種信息時(shí)，執(zhí)行的結(jié)果將輸出字母N；當(dāng)提供的只是部分學(xué)生的名單，且小明恰在此名單之中，則執(zhí)行的結(jié)果將輸出字母Y。但如果在提供的部分學(xué)生的名單中找不到小明的名字．則在執(zhí)行該指令時(shí)無法確定小明是否是學(xué)生。,通常，算法中的各種運(yùn)算總是要施加到各個(gè)運(yùn)算對(duì)象上，而這些運(yùn)算對(duì)象又可能具有某種初始狀態(tài)．這是算法執(zhí)行的起點(diǎn)或是依據(jù)。因此，一個(gè)算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)，不同的輸入將會(huì)有不同的結(jié)果輸出。如果輸入不夠或輸入錯(cuò)誤，則算法本身也就無法執(zhí)行或執(zhí)行有錯(cuò)。一般來說，只有當(dāng)算法擁有足夠的情報(bào)時(shí)，該算法才是有效的；而如果提供的情報(bào)不夠，則算法并不是有效的。,綜上所述，所謂算法，是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止,同學(xué)們,來學(xué)校和回家的路上要注意安全,同學(xué)們,來學(xué)校和回家的路上要注意安全,