|
锁定老帖子 主题：发一个今天面试的算法题
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-10-14
kldwq2002 写道 分三份，第一份份五十个，第二份五十个，第三份份一个。
第一次：将两份五十个分别放到天平两端。 如果天平是平的，证明第三份是假的。这时只要从真的里拿出一个，和假的分别放到天平两端，就能知道假的是轻是重。 如果天平是不平的，证明在天平上的两份中有一份包含假的，而第三份是真的。 将重的那一份分成两份，每份25个，分别放到天平两端，如果天平是平的，证明这些全部是真的，而假的在轻的那一堆里，就能证明假的轻。 如果天平不是平的，证明假的包含在这50个里，因为这50个是重的那一堆，所以假的重。 一样 |
| 返回顶楼 | |
|
发表时间：2010-10-14
kldwq2002 写道 分三份，第一份份五十个，第二份五十个，第三份份一个。
第一次：将两份五十个分别放到天平两端。 如果天平是平的，证明第三份是假的。这时只要从真的里拿出一个，和假的分别放到天平两端，就能知道假的是轻是重。 如果天平是不平的，证明在天平上的两份中有一份包含假的，而第三份是真的。 将重的那一份分成两份，每份25个，分别放到天平两端，如果天平是平的，证明这些全部是真的，而假的在轻的那一堆里，就能证明假的轻。 如果天平不是平的，证明假的包含在这50个里，因为这50个是重的那一堆，所以假的重。  缜密
|
| 返回顶楼 | |
|
发表时间：2010-10-14
这叫算法？
|
| 返回顶楼 | |
|
发表时间：2010-10-14
分成3份每份33个，剩2个单独的。
1。任意两组（33个的）放在天平两端，并且把剩的两个也放天平两端。 2。 如果天平平衡（说明第三份是假），换上剩下的一组，并把上一组的单独那个放这边。 结果：偏新的这边就是重反之轻。 如果天平不平衡（说明其中一份是假），换上剩下的一组，并把上一组的单独那个放这边. 结果：天平平衡，轻重由上一组天平偏斜决定。 天平偏向一边，轻重由另一边决定。 |
| 返回顶楼 | |
|
发表时间：2010-10-14
这么简单的题目 晕死
|
| 返回顶楼 | |
|
发表时间：2010-10-14
很简单：
33 \ 33 \33 1 \ 1 |
| 返回顶楼 | |
|
发表时间：2010-10-14
冇心人 写道
有101块金币，其中一块是假的，要求用无砝码的天平称两次，判断是真的金币重还是假的重
1、分3堆，50、50、1 2、把2堆50的放上天平两边称重 3、若相等则说明剩下的那个金币是假币，任取其中的一个金币跟剩下的那一个金币称重即可 4、若不等将剩下的那个金币放到轻的那边，如果变重了说明假币比真币轻，反之假币比真币重
|
| 返回顶楼 | |
|
发表时间：2010-10-14
简单分治法。 可以引申开很多内容： 业务逻辑分析，bug定位，性能分析，二分法搜索，其实还和“将变与不变相隔离”的OOP思想也相通。 大道至简。 细节不用考虑太多，适合面试的小时间量，好题！ |
| 返回顶楼 | |
|
发表时间：2010-10-14
我就想问下
50 50 1 这种分法 从50个里面取一个来称 违反规则吗? |
| 返回顶楼 | |
|
发表时间：2010-10-14
kldwq2002 写道 分三份，第一份份五十个，第二份五十个，第三份份一个。
第一次：将两份五十个分别放到天平两端。 如果天平是平的，证明第三份是假的。这时只要从真的里拿出一个，和假的分别放到天平两端，就能知道假的是轻是重。 如果天平是不平的，证明在天平上的两份中有一份包含假的，而第三份是真的。 将重的那一份分成两份，每份25个，分别放到天平两端，如果天平是平的，证明这些全部是真的，而假的在轻的那一堆里，就能证明假的轻。 如果天平不是平的，证明假的包含在这50个里，因为这50个是重的那一堆，所以假的重。 聪明！赞一个～ |
| 返回顶楼 | |
