微软面试题中金子分段问题的延伸及总结

对微软面试题中金子分段问题的延伸及总结

 |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| 
 |   Date   :      2002.03.08       | 
 |  Author  :    Seraph Chutium     | 
 | Homepage : http://com.6to23.com/ | 
 |                                  | 
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 


声明：写的比较仓促，基本思想肯定是没错，如果表述上有错误望大家见谅，
　　　若有严重的逻辑错误希望得到大家指正。（可以来留言簿留言讨论）

　　　学习过二进制算法的朋友遍可略过此文，只是举一小例胡乱说说2^n与二进制数的关系而已。
　　　编程高手更可不必为此费时，诸位大侠如能幸得闲暇，定能写的比这个明了深刻数倍。


1. 试题分析延伸

在《程序员》杂志试刊一中曾刊登过一道微软用来面试的题目：

工人为你工作7天，回报为一根金条，必须在每天付给他们一段，且只能截2次，你将如何付费？
我们再来看我自己编的一道题目：如何将7块金子放入3个箱子中，使我可以整箱取走任意块数？

我们可以很容易的发现，这样的两道题目实质是一样的，而其答案也是相同的。
即：将金条切成 1,2,4 三段，或者说将7块金子分别以 1,2,4 块放入箱子中。

这道题目是比较简单的，但是如果用同样的情景，出一道这样的题呢？

工人为你工作365天，回报为一根金条，必须在每天付给他们一段，且只能截9次，你将如何付费？
或者说如何将365块金子放入9个箱子中，使我可以整箱取走任意块数？

用这样的数字可能比较难看出其中的玄机，我们换做这样的一组数：

………………255天，…………………………7次，你将如何付费？
或者说如何将255块金子放入8个箱子中，可以整箱取走任意块数？

看到8和255这样两个数字想必大家就会马上意识到255=2^8-1。
那么这样的一组数字和金子分段有什么关系呢？我们来看看上面两个更复杂些的题目的答案。

365天的情况：切 8 次就等于将原金条分成 9 段装入 9 个箱子，
则其分法为 ：I: 1, II: 2, III: 4, IV: 8, V: 16, VI: 32, VII: 64, VIII: 128,
　　　　　　 IX: 365-255=110.

255天的情况：切 7 次就等于将原金条分成 8 段装入 8 个箱子，
则其分法为 ：I: 1, II: 2, III: 4, IV: 8, V: 16, VI: 32, VII: 64, VIII: 128.


2. 对此类题目的总结

这样，我们不难发现，m 个箱子所能完成上述过程所装的“金子”数最多为 2^m-1 个。
而此时箱子中的“金子”数分别为：2^0, 2^1, 2^2, ... 2^(m-1) 个。

由此我们就可导出对于任意一个自然数 N ，都可以将它分成若干份，使我们可以整份
取出任意数量。

在(0,N)中必有一个最大的 2^n 值，此自然数 N 就可以分成 n+1 份，
每份中数值分别为：2^0, 2^1, 2^2, ... 2^(n-1), N-2^n


3. 寻根问源

那么这是为什么呢？

我们拿最简单的 7, 8, 15, 16 来做个说明。

先写出 16 以内十进制数和二进制数的对应表，我们从中会悟出一些道理。

0
0

1     2
1     10

3     4
11    100

5     6      7      8
101   110    111    1000

9     10     11     12     13     14     15     16
1001  1010   1011   1100   1101   1110   1111   10000

而如果分 7, 8, 15, 16 这四个数为几份，分别应该是：

 7: 1, 2, 4
16: 1, 2, 4, 8, 1

对于 7，如果我们要拿出  5 (101) 就是  1,4  两份；拿出 7  (111) 就是 1,2,4 三份。
对于16，如果我们要拿出 11(1011) 就是 1,2,8 三份；拿出12 (1100) 就是  4,8  两份；
　　　　　　　　　拿出 14(1110) 就是 2,4,8 三份；拿出 15(1111) 就是1,2,4,8四份；

这样，很明显的可以看出，对于任意一个自然数 N ，依照前面讲过的方法，分成 n+1 份后，
如果要拿出N，自然就取出全部的n+1份即可；
如果要拿出一定的数量 a (a<=N-1, a=0,1,2,3...)，
将它写成二进制数后，哪一位上的数是1，就拿出那一份，组成的就是这个数 a 。


 |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| 
 |   Date   :      2002.03.08       | 
 |  Author  :    Seraph Chutium     | 
 | Homepage : http://com.6to23.com/ | 
 |                                  | 
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~