有一个人，有很多盘录像带。每个录像带买的时候都带有0到9这10个数码（各一个）。他想把所有录像带从一开始用这些数码编号，发现数码不够用，于是改成用16进位，再用上A到F这6个字母，就够用了。他最少有多少录像带？最多有多少？
更一般一点，设b是偶数，用b进制，最多可以标多少盘录像带？
这题实际上是说，什么时候1到n所有的数用到的1的数量超过n？（1总是最先用完。）
我们定义两个函数：f(n)是1到n所有的数用到的1的数量，g(n) = f(n) - n。我们要找最小的n使得g(n)大于0。
首先证明这个n的首位一定是1。如果不是1，是a，则有 n = a*10^k + x，及 g(a*10^k + x) > 0, g(a*10^k) <= 0。而 g(a*10^k + x) - g(a*10^k) = g(x) - g(0) = g(x) > 0。所以这个n不可能是最小的。
因为首位为1时g(n)是递增函数，我们只需要检查所有的19，199，1999，...，看看什么时候g(n)变成正数，然后就可以倒退回去找到最小的n.
一般来说，g(2*10^k - 1) = 10^k + 2 * g(10^k - 1) = 10^k + 2 * k*(10^(k-1))。如果要 g(2*10^k - 1) > 2*10^k - 1，则有 2 * k*(10^(k-1)) > 10^k - 1，即 2*k >= 10。所以 k = 5。这时 g(199999) = 1，数下去就会发现 g(199991) = 1 及 g(199990) = 0。
以上论证对所有偶数进位制都有效：设b为偶数，则b进位时最小的 n 使得g(n) > n 的是 2*b^(b/2) - b + 1。
对于一开始的录像带问题，这个人最少有199991盘，最多有1FFFFFFF0 = 8589934576盘。
| 欢迎光临 珍珠湾ART (http://66.160.158.134/) | Powered by Discuz! X3 |