골롬 시퀀스


난이도 쉽게
자주 묻는 질문 케이던스 인도 과연 타임즈 인터넷 야 트라
동적 프로그래밍 순서

문제 정책

"골롬 시퀀스"문제는 입력이 주어 졌다는 것을 나타냅니다. 정수 n 및 n 번째 요소까지 골롬 시퀀스의 모든 요소를 ​​찾아야합니다.

n = 8
1 2 2 3 3 4 4 4

설명
Golomb 시퀀스의 처음 8 개 항을 찾아 인쇄합니다. 출력이 골롬 시퀀스의 처음 8 개 요소를 나타내므로 출력이 정확합니다.

접근

수학에서 주어진 시퀀스는 Silverman의 시퀀스라고도합니다. 시퀀스 이름은 Solomon W. Golomb의 이름을 따서 명명되었습니다. a (n)은 시퀀스에서 n이 발생하는 횟수 인 비 감소 정수 시퀀스입니다. Golomb 시퀀스의 첫 번째 요소는 1입니다. 예를 들어 a1 = 1은 시퀀스에서 1이 한 번만 발생한다는 것을 의미하므로 a2도 1 일 수는 없지만 2 일 수 있으므로 XNUMX 여야합니다.

시퀀스의 처음 몇 항은 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12.

우리는 Golomb 시퀀스의 요소를 생성하기위한 반복 관계를 알고 있습니다. 재귀 공식은 다음과 같습니다.

골롬 시퀀스
재귀 공식을 사용하여 문제를 해결할 것입니다. 한 가지 방법은 재귀를 사용하여 문제를 해결하는 것입니다. 그러나 동일한 값을 반복해서 계산하기 때문에 기하 급수적 인 시간 복잡성이 발생합니다. 반복 관계에서 볼 수 있듯이 시퀀스의 n 번째 요소는 이전에 계산 된 항에 의존하기 때문입니다. 따라서 동적 프로그래밍을 사용하여 문제를 해결합니다. 다른 값을 다시 계산할 필요가 없기 때문입니다.

암호

Golomb 시퀀스 용 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

int main(){
  // number of elements of Golomb sequence which are required
  int n;cin>>n;

  cout<<1<<" ";
  int dp[n+1];
  dp[1] = 1;
  for(int i=2;i<=n;i++){
    dp[i] = 1 + dp[i-dp[dp[i-1]]];
    cout<<dp[i]<<" ";
  }
}
10
1 2 2 3 3 4 4 4 5 5

Golomb 시퀀스 용 Java 코드

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    // number of elements of Golomb sequence which are required
    int n = sc.nextInt();

    System.out.print("1 ");
    int dp[] = new int[n+1];
    dp[1] = 1;
    for(int i=2;i<=n;i++){
      dp[i] = 1 + dp[i-dp[dp[i-1]]];
      System.out.print(dp[i]+" ");
    }
  }
}
10
1 2 2 3 3 4 4 4 5 5

복잡성 분석

시간 복잡성

O (N), n 번째 요소가 이전에 계산 된 단일 요소에 의존하기 때문에이 연산은 각 요소에 대해 O (1) 시간이 복잡해집니다. n 개의 요소가 있으므로 시간 복잡도는 선형입니다.

공간 복잡성

O (N), n 개의 요소를 저장하고 있으므로 공간 복잡도도 선형입니다.