Re: [中譯] Projecteuler (280) Ant and seeds
看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者jurian0101 (小維)時間16年前 (2010/03/01 01:30)推噓1(1推 0噓 6→)留言7則, 2人參與討論串2/5 (看更多)
※ 引述《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
→
03/01 01:34, , 1F
03/01 01:34, 1F
推
03/01 06:56, , 2F
03/01 06:56, 2F
→
03/01 06:56, , 3F
03/01 06:56, 3F
→
03/01 06:57, , 4F
03/01 06:57, 4F
→
03/01 06:58, , 5F
03/01 06:58, 5F
→
03/01 08:53, , 6F
03/01 08:53, 6F
→
03/01 08:55, , 7F
03/01 08:55, 7F
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)
討論串 (同標題文章)
puzzle 近期熱門文章
5
21
PTT遊戲區 即時熱門文章
14
32