具體數學-第8課（取整進階）

05-10

原文鏈接：

具體數學-第8課 - WeiYang Blog?

godweiyang.com

今天主要講了取整與遞歸式的結合，還有取模的相關知識。

例題1

給出下列遞歸式：

$egin{array}{l}{K_0}{ m{ = }}1\{K_{n + 1}} = 1 + min (2{K_{leftlfloor {n/2} ight floor }},3{K_{leftlfloor {n/3} ight floor }}),n ge 0end{array}$

現在不要求你求解，要你證明：

${K_n} ge n$

首先想到的就是數學歸納法，假設對於任意 $k le n$ ，都有 ${K_k} ge k$ ，那麼：

$egin{array}{l}{K_{n + 1}} = 1 + min (2{K_{leftlfloor {n/2} ight floor }},3{K_{leftlfloor {n/3} ight floor }})\ ge 1 + min (2leftlfloor {frac{n}{2}} ight floor ,3leftlfloor {frac{n}{3}} ight floor )end{array}$

如果 $n = 2k$ ，那麼 ${K_{n + 1}} ge 1 + n$ 。

如果 $n = 2k + 1$ ，那麼 ${K_{n + 1}} ge n$ ，這時不成立。

所以數學歸納法無法證明，今後我們會用其他方法來證明這個式子。

約瑟夫環新解

還記得約瑟夫環問題嗎？詳見第一節課。

這裡我們繼續推廣到一般情況，如果有 $n$ 個人，每隔 $q$ 個人踢掉一個人，最後剩下的是幾號？

初始編號為 $1 ldots n$ ，現在考慮一種新的編號方式。

第一個人不會被踢掉，編號加 $1$ ，變成 $n+1$ ，然後第二個人編號變為 $n+2$ ，直到第 $q$ 個人，他被踢掉了。

然後第 $q+1$ 個人編號繼續加 $1$ ，變成了 $n+q$ ，依次下去。

考慮當前踢到的人編號為 $kq$ ，那麼此時已經踢掉了 $k$ 個人，所以接下去的人新的編號為 $n + k(q - 1) + 1 ldots$ 。

所以編號為 $kq+d$ 的人編號變成了 $n + k(q - 1) + d$ ，其中 $1 le d < q$ 。

直到最後，可以發現活下來的人編號為 $qn$ ，問題是怎麼根據這個編號推出他原來的編號？

以 $n=10$ ， $q=3$ 為例，下圖就是每個人新的編號：

令

$N = n + k(q - 1) + d$

所以他上一次的編號是

$kq + d = kq + N - n - k(q - 1) = k + N - n$

因為

$k = frac{ {N - n - d}}{ {q - 1}} = leftlfloor {frac{ {N - n - 1}}{ {q - 1}}} ight floor$

所以上一次編號可以寫為

$leftlfloor {frac{ {N - n - 1}}{ {q - 1}}} ight floor + N - n$

因此最後存活的人編號可以用如下的演算法計算：

N = qnwhile N > n: N = k + N - nans = N

其中 $k = leftlfloor {frac{ {N - n - 1}}{ {q - 1}}} ight floor$

如果我們用 $D = qn + 1 - N$ 替代 $N$ ，將會進一步簡化演算法：

$egin{array}{l}D = qn + 1 - N\ = qn + 1 - left( {leftlfloor {frac{ {(qn + 1 - D) - n - 1}}{ {q - 1}}} ight floor + qn + 1 - D - n} ight)\ = n + D - leftlfloor {frac{ {(q - 1)n - D}}{ {q - 1}}} ight floor \ = D - leftlfloor {frac{ { - D}}{ {q - 1}}} ight floor \ = D + leftlceil {frac{D}{ {q - 1}}} ight ceil \ = leftlceil {frac{q}{ {q - 1}}D} ight ceil end{array}$

演算法偽代碼如下：

D = 1while D <= (q-1)n: D = kans = qn + 1 - D

其中 $k = leftlceil {frac{q}{ {q - 1}}D} ight ceil$

模的性質

定義與性質

模定義如下：

$xmod y = x - yleftlfloor {frac{x}{y}} ight floor$

特別的

$xmod 0 = x$

與此類似，定義一個與模類似的運算：

$x{ m{ mumble }}y = yleftlceil {frac{x}{y}} ight ceil - x$

形象理解如下圖所示：

圓的周長是 $y$ ，一共走過的路長（紅色+綠色部分）是 $x$ ，所以 $xmod y$ 就是綠色部分， $x{ m{ mumble }}y$ 就是一圈長度減去綠色部分。

模有一些性質：

$c(xmod y) = (cx)mod (cy)$

應用

考慮如下問題，怎麼平均分配 $n$ 個東西給 $m$ 個人？

很容易想到，首先分給每個人 $leftlfloor {frac{n}{m}} ight floor$ 個東西，剩下 $nmod m$ 件東西分給前 $nmod m$ 個人，一人多一件就行。

概括起來就是，前 $nmod m$ 個人，每人 $leftlceil {frac{n}{m}} ight ceil$ 件，剩下的人，每人 $leftlfloor {frac{n}{m}} ight floor$ 件。

那有沒有辦法統一表示呢？有的，每個人分到的件數為

$leftlceil {frac{ {n - k + 1}}{m}} ight ceil ,1 le k le m$

為什麼呢？假設

$n = qm + r,0 le r < m$

那麼

$egin{array}{l}leftlceil {frac{ {n - k + 1}}{m}} ight ceil = leftlceil {frac{ {qm + r - k + 1}}{m}} ight ceil \ = q + leftlceil {frac{ {r - k + 1}}{m}} ight ceil end{array}$

當 $1 le k le r$ 時，

$leftlceil {frac{ {r - k + 1}}{m}} ight ceil = 1$

當 $r < k le m$ 時，

$leftlceil {frac{ {r - k + 1}}{m}} ight ceil = 0$

得證，因此可以得到如下等式：

$n = leftlceil {frac{n}{m}} ight ceil + leftlceil {frac{ {n - 1}}{m}} ight ceil + cdots + leftlceil {frac{ {n - m + 1}}{m}} ight ceil$

由 $n = leftlfloor {frac{n}{2}} ight floor + leftlceil {frac{n}{2}} ight ceil$

可以進一步將其轉換為下取整形式：

$n = leftlfloor {frac{n}{m}} ight floor + leftlfloor {frac{ {n + 1}}{m}} ight floor + cdots + leftlfloor {frac{ {n + m - 1}}{m}} ight floor$

令 $n = leftlfloor {mx} ight floor$

我們得到了一個令人驚奇的等式：

$leftlfloor {mx} ight floor = leftlfloor x ight floor + leftlfloor {x + frac{1}{m}} ight floor + cdots + leftlfloor {x + frac{ {m - 1}}{m}} ight floor$

HDU3089

最後用今天介紹的約瑟夫環演算法來解決一道經典的ACM題！題目鏈接：杭電3089。

C++代碼如下：

#include<bits/stdc++.h>using namespace std;typedef long long LL;LL Ceil(LL x, LL y) { if (x % y == 0) return x / y; return x / y + 1;}LL J(LL n, LL q) { LL D = 1, end = (q - 1) * n; while (D <= end) { D = Ceil(q * D, q - 1); } return q * n + 1 - D;}int main() { LL n, q; while (~scanf("%lld%lld", &n, &q)) { printf("%lld ", J(n, q)); } return 0;}

比網上各種快速演算法還要快哦，理論時間複雜度是 $log n$ 的。