在編程中有沒有巧妙運用數學知識解決過問題？

01-03

題主才剛學嘛。。見識淺薄。。何必這麼較真呢。。

用帶符號距離場（signed distance field, SDF） $phi(mathbf{x})$ 表示形狀時，形狀表面上的法線就是 SDF 的梯度 $abla phi(mathbf{x})$ 。對於 SDF 還有 $left | abla phi(mathbf{x}) ight |=1$ 的特性，連歸一化也省了：

$hat{mathbf{n}}(mathbf{x}) = abla phi(mathbf{x})quad ext{for}quad phi(mathbf{x})=0$

謝邀，題主自己加了「ACM競賽」的標籤，怎麼還會問這樣的問題啊，不可思議。

很久以前我在這裡整理過一篇回答，大致就是 ACM 競賽中涉及到的基礎演算法，這當中本身就會有許多的數學背景：

程序員必須掌握哪些演算法？ - SimonS 的回答

這裡會提一些工程上的應用，簡單來說數學在編程中有這麼幾個粗獷的分支：

離散數學

離散數學在編程中應用最大的必然是樹和圖這兩個數據結構，這裡舉一個大家耳熟能詳的求最短路徑的例子，但是有一個非常巧妙的方法來計算當選擇哪一個節點作為下一節點時，可以得到最優解和次優解。這個好的特性被應用在了 GPS 導航中，節省了大量計算時間：

$Q_{d}(i,j)$ 被定義為車輛在節點 i 時，如果選擇通過邊(i, j)到達目的節點d，車輛從節點 i 行駛到重點 d 所要花費的最小成本（比如時間）。在該演算法中Q值通過以下公式不斷迭代，最終將收斂，其收斂值就是車輛經過邊 (i, j) 到達目的節點d，索要花費的最小成本：

$Q_{d}(i,j) leftarrow Cost_{ij} + minleft{ Q_{d}(i,k) ight} (k in A(j))$

其中，

$i,j in I$ ：交通網路中所有節點的集合；

$din D$ ：所有終點的集合；

$Cost_{ij}$ ：車輛從i到j的成本；

$A(j)$ ：所有以 j 為起點的車道的終點的集合。

有興趣的同學可以通過該關鍵詞繼續了解：Boltzmann全局最優尋路演算法

初等數論

初等數論最大的應用恐怕就是密碼學了，但這裡展開講 RSA 的話有點無聊，還會涉及素數檢驗，篇幅也會過長。這裡簡單提一下隨機數，我們在編程中或多或少都用到過隨機數，但非0即1的計算機是如何產生一個隨機數的？這裡就涉及到初等數論中的線性同餘法（LCG），它根據以下遞推公式生成隨機數：

$N_{i+1}equiv (A imes N_{i}+B)(mod M)$

其中乘數 A、增量 B、模數 M 都是產生器設定的常數，LCG 的最大周期是 M，但並不是一定會達到最大周期。如果 LCG 達到了最大周期，需要滿足：

B 和 M 互質

M 的所有質因子的積能整除 A - 1

如果 M 是4的倍數，那麼 A - 1 也是

A，B，N0 都比 M 小

A，B 是正整數

其中 $N_{0}$ 往往被稱為隨機種子，因為它是這個隨機序列的第一個數，如果這個數不變的話，那麼很顯然不管我們產生多少次這個序列，都是相同的，所以我們需要不斷去改變這個隨機種子。比較常見的做法就是取系統時間作為隨機種子，這也是一種比較高效的辦法。對於時效性不高的場景，比如現在很多1元賭場里的演算法，就有取最近一期時時彩開獎結果作為隨機種子的。

計算幾何

這塊是我當年競賽的弱項，也就擅長敲計算凸包的……模板。玩笑，這塊主要應用還是在於各種圖形引擎的開發，前面有一個Milo Yip大大，我就不班門弄斧了。我在工作中只遇到過幾個非常簡單的問題，比如給出國內城市的多邊形 GPS 數據，給一個經緯度，快速求出是哪個城市。這是目前 LBS 電子圍欄中非常經典的基礎問題，其實就是判斷點在多邊形內。我們通常使用一個巧妙的射線法來解決，即從目標點出發引一條射線（一般取水平線即可），如果單邊交點個數為奇數，則在多邊形內，高效解決：

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy) { int c = 0; for (int i = 0, j = nvert-1; i &< nvert; j = i++) { if ( ((verty[i]&>testy) != (verty[j]&>testy)) (testx &< (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) ) c = !c; } return c; }

運籌學

這當中我所接觸的也就是動態規劃（Dynamic Programming）了，或者叫它記憶化搜索也行。我在本文開頭的離散數學中舉的例子，其實也有涉及到 DP 思想。如果你讀過《數學之美》的話，就應該知道在中文分詞中，如果要把一個句子拆成幾個片語，應該盡量把它拆成高頻詞，越高越好。如果我們遍歷所有組合找到最大概率方案，太過費時，這裡我們就可以引入 DP 來解決，因為不同的劃分其實是構成了不同的路徑，求解最佳分詞便可以轉換為圖論中最短路問題來解決。如果對分詞有興趣做入門了解的，我這裡翻出了 Matrix67 早年的一篇博文，可供參閱：

漫話中文自動分詞和語義識別（上）：中文分詞演算法

微積分/統計

這個在編程中的應用地位越來越重要了，目前大家所知的機器學習、人工智慧，核心其實都是統計學。除此之外的應用也非常廣泛，比如電子競技遊戲中的匹配系統，我寫過一篇關於 ELO 匹配演算法的文章可以參考，也是比較巧妙地利用了統計學解決了匹配偏差過大的難題：

競技遊戲的匹配系統要做到儘可能使雙方實力接近有多難？ - SimonS 的回答

至於機器學習相關的，說實話我第一次接觸的時候，我覺得每一個統計學模型的設計都很巧妙。如果在數學表達上非要談巧妙和優雅的話，我會推薦支持向量機。有興趣了解的可以看這裡：

支持向量機(SVM)是什麼意思？ - 人工智慧

以上，這裡就先拋磚引玉了 ~

可以關注我個人的演算法專欄，不定時更新演算法趣解：

SimonS"s Algo - 知乎專欄

大部分答案都是討論某一具體數學理論，比如說數論，對編程的作用。這裡我介紹一個比較泛化的工具對編程的幫助。即，在 Haskell 等函數式語言中編寫很通用的代碼時，可以通過交換圖（commutative diagram）來得到所需的函數。

舉一個具體例子，在處理遞歸數據結構的時候，有一系列結構相似的遞歸函數，稱之為 recursion scheme。以鏈表（list）為例，下列 Haskell 代碼定義了鏈表數據結構：

data List a = Empty | Node a (List a)

這裡的 a 可以指代任意類型，可以是整數 Integer，可以是一個字元 Char，可以是一段文本 Text；這些類型對應的鏈表的類型分別寫作 List Integer、List Char、List Text。熟悉 C++、Java 的同學可以把這個語法看成 List&。Empty 可以看成一個常量，類型為 List a，換句話說它代表任意類型的鏈表的空表。Node 可以看成一個二元函數，分別是鏈表的一節點中的與鏈表的剩餘項。一個具體的例子：

[1, 2, 3] == Node 1 (Node 2 (Node 3 Empty))

熟悉 JavaScript 或者 Swift 的同學可能知道，有一個函數叫 reduce，給定一個「累積函數」，我們可以把一個數組「reduce」成一個值。比如說，下列 JavaScript 代碼可以求一個數組的和。

function sum (array) { return array.reduce(((x, y) =&> x + y), 0); }

reduce 在 Haskell 中叫 foldl，其中「l」代表「left」；正如最新的 JavaScript 加入了 reduceRight 一樣，Haskell 里還定義了「foldr」，這兩個函數指定了 fold/reduce 的方向，有興趣的同學可以自行搜索分別兩者的不同。上述 JavaScript 代碼可以翻譯成：

sum :: [Int] -&> Int sum list = foldl add 0 list where add :: Int -&> Int -&> Int add x y = x + y

Haskell 中的函數允許化簡等號兩邊右側相同項，類似解方程的時候 x + 5 = 5 可以在兩邊同時減五得到 x = 0，sum 定義里等號兩邊的 list 也可以消去。此外，(+) 等價於上述函數里定義的 add，因此，上述代碼可以化簡成：

sum :: [Int] -&> Int sum = foldl (+) 0

foldl 的定義很簡單：

foldl :: (b -&> a -&> b) -&> b -&> [a] -&> b foldl acc zero Empty = zero foldl acc zero (Node x xs) = foldl acc (acc zero x) xs

acc 是英文 accumulator 的縮寫，是一個「合併」函數；zero 顧名思義，代表 reduce 過程的初始值。這裡的 foldl 的定義類似數學歸納法：如果我們有一個空鏈表，那麼 fold 的結果就是 zero，否則，我們把 zero 和鏈表的第一項合併起來當作新的 zero 去 fold 鏈表剩下的部分。

好像繞的有些遠，重複一下第二段話：

舉一個具體例子，在處理遞歸數據結構的時候，有一系列結構相似的遞歸函數，稱之為 recursion scheme。

我們發現 fold 可以在很多遞歸的數據結構上定義，於是給了它一個新名字「catamorphism」，姑且翻譯為「下射」，其中「cata-」是個希臘語詞綴，代表向下，「morphism」是態射，可以理解為函數的推廣。有代數基礎的同學可以發現，同態一次里的「homomorphism」便是由「同」（homo-）和「態」（morphism）構成（或許應該翻譯成「下態」？）。

編程的核心原則便是避免重複代碼，如果我們可以給鏈表和二叉樹都定義 fold，或者說 catamorphism，那麼最好這段代碼能共用。有兩種方法可以實現這個目標，其一是使用元編程技術，讀取鏈表和二叉樹的定義，生成相應的代碼；另一種便是重新定義鏈表這個數據結構，使得它滿足一些共性。我們發現，我們可以這麼定義鏈表：

data ListF a f = Empty | Node a f

這個類型有些複雜，尤其是其中的「f」作用。我們可以先假設 Empty 代表整數空鏈表，它的類型是 ListF Int f，隨便取一個 f——因為等號右邊沒有用到 f，選擇任意類型不影響——比如說零元元組 ()，我們有：

empty = Empty :: ListF Int () -- substitute f with the type of ``empty`` one = Node 1 empty :: ListF Int (ListF Int ()) -- substitute f with the type of ``one`` two = Node 2 one :: ListF Int (ListF Int (ListF Int ()))

我們發現，鏈表的長度和其類型的長度一一對應！我們失去了鏈表的遞歸性質。如何解決這個問題呢？我們可以在類型層面嵌入遞歸，數學一點的叫法叫做類型的不動點：

data Fix f = Fix (f (Fix f))) type List a = Fix (ListF a)

大家可以這麼理解 Fix 的定義，一個 Fix f，由一個 f 和一個 Fix f 構成（等號右邊的第一個 Fix 稱之為 constructor，可以看成函數名），因此我們嵌入了遞歸。大家可以把 ListF 的定義和 Fix 相互展開：

List Int = Fix (ListF Int) = Fix (ListF Int (Fix (ListF Int))) = Fix (ListF Int (Fix (ListF Int (Fix (ListF Int))))) = ...

因此，我們的鏈表又可以用一個類型代表不同的長度了。不用擔心無窮鏈表，因為我們的 Empty，即空表，它的類型是 ListF a b，也就包括了

Empty :: ListF a (Fix (ListF Int))

因為鏈表中隨時「可以用」Empty 終結，我們的鏈表長度依然是由窮的。

未完待續……

圖形學裡面一個很有趣的例子：二維平面，如何判定一個點是否在一個多邊形內？一個簡單有效的演算法是，從這點向外畫一條射線，數它和多邊形多少條邊相交：奇數在形內，偶數在行外。

Even–odd rule

初中老師總是愛讓我們寫計算1+2+...+n的函數，說是練習循環什麼的，我怎麼想都跟循環沒有關係啊（逃

其實，在演算法競賽中有這麼一類題叫做數論（

其實，還有一類題叫做圖論（

其實，還有一類題叫做動態規劃（

其實，還有一類題叫做計算幾何（

所以你要問數學和編程的關係，我只能說你所謂的編程也太狹義了……

矩陣快速冪求斐波那契第k項

以前做過的一個例子，把下面這些從正常的單詞/句子裡面判出來

XAkziGvtI aupwOBaq8dI ytjkacvzw hakjuig

用馬爾科夫鏈實現會很容易。想詳細了解的話，這裡有一個簡單的sample: Gibberish-Detector-js

OJ的例子就更多了

舉個簡單的，大意是：輸入n，代表有n個燈泡。接著觸發n輪，在第i輪翻轉掉i的整數倍燈泡的狀態，返回處於亮的狀態的燈泡個數。搞清楚原理的話，一行代碼就結束了。

return sqrt(n);

題目的鏈接在這：Bulb Switcher

平方根倒數演算法中用到了一個神奇的數字：0x5f3759df

float FastInvSqrt(float x) { float xhalf = 0.5f * x; int i = *(int*)x; // evil floating point bit level hacking i = 0x5f3759df - (i &>&> 1); // what the fuck? x = *(float*)i; x = x*(1.5f-(xhalf*x*x)); return x; }

這個函數可以快速計算出

$1/sqrt{x}$

的高精度近似值

推薦一本計算幾何的書：http://www.springer.com/gp/book/9783540779735

這本書是從實際問題引入，包含演算法和數據結構，妥妥的「數學解決編程問題」

來講一個用群論的思想來解決一個經典面試題的無聊例子：

Rotate Array（leetcode 189）

Rotate an array of n elements to the right by k steps.
For example, with n = 6 and k = 2, the array [1,2,3,4,5,6]
is rotated to [5,6,1,2,3,4].

網上的解法基本上是翻轉兩次

class Solution { public: void rotate(vector& nums, int k) { int n = nums.size(); reverse(nums.begin(), nums.end() - k%n); reverse(nums.end() - k%n, nums.end()); reverse(nums.begin(), nums.end()); } };

演算法複雜度是O(n)，空間複雜度O(1)，即數組每個元素只賦值兩次。我們應用一點群論的知識，可以把演算法複雜度從2n進一步優化到n。先貼代碼：

class Solution { int gcd(int m, int n) { int tmp; while (tmp = m % n) { m = n; n = tmp; } return n; } public: void rotate(vector& nums, int k) { int n = nums.size(); if (!(k %= n)) return; int num_orbit = gcd(n, k); for (int i = 0; i &< num_orbit; i++) { int j = (i + k) % n; int tmp = nums[i]; while (j != i) { swap(tmp, nums[j]); j = (j + k) % n; } nums[j] = tmp; } } };