Надрукуйте n термінів послідовності Ньюмена-Конвея


Рівень складності Легко
Часто запитують у Амазонка Цитадель Факти Фанатики JP Morgan
Динамічне програмування Математика Серія

Постановка проблеми

У проблемі “Вивести n умов послідовності Ньюмана-Конвея” зазначено, що вам дано ціле число “n”. Знайдіть перші n термінів послідовності Ньюмана-Конвея, а потім роздрукуйте їх.

Приклад

n = 6
1 1 2 2 3 4

Пояснення
Всі терміни, які надруковані, відповідають послідовності Ньюмана-Конвея, і, отже, нам потрібно зробити те саме. Ми спробуємо знайти перші російські терміни.

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

Послідовність Ньюмена-Конвея - це послідовність, кожен термін якої відповідає наступному відношенню рецидивів:

P (1) = P (2) = 1

Надрукуйте n термінів послідовності Ньюмена-Конвея

Тепер нам потрібно знайти перші n членів послідовності. Ми вже вирішили подібну задачу, де нам довелося знайти n-й елемент Ньюмен-Конвей Секвенкe. На той момент у нас було два варіанти. Або ми могли б вирішити проблему за допомогою рекурсії, або ми могли використати Динамічне програмування. Ми дізналися, що використання рекурсії перевищує обмеження часу. Оскільки часова складність рекурсії експоненціальна. Для рішення рекурсії ми будемо використовувати формулу повторення і будемо продовжувати обчислювати значення для різних елементів. Вважайте, що вам потрібно знайти P (3), тож ви знайдете P (P (2)) і P (3-P (2)). Отже, щоб знайти P (3), спочатку потрібно обчислити P (2), а потім знову зробити ті ж розрахунки. Це завдання дуже трудомістке.

Підхід до динамічного програмування

Щоб зменшити складність часу, ми використовували динамічне програмування. Тому що ми обчислювали деякі елементи кілька разів. Замість того, щоб обчислювати елементи кілька разів, ми зберігали відповідь для проміжних елементів. Методика дуже схожа на рекурсію. Але є доповнення однієї частини, яка використовує таблицю пам’ятки. Мемоізація зберігає значення для кожного обчисленого терміну.

Отже, коли нам потрібен якийсь термін, ми просто перевіряємо, чи він вже розрахований. Якщо ні, ми обчислюємо його, інакше використовуємо його. Ця техніка зберігання проміжних термінів зазвичай відома як Динамічне програмування. Таким чином, ми будемо продовжувати кешування значень і, нарешті, ми надрукуємо ці значення.

код

Код C ++ для друку n термінів послідовності Ньюмена-Конвея

#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

Код Java для друку n термінів послідовності Ньюмена-Конвея

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

Аналіз складності

Складність часу

O (N), тому що ми щойно провели цикл у підході динамічного програмування. Як ми завжди перераховували всі елементи, необхідні для обчислення поточного елемента.

Складність простору

O (N), для зберігання всіх n елементів потрібно лінійний простір, а отже, складність простору також є лінійною.