作者jurian0101 (Hysterisis)
看板puzzle
標題Re: [中譯] ProjectEuler 394 Eating pie
時間Mon Oct 8 12:48:10 2012
※ 引述《babufong (嗶嗶)》之銘言:
: 394. Eating pie
: http://projecteuler.net/problem=394
: 傑夫吃派,方法怪怪。
: 派是圓的,他先在派上從圓心順著半徑至圓周劃初始第一刀。
: 給定一個分數 F,如果還有超過 F 的派留著,他就進行切派程序:
: - 他從剩下的圓周上選兩點(第一、二點)並依序從圓心至該點作切割,每點被選中的機
: 率是一樣的,這會將剩下的派分為三塊。
: - 從初始第一刀逆時針算起吃兩塊派。
: 此為 x=40 其中一種切割的示意圖:
: http://projecteuler.net/project/images/p_394_eatpie.gif
: 如果剩下的派少於 F,他就不重複切派程序了,取而代之的是直接嗑掉剩下的所有派。
: x ≧ 1,E(x) 為 F = 1/x 時,傑夫重複切派程序的次數的期望值。
: 可確定 E(1) = 1,E(2) ≒ 1.2676536759,E(7.5) ≒ 2.1215732071。
: 請求出 E(40),並將答案給至小數點下十位。
解開了XD 這題出23天了也只176人可見手法有難度。看thread有兩種平行通用的解法
一是從遞回關係推出的積分方程推是推出來了,但再導回微方我不會qq
所以借了機率論教科書開始用r.v跟他硬幹,是為較不優雅但過程蠻好玩的機率法
所求 E(x) = Σ n P(x1...xn < A| x1..x[n-1] > A)
之後用了我在數學板自問自答的結論、拉普拉斯變換捲積 etc 終於修成正果,幸虧收斂啊
叫Mathematica做牛做馬的代碼應該也只比優雅法(一行)多一點,共四行而已^^
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.125.33
推 LPH66:那條積分方程要導回微方只要大著膽子微下去就對了XD 10/08 13:42
→ LPH66:(雖然為了方便運算有小小的前處理需要弄一下就是 10/08 13:42
→ LPH66: 我第一次沒有弄這個前處理做出來的微方好醜...) 10/08 13:43
→ LPH66:然後後來才發現雖然那條微方表面上是二次實際上是一次 (爆) 10/08 13:46
→ LPH66:當初看到二次微方就開 Mathematica 了沒仔細看... 10/08 13:46
※ 編輯: jurian0101 來自: 140.112.213.88 (10/08 14:00)
→ jurian0101:本來走投無路,還以為積分方程是拿來驗證數值解的哈哈 10/08 16:53
→ jurian0101:偏偏我會的數值法除了牛頓法別無他,RK4神馬的不熟也 10/08 16:53