Ньюман-Конвей тізбегінің n шарттарын басып шығару


Күрделілік дәрежесі оңай
Жиі кіреді Amazon Цитадель Factset Фанатика JP Morgan
Динамикалық бағдарламалау математика серия

Проблемалық мәлімдеме

«Ньюман-Конвей тізбегінің n шарттарын басып шығару» мәселесінде сізге «n» бүтін саны берілгені айтылған. Ньюман-Конвей тізбегінің алғашқы n шарттарын тауып, оларды басып шығарыңыз.

мысал

n = 6
1 1 2 2 3 4

Түсіндіру
Барлық басылған терминдер Ньюман-Конвей тізбегіне сәйкес келеді, сондықтан біз де осылай жасауымыз керек. Біз алғашқы n терминді табуға тырысамыз.

Ньюман-Конвей кезегінің n шарттарын басып шығару тәсілдері

Ньюман-Конвей тізбегі - бұл әр мүшесі келесі қайталану қатынасын қанағаттандыратын тізбек:

P (1) = P (2) = 1

Ньюман-Конвей тізбегінің n шарттарын басып шығару

Енді бізге істеу керек - тізбектің алғашқы n мүшесін табу. Біз $ n $ элементін табу керек болатын ұқсас есепті шештік Ньюман-Конвей кезегіe. Ол кезде бізде екі жол болды. Немесе біз есепті рекурсияны қолдана отырып шеше алатын едік немесе қолданған болар едік Динамикалық бағдарламалау. Біз рекурсияны қолдану уақыттың шегінен асып түсетінін білдік. Уақыт бойынша рекурсияның күрделілігі экспоненциалды. Рекурсиялық шешім үшін біз қайталану формуласын қолданамыз және әр түрлі элементтердің мәндерін есептей береміз. Сізге P (3) табу керек деп санаңыз, сондықтан сіз P (P (2)) және P (3-P (2)) табасыз. Сондықтан P (3) табу үшін алдымен P (2) есептеу керек, содан кейін тағы сол есептеулерді орындау керек. Бұл тапсырма өте көп уақытты қажет етеді.

Бағдарламалаудың динамикалық тәсілі

Уақыттың күрделілігін азайту үшін біз қолдандық динамикалық бағдарламалау. Себебі біз кейбір элементтерді бірнеше рет есептеп шығардық. Элементтерді бірнеше рет есептеудің орнына біз аралық элементтер үшін жауапты сақтадық. Техника рекурсияға өте ұқсас. Бірақ есте сақтау кестесін қолданатын бір бөліктің қосылуы бар. Есте сақтау әр есептелген термин үшін мәндерді сақтайды.

Сондықтан бізге қандай-да бір термин қажет болған кезде, оның есептелгендігін тексеріп отырамыз. Егер жоқ болса, біз оны есептейміз, басқаша пайдаланыңыз. Аралық терминдерді сақтаудың бұл әдісі әдетте белгілі Динамикалық бағдарламалау. Осылайша, біз мәндерді кэштеуді жалғастырамыз және ақыр соңында біз осы мәндерді басып шығарамыз.

код

Newman-Conway Sequence басылымының n шартына арналған C ++ коды

#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 шарттарын басып шығару үшін Java коды

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

Күрделілікті талдау

Уақыттың күрделілігі

O (N), өйткені біз жай ғана динамикалық бағдарламалау тәсілінде цикл жүргіздік. Бізде әрқашан ағымдағы элементті есептеу үшін қажет болатын барлық элементтер қайта есептелген болатын.

Ғарыштың күрделілігі

O (N), барлық n элементтерін сақтау үшін сызықтық кеңістік қажет, сондықтан кеңістіктің қиындығы сызықтық болады.