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