Последовательность Ньюмана-Конвея


Сложный уровень Легко
Часто спрашивают в Амазонка Honeywell
Динамическое программирование Экзамен Математики Последовательность

Постановка задачи

Задача «Последовательность Ньюмана-Конвея» утверждает, что вам дано входное целое число «n». Затем вам нужно вывести первый n-й элемент последовательности Ньюмана-Конвея.

Пример

n = 6
4
n = 10
6

объяснение

Поскольку выходные элементы представляют шестой и десятый элементы последовательности Ньюмана-Конвея. Вывод абсолютно правильный.

Подход к поиску последовательности Ньюмана-Конвея

Последовательность Ньюмана-Конвея - это последовательность, каждый член которой удовлетворяет следующему рекуррентному соотношению.
P (1) = P (2) = 1

Последовательность Ньюмана-Конвея

 

Теперь нам нужно вывести n-е число из последовательности. Может быть два метода, потому что каждый элемент последовательности зависит от ранее сгенерированных элементов. Итак, один из способов - использовать рекурсия но этот метод неэффективен. Потому что мы будем решать для каждого элемента много раз, поскольку мы продолжаем вычислять для более высоких членов в ряду. Таким образом, нам нужно выполнить гораздо большее количество вычислений. Итак, чтобы решить эту проблему повторного вычисления. Мы можем использовать Динамическое программирование что может значительно повысить эффективность алгоритма. В настоящее время рекурсивный алгоритм требует экспоненциальной временной сложности. Мы можем свести его к линейному решению, потому что есть только одно состояние.

Итак, в динамическое программирование решение. Мы создадим массив, в котором будут храниться элементы, предшествующие n-му элементу. Это все элементы от первого до (n-1) -го элемента. Затем, используя эти предварительно вычисленные, мы найдем наш n-й элемент. Поскольку у нас есть все числа, которые необходимо предварительно вычислить до n-го числа. Мы можем легко использовать эти значения вместо того, чтобы вычислять требуемые элементы снова и снова. Этот метод используется для уменьшения временной сложности

Код:

Код C ++ для поиска n-го элемента последовательности Ньюмана-Конвея

#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

Код Java для поиска n-го элемента последовательности Ньюмана-Конвея

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-й элемент последовательности. Таким образом, временная сложность линейна.

Космическая сложность

НА), поскольку мы использовали массив DP для хранения промежуточных результатов, которые требовались для вычисления n-го элемента. Сложность пространства также линейна.

дело