0

ゴロム数列のn番目の数を計算するという小さなプログラミングの課題を解決しようとしています（詳細については、これを参照してください）。簡単な解決策を書きましたが、2500000の位置の番号が10813であるため、問題が発生する可能性がありますが、私のプログラムでは10814が返されます。

var golomb = (function(){
    var cache = [null, 1];
    const o = 0.5 * (1 + Math.sqrt(5)); // Golden ratio 
    return function(n){
        return cache[n] || (function(){
            return Math.round(Math.pow(o, 2-o) * Math.pow(n, o-1));
        })();
    };
})();

var num = golomb(process.argv[2]);
console.log(num);

たぶん、黄金比はJavaScriptが与えるよりも長い必要があります。誰かが助けることができますか？ありがとう。

4

3 に答える 3

1

価値のあるものとして、ここに、キャッシュを使用した漸化式に基づく関数があります。これにより、正解がすぐに得られます。

var golomb = (function() {
    var cache = [null, 1];
    return function(n) {
       var i;
       for (i=cache.length;i<n;i++) cache[i]=golomb(i);
       return cache[n] || (cache[n]=1+golomb(n-golomb(golomb(n-1))));
    }
})();

jsFiddleで確認してください

于 2012-06-10T20:43:49.850 に答える
1

Sgmonda、Wolfram Alphaから得た式は、正確な解決策ではありません。私はゴロム数列が好きなので、実際に彼らに不平を言いました。漸化式は正確ですが、キャッシュしても低速です。ええ、それがプログラミングの挑戦が挑戦である理由です。

于 2012-06-18T01:56:58.947 に答える
0

ウィキペディアの記事から：

Colin Mallowsは、明示的な漸化式を示しています。

a(1) = 1;
a(n + 1) = 1 + a(n + 1 − a(a(n)))

整数を使用するこの反復法でソリューションを実装する必要があります。

それを実装しようとする簡単な試みは次のようになります。

function golomb(n) {
    if(n == 1) return 1;
    else return 1 + golomb(n − golomb(golomb(n-1)));
}
于 2012-06-10T19:45:12.933 に答える