|
锁定老帖子 主题：发一个今天面试的算法题
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-10-14
蛮简单的，两三分钟搞定
|
| 返回顶楼 | |
|
发表时间：2010-10-14
Kensai 写道 分成3份每份33个，剩2个单独的。
1。任意两组（33个的）放在天平两端，并且把剩的两个也放天平两端。 2。 如果天平平衡（说明第三份是假），换上剩下的一组，并把上一组的单独那个放这边。 结果：偏新的这边就是重反之轻。 如果天平不平衡（说明其中一份是假），换上剩下的一组，并把上一组的单独那个放这边. 结果：天平平衡，轻重由上一组天平偏斜决定。 天平偏向一边，轻重由另一边决定。 这种方法好像有问题的吧 |
| 返回顶楼 | |
|
发表时间：2010-10-14
这个题目 很简单阿
|
| 返回顶楼 | |
|
发表时间：2010-10-14
其实这个方法很多，呵呵，我的分法是分成3堆，33 34 34
第一种情况，两个34比，如果平衡，说明假币在33里，这样从34里拿走一个，在和33比，便知孰轻孰重 第二种情况，两个34比，不平衡，把重的分成17 17，这两堆17的比，如果不平衡，说明假币在重的里面，即假币重，要是两堆17平衡，说明假币在轻的那堆34里，即假币轻 |
| 返回顶楼 | |
|
发表时间：2010-10-15
zhangzijun1984 写道 其实这个方法很多，呵呵，我的分法是分成3堆，33 34 34
第一种情况，两个34比，如果平衡，说明假币在33里，这样从34里拿走一个，在和33比，便知孰轻孰重 第二种情况，两个34比，不平衡，把重的分成17 17，这两堆17的比，如果不平衡，说明假币在重的里面，即假币重，要是两堆17平衡，说明假币在轻的那堆34里，即假币轻 有问题，34*2+33的方法我想了好久，肯定不成功的。 |
| 返回顶楼 | |
|
发表时间：2010-10-15
kldwq2002 写道 分三份，第一份份五十个，第二份五十个，第三份份一个。
第一次：将两份五十个分别放到天平两端。 如果天平是平的，证明第三份是假的。这时只要从真的里拿出一个，和假的分别放到天平两端，就能知道假的是轻是重。 如果天平是不平的，证明在天平上的两份中有一份包含假的，而第三份是真的。 将重的那一份分成两份，每份25个，分别放到天平两端，如果天平是平的，证明这些全部是真的，而假的在轻的那一堆里，就能证明假的轻。 如果天平不是平的，证明假的包含在这50个里，因为这50个是重的那一堆，所以假的重。 正解。 |
| 返回顶楼 | |
|
发表时间：2010-10-15
zhangzijun1984 写道 其实这个方法很多，呵呵，我的分法是分成3堆，33 34 34
第一种情况，两个34比，如果平衡，说明假币在33里，这样从34里拿走一个，在和33比，便知孰轻孰重 第二种情况，两个34比，不平衡，把重的分成17 17，这两堆17的比，如果不平衡，说明假币在重的里面，即假币重，要是两堆17平衡，说明假币在轻的那堆34里，即假币轻 不错，比1,50,25,25 好 |
| 返回顶楼 | |
|
发表时间：2010-10-15
最后修改：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个怎么称？ |
| 返回顶楼 | |
|
发表时间：2010-10-15
差距啊！！！！！！！！！！！
|
| 返回顶楼 | |
|
发表时间：2010-10-15
最后修改：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里，即假币轻 |
| 返回顶楼 | |
