Невман-Цонваиова секвенца


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

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

Проблем „Невман-Цонваи Секуенце“ наводи да сте добили улазни цели број „н“. Затим треба да одштампате први н-ти елемент Невман-Цонваи-ове секвенце.

Пример

n = 6
4
n = 10
6

Објашњење

Пошто излазни елементи представљају шести и десети елемент Невман-Цонваиеве секвенце. Излаз је апсолутно тачан.

Приступ проналажењу Невман-Цонваиове секвенце

Невман-Цонваиова секвенца је секвенца чији сваки појам задовољава следећу релацију понављања.
П (1) = П (2) = 1

Невман-Цонваиова секвенца

 

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

Дакле, у динамичко програмирање решење. Створићемо низ који ће чувати елементе који долазе испред н-тог елемента. То су сви елементи од првог елемента до (н-1) тх елемента. Тада ћемо помоћу ових прерачунатих пронаћи наш н-ти елемент. Будући да имамо све бројеве које је потребно прерачунати пре н-тог броја. Те вредности можемо лако користити уместо да изнова израчунавамо тражене елементе. Ова техника се користи за смањење временске сложености

код

Ц ++ код за проналажење н-тог Невман-Цонваи Секуенце елемента

#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

Јава код за проналажење н-тог Невман-Цонваи Секуенце елемента

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

Анализа сложености

Сложеност времена

НА), јер смо једноставно покренули једну петљу да бисмо пронашли н-ти елемент низа. Стога је временска сложеност линеарна.

Сложеност простора

НА), с обзиром да смо користили ДП низ за чување средњих резултата потребних за израчунавање н-тог елемента. Сложеност простора је такође линеарна.

Референце