Hatena::Groupactionscript

nitoyon.dispatchEvent(null)

 | 

2010-04-21

Project Euler #99

| 00:27 | Project Euler #99 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #99 - nitoyon.dispatchEvent(null)

指数の形で表される2つの数, 例えば 2^11 と 3^7, の大小を調べることは難しくはない. 電卓を使えば, 2^11 = 2048 < 3^7 = 2187 であることが確かめられる.

しかし, 632382^518061 > 519432^525806 を確認することは非常に難しい (両者ともに300万桁以上になる).

各行に1組が書かれている1000個の組を含んだ22Kのテキストファイルbase_exp.txtから, 最大の数が書かれている行の番号を求めよ.

Problem 99 - PukiWiki

まじめに計算するなら気が遠くなるが、log を取れば激しく簡単な問題になる。それだけ。

package{
import flash.display.Sprite;
import flash.text.TextField;

public class Problem99 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));

    public function Problem99(){
		var max:int = -1;
		var max_num:Number = 0;

		var list:Array = data.split(/\r?\n/);
		for (var i:int = 0; i < list.length; i++) {
			var v:Array = list[i].split(",");
			var n:Number = parseFloat(v[1]) * Math.log(parseFloat(v[0]));
			if (n > max_num) {
				max_num = n;
				max = i + 1;
			}
		}

		t.text = max.toString();
    }

	private var data:String = <>519432,525806
632382,518061
78864,613712
466580,530130
780495,510032
525895,525320
  :
13846,725685</>.toString();
}
}

Project Euler #81

| 01:01 | Project Euler #81 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #81 - nitoyon.dispatchEvent(null)

下記の5次の正方行列で、左上のセルから開始し右下のセルで終わる道を探索する。ただし下方向と右方向にのみ移動できるものとする。一番小さなパスは下で太字で示されたものである。このときの合計は2427になる。

131 673 234 103 18
201 96 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 37 331

今、31Kのテキストファイルmatrix.txtには80×80の行列が書かれている. 左上のセルから開始し右下のセルで終わりかつ右方向と下方向にのみ移動するときの最小の道の和を求めよ.

Problem 81 - PukiWiki

80×80だけど、DP の標準的な適用例なのでそのまま解く。

package{
import flash.display.Sprite;
import flash.text.TextField;

public class Problem81 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));

    public function Problem81(){
        var list:Array = data.split(/\r?\n/);
        var a:Array = [0];

        for each (var line:String in list) {
            var s:Array = line.split(/,/);
            for (var i:int = 0; i < s.length; i++) {
                a[i] = (a[i] == undefined ? Infinity : a[i]);
                a[i] = Math.min(a[i], i == 0 ? Infinity : a[i - 1]) + parseInt(s[i]);
            }
        }

        t.text = a[a.length - 1];
    }

    private var data:String = <>4445,2697,5115,718,2209,2212,654,4348,3079,6821,7668,3276,8874,4190,3785,2752,9473,7817,9137,496,7338,3434,7152,4355,4552,7917,7827,2460,2350,691,3514,5880,3145,7633,7199,3783,5066,7487,3285,1084,8985,760,872,8609,8051,1134,9536,5750,9716,9371,7619,5617,275,9721,2997,2698,1887,8825,6372,3014,2113,7122,7050,6775,5948,2758,1219,3539,348,7989,2735,9862,1263,8089,6401,9462,3168,2758,3748,5870
    :
5304,5499,564,2801,679,2653,1783,3608,7359,7797,3284,796,3222,437,7185,6135,8571,2778,7488,5746,678,6140,861,7750,803,9859,9918,2425,3734,2698,9005,4864,9818,6743,2475,132,9486,3825,5472,919,292,4411,7213,7699,6435,9019,6769,1388,802,2124,1345,8493,9487,8558,7061,8777,8833,2427,2238,5409,4957,8503,3171,7622,5779,6145,2417,5873,5563,5693,9574,9491,1937,7384,4563,6842,5432,2751,3406,7981</>.toString();
}
}

 |