第一夜 · 一枚假幣燈亮了。第一夜不講王子也不講公主。講一枚假幣——和一句我背了十二年的答案。2014 年我上高中。一堂數(shù)學(xué)課講方程的近似解老師引入的方式很特別一堆金幣里混了一枚假的比真幣略輕。手里有一架沒有砝碼的天平問最少稱幾次能把假幣找出來教室里吵了一陣答案慢慢統(tǒng)一對半分。一半上一邊天平一斜假幣就在輕的那邊輕的那邊再對半分。一百枚七次。老師說對。這叫二分法它是最優(yōu)的。我把這句話抄在本子上抄得工工整整。這一抄就是十二年。許多年后一間大學(xué)的階梯教室一位客座教授來講計算思維。他把同一道題擺到同一群年輕人面前。教室里的答案和當(dāng)年的我一模一樣對半分稱輕的繼續(xù)二分法最快。教授不置可否。他只問了一句誰規(guī)定所有金幣都必須上秤教室安靜了下來。天平是會說話的。只有兩枚金幣的時候它有兩種回答左邊輕右邊輕。可金幣一多它就多出了一種回答平衡——兩邊一樣重說明假幣根本沒上秤。當(dāng)年那道題里這種回答從沒出現(xiàn)過因為老師把全部上秤寫進(jìn)了規(guī)矩。規(guī)矩里沒有平衡天平就只剩兩個詞。教授說允許一堆金幣不上秤。把一百枚分成三份三十三、三十三、三十四兩份上秤若平假幣在看熱鬧的三十四枚里若斜假幣在輕的那三十三枚里。無論天平怎么回答嫌疑都只剩下三分之一。三十三枚再分三份。一百枚金幣五次穩(wěn)穩(wěn)找出來。圖 1-1 三分找假幣的流程。每一次稱量嫌疑都切成三份平了假幣在看熱鬧的那堆里斜了在輕的那堆里。五次稱量后一百枚里只剩一枚。作為對比老規(guī)矩“全部上秤、對半分”要稱七次——省下的兩次就是“留一堆看熱鬧”換來的。七次和五次差的不是聰明是一條規(guī)矩。二分沒有錯——在那條全部上秤的規(guī)矩里它就是最優(yōu)數(shù)學(xué)可以證明?？梢?guī)矩一旦改寫最優(yōu)就換了主人。那年教室里的我以為最優(yōu)是題目發(fā)的獎牌天生掛在某一種解法的脖子上。十二年后的我才懂最優(yōu)從來不屬于題目它屬于題目和規(guī)矩的婚姻。規(guī)矩改一條最優(yōu)就改嫁一次。后來我寫代碼謀生無數(shù)次遇見這架天平。程序里的每一次比較都是一次稱量。只是代碼里的天平是個啞巴它只會說兩個詞小于大于等于。所以在代碼的世界里二分查找稱王誰也奪不走它的冠冕——不是它天賦異稟是那架天平天生只會兩個詞。直到有一天你在 Java 里遇見一位老朋友compareTo。它每次稱量返回的恰恰是三種結(jié)果小了一樣大了。三結(jié)果的天平早就住進(jìn)了每一行代碼里只是很少有人想起它還有一種回答沒有用上。故事講到這里其實漏了一位主角。那堂 2014 年的數(shù)學(xué)課講的從來不是假幣——假幣是它借來的比喻。那堂課的真身是解方程求 f(x) 0 的近似解。二分法在方程的世界里也是老姿勢掐頭去尾每次砍一半。只是它有個毛病只問正負(fù)從不問高低。函數(shù)在每個點上站得多高、跌得多深它看也不看全部扔掉。被扔掉的東西里藏著速度。把已經(jīng)算過的點連成一條曲線直接跳到這條曲線穿過零線的地方這叫插值。兩點連一條直線是試位法每走一步就扔掉更老的那個點、只留最新兩個是割線法三點連一條彎的用的是拉格朗日插值。它們都瞧不起二分你稱三十次才攢下的那點信息我們幾步就用盡了。圖 1-2 插值為什么快。同一段區(qū)間 [2, 3]二分只問正負(fù)第一步走到中點 2.5割線把兩個起點 (2, ?1) 與 (3, 16) 連成直線第一步就落在 2.059——離根 2.0946只剩半步的路。虛線就是這條割線它穿過零線的位置 2.059就是插值交出的第一個答案。牛頓的名字在這里物歸原主。1669 年他在手稿里演示自己的方法挑的方程是 x3 ? 2x ? 5 0——根在 2 和 3 之間。三百年后全世界的教科書還在用這一條方程考一代又一代的學(xué)生。當(dāng)年把牛頓錯寫在二分法旁邊的少年直到寫這一夜才把名字還了回去。同一條方程照出了三種人生。守規(guī)矩的笨人用二分走了三十步永不失手也從不加速。念舊的人用試位法聰明地把兩點連成線卻死死抱著右端點不撒手——走了一百萬步還在半路上。放手的人用割線法同樣兩點插值只是每一步都更新全部的已知六步到家。原來插值也不是萬能藥。同一個方法抱著舊點不放的人比笨人還慢。這一夜的規(guī)矩又多了一條信息要用舊的點要舍得扔。寫給孩子的話就放在這里做題的時候先別急著抓最聰明的解法。放下筆看一眼題目里有沒有一條沒人念出來的規(guī)矩。很多你以為的天花板只是某條規(guī)矩的房檐你挪開它頭上就是另一片天。也看一眼你手里的信息——每一次算出來的高低深淺都是別人隨手扔掉的東西抱著舊結(jié)果不撒手的人跑不過肯更新的人。最優(yōu)從來不在題目里它在規(guī)矩里。規(guī)矩改一條最優(yōu)就改嫁一次而每一次改嫁都要你交出一樣舊東西——上一次是全部上秤的迷信這一次是那個抱了太久的端點。這一夜的三架天平我都寫成了能跑的程序附在下面的三面鏡子里。你要是不信次數(shù)會變、路程會短自己跑一遍數(shù)一數(shù)。鏡子一 · 全部上秤二分的天平importjava.util.*;/** * 《算法一千零一夜》第一夜 · 找假幣二分的天平 * 改編自作者的高中課堂。一堆金幣里混著一枚略輕的假幣 * 店規(guī)是所有金幣必須上秤——天平只會說兩個詞左邊輕右邊輕。 * 老師的策略是貪心式的干脆對半分輕的那邊繼續(xù)永不回頭。 */publicclassFakeCoinBisect{publicstaticvoidmain(String[]args){intn100;// 一百枚金幣其中一枚略輕。inttimes0;while(n1){times;intleftn/2,rightn-left;// 全部上秤一邊一半。System.out.println(第 times 次稱量左盤 left 枚右盤 right 枚全部上秤。);System.out.println(天平傾斜了——嫌疑只剩下 Math.max(left,right) 枚。);nMath.max(left,right);}System.out.println(二分的天平稱了 times 次。假幣無處可逃規(guī)矩毫發(fā)無損。);}}鏡子二 · 留一堆不上秤三分的天平importjava.util.*;/** * 《算法一千零一夜》第一夜 · 找假幣三分的天平 * 同樣的金幣同樣的天平。改變的只有一條規(guī)矩 * 允許留一堆金幣不上秤——于是天平多學(xué)會了一個詞平。 * 她的策略三等分稱其中兩堆平了看熱鬧的那堆斜了聽輕的那堆。 */publicclassFakeCoinTrisect{publicstaticvoidmain(String[]args){intn100;// 一百枚金幣其中一枚略輕。inttimes0;while(n1){times;inta(n2)/3;// 上秤的兩堆每堆這么多。intcn-2*a;// 留在旁邊看熱鬧的那一堆。if(c0){System.out.println(第 times 次稱量兩堆各 a 枚上秤c 枚在旁邊看熱鬧。);}else{System.out.println(第 times 次稱量兩堆各 a 枚上秤。);}System.out.println(不管天平怎么答——平了聽看熱鬧的斜了聽輕的那堆——嫌疑只剩下 Math.max(a,c) 枚。);nMath.max(a,c);}System.out.println(三分的天平只稱了 times 次。金幣一枚沒少規(guī)矩?fù)Q了一條。);}}鏡子三 · 同一條方程的三種人生importjava.util.*;/** * 《算法一千零一夜》第一夜 · 同一條方程的三種人生鏡子三 * 方程x3 ? 2x ? 5 0。牛頓在他 1669 年的手稿里用的正是這一條。 * 根在 2 與 3 之間f(2) ?1f(3) 16。 * * 三種人三種求根的活法 * 一、守規(guī)矩的笨人二分只問正負(fù)永不失手每次把區(qū)間砍一半。 * 二、念舊的人試位用兩點連線的插值找根聰明——但右端點抱著不放手。 * 三、放手的人割線同樣兩點插值每一步都更新全部已知超線性收斂。 */publicclassNewtonNight{staticdoublef(doublex){returnx*x*x-2*x-5;}staticfinaldoubleEPS1e-9;// 精度要求區(qū)間窄過十億分之一。publicstaticvoidmain(String[]args){System.out.println(方程x^3 - 2x - 5 0牛頓 1669 年手稿里那條。根在 2 與 3 之間。);System.out.println(精度要求區(qū)間窄于 0.000000001。);System.out.println();// 一、守規(guī)矩的笨人二分。只問正負(fù)每次砍一半。doublea2,b3;intsteps0;while(b-aEPS){doublem(ab)/2;if(f(a)*f(m)0)bm;elseam;steps;}System.out.println(一、守規(guī)矩的笨人二分走了 steps 步根 ≈ (ab)/2);System.out.println( 永不失手也從不加速——每一步都只知道一半。\n);// 二、念舊的人試位法。兩點連線找根但右端點 3 永遠(yuǎn)不更新。a2;b3;steps0;while(b-aEPS){doublec(a*f(b)-b*f(a))/(f(b)-f(a));// 兩點的插值零點if(f(a)*f(c)0)bc;elseac;steps;if(steps100000)break;// 念舊的人可能要走很久很久}System.out.println(二、念舊的人試位法端點抱著不撒手走了 steps 步區(qū)間還剩 String.format(java.util.Locale.ROOT,%.6f,b-a));System.out.println( 聰明卻把舊消息攥出了褶子。\n);// 三、放手的人割線法。同樣兩點插值但每一步都更新全部已知。doublex02,x13;steps0;while(Math.abs(f(x1))EPSsteps100){doublex2x1-f(x1)*(x1-x0)/(f(x1)-f(x0));x0x1;x1x2;steps;}System.out.println(三、放手的人割線法兩點插值步步更新走了 steps 步根 ≈ x1);System.out.println( 同樣的插值同樣的兩點——它只是舍得搬家。);}}改編來源稱金幣問題是流傳已久的經(jīng)典智力題“允許不上秤則三分優(yōu)于二分的解法與解釋為真2014 年的課堂與客座教授的插曲是作者親歷。方程段史實牛頓在 1669 年寫成的手稿后于 1711 年發(fā)表中以 x3 ? 2x ? 5 0 演示其方法根約 2.09455148試位法與割線法的歷史源流、插值法的現(xiàn)代表述見數(shù)值分析標(biāo)準(zhǔn)教材。另照實標(biāo)注作者自己的錯名當(dāng)年筆記里的牛頓二分法”名字是記串的——教材里它叫二分法牛頓法是另一種用切線逼近的解法。錯誤也是故事的一部分照單全收。一條真核也照實入賬這條方程在 [2, 3] 上是凸的試位法的弦交點永遠(yuǎn)落在真根左側(cè)于是右端點 3 釘死不動、左端點獨自爬行。念舊的人走滿一百萬步仍在半路是數(shù)學(xué)的必然不是程序?qū)戝e程序?qū)嵟転樽C。今夜習(xí)題八十一枚金幣混著一枚略輕的假幣。用允許留一堆不上秤的稱法最少幾次保證找出提示3 的幾次方恰好是 81你算出來幾次評論區(qū)見。答案與參考程序收在書后《參考解答》。版權(quán)聲明本文為作者原創(chuàng)受著作權(quán)法保護(hù)。未經(jīng)授權(quán)禁止轉(zhuǎn)載、搬運、摘編、改編及任何形式的二次創(chuàng)作個人學(xué)習(xí)引用請注明作者與原文出處。轉(zhuǎn)載授權(quán)請聯(lián)系作者CSDN 私信。侵權(quán)必究。