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


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

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

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

Приклад

n = 6
4
n = 10
6

Пояснення

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

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

Послідовність Ньюмена-Конвея - це послідовність, кожен член якої задовольняє наступне відношення рецидивів.
P (1) = P (2) = 1

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

 

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

Отже, в динамічне програмування рішення. Ми створимо масив, який буде зберігати елементи, які стоять перед n-м елементом. Це всі елементи від першого елемента до (n-1) -го елемента. Тоді за допомогою цих попередньо обчислених ми знайдемо наш n-й елемент. Оскільки ми маємо всі числа, які потрібно попередньо обчислити до n-го числа. Ми можемо легко використовувати ці значення, замість того, щоб обчислювати необхідні елементи знову і знову. Цей прийом використовується для зменшення часової складності

код

Код С ++ для пошуку 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

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

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

O (N), тому що ми просто провели один цикл, щоб знайти n-й елемент послідовності. Таким чином, часова складність є лінійною.

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

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

посилання