发一个今天面试的算法题

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

评论

40 楼 jiminsc 2011-02-24  

aria 写道

这叫算法？

同感，还以为要用到什么递归，只是逻辑思考即解决了

39 楼 zsx923 2010-12-09  

smzd 写道

清风_夕瑶 写道

zhangzijun1984 写道

其实这个方法很多，呵呵，我的分法是分成3堆，33  34  34
第一种情况，两个34比，如果平衡，说明假币在33里，这样从34里拿走一个，在和33比，便知孰轻孰重
第二种情况，两个34比，不平衡，把重的分成17  17，这两堆17的比，如果不平衡，说明假币在重的里面，即假币重，要是两堆17平衡，说明假币在轻的那堆34里，即假币轻

不错，比1,50,25,25 好

这两个原理是一样的吧？区别在于顺序不同而已。
其实就是这样：
分成三份，分别数量为X，X， Y，满足：2X+Y=101; X=2n（n>0即，X是非零偶数）; X>=Y即可。
称的时候先将两个X分别放在天平两端，如果平衡，表示有瑕疵的在Y中。将天平一端清空，放上Y，由于X>=Y，因此从另一端取出（X-Y）个来，看看Y这边沉则有瑕疵的重，否则轻；若不平衡，则将天平一端清空（哪一端无所谓，但要记住留下的是沉的一端还是轻的一端），将另一侧的取一半（X是偶数）到这一端，若平衡，则这一组都没问题，有问题的是取下去的那一组，很容易就判断出轻重；若仍不平衡，也很容易了。

这是分法，而50，25，25，1实际上是合法。两种本质上是一样的

的确50，25，25，1是有一点问题的，但对于本题没有一点问题。这种分法钻了一个空子，就是101是奇数，而100是4的倍数。试一下如果是100个怎么称？或者奇数的话，99个怎么称？

两种方法都是一样的，不存在有什么问题，相反我倒觉得33，34，34这种方法数字太偏
个人认为大众首先想到的就是50，50，1
1. 50平衡，则1VS1
2. 不平衡则随便拿一堆50(假设轻的一边)的，分开，一边25
  1)平衡，则这堆50是真的，假币在另外一堆50中，而另外一堆50又重
  2)不平衡，则假币就在这堆50中，而这堆又轻

还有上面提到什么奇数，什么钻空子，没必要研究那么深，就是一道益智题，真要像你说的100或99，那又另当别论了

38 楼 hadesmile 2010-11-09  

50 50 1
48 48 5
46 46 9
44 44 13
42 42 17
40 40 21
...
34 34 33

只要满足前两份相等数量，且是偶数份，且大于第三份，都能称出来

37 楼 徐风子 2010-10-16  

这是算法题还是IQ题呀？？

36 楼 kuchaguangjie 2010-10-16  

50,50,1

第1次： 50 和 50 对称，
第2次：
   如果 50 和 50 相等，则拿那1个替换某个50的1个，即可，
   如果 50 不等，则取轻的50，分为 25,25 ，对称，
      如果相等，则重了，
      如果不等，则轻了，

35 楼 antjava 2010-10-15  

好题！ 我怎么没遇到这样的题。

34 楼 duesouth 2010-10-15  

tedeyang 写道

简单分治法。
可以引申开很多内容：
  业务逻辑分析，bug定位，性能分析，二分法搜索，其实还和“将变与不变相隔离”的OOP思想也相通。

大道至简。
细节不用考虑太多，适合面试的小时间量，好题！

引的出来这么多吗？就是一简单的智力题，只要说得通都可以得分。

33 楼 清风_夕瑶 2010-10-15  

从smzd解析来看，smzd在数学方面应当颇有研究；nid007思维更加灵活。

32 楼 snow8261 2010-10-15  

佩服啊 。。。。

31 楼 smzd 2010-10-15  

nid007高人啊！吾不及也！闪了

30 楼 nid007 2010-10-15  

smzd 写道

清风_夕瑶 写道

zhangzijun1984 写道

其实这个方法很多，呵呵，我的分法是分成3堆，33  34  34
第一种情况，两个34比，如果平衡，说明假币在33里，这样从34里拿走一个，在和33比，便知孰轻孰重
第二种情况，两个34比，不平衡，把重的分成17  17，这两堆17的比，如果不平衡，说明假币在重的里面，即假币重，要是两堆17平衡，说明假币在轻的那堆34里，即假币轻

不错，比1,50,25,25 好

这两个原理是一样的吧？区别在于顺序不同而已。
其实就是这样：
分成三份，分别数量为X，X， Y，满足：2X+Y=101; X=2n（n>0即，X是非零偶数）; X>=Y即可。
称的时候先将两个X分别放在天平两端，如果平衡，表示有瑕疵的在Y中。将天平一端清空，放上Y，由于X>=Y，因此从另一端取出（X-Y）个来，看看Y这边沉则有瑕疵的重，否则轻；若不平衡，则将天平一端清空（哪一端无所谓，但要记住留下的是沉的一端还是轻的一端），将另一侧的取一半（X是偶数）到这一端，若平衡，则这一组都没问题，有问题的是取下去的那一组，很容易就判断出轻重；若仍不平衡，也很容易了。

这是分法，而50，25，25，1实际上是合法。两种本质上是一样的

的确50，25，25，1是有一点问题的，但对于本题没有一点问题。这种分法钻了一个空子，就是101是奇数，而100是4的倍数。试一下如果是100个怎么称？或者奇数的话，99个怎么称？

100个的情况可以这样：
分成三份48 48 4
情况一：两个48相比，如果平衡，说明假币在4里，这样从48里拿出4个真币，再和含假币的4比，便知孰轻孰重
情况二：两个48比，不平衡，把重的分成24  24，这两堆24的比，如果不平衡，说明假币在重的里面，即假币重，要是两堆24平衡，说明假币在轻的那堆48里，即假币轻

99个情况可以这样：
分成三份48 48 1
情况一：两个48相比，如果平衡，说明假币在1里，这样从48里拿出1个真币，再和1比，便知孰轻孰重
情况二：两个48比，不平衡，把重的分成24  24，这两堆24的比，如果不平衡，说明假币在重的里面，即假币重，要是两堆24平衡，说明假币在轻的那堆48里，即假币轻

29 楼 抢街饭 2010-10-15  

差距啊！！！！！！！！！！！

28 楼 smzd 2010-10-15  

清风_夕瑶 写道

zhangzijun1984 写道

其实这个方法很多，呵呵，我的分法是分成3堆，33  34  34
第一种情况，两个34比，如果平衡，说明假币在33里，这样从34里拿走一个，在和33比，便知孰轻孰重
第二种情况，两个34比，不平衡，把重的分成17  17，这两堆17的比，如果不平衡，说明假币在重的里面，即假币重，要是两堆17平衡，说明假币在轻的那堆34里，即假币轻

不错，比1,50,25,25 好

这两个原理是一样的吧？区别在于顺序不同而已。
其实就是这样：
分成三份，分别数量为X，X， Y，满足：2X+Y=101; X=2n（n>0即，X是非零偶数）; X>=Y即可。
称的时候先将两个X分别放在天平两端，如果平衡，表示有瑕疵的在Y中。将天平一端清空，放上Y，由于X>=Y，因此从另一端取出（X-Y）个来，看看Y这边沉则有瑕疵的重，否则轻；若不平衡，则将天平一端清空（哪一端无所谓，但要记住留下的是沉的一端还是轻的一端），将另一侧的取一半（X是偶数）到这一端，若平衡，则这一组都没问题，有问题的是取下去的那一组，很容易就判断出轻重；若仍不平衡，也很容易了。

这是分法，而50，25，25，1实际上是合法。两种本质上是一样的

的确50，25，25，1是有一点问题的，但对于本题没有一点问题。这种分法钻了一个空子，就是101是奇数，而100是4的倍数。试一下如果是100个怎么称？或者奇数的话，99个怎么称？

27 楼 清风_夕瑶 2010-10-15  

zhangzijun1984 写道

其实这个方法很多，呵呵，我的分法是分成3堆，33  34  34
第一种情况，两个34比，如果平衡，说明假币在33里，这样从34里拿走一个，在和33比，便知孰轻孰重
第二种情况，两个34比，不平衡，把重的分成17  17，这两堆17的比，如果不平衡，说明假币在重的里面，即假币重，要是两堆17平衡，说明假币在轻的那堆34里，即假币轻

不错，比1,50,25,25 好

26 楼 shaobaitou 2010-10-15  

kldwq2002 写道

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

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

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

正解。

25 楼 xhdwell 2010-10-15  

zhangzijun1984 写道

其实这个方法很多，呵呵，我的分法是分成3堆，33  34  34
第一种情况，两个34比，如果平衡，说明假币在33里，这样从34里拿走一个，在和33比，便知孰轻孰重
第二种情况，两个34比，不平衡，把重的分成17  17，这两堆17的比，如果不平衡，说明假币在重的里面，即假币重，要是两堆17平衡，说明假币在轻的那堆34里，即假币轻

有问题，34*2+33的方法我想了好久，肯定不成功的。

24 楼 zhangzijun1984 2010-10-14  

其实这个方法很多，呵呵，我的分法是分成3堆，33  34  34
第一种情况，两个34比，如果平衡，说明假币在33里，这样从34里拿走一个，在和33比，便知孰轻孰重
第二种情况，两个34比，不平衡，把重的分成17  17，这两堆17的比，如果不平衡，说明假币在重的里面，即假币重，要是两堆17平衡，说明假币在轻的那堆34里，即假币轻

23 楼 kaipingk 2010-10-14  

这个题目 很简单阿

22 楼 tqjy13 2010-10-14  

Kensai 写道

分成3份每份33个，剩2个单独的。
1。任意两组（33个的）放在天平两端，并且把剩的两个也放天平两端。
2。 如果天平平衡（说明第三份是假），换上剩下的一组，并把上一组的单独那个放这边。
结果：偏新的这边就是重反之轻。
   如果天平不平衡（说明其中一份是假），换上剩下的一组，并把上一组的单独那个放这边.
结果：天平平衡，轻重由上一组天平偏斜决定。
     天平偏向一边，轻重由另一边决定。

这种方法好像有问题的吧

21 楼 tqjy13 2010-10-14  

蛮简单的，两三分钟搞定