Низа Newуман-Конвеј


Ниво на тешкотија Лесно
Често прашувано во Амазон Honeywell
Динамичко програмирање Математика Секвенца

Изјава за проблем

Проблемот „Секвенца Newуман-Конвеј“ наведува дека ви е даден влезен цел број „n“. Потоа треба да го испечатите првиот n-ти елемент од низата Newуман-Конвеј.

пример

n = 6
4
n = 10
6

Објаснување

Бидејќи излезните елементи го претставуваат шестиот и десеттиот елемент на низата Newуман-Конвеј. Излезот е апсолутно точен.

Пристап да ја пронајдете низата Newуман-Конвеј

Низата Newуман-Конвеј е низа чијшто поим ја задоволува следната рецидивна релација.
P (1) = P (2) = 1

Низа Newуман-Конвеј

 

Сега треба да го испечатиме n-тиот број од низата. Може да има два методи затоа што секој елемент од низата зависи од претходно генерираните елементи. Значи, еден од начините е да се користи рекурзија но овој метод е неефикасен. Затоа што ќе решаваме за секој елемент многу пати, како што продолжуваме да пресметуваме за повисоки термини во серијата. Така, треба да извршиме многу поголем број пресметки. Значи, за да се реши овој проблем на повторна пресметка. Може да користиме Динамичко програмирање што може многу да ја подобри ефикасноста на алгоритмот. Во моментов, на рекурзивниот алгоритам му е потребна експоненцијална временска сложеност. Можеме да го сведеме на линеарно решение затоа што постои само една држава.

Значи, во динамично програмирање решение. Willе создадеме низа што ќе ги зачувува елементите што доаѓаат пред n-от елемент. Тоа се сите елементи од првиот елемент до (n-1) тиот елемент. Потоа користејќи ги овие претпоставени ќе го најдеме нашиот n-ти елемент. Бидејќи ги имаме сите броеви што треба да се пресметаат пред n-тиот број. Лесно можеме да ги користиме овие вредности наместо повторно и повторно да ги пресметуваме потребните елементи. Оваа техника се користи за да се намали временската сложеност на

Код

C ++ код за пронаоѓање на n-тиот елемент на низата Newman-Conway

#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

Јава код за наоѓање на третиот елемент на низата Newуман-Конвеј

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-тиот елемент на низата. Така, временската сложеност е линеарна.

Комплексноста на просторот

НА), бидејќи користевме низа ДП за складирање на средните резултати што беа потребни за пресметка на n-тиот елемент. Комплексноста на просторот е исто така линеарна.

Референци