33,008
社区成员
发帖
与我相关
我的任务
分享过年前的讨论2！关于天平称球问题的统一解法!
前段时间有几个帖子都是关于天平称球问题的，我也从中学习了不少。
有个哥们提出，可以用信息论解这类的题，可以求出次数的范围，
我按照他们给的方法算了一些小的模型，发现确实如此。
以比较有名的12彩球问题为例，天平有3种状态，因此每次可以获得信息为log3 bit,
12个彩球，由于不知其轻重，因此共12*2 = 24种状态，
2 < log24 / log3 < 3 因此3次可以搞定。并且可以推出3次最多可以称13个球。
用这种方法还可以推算出，假如存在2个坏球(两个坏球质量相同)，那么总共C(12,2) * 2 = 132种状态
因为4 < log132 / log3 < 5，那么只需要5次就能称出，也可以推出5次最多可以从16个球中挑出2个坏球。
到了这里，问题来了，别人会跟我说，5次不可能，除非你告诉我怎么称，我虽然会算次数，但称的过程却说不出来。
如果用程序，应该怎么做呢？我也没什么好的思路，用穷举法，规模太大了......该咋办呢？
有个哥们提出，可以用信息论解这类的题，可以求出次数的范围，
我按照他们给的方法算了一些小的模型，发现确实如此。
以比较有名的12彩球问题为例，天平有3种状态，因此每次可以获得信息为log3 bit,
12个彩球，由于不知其轻重，因此共12*2 = 24种状态，
2 < log24 / log3 < 3 因此3次可以搞定。并且可以推出3次最多可以称13个球。
用这种方法还可以推算出，假如存在2个坏球(两个坏球质量相同)，那么总共C(12,2) * 2 = 132种状态
因为4 < log132 / log3 < 5，那么只需要5次就能称出，也可以推出5次最多可以从16个球中挑出2个坏球。
到了这里，问题来了，别人会跟我说，5次不可能，除非你告诉我怎么称，我虽然会算次数，但称的过程却说不出来。
如果用程序，应该怎么做呢？我也没什么好的思路，用穷举法，规模太大了......该咋办呢？
...全文
请发表友善的回复…
发表回复
高级码工 2012-08-17
- 打赏
- 举报
很好很强大，不过我看不太懂。。
jdtxse 2010-05-16
- 打赏
- 举报
学习了
ccqmpux 2009-11-29
- 打赏
- 举报
very good!!!
bbqqqbq 2009-02-04
- 打赏
- 举报
[Quote=引用 22 楼 woxueliuyun 的回复:]
12个球, 其中一个是次品, 一架标准天平, 称3次指出哪个是次品球, 重了还是轻了?
方法很简单：
第一次：两边个六个，留下轻的那边的六个。
第二次：两边个三个，留下轻的那边的三个。
第三次：任意放两个上去，如果天平平衡则说明次品没在天平上。如果天平不平衡，则说明次品在轻的一端。
[/Quote]
按照以上方法完全可以判断出来哪一个是坏球。。。。
大伙是不是把简单的问题复杂化了
12个球, 其中一个是次品, 一架标准天平, 称3次指出哪个是次品球, 重了还是轻了?
方法很简单：
第一次：两边个六个，留下轻的那边的六个。
第二次：两边个三个，留下轻的那边的三个。
第三次：任意放两个上去，如果天平平衡则说明次品没在天平上。如果天平不平衡，则说明次品在轻的一端。
[/Quote]
按照以上方法完全可以判断出来哪一个是坏球。。。。
大伙是不是把简单的问题复杂化了
northwolves 2009-02-04
- 打赏
- 举报
[Quote=引用 46 楼 bbqqqbq 的回复:]
引用 22 楼 woxueliuyun 的回复:
12个球, 其中一个是次品, 一架标准天平, 称3次指出哪个是次品球, 重了还是轻了?
方法很简单：
第一次：两边个六个，留下轻的那边的六个。
第二次：两边个三个，留下轻的那边的三个。
第三次：任意放两个上去，如果天平平衡则说明次品没在天平上。如果天平不平衡，则说明次品在轻的一端。
按照以上方法完全可以判断出来哪一个是坏球。。。。
大伙是不是把简单的问题复杂化了
[/Quote]
第二次：两边个三个，天平平衡了，怎么回事？又该怎么办？
引用 22 楼 woxueliuyun 的回复:
12个球, 其中一个是次品, 一架标准天平, 称3次指出哪个是次品球, 重了还是轻了?
方法很简单：
第一次：两边个六个，留下轻的那边的六个。
第二次：两边个三个，留下轻的那边的三个。
第三次：任意放两个上去，如果天平平衡则说明次品没在天平上。如果天平不平衡，则说明次品在轻的一端。
按照以上方法完全可以判断出来哪一个是坏球。。。。
大伙是不是把简单的问题复杂化了
[/Quote]
第二次：两边个三个，天平平衡了，怎么回事？又该怎么办？
芽疼 2009-02-03
- 打赏
- 举报
看了题目，我晕了。大学数学没有学好，真后悔！
zhuweiping2003 2009-02-02
- 打赏
- 举报
哈哈 学习
kofkyo 2009-02-02
- 打赏
- 举报
学习
fxhhnhj 2009-02-02
- 打赏
- 举报
招聘启示
本公司是一家大型的信息专业网站，公司09年为了开拓全国业务需要，现急需招聘具备良好的团队合作精神，责任感强，善于沟通，能够承受压力的程序员3-5名，职位要求如下：
（一）Delphi程序员
1、三年以上Delphi开发经验，精通Delphi+SQL Server编程, 熟悉SQ LServer数据库；
2、从事过行业管理信息系统开发全过程，具有一定的软件工程思想；
3、有电子商务、国际货运代理、仓储、物流EDICRM软件开发经验优。
（二）C#程序员
1.二年以上C#软件研发工作经验；
2.有软件体系结构设计经验，有很强的C#编码技能；
3.精通XML、MSDTC、COM+/COM、Web Services和.net framework；
4.熟练掌握Oracle、SQL Server等大型数据库系统，熟悉数据库设计、调优及SQL存储过程的编写。
（三）网站设计程序员
1. 美术、计算机二年以上工作经验；
2. 熟悉SQL数据，精通ASP.NET编程进行后台的开发，有一定的编辑经验，能够独立完成项目方案的设计；
3. 精通网页设计和平面设计的相关软件，如Dreamweaver、Photoshop、Flash、Coredraw等 ；
4.文字功底好，有丰富的想象策划能力，能独立完成大型网站的建设需求/策划方案。
工作地点：河南 工作方式：全职
福利待遇：面议（不会低于你的期望值）
联系方式：冯先生 13603728111
本公司是一家大型的信息专业网站，公司09年为了开拓全国业务需要，现急需招聘具备良好的团队合作精神，责任感强，善于沟通，能够承受压力的程序员3-5名，职位要求如下：
（一）Delphi程序员
1、三年以上Delphi开发经验，精通Delphi+SQL Server编程, 熟悉SQ LServer数据库；
2、从事过行业管理信息系统开发全过程，具有一定的软件工程思想；
3、有电子商务、国际货运代理、仓储、物流EDICRM软件开发经验优。
（二）C#程序员
1.二年以上C#软件研发工作经验；
2.有软件体系结构设计经验，有很强的C#编码技能；
3.精通XML、MSDTC、COM+/COM、Web Services和.net framework；
4.熟练掌握Oracle、SQL Server等大型数据库系统，熟悉数据库设计、调优及SQL存储过程的编写。
（三）网站设计程序员
1. 美术、计算机二年以上工作经验；
2. 熟悉SQL数据，精通ASP.NET编程进行后台的开发，有一定的编辑经验，能够独立完成项目方案的设计；
3. 精通网页设计和平面设计的相关软件，如Dreamweaver、Photoshop、Flash、Coredraw等 ；
4.文字功底好，有丰富的想象策划能力，能独立完成大型网站的建设需求/策划方案。
工作地点：河南 工作方式：全职
福利待遇：面议（不会低于你的期望值）
联系方式：冯先生 13603728111
homejiji 2009-02-02
- 打赏
- 举报
在惊叹中学习！
zgb915 2009-02-02
- 打赏
- 举报
不错,学习
skykingwcg 2009-02-01
- 打赏
- 举报
mark
cyxin2121921 2009-02-01
- 打赏
- 举报
mark
学习！
学习！
sol0neu 2009-02-01
- 打赏
- 举报
看着算法我就头疼 是不是不适合做程序员啊
ljy_lhy2008 2009-01-31
- 打赏
- 举报
不错，相当好，支持先！
绿色夹克衫 2009-01-31
- 打赏
- 举报
过年比较忙，没啥时间想更多的，感觉用编码+构造，应该可以解这类问题，过两天写个程序试试。
再转贴一个天平的问题：
10个铜球形状相同，8个重量正常，1个轻，1个重，且1个轻+1个重=2个正常
现在要求用天枰找出特殊球
天枰每次只能判断轻重，无刻度记录
求最少称球次数
http://topic.csdn.net/u/20081201/00/5958e542-5ca3-4775-ade8-2eff5c26f114.html
再转贴一个天平的问题：
10个铜球形状相同，8个重量正常，1个轻，1个重，且1个轻+1个重=2个正常
现在要求用天枰找出特殊球
天枰每次只能判断轻重，无刻度记录
求最少称球次数
http://topic.csdn.net/u/20081201/00/5958e542-5ca3-4775-ade8-2eff5c26f114.html
项目花园范德彪 2009-01-30
- 打赏
- 举报
等着新算法重现
hero38074053 2009-01-30
- 打赏
- 举报
默默观望
DeGer2008 2009-01-30
- 打赏
- 举报
看着头都大了！！难啊！！
laomai 2009-01-29
- 打赏
- 举报
学习
加载更多回复（29）
