[ Pi algorithms - John Machin's formula ] 梅欽公式計算圓周率

我們知道
$$\frac{\pi}{4}= \arctan 1$$
而$\arctan(x)$的泰勒展開式長這樣
$$\arctan(x)=x-\frac{x^3}{3}+\frac{x^5}{5}-\frac{x^7}{7}+\frac{x^9}{9}- \cdots \; (x \leq 1)$$
故可以求出莱布尼茨公式如下:
$$\frac{\pi}{4}= 1 \,-\, \frac{1}{3} \,+\, \frac{1}{5} \,-\, \frac{1}{7} \,+\, \frac{1}{9} \,-\, \cdots$$
但是這用來計算$\pi$到小數點後指定位數是非常困難的，因此有了以下的梅欽公式:
$$\frac{\pi}{4} = 4 \arctan \frac{1}{5} - \arctan \frac{1}{239}$$
再用泰勒展開，可以得到:
$$\pi=(\frac{16}{5} - \frac{16} {3*5^3} + \frac{16}{5 * 5^5} - \frac{16} {7 * 5^7} + \cdots) \\ - (\frac{4}{239} - \frac{4}{3 * 239^3} + \frac{4}{5 * 239^5} - \frac{4}{7 * 239^7} + \cdots)$$
可以將這個公式整理為:
$$\pi=\frac{\frac{16}{5} - \frac{4}{239}}{1} -\frac{\frac{16}{5^3} - \frac{4}{239^3}}{3} + \frac{\frac{16}{5^5} - \frac{4}{239^5}}{5} - \cdots$$
如果我們要計算圓周率至10的負$L$次方，由於$\frac{16}{5^{2*n-1}} - \frac{4}{239^{2*n-1}}$中$\frac{16}{5^{2*n-1}}$比$\frac{4}{239^{2*n-1}}$來的大，具有決定性，所以表示至少必須計算至第n項:
$$\frac{16}{(2*n-1)*5^{2*n-1}}=10^{-L}$$
將上面的等式取log並經過化簡，我們可以求得(誤差什麼得先不管它):
$$n =\frac{L}{2log_{10} 5} = \frac{L}{1.39794}$$
這樣就可以計算$\pi$到小數點後第$L$位了

這裡有其他可以快速算出圓周率的梅欽類公式
http://jeux-et-mathematiques.davalan.org/calc/formulespi.pdf

[ Earley parser ] Earley語法解析器

有一天蚯蚓跟我說CYK算法很慢，推薦了這個東西，所以我就把他寫出來了。
他主要是先建構出類似於自動機的圖，有很多個狀態在跳來跳去，在我的實作裡有將其轉成語法樹的方法。
這裡需要自己實作的有lexer，還有最後的語法一定要有一個gamma rule，gamma rule就是有一個$gamma \Longrightarrow S$，$S$是初始符號。
首先是語法規則的部分:

這是分析器的本體，lexer的部分要自己去完成，lexer的結果會是parse的第二個參數，計算出來一些資料會存在table裡面
以下為模板:

最後是構造語法樹的部分，因為div是一顆左兄弟右兒子的樹，所以要將她轉換成正常的語法樹，還要去記錄曖昧文法的部分:

[ Cocke-Younger-Kasami algorithm ] CYK算法

它是一個用來判定任意給定的字符串是否屬於某一個上下文無關文法的算法，還可以順便構造出二元語法樹和判斷是否有曖昧文法(Ambiguous Grammar)。對於一個任意給定的上下文無關文法，都可以使用CYK算法來計算上述問題，所以它是一個幾乎萬能的算法，但首先要將該文法轉換成喬姆斯基範式(CNF)。
這個算法主要是利用動態規劃的思想，給一個有$n$個字符的字符串s，和$R$條語法規則，則他的計算複雜度為$\ord{n^3R}$，空間複雜度為$\ord{n^2R}$。類似於optimal binary search tree的算法，對於每個s[l,r]我們去計算s[l,k]和s[k+1,r]能符合的所有規則。

我們用2016 NCPC的題目當例子
這裡給一個簡單的範例，給你一個語法規則如下 :
$
A \Longrightarrow AAAAAAA \qquad 20 \\
A \Longrightarrow AA \qquad 15 \\
A \Longrightarrow a \qquad 5
$
如果看不懂的，他大約的意思如下:
一個合法字串$A$可以是七個合法字串$A$所組成，也可以是兩個合法字串$A$所組成，也可以是小寫字母$a$所組成。
每個規則都給他一個權重，表示經過這個規則的轉換會有這些花費，我們會給一個目標字串，要找出把整個字串轉換成$A$的最小花費，例如給定字串$aaaaaaaa$，他的最小花費就是75。
這裡舉另一個例子:
$
A \Longrightarrow BA \qquad 10 \\
A \Longrightarrow bcd \qquad 5 \\
B \Longrightarrow c \qquad 4
$
給定字串$ccbcd$，他的最小花費就是33。
當然也會發生無法轉換的情況，這個時候叫要輸出$NIR$ 。

首先必須要把規則轉成喬姆斯基範式，這裡我以數字當作規則的名稱，當y=-1時表示這個cnf是s->x的規則，否則是s->xy的規則。
接著就可以跑我們的演算法啦:
當然它也可以用來判斷是不是有曖昧語法(ambiguous)，只要做一些小修改就行了

[ cantor expansion ] 康托展开

給一個$0 \sim n-1$共$n$個數字的全排列，求他是排名第幾的全排列；給一個名次，求全排列。這東西可以有效的減少hash_table的大小。
以下附上code:

使用前記得要呼叫init();

[ closest pair of points ] 平面上歐基里德距離最近點對

用分治法寫的，複雜度$\ord{n\log^2 n}$:

[ tree centroid ] 樹重心

一棵無向樹\(T=(V,E)\)，定義:
\(w_v(u)\)為點\(u\)的權重，\(u \in V\)
\(w_e(e)\)為邊\(e\)的權重，\(e \in E\)
\(d(u,v)\)為\(u\)到\(v\)路徑的權重和，\(u,v \in V\)

重心的定義是:
以這個點為根，那麼所有的子樹(不算整個樹自身)的大小都不超過整個樹大小的一半
即為最大的子樹最小的點

廣義的樹的重心:
無向樹\(T=(V,E)\)滿足
 \(w_v(u)≧0, \; \forall u \in V \)
 \(w_e(e)>0, \; \forall e \in E \)
設
\(c(u)=\sum_{v \in V}d(u,v)*w_v(v)\)
則樹重心 \(tree \; centroid=u \; | \; min(\{c(u):u \in V\})\)

在
 \(w_v(u)=1, \; \forall u \in V \)
 \(w_e(e)=1, \; \forall e \in E \)
的情況下，就是一般的樹重心

性質:

1. 把兩個樹通過一條邊相連得到一個新的樹，那麼新的樹的重心在連接原來兩個樹的重心的路徑上。
2. 把一個樹添加或刪除一個葉子，那麼它的重心最多只移動一條邊的距離。

用途:
樹分治、動態求樹重心等

可以利用DFS找出最大的子樹最小的點，即為樹重心
樹重心求法(用vector存無向樹):

[ bipartite graph multiple matching ] 二分圖多重匹配增廣路算法

這種問題的題目通常是這樣:

給一張圖G有n1個點和n2個點，n1個點之間沒有邊，n2個點之間也沒有邊，但是n1和n2個點之間有m條邊(簡單的來說就是n1個點和n2個點的二分圖啦)，沒有重邊；其中n2個點每個點\(u\)都有一個可接受匹配數 \(c_u\)。
n1的點只能跟一個點匹配，但n2的點在不超過可接受匹配數的情況下，可以跟多個點匹配，求這張圖的最大匹配

通常可以利用拆點的方法或是flow來做，但是這樣空間跟效率都不是很好，這裡提供一個有效率的方法:

複雜度分析:
設n2個點每個點\(u\)都有一個值\(E_u\)表示和\(u\)相鄰的邊數，則總複雜度為
$$ \ord{n1*(\sum{c_u*E_u}+n1+n2)} $$