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