DouKaku?beta

challenge コラッツ・角谷の問題 

任意の数nを与えたときに
・nが偶数ならば2で割る　(n=n/2)
・nが奇数ならば3倍して1を足す （n = 3*n+1)
を繰り返すと、いづれは1になる。というものがあります。

数値計算の上ではかなりの数まで成り立つことが知られています。
（すべての数について成り立つかは不明）
参考リンク先参照

ある任意の数nがコラッツ・角谷の問題で1になるまでのステップ数をf(n)とします。
1～2^20までの数でf(n)を求めて、f(n)が最大になるときのnとf(n)を表示してください。

たとえばn=9だと次のような数列をたどって、19ステップで1になります。
9->28->14->7->22->11->34->17->52->26->13->40->20->10->5->16->8->4->2->1
つまりf(9)=19です。

また、最大を求めた際の実行時間と環境を書いてください。

see: コラッツの問題の成り立つ範囲

post comment

Posted feedbacks - Java

Pen4 2.40GHz で、以下のような結果になりました。最初にIntegerでやっていたので、113383 ではまってました。

f(837799)=524 elapse: 15469(ms)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Sample120 {
    private final long maxIndex_;
    private final Map<Long, Long> memo = new HashMap<Long, Long>();

    public Sample120(int max) {
        long maxInd = 0;
        long maxLen = 0;
        List<Long> sequence = new ArrayList<Long>();
        for (long index = 1; index <= max; index++) {
            sequence.clear();
            long len = calc3n1(index, 0, sequence);
            createMemo(len, sequence);
            if (maxLen < len) {
                maxLen = len;
                maxInd = index;
            }
        }
        maxIndex_ = maxInd;
    }
    private long calc3n1(long x, long length, List<Long> sequence) {
        sequence.add(x);
        if (x == 1) return length;

        Long longVal = memo.get(x);
        if (longVal != null) return length + longVal.longValue();

        if ((x & 1) == 0) {
            return calc3n1(x / 2, length + 1, sequence);
        } else {
            return calc3n1(3 * x + 1, length + 1, sequence);
        }
    }
    private void createMemo(long length, List<Long> sequence) {
        long len = length;
        for (int index = 0, max = sequence.size(); index < max; index++) {
            Long longVal = sequence.get(index);
            if (memo.get(longVal) == null) {
                memo.put(longVal, len--);
            }
        }
    }

    public long getMaxIndex() {
        return maxIndex_;
    }
    public long getMaxLength() {
        return memo.get(maxIndex_);
    }


    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        Sample120 instance = new Sample120((int)Math.pow(2, 20));
        System.out.println(instance.getMaxIndex() + ":" + instance.getMaxLength());

        long end = System.currentTimeMillis();
        System.out.println("elapse: " + (end - start) + "(ms)");
    }
}


Max(f(n)) = 524
n =
  837799
Time: 2652[ms]

Athlon64 X2 5000+(2.6GHz) / Windows Vista HP x64 / JRE1.6.0_03

これが限界・・・1秒切りたいなぁ
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package challenge120;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Challenge120 {

    private final static int LIM = 1 << 20; // 1<<20 = 2^20

    private final static Map<Long, Integer> CACHE = new HashMap<Long, Integer>();

    public static void main(final String[] args) {

        final long start = System.currentTimeMillis();

        int fnMax = 0;
        final List<Integer> fnMaxN = new ArrayList<Integer>();

        for (int n = 1; n <= LIM; n++) {
            final int fn = f(n);
            if (fn > fnMax) {
                fnMax = fn;
                fnMaxN.clear();
                fnMaxN.add(n);
            } else if (fn == fnMax) {
                fnMaxN.add(n);
            }
        }
        out(fnMax, fnMaxN);
        System.out.println("Time: " + (System.currentTimeMillis() - start)
                + "[ms]");
    }

    private static int f(final int n) {
        int fn = 0;
        for (long nTemp = n; nTemp != 1;) {
            final Integer cached = CACHE.get(nTemp);
            if (cached == null) {
                nTemp = (nTemp % 2 == 0) ? nTemp / 2 : nTemp * 3 + 1;
                fn++;
            } else {
                fn += cached;
                break;
            }
        }
        CACHE.put(Long.valueOf(n), fn);
        return fn;
    }

    private static void out(final int maxN, final List<Integer> fnMaxN) {

        System.out.println("Max(f(n)) = " + maxN);
        System.out.println("n =");
        for (final int n : fnMaxN) {
            System.out.println("  " + n);
        }
    }
}


Listではなく、ただの配列でキャッシュを実装するとかなり高速化できますね。

PentiumM 2GHz/Windows XP (32bit)で125msでした。

C:¥>java Dk120
f(837799)=524 in 125 ms
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Dk120 {
    static final int maxN = (1 << 20);
    static final int cacheN = maxN;
    
    private static int[] cache = new int[cacheN+1];
    
    private static int colatz(long n) {
        if (n == 1) return 0;
        if (n <= cacheN && cache[(int)n] != 0) return cache[(int)n];
        
        int c = 1 + ((n % 2 == 0) ? colatz(n >> 1) : colatz(n * 3 + 1));
        if (n <= cacheN) cache[(int)n] = c;
        return c;
    }
    
    public static void main(String[] args) {
        int max = 1;
        int maxValue = 0;
        long start = System.currentTimeMillis();
        
        for (int i = 1; i <= maxN; i++) {
            int c = colatz(i);
            if (max < c) { max = c; maxValue = i; }
        }
        System.out.printf("f(%d)=%d in %d ms", maxValue, max, System.currentTimeMillis() - start);
    }    
}

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]