Отпечатайте n условия на Newman-Conway Sequence


Ниво на трудност Лесно
Често задавани в Амазонка Цитадела FactSet Фанатиците JP Morgan
Динамично програмиране Математически Серия

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

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

Пример

n = 6
1 1 2 2 3 4

Обяснение
Всички отпечатани условия следват последователността на Нюман-Конуей и следователно трябва да направим същото. Ще се опитаме да намерим първите n термини.

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

Последователността на Нюман-Конуей е последователност, чийто всеки член удовлетворява следната рецидивираща връзка:

P (1) = P (2) = 1

Отпечатайте n условия на Newman-Conway Sequence

Сега това, което трябва да направим, е да намерим първите n членове на последователността. Вече решихме подобен проблем, където трябваше да намерим n-ия елемент на Нюман-Конуей Секвенд. По това време имахме две възможности. Или бихме могли да разрешим проблема с помощта на рекурсия, или бихме могли да използваме Динамично програмиране. Научихме, че използването на рекурсия ще надхвърли ограничението във времето. Тъй като сложността на времето на рекурсията е експоненциална. За решението за рекурсия ще използваме формулата за повторение и ще продължим да изчисляваме стойностите за различни елементи. Помислете, че трябва да намерите P (3), така че ще намерите P (P (2)) и P (3-P (2)). Така че, за да намерите P (3), първо трябва да изчислите P (2), след това отново да направите същите изчисления. Тази задача отнема много време.

Подход за динамично програмиране

За да намалим сложността във времето, използвахме динамично програмиране. Защото изчислявахме някои от елементите няколко пъти. Вместо да изчисляваме елементите няколко пъти, ние съхранихме отговора за междинните елементи. Техниката много прилича на рекурсия. Но има добавяне на една част, която използва таблица за запомняне. Мемоизирането съхранява стойностите за всеки изчислен термин.

Така че, когато имаме нужда от някакъв термин, ние просто просто проверяваме дали той вече е изчислен. Ако не го изчислим, иначе го използвайте. Тази техника на съхранение на междинни термини е известна като Динамично програмиране. По този начин ще продължим да кешираме стойностите и накрая ще ги отпечатаме.

код

C ++ код за отпечатване на n условия на последователността на Нюман-Конуей

#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

Java код за отпечатване на n условия на последователността на Newman-Conway

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