魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
楼主: yang_bigarm

监狱长给犯人们出的难题 [复制链接]

银魔

宇宙起源

Rank: 7Rank: 7Rank: 7

积分
3197
帖子
1034
精华
12
UID
564
性别

魔方理论探索者 魔方破解专家 论坛建设奖 六年元老

发表于 2009-8-8 00:03:05 |显示全部楼层

回复 20# 的帖子

你算的是四个人没有任何约定,每个人都随机的去选的吗?每个人选中的概率是1/2没有异议,那么为什么模拟结果不是1/16呢?
我怀疑是不是计算机中的随机数发生器有规律可循的缘故?
The Answer to the Ultimate Question of Life, the Universe, and Everything 

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 2009-8-8 12:20:21 |显示全部楼层
对于21楼的质疑,我仔细考虑一下,觉得没理由不是独立事件,得到的概率应该等于1/16。
问题出在哪里?又重新运行多次,得到的概率分别是7.5%、11.2%。波动还挺大的,按理说1千万次的模拟,概率波动不应这么大?真的应该像Noski所说的随机序列生成器出了问题。
每个人随机选号码箱的号码组合,我设计了一个子程序,每运行一下子程序,就随机生成一个号码组合。
这个子程序是,先初始化随机序列生成器(以免每次生成相同的随机数序列),再运用随机函数,随机生成号码组合。
按理说这个子程序设计应该没问题,但后来证实恰恰是这个子程序出了问题。问题在 初始化随机序列生成器。
因为每个人随机设定他选择的号码组合,都要调用一次那个子程序,而每调用一下子程序,就初始化一次随机序列生成器。
最后造成每个随机数序列都不是完整的,每每被中断。
--------------------------------------------------------------------------
最后删除子程序中的初始化随机序列生成器的语句,将初始化随机序列生成器语句直接放在主程序调用随机函数之前。
重新运行程序,
    1百万次,成功62640次
    1千万次,成功624466次。概率非常接近 1/16=0.625

使用道具 举报

银魔

宇宙起源

Rank: 7Rank: 7Rank: 7

积分
3197
帖子
1034
精华
12
UID
564
性别

魔方理论探索者 魔方破解专家 论坛建设奖 六年元老

发表于 2009-8-8 12:27:59 |显示全部楼层

回复 22# 的帖子

赞!看来一个程序里只要将随机数生成器初始化一次就够了,这可真是一个隐蔽的BUG。。
The Answer to the Ultimate Question of Life, the Universe, and Everything 

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 2009-8-8 12:33:19 |显示全部楼层
计算p(4),但如果这三个人约定好,1选1和2,2选2和3,3选3和4,4选4和1,那么这时P(4)就等于1/12?
---------------------------------
电脑模拟:1百万次,成功83375次,非常接近1/12。
P(4)中最大的概率是不是1/12,还有其他方案更佳么?
推广到P(m),概率最大的方案到底如何呢?    P(m)采用noski定义

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 2009-8-8 14:13:34 |显示全部楼层
p(4),方案:1选1、2,2选1、2,3选3、4,4选3、4,
    模拟1百万次,成功167006次,概率接近于1/6。
所以P(4)的最大值不小于1/6。

使用道具 举报

Rank: 1

积分
37
帖子
33
精华
0
UID
72750
性别
保密
发表于 2009-8-8 14:26:14 |显示全部楼层
每次都恢复原样,和独立操作有什么区别啊。他们商量个屁啊。

使用道具 举报

银魔

宇宙起源

Rank: 7Rank: 7Rank: 7

积分
3197
帖子
1034
精华
12
UID
564
性别

魔方理论探索者 魔方破解专家 论坛建设奖 六年元老

发表于 2009-8-8 14:42:44 |显示全部楼层

回复 25# 的帖子

这个方法比我那个有效,那么来猜测一下:
m为偶数的时候,约定前一半人选前一半的数字,后一半人选后一半的数字,那么概率:
P(m) = (m/2)! * (m/2)! / m!
验证一下:P(2) = 1/2,P(4)=1/6,P(6) = 1/20 ……
The Answer to the Ultimate Question of Life, the Universe, and Everything 

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 2009-8-8 14:51:53 |显示全部楼层
p(6),方案:第1、2、3个人选1、2、3号码,第4、5、6个人选4、5、6号码,
    模拟1百万次,成功50044次,概率接近于1/20。
比其他方案概率好像都大。
----------------------------------------------
所以我的感觉对于P(m),最佳方案是:将m个箱子随便平分成两组,一半的人都选这一组号码,另一半人都选另一组号码。这样的方案全部成功的概率最大。最大概率等于1/ C(m,m/2) 。        C(m,2/m)是组合数。
这样P(2)=1/C(2,1)=1/2
       P(4)=1/C(4,2)=1/6
      P(6)=1/C(6,3)=1/20
对于楼主的m=100
   最大概率=1/C(100,50)≈1/10^29
---------------------------------------------------
不知我的感觉对不对。

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 2009-8-8 14:53:08 |显示全部楼层
哈哈,楼上的观点和我想法一样阿,不知能不能证明。

使用道具 举报

Rank: 2

积分
506
帖子
483
精华
0
UID
68301
性别
保密
发表于 2009-8-8 15:17:55 |显示全部楼层
不知道能不能改变 箱子的位置..改变了会被 监狱长复原吗?

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2019-1-19 04:25

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部