发一个今天面试的算法题有101块金币，其中一块是假的，要求用无砝码的天平称两次，判断是真的金币重还是假的
发一个今天面试的算法题
有101块金币，其中一块是假的，要求用无砝码的天平称两次，判断是真的金币重还是假的重
21 楼 tqjy13 2010-10-14 蛮简单的，两三分钟搞定 22 楼 tqjy13 2010-10-14 Kensai 写道分成3份每份33个，剩2个单独的。
1。任意两组（33个的）放在天平两端，并且把剩的两个也放天平两端。
2。 如果天平平衡（说明第三份是假），换上剩下的一组，并把上一组的单独那个放这边。
结果：偏新的这边就是重反之轻。
如果天平不平衡（说明其中一份是假），换上剩下的一组，并把上一组的单独那个放这边.
结果：天平平衡，轻重由上一组天平偏斜决定。
天平偏向一边，轻重由另一边决定。
这种方法好像有问题的吧 23 楼 kaipingk 2010-10-14 这个题目 很简单阿 24 楼 zhangzijun1984 2010-10-14 其实这个方法很多，呵呵，我的分法是分成3堆，33 34 34
第一种情况，两个34比，如果平衡，说明假币在33里，这样从34里拿走一个，在和33比，便知孰轻孰重
第二种情况，两个34比，不平衡，把重的分成17 17，这两堆17的比，如果不平衡，说明假币在重的里面，即假币重，要是两堆17平衡，说明假币在轻的那堆34里，即假币轻 25 楼 xhdwell 2010-10-15 zhangzijun1984 写道其实这个方法很多，呵呵，我的分法是分成3堆，33 34 34
第一种情况，两个34比，如果平衡，说明假币在33里，这样从34里拿走一个，在和33比，便知孰轻孰重
第二种情况，两个34比，不平衡，把重的分成17 17，这两堆17的比，如果不平衡，说明假币在重的里面，即假币重，要是两堆17平衡，说明假币在轻的那堆34里，即假币轻
有问题，34*2+33的方法我想了好久，肯定不成功的。 26 楼 shaobaitou 2010-10-15 kldwq2002 写道分三份，第一份份五十个，第二份五十个，第三份份一个。
第一次：将两份五十个分别放到天平两端。
如果天平是平的，证明第三份是假的。这时只要从真的里拿出一个，和假的分别放到天平两端，就能知道假的是轻是重。
如果天平是不平的，证明在天平上的两份中有一份包含假的，而第三份是真的。
将重的那一份分成两份，每份25个，分别放到天平两端，如果天平是平的，证明这些全部是真的，而假的在轻的那一堆里，就能证明假的轻。
如果天平不是平的，证明假的包含在这50个里，因为这50个是重的那一堆，所以假的重。
正解。
27 楼 清风_夕瑶 2010-10-15 zhangzijun1984 写道其实这个方法很多，呵呵，我的分法是分成3堆，33 34 34
第一种情况，两个34比，如果平衡，说明假币在33里，这样从34里拿走一个，在和33比，便知孰轻孰重
第二种情况，两个34比，不平衡，把重的分成17 17，这两堆17的比，如果不平衡，说明假币在重的里面，即假币重，要是两堆17平衡，说明假币在轻的那堆34里，即假币轻
不错，比1,50,25,25 好 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个怎么称？ 29 楼 抢街饭 2010-10-15 差距啊！！！！！！！！！！！ 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里，即假币轻
31 楼 smzd 2010-10-15 nid007高人啊！吾不及也！闪了 32 楼 snow8261 2010-10-15 佩服啊 。。。。 33 楼 清风_夕瑶 2010-10-15 从smzd解析来看，smzd在数学方面应当颇有研究；nid007思维更加灵活。
34 楼 duesouth 2010-10-15 tedeyang 写道
简单分治法。
可以引申开很多内容：
业务逻辑分析，bug定位，性能分析，二分法搜索，其实还和“将变与不变相隔离”的OOP思想也相通。
大道至简。
细节不用考虑太多，适合面试的小时间量，好题！
引的出来这么多吗？就是一简单的智力题，只要说得通都可以得分。 35 楼 antjava 2010-10-15 好题！ 我怎么没遇到这样的题。 36 楼 kuchaguangjie 2010-10-16 50,50,1
第1次： 50 和 50 对称，
第2次：
如果 50 和 50 相等，则拿那1个替换某个50的1个，即可，
如果 50 不等，则取轻的50，分为 25,25 ，对称，
如果相等，则重了，
如果不等，则轻了， 37 楼 徐风子 2010-10-16 这是算法题还是IQ题呀？？ 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
只要满足前两份相等数量，且是偶数份，且大于第三份，都能称出来 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，那又另当别论了 40 楼 jiminsc 2011-02-24 aria 写道这叫算法？
同感，还以为要用到什么递归，只是逻辑思考即解决了
