시퀀스에 숫자를 맞추는 일반적인 방법

Question

일반적인 문제는 다음과 같습니다. 양의 정수가 증가하는 경우 0 < s_1 < s_2 < s_3 < ... 및 양의 정수가 n 인 경우 고유 한 색인 k을 찾을 수있는 효율적인 알고리즘이 있습니까? s_k <= n < s_(k+1)?

좋은 해결책이있는이 문제의 구체적인 예로는 s_i = 2^(i-1)을 가져온 다음 k = log_2(n)을 가져 오는 가장 큰 0이 아닌 숫자를 찾는 것입니다.

계승 확장에서 가장 큰 0이 아닌 자리수를 찾는 것이 조금 더 어렵습니다 (예 : s_i = i!).

s_i = i 번째 삼각수 = 1 + 2 + ... + i = i(i+1)/2

나는이에 좋은 솔루션을 싶습니다

의미 일 :

이 질문에 나타납니다 내가 생각하고있는 예는 다음과 같다

for(int i=1; ; ++i) { 
    if (triangle[i] > n) 
    break; 
} 
return i; 

다음보다 더 나은 참고는 : 하나는 sequ 때문에 여기에 이진 검색을 사용할 수 없습니다 예 : 무한입니다. 물론, k <= n이라는 명백한 제약이 있습니다. 그러나 이것은 일반적으로 끔찍한 경계입니다. 예를 들어 s_i = i! 인 경우 n=20에서 이진 검색을 사용하면 k=3 일 때 20!을 계산해야하므로 4!을 초과하여 계산할 필요가 없습니다.

Answer 1

일반적인 접근법 : 방정식 n = s(x) 및 집합 k = floor(x)을 풀어 봅니다.

s_i=2^(i-1)의 경우 x=log2(n)+1이 표시됩니다. s_i=i*(i+1)/2의 경우 x=(sqrt(1+8n)-1)/2이 표시됩니다.

방정식을 분석적으로 해석 할 수없는 경우 근사값 (예 : Newton's method)을 사용하거나 단순히 이진 검색을 사용합니다.