注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

海河入海口的窝

本博帖中所有照片视频等内容未经许可不得转发或用于商业用途,谢谢

 
 
 

日志

 
 

一道看似非常简单的数学题  

2010-04-06 21:19:02|  分类: 计算机 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一个非常简单的数学题,不过做出来了就是天才
于 2010-04-06 13:20 
题目:有12个球,外观一样,有一个跟其他11个质量不同,但无法指导质量是大还是小,现规定用天平称,称的次数不能超过3次,如何才能把这个质量不同的球称出来,且要称出是重还是轻。
注:天平只能判断重量的大还是小,无法具体称出重量是多少?
背景知识:高中学习代数时对参数范围的分类讨论,要具备严密的逻辑思维和分类讨论思想,也许这个题对计科的人来说非常简单。
那么你能在1个小时内做出来么。

于 2010-04-06 14:20 
几年前做过。没那么复杂,是个三叉树。
把球编号1,2,3,4,5,6,7,8,9,A,B,C
三个一组,分成4组:1-3,4-6,7-9,A-C
第一次,天平称1-3和4-6,有如下结果:
  如果<,那么7-9和A-C可以排除,不用称了。
第二次,比较1-2和3-4
  如果<,那么排除5、6
第三次,比较1和2
  如果<,排除3、4,并可以确定是1轻。
这是第一条路径,可以根据这三次比较的结果确定是1轻。
第一次比较可以推断出7-9=A-C,
第二次可以推断5=6=7=...=C,
第三次可以推断3=4=5=6=7=...=C,并且2不重
 
原创:12球称重不合格解法
 
题目:有12个球,外观一样,有一个跟其他11个质量不同,但无法指导质量是大还是小,现规定用天平称,称的次数不能超过3次,如何才能把这个质量不同的球称出来,且要称出是重还是轻。
注:天平只能判断重量的大还是小,无法具体称出重量是多少?

思路:无序数列中查找一个特定值,最简单快速的方法应该是折半,所以根据每次排除一半分组,因为特殊球比普通球重还是轻不清楚,所以分成四组,一次称重可以排除一半。
解法:用小学数学不等式+逻辑判断。
先给12个球编号:1,2,3,4,5,6,7,8,9,A,B,C
再给特殊球编号:X
分成4组,三个一组,分别命名为Z1、Z2、Z3、Z4:Z1=1+2+3, Z2=4+5+6, Z3=7+8+9, Z4=A+B+C
1. 第一种比较可能结果的排列
  先任取两组比较
  1.1  a:  Z1<Z2 , 可知,b:X在Z1和Z2中
  再在可疑球中取一半,与已知普通球比较
  1.2  a:Z1<三个普通球,可知,b:X在1、2、3中,c:X比普通球轻
    Z1 = 1+2+3 = X + 两个普通球
    由1.2 a式,两侧各减去两个普通球,可得:X < 一个普通球。
  最后在可疑球中取两个比较
  1.3  a:1<2
  因为1、2中有一个普通球,而且X<普通球,所以1是X,X比普通球轻。
 
2.第二种可能
  2.1  a:  Z1<Z2
  2.2  a:Z1<三个普通球
  2.3  a:1=2,可知1、2是正常球,3是X,X比普通球轻。
3.第三种
  3.1  a:  Z1<Z2
  3.2  a:Z1<三个普通球
  3.3  a:1>2,可知2是X,X比普通球轻。
4.
  4.1  a:  Z1<Z2
  4.2  a:Z1=三个普通球,可知,b:X在4、5、6中,c:X比普通球重
  4.3  a:4<5,可知5是X,X比普通球重。
5.
  5.1  a:  Z1<Z2
  5.2  a:Z1=三个普通球
  5.3  a:4=5,可知6是X,X比普通球重。
6.
  6.1  a:  Z1<Z2
  6.2  a:Z1=三个普通球
  6.3  a:4>5,可知4是X,X比普通球重。
7.
  7.1  a:  Z1<Z2
  7.2  a:Z1>三个普通球,可知,b:X在1、2、3中,c:X比普通球重
  矛盾,因此这种可能不存在。
8.
  8.1  a:  Z1=Z2,可知,b:X在Z3、Z4中
  8.2  a:Z3<三个普通球,可知,b:X在7、8、9中,c:X比普通球轻
  8.3  a:7<8,可知7是X,X比普通球轻。
9.
  9.1  a:  Z1=Z2
  9.2  a:Z3<三个普通球
  9.3  a:7=8,可知9是X,X比普通球轻。
10.
  10.1  a:  Z1=Z2
  10.2  a:Z3<三个普通球
  10.3  a:7>8,可知8是X,X比普通球轻。
11.
  11.1  a:  Z1=Z2
  11.2  a:Z3=三个普通球,可知,b:X在10、11、12中,c:X轻重未知。这个情况未考虑好,需多称一次
  11.3  a:Z4<三个普通球
  11.4  a:10<11,可知10是X,X比普通球轻。
12.
  12.1  a:  Z1=Z2
  12.2  a:Z3=三个普通球,可知,b:X在10、11、12中,c:X轻重未知。这个情况未考虑好,需多称一次
  12.3  a:Z4<三个普通球
  12.4  a:10=11,可知12是X,X比普通球轻。
13.
  13.1  a:  Z1=Z2
  13.2  a:Z3=三个普通球,可知,b:X在10、11、12中,c:X轻重未知。这个情况未考虑好,需多称一次
  13.3  a:Z4<三个普通球
  13.4  a:10>11,可知11是X,X比普通球轻。
14.
  14.1  a:  Z1=Z2
  14.2  a:Z3=三个普通球
  14.3  a:Z4=三个普通球
  与题目矛盾,不可能出现
15.
  15.1  a:  Z1=Z2
  15.2  a:Z3=三个普通球,可知,b:X在10、11、12中,c:X轻重未知。这个情况未考虑好,需多称一次
  15.3  a:Z4>三个普通球
  15.4  a:10<11,可知11是X,X比普通球重。
16.
  16.1  a:  Z1=Z2
  16.2  a:Z3=三个普通球,可知,b:X在10、11、12中,c:X轻重未知。这个情况未考虑好,需多称一次
  16.3  a:Z4>三个普通球
  16.4  a:10=11,可知12是X,X比普通球重。
17.
  15.1  a:  Z1=Z2
  15.2  a:Z3=三个普通球,可知,b:X在10、11、12中,c:X轻重未知。这个情况未考虑好,需多称一次
  15.3  a:Z4>三个普通球
  15.4  a:10>11,可知10是X,X比普通球重。
18.
  18.1  a:  Z1=Z2
  18.2  a:Z3>三个普通球,可知,b:X在7、8、9中,c:X比普通球重。
  18.3  a:7<8,可知8是X,X比普通球重。
19.
  19.1  a:  Z1=Z2
  19.2  a:Z3>三个普通球
  19.3  a:7=8,可知9是X,X比普通球重。
20.
  20.1  a:  Z1=Z2
  20.2  a:Z3>三个普通球
  20.3  a:7>8,可知7是X,X比普通球重。
21.
  21.1  a:  Z1>Z2
  21.2  a:Z1<三个普通球,矛盾,不存在
22.
  22.1  a:  Z1>Z2
  22.2  a:Z1=三个普通球,可知,b:X在4、5、6中,c:X比普通球轻
  22.3  a:4<5,可知4是X,X比普通球轻。
23.
  23.1  a:  Z1>Z2
  23.2  a:Z1=三个普通球
  23.3  a:4=5,可知6是X,X比普通球轻。
24.
  24.1  a:  Z1>Z2
  24.2  a:Z1=三个普通球
  24.3  a:4>5,可知5是X,X比普通球轻。
25.
  25.1  a:  Z1>Z2
  25.2  a:Z1>三个普通球,可知,b:X在1、2、3中,c:X比普通球重
  25.3  a:1<2,可知2是X,X比普通球重。
26.
  26.1  a:  Z1>Z2
  26.2  a:Z1>三个普通球
  26.3  a:1=2,可知3是X,X比普通球重。
27.
  27.1  a:  Z1>Z2
  27.2  a:Z1>三个普通球
  27.3  a:1>2,可知1是X,X比普通球重。

费劲写半天,到一半发现有问题,再一搜索发现网上说有10多种解法,没一种是分四组的,分四组的只能确定特殊球,不能确定轻重。基本上解法没有小学数学+逻辑判断的。
我觉着,解决实际应用问题,还是应该尽量用最简单最基本的方法,容易理解和实现。
虽然不符合解题要求,我还是觉着这种解法容易理解,就当抛砖吧,反正咱脸皮厚。
应用为王,研究是为了用,即使这种解法在比较次数上有欠缺,但是相对是比较简单并且容易实现的。
在实际应用中,Oracle数据库索引即使用类似的B-Tree查找,效率应该没几个说比Oracle用法还高的了。
忽略了一点,数据库中搜索数据,比较时两个相等数据多数情况下可以认为是一个的
本来cpu就只认识二进制加法,理由也只是为了容易实现、降低成本,所有一切都要用最简单的功能解决一切。
用简单方法和逻辑来解决应该是最实用的。
  评论这张
 
阅读(122)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017