有一个人，有很多盘录像带。每个录像带买的时候都带有0到9这10个数码（各一个）。他想把所有录像带从一开始用这些数码编号，发现数码不够用，于是改成用16进位，再用上A到F这6个字母，就够用了。他最少有多少录像带？最多有多少？ 更一般一点，设b是偶数，用b进制，最多可以标多少盘录像带？ www.ddhw.com 这题实际上是说，什么时候1到n所有的数用到的1的数量超过n？（1总是最先用完。） 我们定义两个函数：f(n)是1到n所有的数用到的1的数量，g(n) = f(n) - n。我们要找最小的n使得g(n)大于0。www.ddhw.com 首先证明这个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不可能是最小的。 www.ddhw.com 因为首位为1时g(n)是递增函数，我们只需要检查所有的19，199，1999，...，看看什么时候g(n)变成正数，然后就可以倒退回去找到最小的n. www.ddhw.com 一般来说，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。www.ddhw.com www.ddhw.com 以上论证对所有偶数进位制都有效：设b为偶数，则b进位时最小的 n 使得g(n) > n 的是 2*b^(b/2) - b + 1。 www.ddhw.com 对于一开始的录像带问题，这个人最少有199991盘，最多有1FFFFFFF0 = 8589934576盘。
| 
哈哈哈哈 O(∩_∩)O哈哈~ 好久不来了，不小心看了一眼自己主页，发现自动关联了自己以往发过的帖，点进这个看了一眼，笑个半死。。。敢情我当初还发过这么搞笑的东西啊，我自己完全不记得了 
雷达卡
发表于 2005-12-1 21:56:10
收藏
分享
支持
反对
置顶卡
千斤顶
