對于“算法一詞給以精的定義不是件容易事，一些意義相的同義語，是一些其他名詞，它們有時）會給差不多同樣東西，例如 "法則"" 技巧”“程”還有“方”等等都是種同義語。可以給出一例子，如長法，就是小生學的把兩正整數(shù)相乘豎式乘法。而，雖然非式的解釋和當?shù)睦訉?什么是算法出了很好的覺，但算法詞中所深藏思想?yún)s經(jīng)歷一個很長的化歷程，直到 20 世紀才得到了人滿意的形定義，而關(guān)算法的觀念直到如今還演進。算盤和算法家回關(guān)于乘法的子，有一點顯然的：怎把兩個數(shù)相？表示這些的方法極大影響了乘法具體作法。了弄明白這，試著把兩羅馬數(shù)字 CXLVII 和 XXIX 相乘，但不要先把它們成等價的十數(shù)字 147 和 29。這件事既難明白，明白以后進行計也極其花時，而這就可解釋何以留至今的羅馬國關(guān)于乘法材料極為零。記數(shù)制可是 " 累加的 "，如羅馬記數(shù)法：C 表示 100。X 表示 10。L 表示 50，但是 X 放在 L 左方表示要從 L 中減去 X，所以就是 40，V 表示 5，I 表示 1，兩個 I 放在 V 的右方，表示要把們加到 V 上，所以是 7。把所有以上的解釋“加”起來，是羅馬數(shù)學 147。記數(shù)制度也可是進位的，我們今天所的那樣。如是進位的，以使用一個多個基底。很長的時期，進行計算以使用一種算工具 "算盤（abacus）"。這些計算工具以表示一定底下的進位的數(shù)。例如如果以 10 為基底、則一個標記物以代表 1 個單位、或 10?；蛘?100 等等，視它是在哪一橫行豎列而定。照精確的規(guī)移動這些標物，就可以行算術(shù)四則算。中國的盤就是 abacus 的一種。到 12 世紀，阿拉伯數(shù)學著被翻譯為拉文以后，十制就在歐洲行開來了。種進位制特適合于算術(shù)算，并且引到許多新的算方法。這方法就通稱算法（algoritmus），而與在算盤上用標物進行計算區(qū)別。雖然字符號，就數(shù)碼，來自度人的實踐而后來才為拉伯人所知現(xiàn)在這些數(shù)卻叫做阿拉數(shù)碼．算法algorithm）的字源卻是阿拉文，它是阿伯數(shù)學家阿?花拉子米名字的變體花拉子米是在已知的最老的數(shù)學書作者，這一作名為 《通過補全和還做計算的綱》（al-Kitab al-mukhtasar f hisib al-jabr wod ll-mugi balo），其中的 al-jabr 后來就變成了“數(shù)”（algebra）一詞。有限性們已經(jīng)看到算法”一詞中世紀是指整數(shù)的十進表示為基礎計算程序。是到了 17 世紀，在達朗貝爾主編《百科全書中，算法一被賦予了更泛的意義，只用于算術(shù)還用于關(guān)于數(shù)方法以及他的計算程，諸如 "積分學的算法"" 正弦的算法 " 等等。算法這個又逐漸地被來表示任意具有精確規(guī)的系統(tǒng)的計程序。最后隨著計算機作用越來越，有限性的要性被充分識到了，很質(zhì)的要求是這個過程在限時間以后會停止，而出結(jié)果。所就得到了下的樸素的定：一個算法是有限多個則的集合，以對數(shù)量有的數(shù)據(jù)進行作，而在有多步以后產(chǎn)結(jié)果。注意在這里一直調(diào)有限性，寫出算法時有限性，以在執(zhí)行算法的有限性。面的陳述算上是在經(jīng)典義下的數(shù)學義。我們將看到，把它一步形式化重要的。但我們現(xiàn)在暫也就滿足于個 "定義" 了，而且來看一下數(shù)學的算法的一經(jīng)典例子。個歷史上的子算法具有種我們尚未到的特性：代，也就是單程序的反執(zhí)行。為了清迭代的重性，我們再次來看一下乘法這個例，這是一個任意大小的整數(shù)都適用方法。數(shù)字得越大、程也就越長。是最關(guān)緊要是，方法是同樣的”，果會把兩個位數(shù)相乘，就會把兩個 137 位的數(shù)字相乘，不必再去學么新的原理理由在于長法的方法里包含了大量仔細構(gòu)造好小得多的任的重復執(zhí)行例如把兩個位數(shù)相乘的九表。我們會看到，迭在我們所要論的算法中了重要作用歐幾里得算：迭代歐幾得算法是說算法本質(zhì)的好也是最常的例子。這算法可以追到公元前 3 世紀。歐幾里得用它來算兩個正整的最大公約（gcd）。當我們最開遇到兩個正數(shù) a 和 b 的最大公約數(shù)時，它定義為一個整數(shù)，而且為 a 和 b 的因數(shù)。然而，為了多目的，定它為具有以兩個性質(zhì)的一的整數(shù) d 更好。這兩個性質(zhì)就是首先，d 是 a 和 b 的一個因數(shù)；其次，如 c 是 a 和 b 的另一個因數(shù)則 d 可以被 c 所整除。歐幾里的《幾何原》卷 VII 的前兩個命題給出了求 d 的方法，其中第一個題如下："給定了兩個不等的數(shù)、從大的一數(shù)不地減去較小一數(shù)，如果下的數(shù)位，不能量度前，直到余下數(shù)為一單位止，這時，來的數(shù)為互。" 換句話說，如果輾相減得到了 1，則 gcd 為 1。這時，就原來的兩個互質(zhì)（或互素數(shù)）。輾相減法現(xiàn)在們來一般地述歐幾里得法，它是基以下兩點觀的：（1）如果 a=b，則 a 和 b 的 gcd 就是 b（或 a）。（2）d 是 a 和 b 的公約數(shù)，當且僅當它是 a-b 和 b 的公約數(shù)。現(xiàn)在要求 a 和 b 的 gcd，而且設 a≥b。如果 a=b，則觀察（1）告訴我們，gcd 就是 b。若不然，觀察（2）告訴我們，如求 a-b 和 b 的 gcd 也會得到同樣的案?，F(xiàn)在令 a_1 是 a-b 和 b 中較大的一個，而 b_1 則為其中較小的一，然后再求數(shù)的 gcd。不過，現(xiàn)兩數(shù)中較大一個，即 a_1，小于原來兩數(shù)中較的一個，即 a。這樣我們就可以把上的程序再重一遍：若 a_1=b_1，則 a_1 和 b_1 的 gcd，亦即 a 和 b 的 gcd 是 b_1，若不然，就把 a_1 換成 a_1-b_1，再來組織 a_1-b_1 和 b_1，總之，較大的一個放在前面，后再繼續(xù)下，這就叫做 " 輾轉(zhuǎn)相減 "。為了使這個程序能進行下去，有一個觀察需要的，這是下面的關(guān)正整數(shù)的一基本事實，時稱為良序理：嚴格下的正整數(shù)序 a_0 > a1 > a2 >… 必為有限序。因為上面迭代程序恰產(chǎn)生了一個格下降序列這個迭代最一定會停止這就意味著某一點上必 a_k=b_k，而這個公共值就是 a 和 b 的 gcd。歐幾里得算的流程圖歐里得除法通對于歐幾里算法的陳述此稍有不同可以應用一較復雜的程，稱為歐幾得除法（也是帶余除法，它可以大減少算法的數(shù)，這種算也稱為輾轉(zhuǎn)除法。這個序的基本事是：若 a 和 b 是兩個正整數(shù)，必存在唯一整數(shù) q 和 r，使得數(shù) q 稱為商，而 r 稱為余數(shù)。上的兩點說明1）和（2）現(xiàn)在要代以 r=0，則 a 和 b 的 gcd 就是 b。a 和 b 的 gcd 與 b 和 r 的 gcd 是相同的。這一次，第一步要用b，r）代替（a，b）。如果 r≠0，則還要做二步，并用r，r_1）來代替（b，r），r1 是用 r 去除 b 所得的余數(shù)，所 r_1r>m>r1>r2≥0）。再用一次良序原，即知這個序經(jīng)過有限后一定停止而最后一個零的余數(shù)就 a 和 b 的 gcd。不難看到這兩種方法就求 gcd 而言是等價的，但就算而言則有很區(qū)別。例如設 a=103 438，b=37。如果用輾轉(zhuǎn)相法，就要從 103 438 中累次減去 37，一直到余下的數(shù)小于 37 為止。這個差數(shù)與 103438 除以 37 的余數(shù)是一樣，而如果用二種方法，次就可以得它。這樣，用第二種方的理由就在用累次減法求除法的余是非常低效的。效率上收益在實踐是很重要的第二種方法出的是多項時間算法，第一種方法需的則是指長的時間。廣歐幾里得法可以推廣許多其他背下，只要有法、減法和法的概念就。例如它有個變體，可用于高斯整環(huán)。就是形 a＋ bi，而其中 a，b 為整數(shù)的復數(shù)所成環(huán)，它也可用于系數(shù)為數(shù)的多項式中（就此而，系數(shù)在任域中也行）但有一個要，就是要能定義帶余除的類比物，了這一點以、算法就與整數(shù)情況的法基本上相了。例如下的命題：設 A 和 B 是兩個任意項式，而且 B 不是零多項式、則必在兩個多項 Q 和 R。使得或者 R=0，或者 R 的次數(shù)小于 B 的次數(shù)。正如幾里得在《何原本》中到的那樣，可以對于一數(shù)（a，b）當 a 和 b 不一定是整數(shù)時實行個程序。容驗證，當且當比 a / b 是有理數(shù)時，這個序會停下來這個觀點引到連分數(shù)的念。在 17 世紀以前，沒有特別地究過它，但其中的思想源可以追溯阿基米德。基米德計算 π 的方法：逼近和有限圓周長和圓直徑的比值一個常數(shù)，自從 18 世紀以來就作 π?，F(xiàn)在我們來看一阿基米德怎在公元前 3 世紀就得到了這個比值經(jīng)典的近似 22/7。若在圓內(nèi)作個內(nèi)接的正邊形（其頂都在圓周上，又作其外的正多邊形其邊都是圓的切線），計算這些多形的周長，會得到 x 的下界與上，因為圓的長必定大于意內(nèi)接多邊的周長，而于任意外切邊形的周長阿基米德從六邊形開始然后，每次多邊形的邊加倍，得到越來越精確上下界。他到九十六邊為止，得到π 的逼近這個過程中顯涉及迭代。是稱它為一算法對不對嚴格地說，不是一個算，不論取多邊的多邊形所得到的僅 π 的近似值，所以這過程不是有的。然而我確實得到了個可以近似算 π 到任意精確度的法。例如。果想得到 π 的一個準確到小數(shù)十位近似值，經(jīng)有限多步以，這個算法給出一個我想要的近似。重要的是這個過程是斂的。就是，重要的在由迭代得出值可以任意接近于 π。這個方法的何來源可以來證明這個斂性，而 1609 年德國人作到了 202 邊形（基本上用基米德的方），得到 π 的精確到小數(shù) 35 位的近似值。而，逼近 π 的算法與阿基米德計算個正整數(shù)的 gcd 的算法有一個明的區(qū)別。如幾里得那樣算法時常稱離散算法，與用來計算整數(shù)值的數(shù)算法相對立牛頓-拉夫森方法：遞推式1670 年前后、牛提出了一個方程之根的法，而且就程 x^3-2x-5=0 解釋了他的方法。他的釋從下面的個觀察開始根 x 近似地等于 2。于是他寫出 x=2+p，并用 2＋p 代替原方程的 x，而得到了一個關(guān) p 的方程。這個新方算出來是因 x 接近于 2，所以 p 很小，而他就略去了 p^3 和 6p^2 來估計 p。這就給了他 p 的方程 10p-1=0，即 p=1/10。這當然不是一個確解，但是給了牛頓關(guān)根的新的更的近似值：x=2.1。然后牛頓就重這個過程， x=2.1＋q，代入原方程以后又出了一個關(guān) q 的方程，近似地解個方程，又他的近似解確化了，于得到 q 的估計為-0.0054，所以 x 的下一個近似值 2.0946。盡管如此，我們怎么確定這個過會收斂于 x 呢？讓我們更仔細地考這個方法。線和收斂性頓的方法可從幾何上用數(shù) f 的圖像來解釋，然牛頓本人沒有這樣做f（x）=0 的每一個根 x 都對應于函數(shù) y=f（x）的曲線和 x 軸的一個交點如果從根 x 的一個近似值 a 開始，而且和上做的一樣， p=x- a，于是可以用 a+p 代替 x 而得到一個新函數(shù) g（p），也就是把原點（0，0）有效地移到了（a，0）處。然后 p 的所有高次冪都略，只留下常項和線性項這樣就得到函數(shù) g 的最佳的線性近 —— 從幾何上說，就是 g 在點（0，g（0））處的切線。這樣，于 p 所得到的近似值是函數(shù) y 在點（0，g（0））處的切線與 x 軸的交點。在橫坐標上一個 a，也就是讓原點到原來的（0，0）處，這樣 a＋p 就給出了 f 的根的新近似值。這就牛頓的方法為切線法的因。牛頓方從上圖可以到，再作一切線的逼近如果曲線 y=f（x）與 x 軸的交點在 a 點以及 f 在點（a，f（a））處的切線與 x 軸的交點（即圖中的橫坐為 a+p 的點，即根近似值）之，則第二次近似值（即 a＋p＋q）肯定比第一的近似值 a＋p 好（這里稱 a 為根的零次近）。回到牛的例子，可看到牛頓選 a=2 并不是上面所的情況。但從下一個近值 2.1 開始，以下有的近似值都是這個情了。從幾何看，如果點a，f（a））位于 x 軸的上方，且 y=f（x）的曲線在凸部與 x 軸相交，或點（a，f（a））在 x 軸的下方，而且 y=f（x）曲線在凹部與 x 軸相交，就出現(xiàn)這種有的情況。初的逼近（即次近似）的擇顯然是很要的，而且出了微妙的曾想到的問。如果我們慮復多項式復根，這就加清楚了。頓的方法很易適應這個廣泛的背景設 z 是一個復多項式復根，而 z_0 是初始的逼近，于牛頓方法將出一個序列 z_0，z_1，z_2…… 它可能收斂于 z，也可能不收斂我們定義根 z 的吸引區(qū)域為這樣的始逼近 z_0 的集合，使得所得到序列確實收于 z，并且記這個區(qū)域 A（z）。怎樣來決定 A（z）呢？第一個問這問題的人是萊，時間是 1879 年。他注意到對于二次多式，這個問是很容易的但當次數(shù)為 3 或者更大時，問題就困難了。例多項式 z^2-1 的根 ±1 的吸引區(qū)域分別復平面上以直軸為界的個半平面，是 z^3-1 的三個根 1，w，w^2 的相應的吸引區(qū)域是極復雜的合。這些集是由儒利亞 1918 年描述的，現(xiàn)在稱為分集合。遞推式牛頓方法每一階段都產(chǎn)生一個新程。但是拉森指出實際并無必要。就特殊的例給出在每一都可以使用單一一個公。但是他的本的觀察可一般地適用導出可以用每一個情況一般公式，這個公式用線的解釋就以容易得出事實上，曲 y=f（x）在 x 坐標為 a 處的切線方程它與 x 軸的交點的橫標是 a-f（a）/f'（a）。我們現(xiàn)在所說的頓-拉夫森方法就是指的個公式。我從一個初始近 a_0=a 開始再用這個遞推公得出這樣就到一個逼近序列，在復況下，也就前面說的 z_0，z_1，z_2，…。作為一個子，考慮函 f（x）=x^2-c。這時，牛頓法就給出 c 的平方根根號 c 的一串近似值，推公式現(xiàn)在了在上面的般公式中把 f 換成 x^2-c 即得。這個近平方根的求，公元 1 世紀的亞歷大里亞的海就已經(jīng)知道本文來自微公眾號：老說科學 （ID：LaohuSci），作者：我才老?
