魔方吧·中文魔方俱乐部

标题: 【非专业提问】香农的理论，对求解“上帝之数”或者“最小步程序”有用吗？ [打印本页]

作者: lamianbu 时间: 2010-8-26 22:31:27 标题: 【非专业提问】香农的理论，对求解“上帝之数”或者“最小步程序”有用吗？

题目：12个球，有一个坏球（重量和其它球不同，但不知偏重还是偏轻），天平来秤。最少秤几次可以找到坏球？

香农的信息理论，可以告诉我们log（12）/ log(3) = 2.xx次可以解决问题。但是，香农理论不能告诉我们解决方案。

香农理论的解法过程很简单：我们求解的信息量=log（12）. 天平的一次称重的信息量=log(3) ,因为有左重，右重，平衡三种。相除得到最少需要秤几次。

==========================================================================================

猜想1：香农的理论，能否直接以算术式，直接求解出上帝之数是19.xx，所以最少需要20步完成。

猜想2：香农理论，对最小步解法程序有帮助，解法分为几个步骤，每个步骤解决多少信息量的问题，知道了这个极限，对每个步骤进行优化。

==========================================================================================

香农理论，不是我上面例题那么简单，那只是个信息量公式的简单计算。

我是学通信的，本科和研究生都学过信息论，香农这个人，对通信理论贡献极大。

最典型的应用是，可以计算在一定带宽，和信噪比的信道上，传输信息的极限。（和极限作对比，我们对通信的优化就有了方向）

香农的理论博大精深，是个数学奇才。领先时代几十年。（本科同学一般都不知道，计算极限的公式怎么来的，书上没写推导过程。我是到北京听了清华老师的讲课才知道的。）

已经工作了，不再研究这些了。

[ 本帖最后由 lamianbu 于 2010-8-26 22:34 编辑 ]

作者: kattokid 时间: 2010-8-26 23:22:13

香农啊…好像很NB的样子，抱歉，我孤陋寡闻了

作者: 553975689 时间: 2010-8-26 23:35:08

拉面，也是个不简单的人啊。可以去清华听课。。

作者: wwd_meng 时间: 2010-8-27 01:42:33

好像MF8有不少北大清华的学子，我是望尘莫及啊…还有拉面的说法弄得我好晕

作者: wwd_meng 时间: 2010-8-27 01:46:35

突然有点明白了，所以在公布上帝之数时还列出了魔方所有状态，有几M亿，M代表千还是万忘记了，然后再运用公式就出来了，真是变态厉害

作者: versionxp 时间: 2010-8-27 14:56:43

这是我对12球问题又有了新的认识！我只听说过香农模型，是在上图书馆学概论时了解到的。
没想到香农理论居然这么的神奇啊！香农理论解决12球问题是不是一种巧合呢，那么如果不止12球的话，类似的问题是否验证过这种解法是适用的呢？

作者: Cielo 时间: 2010-8-27 22:31:14

原来拉面在北京了啊！

作者: 小明的马甲 时间: 2010-8-28 00:09:22

其实吧。。信息量和决策树可以看成同一件事情。。。

作者: versionxp 时间: 2010-8-28 10:06:48

刚才计算了下，不仅是12球，就连13,14,15,16其计算结果都是2.xx,这是怎么回事啊，难道这些称3次也能解决吗？

作者: lamianbu 时间: 2010-8-29 23:46:57

原帖由 versionxp 于 2010-8-27 14:56 发表这是我对12球问题又有了新的认识！我只听说过香农模型，是在上图书馆学概论时了解到的。没想到香农理论居然这么的神奇啊！香农理论解决12球问题是不是一种巧合呢，那么如果不止12球的话，类似的问题是否验证过这种 ...

不是巧合，虽然平时香农的理论不是这么用的。第一次在课后题里，看到可以解决12球问题，那时我都惊了。

不止12球，同样适用，只是香农会告诉你，需要几次。

但是，却不会告诉你怎样秤。

作者: rubik-fan 时间: 2010-8-30 18:25:51

到底是最少称几次，还是最多称几次啊？
三个球，其中一个是坏球。答案应该是称几次啊。

是1次还是2次啊？？

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)