Последователност на Нюман-Конуей  


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

Декларация за проблема  

Проблемът “Newman-Conway Sequence” гласи, че сте получили входно цяло число “n”. След това трябва да отпечатате първия n-ти елемент от последователността на Нюман-Конуей.

Пример  

n = 6
4
n = 10
6

Обяснение

Тъй като изходните елементи представляват шестия и десетия елемент от последователността на Нюман-Конуей. Резултатът е абсолютно правилен.

Подход за намиране на последователността на Нюман-Конуей  

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

Последователност на Нюман-Конуейщифт

 

Сега трябва да отпечатаме n-то число от последователността. Може да има два метода, тъй като всеки елемент от последователността зависи от генерираните преди това елементи. И така, един от начините е да се използва рекурсия но този метод е неефективен. Защото ще решаваме за всеки елемент много пъти, тъй като продължаваме да изчисляваме за по-високи членове от поредицата. По този начин трябва да извършим много повече изчисления. За да разрешим този проблем с повторното изчисление. Може да използваме Динамично програмиране което може значително да подобри ефективността на алгоритъма. В момента рекурсивният алгоритъм се нуждае от експоненциална времева сложност. Можем да го намалим до линейно решение, защото има само едно състояние.

И така, в динамично програмиране решение. Ще създадем масив, който ще съхранява елементите, които идват преди n-ия елемент. Това са всички елементи от първия елемент до (n-1)-и елемент. След това с помощта на тези предварително изчислени ще намерим нашия n-ти елемент. Тъй като имаме всички числа, които трябва да бъдат предварително изчислени преди n-то число. Можем лесно да използваме тези стойности, вместо да изчисляваме необходимите елементи отново и отново. Тази техника се използва за намаляване на сложността във времето на

Вижте също
Сума на пътя

код  

C ++ код за намиране на n-ия елемент на Newman-Conway Sequence

#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-ия елемент на Newman-Conway Sequence

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-ти елемент. Сложността на пространството също е линейна.

Препратки