Hatena::Groupactionscript

nitoyon.dispatchEvent(null)

 | 

2010-04-19

Project Euler #92

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

各桁の数を2乗して足し合わせて新たな数を作ることによって、作られる数字の列を考える。

例えば

  • 44 → 32 → 13 → 10 → 1 → 1
  • 85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

のような列である。結果として1か89で無限ループに陥っている。

ここで、ある数から始めた列は1か89に到達することが分かっている。

では、10,000,000より小さい数で89に到達する数はいくつあるか。

Problem 92 - PukiWiki

何も考えずに1000万回ループするだけ。いちおうメモ化してみてけど、しなくてもあまり速度には影響でないと思う。

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

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

    public function Problem92(){
        var n:int = 1;
        var result:int = 0;
        var cache:Object = {
            89: 1,
            1: -1
        };
        var a:Array = [];

        setTimeout(function():void {
            for (var i:int = 0; i < 5000; i++) {
                if (n >= 10000000) {
                    t.text = result.toString();
                    return;
                }

                var m:int = n;
                do {
                    if (cache[m] > 0) { result++; }
                    if (cache[m] != null) {
                        cache[n] = cache[m];
                        break;
                    }

                    m = getNext(m);
                } while (true);
                n++;
            }

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

    private function getNext(i:int):int {
        var ret:int = 0;
        while (i > 0) {
            ret += Math.pow(i % 10, 2);
            i /= 10;
        }
        return ret;
    }
}
}
 |