Project Euler 239

@see http://projecteuler.net/index.php?section=problems&id=239

by uwi 18 Feb 2010

Embed

/**
 * Copyright uwi ( http://wonderfl.net/user/uwi )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/eSVP
 */

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=239
    public class Euler239 extends Sprite {
        private var _tf : TextField;
  
        public function Euler239() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            tr(solve());
            var g : int = getTimer();
            tr((g - s) + " ms");
        }

        // 1から100までの数がランダムにならんでいる。
        // このうち素数は25個あるが、このうち3個だけが正しい位置にいる
        // 確率を求めよ。
        private function solve() : Number
        {
        		var ps : Array = enumP(100);
//        		tr(ps.join('\n'));
	        // ret=C(25,3)*Σ_[k:0~75] p(97-k,0)*(97-k)!/100!*C(75,k)
 	       // を求める
        		var sum : Number = 0;
        		var base : Number = 1/98/99/100;
        		for(var k : uint = 0;k <= 75;k++){
        			if(k > 0)base *= 1.0 / (97-k+1)*(75-k+1)/k;
        			sum += ps[97-k]*base; 
        		}
        		
        		return 25*24*23/3/2/1*sum;
        }
        
        // f(n,k):n個の数を並べ替えてk個が正しい位置にある組み合わせ
        // Σ_k f(n,k)=n!
        // f(n,k)=f(n-k,0)*C(n,k)
        // 
        // 求める値は、まず25個のうちから正しい３個を選んでC(25,3)
        // 残りがf(97-k,0)*C(75,k)
        // ret=(Σ_[k:0~75] f(97-k,0)*C(75,k)*C(25,3))/100!
        // これを直接計算するのは困難なので、
        // 確率p(n,k)=f(n,k)/n!を考えると、
        // ret=C(25,3)*Σ_[k:0~75] p(97-k,0)*(97-k)!/100!*C(75,k)
        // p(n,k)=p(n-k,0)*C(n,k)*(n-k)!/n!=p(n-k,0)/k!
        // よって、p(n,0)=1-Σ_[k:1~n] p(n-k,0)/k!
        
        // p(n,0)を列挙する
        private function enumP(n : uint) : Array
        {
        		var p : Array = [1];
        		for(var i : uint = 1;i <= n;i++){
	        		var p0 : Number = 1.0;
	        		var fact : Number = 1.0;
        			for(var k : uint = 1;k <= i;k++){
        				fact *= k;
        				p0 -= p[i-k]/fact;
        			}
        			p.push(p0);
        		}
        		return p;
        }

        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
            _tf.scrollV = _tf.maxScrollV;
        }
    }
}