31. 画树画出一个大数--TREE(3)漫谈

IT科技2017-12-11 08:37:35 1.8万
声音简介

大家好,上期我们讲了一个大数,叫葛立恒数。今天我们再接再厉,再讲一个超大数,叫TREE(3)。这里TREE就是英文里树木的那个单词TREE。TREE(3)其实就是一个函数,函数名称叫TREE,而函数自变量取值是3。


上期讲过,TREE(3)跟葛立恒数比的话,葛立恒数是属于忽略不计的。更为神奇的是,TREE(3)的定义比葛立恒数更简单,简单来说,它就是一个画“树”的游戏,树林的树。这里,这个“树”的概念,对计算机专业的听众来说再熟悉不过了,什么二叉树,查找树等等。如果你不是计算机专业的,也不要紧。你应该也看到过公司的组织架构图,或是某个人的家谱等等,也是用类似一棵树的结构展示的,这就是我们今天要谈的树的概念。我在节目介绍里也放了一个树的简单示意图。


TREE(3)游戏的开始的可能步数:

你可能关心TREE(3)这个有限的数到底有多大?不管你信不信,这其实是今天节目最难点了。上一期葛立恒数我用箭号表示法,大概还能说明下葛立恒数有多大,但是在TREE(3)面前,箭号表示法已经完全不管用了。但是我们还是可以参考下,上期我们说了葛立恒数可以用64重箭号表示法来表示,那TREE(3)如果要用多重箭号表示法表示,那需要的层数将远远大于葛立恒数。


(每周一题)

本周题目:保险箱大盗

safe_Box.png

你是个保险箱大盗,你想打开一个保险箱。这个保险箱有三个锁(称为1,2,3号锁),每个锁都独立工作。你已经得到了可以开锁的三把钥匙(称为A,B,C钥匙),但是你并不知道A,B,C对应哪把锁。

保险箱工作机制是这样的,箱子外有一个开锁按钮,当你按开锁按钮,每把锁会检查插入的钥匙。如果是插入的是正确的钥匙,且原先是锁定状态,这把锁就会打开;若原先是打开状态,这把锁就会关闭。如果插入是错误的钥匙,这把锁状态保持不变(不管之前是打开还是锁定状态)。只有三把锁状态都变成打开时,保险箱会自动开门。但只要有至少一个锁是关闭状态,整个保险箱维持关闭状态,而且你在任何时候都不知道某把锁是关闭还是打开的状态,你也不知道每次尝试开锁时,有几把锁发生了状态变化。

作为一个出色的的大盗,你想用最少的尝试次数打开保险箱,请问你最少要尝试多少次,才可以确保能够打开保险箱?

提示:保险箱初始状态也未知,可能有某几锁开始时已经处于打开状态。


上期答案:

上周题目是:

张三和李四分一块饼吃,两个人都饿坏了,想多分点。他们约定这种分饼方法:张三先切一刀,分成两片;李四从两片中任选一片切一刀,剩下三片;张三从三片中任选一片,再切一刀,剩下四片。

然后张三得到最大和最小的一片,李四得到中间大小的两片。问张三采取什么样的切法,可以得到最大比例的饼?这个比例是多少?

正确答案是张三可以到的3/5的饼。恭喜1106711411, Magician, 王森,今年不买表答对了! 完整过程是张三先切成1/5和4/5,李四切4/5,变成1/5, 2/5, 2/5。张三再切2/5,变成1/5, 1/5, 1/5和2/5。这样张三可得3/5。

简单证明如下:

设张三将饼切成s和1-s两部分,且s<1/2。接下来有四种情形:

对s<=1/5,李四切完变成s, (1-s)/2和(1-s)/2。张三再切,变成s, (1-s)/4,(1-s)/4和(1-s)/2四部分。张三可得s+(1-s)/2,在s=1/5时,取得最大值3/5。

对1/5<=s<=1/3。李四切完变成s, (1-s)/2和(1-s)/2。张三再切,变成(1-s)/4,(1-s)/4和(1-s)/2四部分。张三可得3(1 – s)/4。当s=1/5时,取得最大值3/5。

对1/3<=s<=3/7。李四切完变成s, (1-s)/2和(1-s)/2。张三再切,变成(1-s)/4,(1-s)/4和(1-s)/2四部分。张三可得(1 + 3s)/4。当s=3/7时,取得最大值4/7。

对3/7<=s<=1/2。李四切下一块e大小的饼,变成e, s和1-s-e,其中e是任意小。张三任意切一下s大小的块,最后得到e+1-s-e=1-s。当s=3/7时,取得最大值4/7。

综上所述,张三的最佳策略是可以得到3/5大小的饼。下期再见!

收听“大老李聊数学”音频                                        关注“大老李聊数学”



用户评论(25)
展示条数:
20条
  • 20条
  • 50条
  • 100条

表情0/300
jesuispig

jesuispig

有趣 听了好几遍

陈秀君_m1

陈秀君_m1

最喜欢大数了主播加油,套娃

豆芽在线

豆芽在线

tree(tree3)有多大?

春天的池塘_wz

春天的池塘_wz

订个小目标,先赚它一个tree3

希格斯玻色子Higgs

希格斯玻色子Higgs

可以用葛立恒数作底数来表示TREE(3)吗?

大老李聊数学

大老李聊数学 回复 @希格斯玻色子Higgs

没有用,葛立恒数的葛立恒数次方也远小于TREE(3)。

miffy_2008

miffy_2008

TREE(4)

miffy_2008

miffy_2008

我是小码农

醉萌_

醉萌_

A,B,C. A,C,B, B,A,C, B,C,A ,C,A,B, C,B,A

1358199dccg

1358199dccg

节目资料在哪找的,规则听不懂

Private_00

Private_00

算的出来 也无法写下来

王平_bv

王平_bv

难道不是0.6125?张三先对半切,每片0.5,李四平分一片之后变成0.5、0.25和0.25,最后张三再把0.25切成两个0.125,张三拿最大的0.5和最小的0.125,一共0.6125。

醉萌_

醉萌_ 回复 @王平_bv

回复@Webcraft大老李:是不是,6种,最多18次

冉冉RAY

冉冉RAY

三生万物的感觉

听友61457665

听友61457665

用一把钥匙逐一尝试三次,可以翻转一把锁的状态。而保险箱共有八种状态,需要转换翻转7次,对应尝试21次。外加初始状态尝试一次,最多尝试22次即可开锁。。。这个不知道是不是最优解。。

大老李聊数学

大老李聊数学 回复 @听友61457665

嗯,很多人都给出了类似答案,但还不是最优!

醉萌_

醉萌_ 回复 @听友61457665

回复@1106711411:18次, ABC ACB BAC BCA CAB CBA

空谷低飞

空谷低飞

听不懂,但很喜欢

5_dtwgb0

5_dtwgb0 回复 @空谷低飞

不丢人,我每一集都听不懂

1811021fhur

1811021fhur

这集实在听不懂

大老李聊数学

大老李聊数学 回复 @1811021fhur

额,太难了吗,我哪里没说清楚?

1811021fhur

1811021fhur 回复 @1811021fhur

太难了,不过每集都听。感觉只有你关注的那个新青年可以与你的节目争锋

听书、听课、听段子 6亿用户的选择!
下载客户端