자연수 k 번째 패스에있는 모든 (k + 1) 번째 요소를 제거합니다.

Question

자연수에서 첫 번째 패스에서 두 번째 요소를 모두 제거해야합니다. 그런 다음 나머지 요소에서 두 번째 패스의 모든 세 번째 요소를 제거합니다. 그런 다음 K 번째 패스에서 나머지 요소에서 모든 (k + 1) 번째 요소를 제거합니다.

시리즈는 (매 2 요소를 제거 후) 1 패스 후이

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, ... 

같이 갈 것,

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, ... 

2 통과 후, (매 3 요소를 제거 후),

1, 3, 7, 9, 13, 15, 19, 21, 25, 27, ... 

3 번 통과 후 (네 번째 요소를 제거한 후)

1, 3, 13, 15, 19, 25, 27, ... 

그래서, 무한 패스, 그것은이 시리즈는 또한 플라 비우스 요세푸스-체라고

1, 3, 7, 13, 19, 27, 39, 49, 63, 79, ... 

될 것이다. 배수로 후 35

주는 5의 배수로 내려가

• 6^2 = 36
• 을 수행

  이에 대한 해결책은 일련의 6 요소를 찾아 다음 4 = 32

• 의 다운 후 3 = 30
• 의 배수로 후 2 = 28
• 의 배수로 1 = 27
의 배수로 솔루션이 어떻게 작동하는지
• 등 6 행운의 숫자가 작동하지만 27

입니다, 내가 이해하지 못하는거야? 이것에 대한

AC 프로그램 설명

int calc(int n) 
{ 
    if (n == 1) return 1; 
    return calc_rec(n*n, n-1); 
} 

int calc_rec(int nu, int level) 
{ 
    int tmp; 
    if (level == 1) return (nu-1); 
    tmp = nu % level; 
    return calc_rec(nu - (tmp ? tmp : level), level-1); 
} 

링크이며,이 http://oeis.org/A000960

Answer 1

이것은 당신이 질문에 대답하지만, 여기에 임의의 요소를 계산하기위한보다 직관적 인 알고리즘의 유도를하지 않습니다 빠른 속도의 스트림.

모든 정수 S [0]을 포함하는 초기 시리즈를 호출 한 다음 S [1]은 첫 번째 전달 다음에 시리즈를, S [2] 두 번째 전달 다음에 시리즈를 호출합니다. 시리즈

[0], N 번째 정수 (0부터 인덱스 시작)의 시리즈 N + 1

1 2 3 4 5 6 7 8 9 10 ... 

인 S S [1], N 번째 정수는 (2N)에 액세스함으로써 얻어진다 S [0]으로부터의 원소이다. 주 2 N = N + (N div 1). 'div'는 정수 나누기, 즉 나머지가 무시되는 나누기입니다.시리즈 S [2]에서

1 3 5 7 9 11 13 15 17 ... 

은 N 번째 정수는 N +에 접속하여 획득된다 (N DIV 2) S로부터 요소 제 [1]. 시리즈 S [3]의

1 3 7 9 13 15 19 21 ... 

은 N 번째 정수는 N +에 접속하여 획득된다 (N DIV 3) S로부터 요소 일 [2], 등. ,

get_number(int series, int N): 
    if (series == 0): 
     return N + 1 
    else: 
     return get_number(series - 1, N + floor(N/series)) 

그러나 시리즈> N이 바닥 (N/시리즈) 동일 때 제로 그래서 당신은 (get_number으로 항상 N을이를 호출 할 수 있습니다 :

1 3 7 13 15 19 ... 

따라서 다음과 같은 재귀 절차를 얻을 엔). 예를 들어

는

get_number(5, 5) = get_number(4, 6) = get_number(3, 7) = 
    get_number(2, 9) = get_number(1, 13) = get_number(0, 26) = 27. 

이것은 당신이 스트림에서 6 (5 만 제로 기반 색인)로 '27'을 얻을 수있는 방법을 보여줍니다.