DouKaku? Add tags

Add tags

Add tags to the following comment

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();
    }
}

Add tags

Tags:
The input will be splited to tags with space.

DouKaku?

Add tags

Add tags

Index

Feed

Other

Link

Pathtraq