Տպեք Newman-Conway Sequence- ի n պայմանները  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Միջնաբերդ Փաստեր Ֆանատիկա JP Morgan
Դինամիկ ծրագրավորում Մաթեմատիկա շարք

Խնդիրի հայտարարություն  

«Newman-Conway Sequence» - ի տպեք n տերմինների »խնդիրը նշում է, որ ձեզ տրված է« n »ամբողջ թիվ: Գտեք Newman-Conway Sequence- ի առաջին n տերմինները, ապա տպեք դրանք:

Օրինակ

n = 6
1 1 2 2 3 4

բացատրություն
Տպագրված բոլոր տերմինները հետևում են Newman-Conway հաջորդականությանը և, հետևաբար, մենք պետք է նույնը անենք: Մենք կփորձենք գտնել առաջին n տերմինները:

Newman-Conway Sequence- ի n տերմինների տպման մոտեցում  

Newman-Conway Sequence- ը հաջորդականություն է, որի յուրաքանչյուր տերմին բավարարում է հետևյալ կրկնության կապը.

P (1) = P (2) = 1

Տպեք Newman-Conway Sequence- ի n պայմաններըPin

Հիմա այն, ինչ մենք պետք է անենք, գտնել հաջորդականության առաջին n տերմինները: Մենք արդեն լուծել ենք նմանատիպ խնդիր, որտեղ պետք է գտնեինք այն-ի n- րդ տարրը Newman-Conway Sequenc- ըե. Այն ժամանակ մենք երկու տարբերակ ունեինք: Կամ մենք կարող էինք խնդիրը լուծել ՝ օգտագործելով ռեկուրսիան, կամ կարող էինք օգտագործել Դինամիկ ծրագրավորում, Մենք իմացանք, որ ռեկուրսիայի օգտագործումը կգերազանցի ժամկետը: Քանի որ հետադարձի ժամանակի բարդությունը էական է: Հետադարձ լուծման համար մենք կօգտագործենք կրկնության բանաձեւը և կշարունակենք հաշվարկել տարբեր տարրերի արժեքները: Հաշվի առեք, որ անհրաժեշտ է գտնել P (3), այնպես որ կգտնեք P (P (2)) և P (3-P (2)): Այսպիսով, P (3) գտնելու համար նախ անհրաժեշտ է հաշվարկել P (2), ապա նորից կատարել նույն հաշվարկները: Այս խնդիրը շատ ժամանակատար է:

Տես նաեւ,
Նոր 21 խաղ

Դինամիկ ծրագրավորման մոտեցում

Որպեսզի ժամանակի բարդությունը նվազեցվի, մենք օգտագործեցինք դինամիկ ծրագրավորում, Քանի որ մենք որոշ տարրեր բազմիցս հաշվարկում էինք: Փոխանակ տարրերը բազմիցս հաշվարկելու, մենք պատասխանը պահեցինք միջանկյալ տարրերի համար: Տեխնիկան շատ նման է ռեկուրսիայի: Բայց կա մեկ մասի ավելացում, որն օգտագործում է հուշագրության աղյուսակ: Հիշողությունը պահում է յուրաքանչյուր հաշվարկված ժամկետի արժեքները:

Այնպես որ, երբ որևէ տերմինի կարիք ունենանք, մենք պարզապես պարզապես ստուգում ենք, արդյոք այն արդեն հաշվարկված է: Եթե ​​ոչ, մենք դա հաշվարկում ենք, այլապես օգտագործենք: Միջանկյալ տերմինների պահպանման այս տեխնիկան սովորաբար հայտնի է որպես Դինամիկ ծրագրավորում, Այսպիսով, մենք կշարունակենք պահել արժեքները և, վերջապես, կտպենք այս արժեքները:

Կոդ  

C ++ կոդ ՝ Newman-Conway Sequence- ի 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 կոդը ՝ Newman-Conway Sequence- ի n պայմանները տպելու համար

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

Բարդության վերլուծություն  

Timeամանակի բարդություն

ՎՐԱ), քանի որ մենք պարզապես շրջանցեցինք մի դինամիկ ծրագրավորման մոտեցում: Քանի որ մենք միշտ ունեինք վերահաշվարկված բոլոր տարրերը, որոնք անհրաժեշտ էին ընթացիկ տարրի հաշվարկման համար:

Տիեզերական բարդություն

ՎՐԱ), Բոլոր n տարրերի պահպանումը պահանջում է գծային տարածություն, ուստի տարածության բարդությունը նույնպես գծային է: