読者です 読者をやめる 読者になる 読者になる

The Balloon Popping Problem

昔演習で出された問題だが,

n 個の風船があり,それぞれの容量を1, 1/2, 1/3, . . . , 1/n とする.
各風船は容量を超える空気を入れると割れてしまう.
風船になるべく多くの空気を詰めたい.
nが十分に大きい時,空気の入れることのできる量の期待値はどうなるか.

というもの.


去年の論文で上界と下界が[1.659, 2]となっていた.
http://www.springerlink.com/content/e87784575830n437/



提出したレポートを見てみると下界が1.6745であることを示していたので少し勝っているかもしれない.
(まだちゃんと読んでないので分からないが.)


その時に使ったプログラム.今となっては解読できない...

import System
import Ratio
import Data.List

main :: IO()
main = do args <- getArgs
             print $ maxExp [1..(read(head args))]
maxExp :: [Int]->Rational
maxExp [n] = 1/fromIntegral n
maxExp ns = max ((l+1/minn)/len) (maxn * len)
         where len = fromIntegral $ length ns
                    minn = fromIntegral $ minimum ns
                    maxn = fromIntegral $ maximum ns
                    l = sum.map maxExp.takens $ ns

takens :: [Int] -> [[Int]]
takens ns = map (taken) [1..(length ns)]
        where taken n = take (n-1) ns ++ drop n ns