Печатете n термини за низата Newуман-Конвеј


Ниво на тешкотија Лесно
Често прашувано во Амазон Цитаделата Факти Фанатици ЈП Морган
Динамичко програмирање Математика Серии

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

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

пример

n = 6
1 1 2 2 3 4

Објаснување
Сите поими што се печатат ја следат низата Newуман-Конвеј и затоа треба да го сториме истото. Е се обидеме да ги најдеме првите n поими.

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

Низата Newуман-Конвеј е низа чијшто поим ја задоволува следната рецидивна релација:

P (1) = P (2) = 1

Печатете n термини за низата Newуман-Конвеј

Сега, она што треба да го направиме е да ги најдеме првите n термини на низата. Ние веќе решивме сличен проблем каде требаше да го најдеме n-тиот елемент на Newуман-Конвеј Секвенчд. Во тоа време, имавме две опции. Или би можеле да го решиме проблемот користејќи рекурзија или можевме да искористиме Динамичко програмирање. Научивме дека користењето рекурзија ќе го надмине временскиот рок. Бидејќи временската сложеност на Рекурзијата е експоненцијална. За решението за повторување, ќе ја користиме формулата за повторување и ќе продолжиме да ги пресметуваме вредностите за различни елементи. Размислете дека треба да најдете P (3), па ќе најдете P (P (2)) и P (3-P (2)). Значи, за да пронајдете P (3), прво, треба да пресметате P (2), а потоа повторно да ги направите истите пресметки. Оваа задача е многу време.

Пристап на динамичко програмирање

За да се намали сложеноста во времето, користевме динамично програмирање. Бидејќи неколку пати пресметувавме некои од елементите. Наместо да ги пресметуваме елементите повеќе пати, ние го сочувавме одговорот за средните елементи. Техниката е многу слична на повторувањето. Но, има додавање на еден дел што користи табела за меморирање. Мемонизацијата ги зачувува вредностите за секој пресметан термин.

Значи, секогаш кога ќе ни треба некој термин, едноставно проверуваме дали тој е веќе пресметан. Ако не, ние го пресметуваме, користете го. Оваа техника на зачувување на средни термини е општо позната како Динамичко програмирање. Така, ќе продолжиме да ги кешираме вредностите и конечно, ќе ги печатиме овие вредности.

Код

C ++ код за печатење n услови на низата Newуман-Конвеј

#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

Јава код за печатење n услови на низата Newуман-Конвеј

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

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

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

НА), затоа што само извршивме јамка во пристапот кон динамично програмирање. Како што секогаш ги имавме препросметани сите елементи што беа потребни за пресметување на тековниот елемент.

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

НА), складирањето на сите n елементи бара линеарен простор и затоа комплексноста на просторот е исто така линеарна.