DouKaku? 5113 あにす: tosikさんの#5098をC#に移植し...(コラッツ・角谷の問題)

Comment detail

This comment is reply for 5098 tosik: Compiler: GCC 3.4.4 ...(コラッツ・角谷の問題). Go to thread root.

tosikさんの#5098をC#に移植してみました。
わずか421ミリ秒でした。.NETがこんなに速いとは驚きです。
コード全体を読まずに構文ごとにC#に書き換えて、最後に型の帳尻を合わせただけなのでtosikさんの意図に沿ったコードになっているか心配です。

    if ( MAX >= n )
    {
        if ( cache[n] != -1 )
        {
            cache[org_n] = cache[n] + depth;
            return cache[n] + depth;
        }
    }

の部分でnがcacheの配列の境界を越えてしまったので
if ( MAX >= n )
を
if ( MAX > n )
にしたけどいいのだろうか…。
C++の配列の宣言の添え字は配列長そのもので良かった…筈…。

OS:Windows XP Home SP2 
CPU:AMD Sempron 3400+ 1.99GHz 
メモリ:480MB

using System;
class Program {
    const int MAX = 1048577;
    static int[] cache = new int[MAX];

    static int collatz(ulong n) {
        return collatz(n, 0, 0);
    }
    static int collatz(ulong n, ulong org_n) {
        return collatz(n, org_n, 0);
    }
    static int collatz(ulong n, ulong org_n, int depth) {
        if(MAX > n) {
            if(cache[n] != -1) {
                cache[org_n] = cache[n] + depth;
                return cache[n] + depth;
            }
        }

        if(n % 2 == 0) {
            return collatz(n / 2, org_n, depth + 1);
        } else if(n == 1) {
            cache[org_n] = depth;
            return depth;
        } else {
            return collatz(n * 3 + 1, org_n, depth + 1);
        }
    }


    static void Main() {
        long tick = DateTime.Now.Ticks;
        for(int i = 0; i < MAX; i++)
            cache[i] = -1;

        ulong max_n = 0;
        int max_steps = 0;

        for(ulong i = 1; i < MAX; i++) {
            int steps = collatz(i, i);
            if(max_steps < steps) {
                max_steps = steps;
                max_n = i;
            }
        }

        Console.WriteLine("f(" + max_n + ")=" + max_steps);
        Console.WriteLine((DateTime.Now.Ticks - tick) / 10000L + "ms");
        Console.ReadLine();
    }
}

移植ありがとうございます。
C++の添え字は長さです。これは僕のミスでした。
2^20までは偶然MAX==nになることはないので、正しく動作してましたが、n>2^20の場合は実行時にエラーがでることがあるでしょうね。
このミスは、はじめにMAX=2^20にしていたときのもので、今のMAX=2^20+1に直したときに修正を忘れたものです。

ちなみにですが、このコードを書くときにひとつのバグにてこずりました。
それは全て int 型にしていたことが原因で、オーバーフローでマイナス値を出していたのが原因でした。
# 不慣れなgdbを使って挑戦したのでなかなか解明できなかった＾＾；

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq