Hatena::Groupactionscript

nitoyon.dispatchEvent(null)

 | 

2010-04-26

Project Euler #71

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

nとdを正の整数として, 分数 n/d を考えよう. n<dかつHCF(n,d)=1のとき, 真既約分数と呼ぶ.</ppp>

d ≤ 8について既約分数を大きさ順に並べると, 以下を得る:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

3/7のすぐ左の分数は2/5である.

d ≤ 1,000,000について真既約分数を大きさ順に並べたとき, 3/7のすぐ左の分数の分子を求めよ.

Problem 71 - PukiWiki

何も考えずに全通り調べると、100万^2 通り調べなきゃいけないので現実的ではない。d を固定して 3/7 の左近傍となる n を求めることはできるので、これを 0<d<=1000000 について調べればいい。</ppp>

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

public class Problem71 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));
    private const D:int = 1000000;

    public function Problem71(){
        var n:int = 1, d:int = 2;
        var nearestN:int = 0, nearest:Number = 0;
        setTimeout(function():void {
            for (var i:int = 0; i < 1000; i++) {
                if (d > D) {
                    t.text = nearestN + "";
                    return;
                }

                n = d * 3 / 7;
                while (true) {
                    if (n / d <= nearest) break;
                    if (gcm(n, d) == 1 && n / d < 1) {
                        if (n / d < 3 / 7 && n / d > nearest) {
                            nearestN = n;
                            nearest = n / d;
                        }
                        break;
                    }
                    n--;
                }

                d++;
            }

            t.text = "checking " + n + "/" + d;
            setTimeout(arguments.callee, 10);
        }, 10);
    }

    private function gcm(a:int, b:int):int {
        if (a < b) return gcm(b, a);
        if (a % b == 0) return b;
        return b > a - b ? gcm(b, a - b) : gcm(a - b, b);
    }
}
}
 |