A:你讓某些人為你工作了七天，你要用一根金條作為報酬。這根金條要被分成七塊。你必須在每天的活干完后交給他們一塊。如果你只能將這根金條切割兩次，你怎樣給這些工人分？

Q
先把金條平均分為七份（不切割）

第一次切割七分之一 第二次切割七分之二

這樣就分為三段 七分之一一段 七分之二一段 七分之四一段

然后根據(jù)每天工作量交換就好了




切成1段,2段,和四段.
1:給出1.
2:給出2,還回1.
3:給出1.
4:給出4,還回3.
5:給出1.
6:給出2,還回1.
7:給出1.

7 ＝ 1 ＋ 2 ＋ 4，分成三段，截2次，由上述“切成1段,2段,和四段”感覺1、2、4有一定的規(guī)律性，由此聯(lián)想到了下面的遞歸等式
2^n -1 = (2^n -1)/(2 – 1 ) = 1 + 2 + …. 2^(n-1) 》》》S(n) – 1 = 1 + 2 + … S(n-1)
其中S(n) ＝ 2^n， S(0) ＝ 1
等比數(shù)列求和的問題，即最后一項為前面所有項的和再加1
這里的加1就相對于每天的工資，故每天給新的金條時要將前面的相應(yīng)項和的對應(yīng)金條取回。
 
如果為15，則是截三次，分別為1 2 4 8，便可處理任意的整數(shù)了
 
即以零換整的問題，鈔票為什么設(shè)計成 1 2 5 10，估計是上述四個數(shù)可以以最小的張數(shù)組合任意的整數(shù)，哈哈，不會出現(xiàn)別人給你整票不能夠找開的問題了。有興趣的朋友可以用程序證明1 2 5 是最高效的方法，我猜是的，要不然為什么全世界都是這么設(shè)計的呢？
 
反向推理：一根金條平均分成N段相連，每天的工資為一段，最少截成幾段才能每天完工后付給工人當天的工資？
2^(n-1) – 1 < N =< 2^n -1
最小的n值必須滿足上述不等式
即（2^(n-1) – 1 ，2^n -1]半開半閉區(qū)間內(nèi)的N值都至少分成n段才能解決當天完畢付工資問題
利用上述不等式，即可針對任意的N值快速算出分段次數(shù)了，不管面試者如何改動N值，都是易如反掌了，以一敵百，輕松搞定

本文來自CSDN博客，轉(zhuǎn)載請標明出處：http://blog.csdn.net/TanXiangHao/archive/2008/10/14/3072905.aspx