Newman-Conway 시퀀스의 n 항 인쇄


난이도 쉽게
자주 묻는 질문 아마존 팩트 셋 광신자 JP 모건
동적 프로그래밍 수학 연속

문제 정책

"Newman-Conway 시퀀스의 n 용어 인쇄"문제는 정수 "n"이 주어 졌다는 것을 나타냅니다. Newman-Conway Sequence의 처음 n 개 항을 찾은 다음 인쇄합니다.

n = 6
1 1 2 2 3 4

설명
인쇄 된 모든 용어는 Newman-Conway 시퀀스를 따르므로 동일한 작업을 수행해야합니다. 처음 n 개의 항을 찾으려고합니다.

Newman-Conway 시퀀스의 n 항을 인쇄하는 방법

Newman-Conway 시퀀스는 각 항이 다음과 같은 반복 관계를 충족하는 시퀀스입니다.

P (1) = P (2) = 1

Newman-Conway 시퀀스의 n 항 인쇄

이제 우리가해야 할 일은 시퀀스의 처음 n 항을 찾는 것입니다. 우리는 이미 n 번째 요소를 찾아야하는 비슷한 문제를 해결했습니다. Newman-Conway 시퀀스이자형. 그 당시에는 두 가지 옵션이있었습니다. 재귀를 사용하여 문제를 해결할 수 있거나 동적 프로그래밍. 재귀를 사용하면 시간 제한이 초과된다는 것을 배웠습니다. Recursion의 시간 복잡성은 기하 급수적입니다. 재귀 솔루션의 경우 반복 공식을 사용하고 다른 요소의 값을 계속 계산합니다. P (3)을 찾아야하므로 P (P (2))와 P (3-P (2))를 찾을 수 있습니다. 따라서 P (3)을 찾으려면 먼저 P (2)를 계산 한 다음 동일한 계산을 다시 수행해야합니다. 이 작업은 시간이 많이 걸립니다.

동적 프로그래밍 접근법

시간 복잡성을 줄이기 위해 동적 프로그래밍. 일부 요소를 여러 번 계산했기 때문입니다. 요소를 여러 번 계산하는 대신 중간 요소에 대한 답을 저장했습니다. 이 기술은 재귀와 매우 유사합니다. 그러나 메모 테이블을 사용하는 단일 부품이 추가되었습니다. 메모 화는 계산 된 각 용어의 값을 저장합니다.

따라서 용어가 필요할 때마다 이미 계산되었는지 확인하기 만하면됩니다. 계산하지 않으면 사용하십시오. 중간 용어를 저장하는이 기술은 일반적으로 다음과 같이 알려져 있습니다. 동적 프로그래밍. 따라서 우리는 값을 계속 캐싱하고 마침내이 값을 인쇄 할 것입니다.

암호

Newman-Conway 시퀀스의 n 용어를 인쇄하는 C ++ 코드

#include <bits/stdc++.h>
using namespace std;
int main(){
  // elements 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]];
  for(int i=1;i<=n;i++)
  	cout<<dp[i]<<" ";
}
6
1 1 2 2 3 4

Newman-Conway 시퀀스의 n 용어를 인쇄하는 Java 코드

import java.util.*;
class Main{
    public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
    // elemnts 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]];
  	for(int i=1;i<=n;i++)
    	System.out.print(dp[i]+" ");
  }
}
6
1 1 2 2 3 4

복잡성 분석

시간 복잡성

의 위에), 동적 프로그래밍 방식으로 루프를 실행했기 때문입니다. 우리는 항상 현재 요소의 계산에 필요한 모든 요소를 ​​다시 계산했습니다.

공간 복잡성

의 위에), n 요소를 모두 저장하려면 선형 공간이 필요하므로 공간 복잡성도 선형입니다.