Golomb 시퀀스

Question

Golomb 시퀀스의 n 번째 숫자를 계산하는 작은 프로그래밍 과제를 해결하려고합니다 (자세한 내용은 this 참조). 나는 간단한 해결책을 서면으로 작성했습니다,하지만 어떤 문제가있을 수 있습니다, 2,500,000 위치의 수는 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); 

어쩌면, 황금 비율은 자바 스크립트를주는 것보다 더 많은 아이폰에 필요 나에게 제공합니다. 누군가 도울 수 있니? 감사. the wikipedia article에서

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

:

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

Answer 3

Sgmonda에 그것을 확인, 당신은 볼프람 알파에서 얻은 공식은 정확한 해결책이 아니다. 나는 실제로 Golomb 시퀀스를 좋아하기 때문에 그들에게 불평을했습니다. 반복 관계는 캐시하더라도 캐시는 정확하지만 느립니다. Heh, 프로그래밍 도전이 어려운 이유입니다.