※ 引述《utomaya (乌托马雅)》之铭言： http://projecteuler.net/index.php?section=problems&id=280 刚刚模拟了简化3x3的情形，有一个很特别的发现。有可能是这题的关键!! ┌─┬─┬─┐ │ａ│ｂ│ｃ│　想法是，既然iso大都提到马可夫了就来测试一下一些走法步数的期望值 ├─┼─┼─┤ │ｄ│ｅ│ｆ│ 程式是简单的D(0)→D(k)的动态规划，例如说求a到h的期望值就令初始 ├─┼─┼─┤ │ｇ│ｈ│ｉ│ 值a=1其余0，b=a/2+e/4+c/2...etc. 每步走到目标h的机率乘上目前k └─┴─┴─┘ (表示这是第k步)，加到Exp，然後把h归零(到达目标就不用再走)。 然後，我的电脑告诉我，这些步数的期望值都是整数?! 大概是我数学的直感真的虚弱吧，总觉得这是很出人意表的结果~~~ a→g exp=>15 b→h exp=>12 a→h exp=>12 b→g exp=>17 a→i exp=>18 因此我猜，这题的答案根本是个整数XD 待我检查一下，如果5x5的每种状况结果也都是 整数...... --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.243.60 Naively, 把所有可能状态都列出来是动态规划的精髓(worst-time 就确定了) 引用utomaya大的原文 ０００００　到　１１１１１　　我想这样表示状态: (3,3) Ant 位置 ０００００　　　０００００ 0 0或1 有无搬运种子 ００╳００　　　００╳００ 11111 上排 ０００００　　　０００００ 11111 下排 １１１１１　　　０００００ 乍看似乎有 5 x 5 x 2 x 32 x 32 = 51200种 电脑有这麽大记忆空间做51200阶方阵的 马可夫过程吗? 不行XD 但先说其实种子的位置只有 Ant状态为"没有搬" : 1+ 5^2 +10^2 +10^2 +5^2 +1 = 252 Ant状态为"搬运中" : 5x1 + 10x5 + 10x10 + 5x10 + 1x5 = 210 一共462种 ａｂｃ ｄｅｆ ｇｈｉ 回到九宫格，我用http://www.uni-bonn.de/~manfear/matrixcalc.php 这个线上 Matrix calculator "手动"算过了 从b到h的期望值不折不扣是12整，当我要呆呆继续算 其他的期望值时......要上课了= = A= 0 1/3 0 1/3 0 0 0 0 0 a 1/2 0 1/2 0 1/4 0 0 0 0 b 0 1/3 0 0 0 1/3 0 0 0 c 1/2 0 0 0 1/4 0 1/2 0 0 d 0 1/3 0 1/3 0 1/3 0 1/3 0 e 0 0 1/2 0 1/4 0 0 0 1/2 f 0 0 0 1/3 0 0 0 1/3 0 g 0 0 0 0 1/4 0 1/2 0 1/2 h 0 0 0 0 0 1/3 0 1/3 0 i A^2= 1/3 0 1/6 0 1/6 0 1/6 0 0 a 0 5/12 0 1/4 0 1/4 0 1/12 0 b 1/6 0 1/3 0 1/6 0 0 0 1/6 c 0 1/4 0 5/12 0 1/12 0 1/4 0 d 1/3 0 1/3 0 1/3 0 1/3 0 1/3 e 0 1/4 0 1/12 0 5/12 0 1/4 0 f 1/6 0 0 0 1/6 0 1/3 0 1/6 g 0 1/12 0 1/4 0 1/4 0 5/12 0 h 0 0 1/6 0 1/6 0 1/6 0 1/3 i WOW.... [手动计算途中] [出现的趣题例] 请找出:<a_n> 1, 23, 241, 2375, 23233, 227063, 2218897, 21683111, 211887457, 2070564695 这个数列的 a. 递回关系 开灯:a_n+2 - 11*a_n+1 + 12*a_n = 0 b. 根据a求数列表达式 开灯:a_n= Ａα^n + Ｂβ^n Ａ= 1/2 + 35/2√73 Ｂ= 1/2 - 35/2√73 α= (11+√73)/2 β=(11-√73)/2 (一般恶心而已)　　　 c. 待求的期望值Exp(b→h)= (0~∞)Σ (2n+2) * a_n / 12^(n+1) ※ 编辑: jurian0101 来自: 140.112.243.60 (03/01 10:02)