日志

更难，但“常识”还可以解决

热度 12已有 672 次阅读2014-2-26 00:54 | 计算机, 程序

有一个计算机随即生成0或1，两个数字出现的机会均等。在足够长的时间内所生成的序列里，出现011的频率和出现010的频率哪个大？

如果不用程序你能想到吗？或者，你能给出直观的解释吗？

回复 coo 2014-2-26 02:43: 010. 010 出现的机会多。因为数字的可重复性机会大.
任意取的连续3-4字节里，两者出现的频率应当没有差别. 但是五个字节010重复01010. 而011需六个字节011011. 拿连续六个字节来说，０１０可以出现两次的 010100, 010101, 010010, 101010, 001010; 011能出现两次的: 011011
010出现三次只要七个字节，而011需要九个字节

造成这个差异的本质是010是个对称的结构，头尾相同，而011是个非对称结构，头尾不同。所以在构成重复单元上，010具有更大的可能性在跟少的字节里重复。类似的差别有101，100

回复石头布 2014-2-26 02:55: 不一样大。010的出现频率比011的大。
每次出现010，向前移两位就可以继续采样。而011要前移3位。
010的“尝试次数”比较多。

回复仁 2014-2-26 05:03: 石头布: 不一样大。010的出现频率比011的大。
每次出现010，向前移两位就可以继续采样。而011要前移3位。
010的“尝试次数”比较多。 ...
我喜欢你这种想法，但是，你要不要考虑两者都出现了01而下一步都没有形成所需格式的情形？

回复仁 2014-2-26 05:04: coo: 010. 010 出现的机会多。因为数字的可重复性机会大.
任意取的连续3-4字节里，两者出现的频率应当没有差别. 但是五个字节010重复01010. 而011需六个字节011011. ...
请参看我对石头布的恢复。

回复仁 2014-2-26 05:06: 穿着裤衩裸奔: 一样大，相当于3个数里面出011和010的概率
我喜欢你的答案。请试着这样想：如果每个格0和1只能使用一次时会怎么样？这个是比较有趣的。

回复仁 2014-2-26 05:10: tanis: 一样~ 都是1／8
喜欢你的答案。如果0和1支能出现在一个所需的格式里的情况又怎样？也就是说相邻的两个格式不能共用同一个0或1。

回复 tanis 2014-2-26 05:16: 仁: 喜欢你的答案。如果0和1支能出现在一个所需的格式里的情况又怎样？也就是说相邻的两个格式不能共用同一个0或1。 ...
那就麻烦了。。。

回复 coo 2014-2-26 05:18: 仁: 请参看我对石头布的恢复。
一样大？因为第三个位置上的数出现的机会一样？回到了第一次的答案？

这个题目的另外一中叙述就是：010和011在随机产生的时候，谁的机会更大？
因为第三位０和１大机会对等，所以一样。

回复仁 2014-2-26 05:22: tanis: 那就麻烦了。。。
就是要引出这个思路。不然只要是等长的格式，出现的几率是不是都一样？

可以参看石头布和我对他的回复。

回复仁 2014-2-26 05:24: coo: 一样大？因为第三个位置上的数出现的机会一样？回到了第一次的答案？

这个题目的另外一中叙述就是：010和011在随机产生的时候，谁的机会更大？
因为第三位０和 ...
如果同一个0或1不可以被相邻的两个所需的格式共用，哪一个频率多？

回复 coo 2014-2-26 05:32: 仁: 如果同一个0或1不可以被相邻的两个所需的格式共用，哪一个频率多？
一样多把. sum M1=0, N-3 2^M1+M2, M1+M2+3=N

回复石头布 2014-2-26 05:41: 仁: 我喜欢你这种想法，但是，你要不要考虑两者都出现了01而下一步都没有形成所需格式的情形？
对不上的话就前移一位，继续对，两个都是一位一位向前滚动搜索。但是一旦对上了，010就前移两位继续搜，011则需前移三位，所以总的来说，010的搜素次数占优啊。

当然这是在一个数字可以被相邻片段共用的的情况下。

回复石头布 2014-2-26 06:02: 如果不能共用数字，那么011的频率大，因为它可以从相邻的其他类型片段里借用的机会多。比如在111里011可借两个数字，010则一个也借不到。几率大致是10对13的关系，如下表。

         010可借个数    011可借个数
000             1                   1
001             2                   2
010             3                   0
011             0                   3
101             2                   2
110             1                   2
100             1                   1
111             0                   2

合计          10                13

回复仁 2014-2-26 06:10: 石头布: 如果不能共用数字，那么011的频率大，因为它可以从其他类型片段里借用的机会多。比如在111里011可借两个数字，010则一个也借不到。几率大致是10对13的关系，如下 ...
对的。这个优势刚好抵消了可以共用情况下010的优势。在可以共用的情况下，他们应该是相同的。

回复石头布 2014-2-26 06:13: 仁: 对的。这个优势刚好抵消了可以共用情况下010的优势。在可以共用的情况下，他们应该是相同的。
哦。把两个因素综合起来考虑就复杂了，怎么知道他们刚好抵消呢？

回复仁 2014-2-26 06:16: 石头布: 对不上的话就前移一位，继续对，两个都是一位一位向前滚动搜索。但是一旦对上了，010就前移两位继续搜，011则需前移三位，所以总的来说，010的搜素次数占优啊。
...
当01出现时，加入形成了格式，010有优势-- 正如你说的。但是如果没有形成格式，011有优势，因为没有形成011就是形成010了吗。在这种情况下，最快需要两步形成011；但对010来说，如果没有形成需要的格式，那就成了011，在这个状态下，起码需要三步才能形成 011。

其实只要不形成010就会形成011，反之亦然。从这点上看，两者的频率应该是一样的。当然这是允许公用0或1 的时候。如果不允许公用0或1，上面说的011的优势依然存在，但010的优势没有了，所以011的频率高。

回复仁 2014-2-26 06:17: coo: 一样多把. sum M1=0, N-3 2^M1+M2, M1+M2+3=N
011的频率多，看我对石头布的回复。谢谢。

回复 coo 2014-2-26 06:22: 石头布: 如果不能共用数字，那么011的频率大，因为它可以从其他类型片段里借用的机会多。比如在111里011可借两个数字，010则一个也借不到。几率大致是10对13的关系，如下 ...
111 011可借个数 0

还要看前一位八

110 1 2
这个２也是CASE DEPENDENT的。看前面有什么, 0 可借

这里的可借也是条件可借，所以那个１０：１３不是个牢靠的比率关系。