发一个今天面试的算法题

楠楠 · 发表于 2011-9-7 10:38

有101块金币，其中一块是假的，要求用无砝码的天平称两次，判断是真的金币重还是假的重

无处不在 · 发表于 2011-9-7 10:38

目前想到的是:
1,分四份 25 25 50 1 先称25 25的若不同.则从50的那堆分25个出来称.则这三堆中就能得到答案.
2,若25 25相同则合并成50 同 50的一起称...若你人品非常有问题...50 = 50的重量...则拿出来的那个是假的...以后就要称第三次了...

江波 · 发表于 2011-9-7 10:38

分三份，第一份份五十个，第二份五十个，第三份份一个。

第一次：将两份五十个分别放到天平两端。
如果天平是平的，证明第三份是假的。这时只要从真的里拿出一个，和假的分别放到天平两端，就能知道假的是轻是重。

如果天平是不平的，证明在天平上的两份中有一份包含假的，而第三份是真的。
将重的那一份分成两份，每份25个，分别放到天平两端，如果天平是平的，证明这些全部是真的，而假的在轻的那一堆里，就能证明假的轻。
如果天平不是平的，证明假的包含在这50个里，因为这50个是重的那一堆，所以假的重。

ksdal · 发表于 2011-9-7 10:39

kldwq2002 写道
分三份，第一份份五十个，第二份五十个，第三份份一个。

第一次：将两份五十个分别放到天平两端。
如果天平是平的，证明第三份是假的。这时只要从真的里拿出一个，和假的分别放到天平两端，就能知道假的是轻是重。

如果天平是不平的，证明在天平上的两份中有一份包含假的，而第三份是真的。
将重的那一份分成两份，每份25个，分别放到天平两端，如果天平是平的，证明这些全部是真的，而假的在轻的那一堆里，就能证明假的轻。
如果天平不是平的，证明假的包含在这50个里，因为这50个是重的那一堆，所以假的重。

啊...我开始想三份的时候...就是这样分的..25 25的我咋用到其他的地方去呢..笨死了.

北大青鸟 · 发表于 2011-9-7 10:39

主要是把第二步的逻辑理清楚，呵。

fl · 发表于 2011-9-7 10:39

kldwq2002 写道
主要是把第二步的逻辑理清楚，呵。

对啊..我就失败在第二部...怎么没想到平均分呢..

话说我当年 · 发表于 2011-9-7 10:40

这个题比称12个球的那个题简单多了

江南枫 · 发表于 2011-9-7 10:40

称两次。。。。

feiguo · 发表于 2011-9-7 10:40

kldwq2002 写道
分三份，第一份份五十个，第二份五十个，第三份份一个。

第一次：将两份五十个分别放到天平两端。
如果天平是平的，证明第三份是假的。这时只要从真的里拿出一个，和假的分别放到天平两端，就能知道假的是轻是重。

如果天平是不平的，证明在天平上的两份中有一份包含假的，而第三份是真的。
将重的那一份分成两份，每份25个，分别放到天平两端，如果天平是平的，证明这些全部是真的，而假的在轻的那一堆里，就能证明假的轻。
如果天平不是平的，证明假的包含在这50个里，因为这50个是重的那一堆，所以假的重。

佩服

走就走吧 · 发表于 2011-9-7 10:40

kldwq2002 写道
分三份，第一份份五十个，第二份五十个，第三份份一个。

第一次：将两份五十个分别放到天平两端。
如果天平是平的，证明第三份是假的。这时只要从真的里拿出一个，和假的分别放到天平两端，就能知道假的是轻是重。

如果天平是不平的，证明在天平上的两份中有一份包含假的，而第三份是真的。
将重的那一份分成两份，每份25个，分别放到天平两端，如果天平是平的，证明这些全部是真的，而假的在轻的那一堆里，就能证明假的轻。
如果天平不是平的，证明假的包含在这50个里，因为这50个是重的那一堆，所以假的重。

呵呵,想法一样.

帐号		自动登录	找回密码
密码			成为会员