DouKaku? 5101 ところてん: お題投稿者です。先日、放送大学を見て...(コラッツ・角谷の問題)

Comment detail

お題投稿者です。
先日、放送大学を見ていたらこの問題が紹介されていたので、懐かしかったので出題してみました。

AthlonXP2500+で4.3秒でした。
2^25まで調べてみました。
これよりも大きい数になると、メモリが必死になるから、メモ化とは別のアプローチが必要になるかなぁ。
だいたいmaxに比例する感じですね。

max =  524288 time =  2.31200003624 sec result = [511935, 469]
max =  1048576 time =  4.28099989891 sec result = [837799, 524]
max =  2097152 time =  8.67200016975 sec result = [1723519, 556]
max =  4194304 time =  17.875 sec result = [3732423, 596]
max =  8388608 time =  37.0779998302 sec result = [6649279, 664]
max =  16777216 time =  74.2660000324 sec result = [15733191, 704]
max =  33554432 time =  153.812000036 sec result = [31466382, 705]

import time
import sys

def main(cMax):
    memo = [0] * (cMax)

    def _f(n):
        if n == 1:
            return 0
        if n < cMax and memo[n] != 0:
            return memo[n]
        if n % 2 == 0:
            step = _f(n/2) + 1
        else:
            step = _f(n*3 + 1) + 1
        if n < cMax:
            memo[n] = step
        return step

    m = [0,0]
    for x in xrange(1, cMax):
        if memo[x] == 0:
            _f(x)
            if memo[x] > m[1]:
                m =[x,memo[x]]

    return m

if __name__ == '__main__':
    for x in xrange(10,25+1):
        t = time.time()
        result = main(2**x)
        print "max = ", 2**x , "time = ", time.time() - t, "sec result =", result

あー、バグめっけ。
24,25行目がタブ一個多いです。
Cに書き直してたら気づいたorz

というわけでCで書き直した。

実行結果＠AthlonXP2500+
----
f(837799)=524
time=0.093000sec

#include <stdio.h>
#include <string.h>
#include <time.h>

#define NMAX 1048576

short memo[NMAX];

int _f(unsigned long long n)
{
    int step;
    if(n == 1)
        return 0;
    if(n < NMAX && memo[n] != 0)
        return memo[n];

    if(n & 1)
        step = _f(n * 3 + 1) + 1;
    else
        step = _f(n >> 1) + 1;

    if(n < NMAX)
        memo[n] = step;
    return step;
}

int main(void)
{
    int i,mf,mi;
    
    mf = 0;
    memset(memo, 0, NMAX * sizeof(short));
    for(i = 1;i < NMAX; ++i) {
        if (memo[i] == 0){
            _f(i);
        }

        if (memo[i] > mf){
            mi = i;
            mf = memo[i];
        }    
    }

    printf("f(%d)=%d\ntime=%fsec", mi,mf, (double)clock() / CLOCKS_PER_SEC);
}

早いですね。 2^20を数えてないようですが。

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq