Newman-Conway 시퀀스

난이도 쉽게
자주 묻는 질문 아마존 하니웰
동적 프로그래밍 수학 순서조회수 22

문제 정책

“Newman-Conway Sequence”문제는 입력 정수“n”이 주어 졌음을 나타냅니다. 그런 다음 Newman-Conway 시퀀스의 첫 번째 n 번째 요소를 인쇄해야합니다.

n = 6
4
n = 10
6

설명

출력 요소는 Newman-Conway 시퀀스의 여섯 번째 및 열 번째 요소를 나타 내기 때문에. 출력은 절대적으로 정확합니다.

Newman-Conway 시퀀스를 찾는 방법

Newman-Conway 시퀀스는 각 항이 다음과 같은 반복 관계를 만족하는 시퀀스입니다.
P (1) = P (2) = 1

Newman-Conway 시퀀스

 

이제 시퀀스에서 n 번째 숫자를 인쇄해야합니다. 시퀀스의 각 요소가 이전에 생성 된 요소에 종속되기 때문에 두 가지 방법이있을 수 있습니다. 따라서 방법 중 하나는 재귀 그러나이 방법은 비효율적입니다. 시리즈에서 더 높은 항을 계속 계산하면서 각 요소에 대해 여러 번 풀기 때문입니다. 따라서 훨씬 더 많은 계산을 수행해야합니다. 따라서이 재 계산 문제를 해결합니다. 우리는 사용할 수 있습니다 동적 프로그래밍 알고리즘의 효율성을 크게 향상시킬 수 있습니다. 현재 재귀 알고리즘에는 기하 급수적 인 시간 복잡성이 필요합니다. 하나의 상태 만 있기 때문에 선형 솔루션으로 줄일 수 있습니다.

그래서 동적 프로그래밍 해결책. n 번째 요소 앞에 오는 요소를 저장할 배열을 만듭니다. 이것이 첫 번째 요소부터 (n-1) 번째 요소까지의 모든 요소입니다. 그런 다음 이러한 미리 계산 된 항목을 사용하여 n 번째 요소를 찾습니다. n 번째 숫자 이전에 미리 계산해야하는 모든 숫자가 있기 때문입니다. 필요한 요소를 반복해서 계산하는 대신 이러한 값을 쉽게 사용할 수 있습니다. 이 기술은 시간 복잡성을 줄이는 데 사용됩니다.

암호

n 번째 Newman-Conway 시퀀스 요소를 찾는 C ++ 코드

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

int main(){
  // element to be printed
  int n;cin>>n;
  int dp[n+1];
  dp[0] = 0;
  dp[1] = dp[2] = 1;
  for(int i=3;i<=n;i++)
    dp[i] = dp[dp[i-1]] + dp[i-dp[i-1]];
  cout<<dp[n];
}
6
4

n 번째 Newman-Conway 시퀀스 요소를 찾는 Java 코드

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    // eleemnt to be printed
    int n = sc.nextInt();
    int dp[] = new int[n+1];
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 1;
    for(int i=3;i<=n;i++)
      dp[i] = dp[dp[i-1]] + dp[i-dp[i-1]];
    System.out.print(dp[n]);
  }
}
6
4

복잡성 분석

시간 복잡성

의 위에), 시퀀스의 n 번째 요소를 찾기 위해 단일 루프를 실행했기 때문입니다. 따라서 시간 복잡도는 선형입니다.

공간 복잡성

의 위에), n 번째 요소의 계산에 필요한 중간 결과를 저장하기 위해 DP 배열을 사용했기 때문입니다. 공간 복잡성도 선형입니다.

참조

Translate »