NO.01
认证: 论文检测

掌柜:论文查重第一家

点击这里给我发消息

支付宝个人认证

2011-03-24

消费者保障协议

该店铺已签署消费者保障协议
已缴纳1000元保证金

店铺动态评分

描述相符5.0

服务态度5.0

物流服务5.0

与同行业相比

高于1.23%

持平0.45%

高于4.31%

开店时长5年老店

一道更难的智力题目

题目如果是, 称出,并告知是重是轻,则 times=[ ln(2*n+3) / ln3 ] 如果不需要告知是重是轻,则为 times=[ ln(2*n+1) / ln3 ] 试题一: 有12个球,其中有一个坏球,但不知道是轻是重。试用天平称三次,找出坏球,并 说出它 是轻是重。 试题二: 称n次,最多可以在多少个球中找出坏球来。(坏球只有一个) 对于天平问题,我们通常都可以把它和3相联系,这是因为对于每一次称物,都可 以分 为三堆,天平上两堆,再加上未放上去的一堆;这样无论天平是否平衡,我们都可 以得 到一些信息,并且信息不浪费。具体先看试题一的解答: 12个球,分别编号1,2,……,11,12。 1、 1,2,3,4 对 5,6,7,8 (一) < 转6 ; > 转10 (类似 <) ;=转2 ; 2、 9,10 对 11,1 (二) < 转 5 ; > 转 4 ; =转3 3、 1 对 12 (三) < 坏球为12 ,重;> 坏球为12 , 轻 ;不可能=。 转999; 4、 9 对 10 (三) < 坏球为9 , 轻;> 坏球为10 , 轻 ;= 坏球为11 重。 转999; 5、 9 对 10 (三) < 坏球为10 , 重;> 坏球为9 , 重 ;= 坏球为 11 轻; 转999; 6、 1 , 2 , 5 对 3,4,6 (二) < 转9 ;> 转 8 ;= 转 7 7、 1 对 7 (三) < 坏球为7 , 重 ;< 坏球为8 , 重 ;= 不可能 8、 3 对 4 (三) < 坏球为 3 ,轻 ;< 坏球为 4 , 重 ;= 坏球 5 ,重 9、 1 对 2 (三) < 坏球为 1 ,轻 ;< 坏球为 2 , 重 ;= 坏球 6 ,重 10、 类似于6—9 999、 结束。 通过对第一题的思索解答,我们可以发现一些规律:对于称n次,若我们能把称 n-1次的 问题解决,n次就可以用递推来求出球的个数。(对于我们要解决的这个问题,用 f(n)表 示。) 但是,也不是单纯简单的递推。因为我们在称第一次的时候,得到了一些信息, 这些信 息可以给我们后面的称球带来帮助。 我们来分析第一次称的三堆球: (一)若不平衡,我们得到的信息是: 1. 坏球在天边上的两堆里; 2. 有一堆的球重,一堆轻。 大家往往会忽视第二条信息,实际上这条信息是非常重要的。若我们知道一些球的 轻重 关系,我们可以用比不知道这个关系称的次数更少就得出结论。如:若告诉你坏球 轻, 那么27个球只要三次就够了。 所以我们要研究一下,若我们知道一些球的轻重关系,n次最多可以称出多少个球 。我们 用函数h(n)表示。 (二)若平衡,则得到的信息是: 1. 坏球在剩下的一堆中; 2. 有若干个好球可以给我们利用。 第二条信息又是大家容易忽视的。就如12个球,称第一次若平衡,我们就可以用天 平上 的球作为标准球。有标准球,两次可以称称出4个球(见第一试题解答部分的2—5 );若 没有的话,就只能称出3个球。 所以我们还要研究一下,若我们有一个标准球,n次最多可以称出多少个球。我们 用函数 g(n)表示。 定义一:若一个球,若知道它不可能偏重(或知道不可能偏轻),则我们称此球为 半确 定重球(或半确定轻球);半确定重球和半确定轻球统称为半确定球。 第一题中,通过第一次称重后,若不平衡,则1,2,3,4,5,6,7,8号球都成为半确定 球, 若1,2,3,4〈5,6,7,8,则1,2,3,4为半确定轻球,5,6,7,8为半确定重球。 定义二:若一个球,若知道它是好球,则我们称此球为确定好球;若知道是坏球, 确定 坏球。确定好球和确定好球统称为确定球。 第一题中,通过第一次称重后,若平衡,则1,2,3,4,5,6,7,8号球都成为确定球好 球。 定义三:若一个球,既不是确定球,也不是半确定球若,则我们称此球为不确定球 。 第一题中,通过第一次称重后,则9,10,11,12号球都成为不确定球。 一次未称之前,所有球都是不确定球。 引理一、对于放上过天平的球,都是半确定球或是确定球 这是个显然成立的命题。 定义四:若所有球都是半确定球,那么n次可称出的球的最大个数我们用 h(n)表示 。 引理二:h(n)=3^n。 证明: 用归纳法来证: ⑴对于n=1,先证3个球是可称的,再证4个是不可称的。 ① 3个球可称, 若全为半确定重球,任意挑两个,若不平衡,重的就是坏重球;否则,剩下的那个 就是 坏重球; 全为半确定轻球同理; 若两个半确定重球,一个半确定轻球,则称两个两半确定重球,若不平衡,重的就 是确 定重球;否则,剩下的那个就是确定轻球; 若一个半确定重球,两个半确定轻球同理。 所以,3个求可称。 ②四个球不可称 若是4个球,天平称一次,只能提供三条信息,由抽屉原理,必然有两个球的信息 是相同 的。故一次无法保证能判断出来。 故,n=1是h(n)=3^n是成立的。 ⑵设n=k时命题成立,对于n=k+1 ①先证t=3^(k+1)个球是可判断的: 设t中有a个半确定重球,b个半确定轻球,t=a + b ; 由对称性,不妨设a>b (a + b是奇数,所以不可能相等) 按如下方法分为三堆: 若a>=2*(3^k),则天平两边各放3^k个半确定重球。若不平衡,坏球在重的那堆中 ;平衡 的话,坏球在剩下的那堆中。这时剩3^k个球,k次可判断出来,共k+1次,成立。 若a<2*(3^k), 则天平两边各放[a/2]个半确定重球,3^k-[a/2]个半确定轻球。若 不平衡 ,坏球在重的那堆中的半确定重球或轻的那堆半确定轻球中;平衡的话,坏球在剩 下的 那堆中。这时剩3^k个球,k次可判断出来,共k+1次,成立。 a < b 同理可证。 所以3^(k+1)个球是可判断的。 ②若3^(k+1)+1个球,称一次,只能提供三条信息,由抽屉原理,必然有3^k+1个球 的信 息是相同的,这3^k+1个球无法用k次称出。故k+1次无法保证能判断出来。 故,n=k+1也成立。 由归纳法,h(n)=3^n对一切自然数都成立。 再回到原题,来求f(n). 对于第一次处理后,若不平衡,天平两边的球都将成为半确定球。设两边球个数各 为a个 ,另外一堆个数为b个。易知,a与b相互独立。为使得f(n)=2a+b最大,即要分别求 出a , b的最大值。 由引理二,这2a个半确定球要在n-1次判断出,当且仅当 2a <=h (n-1)=3^(n-1). 但等号无法取到,因为3^(n-1)为奇数,所以2a<=3(n-1)-1, max(a)=(3^(n-1)-1)/2 f(n)=(3^(n-1)-1)+max(b) 定义四、给一个确定好球,n次能称的最多非确定球的个数用g(n)表示。 引理三:g(n)=f(n)+1 若有任意确定好球的话,g(n)比f(n)可提高效率的地方就在于第一次称的时候可以 两边 放的非确定球的个数不一样多。一边放c个不确定球,一边放a个不确定球和c-a个 确定好 球,剩下一堆为b个。平衡的话,b个球的处理同f(n),所以此时的max(b)显然等于 f(n)的 max(b)。若不平衡的话,就有a + c个不确定球。 a + c <=3 ^ ( n – 1 ) (等号可取) 令c=a+1=(3^(n-1)+1)/2,则此时只需要一个确定好球, g(n)=max(a + c)+max(b)=3^(n-1)+max(b)=f(n)+1 # 再来研究max(b).若不平衡,则b个球全为确定好球,否则,全为非确定球。但天平上 的球 全为确定好球。这时的b就恰好同我们刚刚讨论的g(n). 即有 max(b)=g(n-1)=f(n-1)+1. 故有f(n)=3^(n-1)-1+f(n-1)+1=f(n-1)+3^(n-1) 这是一个递推公式。 我们又易知,f(2)=3 ,所以易解得 f (n)=(3^n-3) / 2 故,称n次,最多可以在(3^n-3) / 2个球中找出坏球来。(坏球只有一个) 当n=3时,即第一题,f(3)=12. 3次能称得的最大数目将是12个。 论文抄袭检测致力于提供免费毕业论文抄袭检测服务

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

论文查重:

论文检测,论文查重第一家,是一家以检测抄袭与剽窃、伪造、篡改、不当署名、一稿多投等学术不端文献的论文检测平台,目前主要推荐的知名、权威检测产品包括中国知网的AMLC系统、VIP、TMLC2系统,万方数据库的万方相似比检测系统,维普文检测系统、gaperpass检测系统,等等常见检测软件

推荐软件知网期刊检测AMLC 知网本科检测 知网硕博检测 万方论文相似比检测 维普论文检测

检测须知:

1.此系统一旦提交,开始检测后,概不退款!2.在淘宝中购买宝贝后,可以在“我已购买宝贝”中看到有“订单编号”,知网系统检测需要输入订单编号才能使用。3.Word文档大小请不要超过15MB ,否则将无法上传;请把不必要的图片删除即可(系统不检测图片);4.上传检测的文档格式为Word的docx,doc格式,请勿上传其他格式的文档。

检测入口返回顶部
知网期刊检测
知网本科检测
知网硕博检测
万方论文检测
维普论文检测
paperpass
返回顶部