分享
 
 
 

对微软面试题中金子分段的延伸总结 高手莫入

王朝other·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

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

|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|

| 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

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有