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