打印n个Newman-Conway序列的项


难度级别 易得奖学金
经常问 亚马逊 堡垒 事实集 狂徒 JP摩根
动态编程 数学 系列

问题陈述

问题“打印Newman-Conway序列的n个项”指出给您一个整数“ n”。 找到Newman-Conway序列的前n个项,然后打印它们。

使用案列

n = 6
1 1 2 2 3 4

说明
所有打印的术语均遵循Newman-Conway序列,因此我们需要执行相同的操作。 我们将尝试查找前n个项。

打印Newman-Conway序列的n项的方法

Newman-Conway序列是一个序列,每个术语均满足以下递归关系:

P(1)= P(2)= 1

打印n个Newman-Conway序列的项

现在我们需要做的是找到序列的前n个项。 我们已经解决了一个类似的问题,我们必须找到该元素的第n个元素。 纽曼·康威·塞昆克e。 当时,我们有两个选择。 我们可以使用递归来解决问题,也可以使用 动态编程。 我们了解到,使用递归将超过时间限制。 由于递归的时间复杂度是指数的。 对于递归解决方案,我们将使用递归公式,并将继续计算不同元素的值。 考虑到您需要找到P(3),因此您将找到P(P(2))和P(3-P(2))。 因此,要找到P(3),首先需要计算P(2),然后再次进行相同的计算。 此任务非常耗时。

动态规划方法

为了减少时间复杂度,我们使用了 动态编程。 因为我们多次计算了一些元素。 我们没有存储多次元素,而是存储了中间元素的答案。 该技术与递归非常相似。 但是增加了使用备忘录表的单个部分。 备注存储每个计算出的术语的值。

因此,每当我们需要某个术语时,我们只需检查它是否已经计算即可。 如果没有,我们计算它,否则使用它。 这种存储中间项的技术通常称为 动态编程。 因此,我们将继续缓存这些值,最后,我们将打印这些值。

代码

用C ++代码打印n个Newman-Conway序列的项

#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

用于打印n个Newman-Conway序列的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个元素需要线性空间,因此空间复杂度也是线性的。