Newman-Conway Sequence н шарттарын басып чыгаруу


Кыйынчылык деңгээли жеңил
Көп суралган Amazon Citadel Factset динчилдер JP Morgan
Динамикалык программалоо Math катар

Маселени билдирүү

"Newman-Conway Sequence н шарттарын басып чыгаруу" көйгөйүндө сизге "n" бүтүн саны берилгендиги айтылат. Ньюман-Конвей Секвенциясынын биринчи n шарттарын таап, аларды басып чыгарыңыз.

мисал

n = 6
1 1 2 2 3 4

түшүндүрүү
Басылып чыккан бардык терминдер Ньюман-Конвей Секвенциясын карманат, ошондуктан биз дагы ошону жасашыбыз керек. Биринчи n шартты табууга аракет кылабыз.

Ньюман-Конвей Секвенциясынын n шарттарын басып чыгаруу ыкмасы

Ньюман-Конвей ырааттуулугу - бул ар бир мүчөсү төмөнкүдөй кайталанма байланышты канааттандырган ырааттуулук:

P (1) = P (2) = 1

Newman-Conway Sequence н шарттарын басып чыгаруу

Эми бизге эмне керек, бул ырааттуулуктун биринчи n мүчөсүн табуу. Ушундай эле көйгөйдү буга чейин эле чечип, анда n элементин табышыбыз керек болчу Newman-Conway Sequencд. Ошол учурда бизде эки жол бар болчу. Же биз көйгөйдү рекурсиянын жардамы менен чечмекпиз же колдонсо болмок Динамикалык программалоо. Рекурсияны колдонуу убакыттын чегинен ашып кетерин билдик. Рекурсиянын татаалдыгы экспоненциалдуу болгондуктан. Рекурсиялык чечим үчүн биз кайталоо формуласын колдонобуз жана ар кандай элементтердин маанилерин эсептей беребиз. P (3) табуу керек деп эсептесеңиз, анда P (P (2)) жана P (3-P (2)) табасыз. Ошентип, P (3) табуу үчүн, алгач P (2) эсептөө керек, андан кийин дагы ошол эле эсептөөлөрдү жүргүзүү керек. Бул тапшырма өтө көп убакытты талап кылат.

Динамикалык программалоо ыкмасы

Убакыттын татаалдыгын азайтуу үчүн, биз колдондук динамикалык программалоо. Себеби биз кээ бир элементтерди бир нече жолу эсептеп жатканбыз. Элементтерди бир нече жолу эсептөөнүн ордуна, жоопту аралык элементтер үчүн сактадык. Техника рекурсияга абдан окшош. Бирок бул жерде эс тутум таблицасын колдонуп жаткан бир бөлүктүн кошулушу бар. Эске салууда ар бир эсептелген термин үчүн маанилер сакталат.

Андыктан кандайдыр бир мөөнөткө муктаж болгондо, анын жөн эле эсептелгенин текшерип коёбуз. Эгерде биз эсептебесек, анда аны колдонуңуз. Ортоңку терминдерди сактоонун мындай ыкмасы жалпысынан белгилүү Динамикалык программалоо. Ошентип, баалуулуктарды кэштей беребиз жана акыры, бул баалуулуктарды басып чыгарабыз.

коду

Newman-Conway Sequence н шарттарын басып чыгаруу үчүн 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

Newman-Conway Sequence н шарттарын басып чыгаруу үчүн 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 элементтерин сактоо үчүн сызыктуу мейкиндик талап кылынат, ошондуктан мейкиндиктин татаалдыгы дагы сызыктуу болот.