作者LPH66 (-858993460)
看板puzzle
标题[中译] ProjectEuler 367 bozo sort
时间Sun Jan 15 06:50:57 2012
367. bozo sort
http://projecteuler.net/problem=367
所谓的 bozo sort（不要把它和效率稍微差一点的 bogo sort 搞混），
是一个排序演算法，当序列不是已排好时就随机交换两个元素，直到排好为止。
若考虑前四个自然数的 4! 种排列，各自计算其期望排序完成的交换次数再加以平均，
这个平均次数是 24.75 次。
已排好的那一串视为需要 0 次交换。
这个题目里考虑一个 bozo sort 的变种：
当序列不是已排好时，随机选出三个元素并随机打乱它们直到排好为止。
打乱三个元素的 3! = 6 种可能是均匀随机出现的。
同样的已排好的那一串视为需要 0 次操作。
对前四个自然数的 4! 种排列各自计算期望完成的次数後加以平均，
这个平均次数是 27.5 次。
若对前 11 个自然数的 11! 种排列进行相同的计算，问这个平均次数是多少？
答案四舍五入至整数。
--
补充：题目中说的那个「效率稍微差一点」的 bogo sort 和 bozo sort 只差在一点
当序列是没排好时是全部洗牌而不仅是交换随机两个元素
这题看起来好像有机关在里面的样子 = =+
--
有人喜欢边
玩游戏边
上逼；
也有人喜欢边
听歌边
打字。
但是，我有个请求，
选字的时候请
专心好吗？
-- 改编自「古 火田 任三郎」之开场白
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.230.62
※ 编辑: LPH66 来自: 140.112.230.62 (01/15 06:51)
1F：推 utomaya:我猜是马可夫链的问题 应该不难写, 可是, 目前才一人解出? 01/15 07:17
2F：→ LPH66:我是也有想到这个方向 不过 11 个数需要 56 个状态... 01/15 07:48
3F：推 utomaya:想来想去 好像也只有马可夫链可以解 01/15 07:58
4F：→ LPH66:暴力法万岁...感谢 Mathematica 的 Combinatorica` package 01/15 08:35
5F：推 utomaya:第7! L大好强! 01/15 08:37