javascript - 哥伦布序列

Question

我正在尝试解决一个小的编程挑战，即计算 Golomb 序列的第 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 提供的更长的长度。有人可以帮忙吗？谢谢。

Answer 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上检查一下

Answer 2

Sgmonda，你从 Wolfram Alpha 那里得到的公式不是一个精确的解决方案。我实际上向他们抱怨过，因为我喜欢 Golomb 序列。重复关系是精确的，但速度很慢，即使您缓存它也是如此。呵呵，这就是为什么编程挑战是一个挑战。

Answer 3

来自维基百科文章：

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