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

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