Newman-Conway հաջորդականություն  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon HONEYWELL
Դինամիկ ծրագրավորում Մաթեմատիկա Հերթականություն

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

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

Օրինակ  

n = 6
4
n = 10
6

բացատրություն

Քանի որ ելքային տարրերը ներկայացնում են Newman-Conway Sequence- ի վեցերորդ և տասներորդ տարրերը: Արդյունքը միանգամայն ճիշտ է:

Մոտեցում գտնելու Newman-Conway Sequence- ին  

Newman-Conway Sequence- ը հաջորդականություն է, որի յուրաքանչյուր տերմին բավարարում է հետևյալ կրկնության հարաբերությունը:
P (1) = P (2) = 1

Newman-Conway հաջորդականությունPin

 

Այժմ մենք պետք է հաջորդականությունից տպենք n- րդ համարը: Կարող են լինել երկու մեթոդներ, քանի որ հաջորդականության յուրաքանչյուր տարր կախված է նախկինում առաջացած տարրերից: Այսպիսով, եղանակներից մեկը օգտագործելն է հետադարձություն բայց այս մեթոդը անարդյունավետ է: Քանի որ յուրաքանչյուր տարրի համար մենք բազմիցս լուծումներ ենք տալու, քանի որ շարքի ավելի բարձր տերմինների հաշվարկը շարունակում ենք: Այսպիսով, մենք պետք է շատ ավելի շատ հաշվարկներ կատարենք: Այսպիսով, վերահաշվարկի այս խնդիրը լուծելու համար: Մենք կարող ենք օգտագործել Դինամիկ ծրագրավորում ինչը կարող է շատ բարձրացնել ալգորիթմի արդյունավետությունը: Ներկայումս ռեկուրսիվ ալգորիթմին անհրաժեշտ է ցուցիչ ժամանակի բարդություն: Մենք կարող ենք այն իջեցնել գծային լուծման, քանի որ գոյություն ունի միայն մեկ պետություն:

Այսպիսով, դինամիկ ծրագրավորում լուծում Մենք կստեղծենք մի զանգված, որը կպահպանի այն տարրերը, որոնք գալիս են n- րդ տարրից առաջ: Դա բոլոր տարրերն են առաջին տարրից մինչև (n-1) րդ տարր: Դրանից հետո օգտագործելով այս նախահաշվարկվածը մենք կգտնենք մեր n-րդ տարրը: Քանի որ մենք ունենք բոլոր թվերը, որոնք պետք է նախահաշվարկվեն մինչ n-րդ համարը: Մենք կարող ենք հեշտությամբ օգտագործել այս արժեքները `պահանջվող տարրերը կրկին ու կրկին հաշվարկելու փոխարեն: Այս տեխնիկան օգտագործվում է ժամանակի բարդությունը նվազեցնելու համար

Տես նաեւ,
Ուղի գումար

Կոդ  

C ++ կոդ ՝ Newman-Conway հաջորդականության n-րդ տարրը գտնելու համար

#include <bits/stdc++.h>
using namespace std;

int main(){
  // element 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]];
  cout<<dp[n];
}
6
4

Java- ի կոդ ՝ Newman-Conway հաջորդականության n-րդ տարրը գտնելու համար

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    // eleemnt 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]];
    System.out.print(dp[n]);
  }
}
6
4

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

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

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

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

ՎՐԱ), քանի որ մենք օգտագործել ենք DP զանգված `միջանկյալ արդյունքները պահելու համար, որոնք պահանջվում էին n- ի տարրի հաշվարկման համար: Տիեզերական բարդությունը նույնպես գծային է:

Սայլակ