న్యూమాన్-కాన్వే సీక్వెన్స్


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ హనీవెల్
డైనమిక్ ప్రోగ్రామింగ్ మఠం సీక్వెన్స్

సమస్యల నివేదిక

“న్యూమాన్-కాన్వే సీక్వెన్స్” సమస్య మీకు ఇన్పుట్ పూర్ణాంకం “n” ఇవ్వబడిందని పేర్కొంది. అప్పుడు మీరు న్యూమాన్-కాన్వే సీక్వెన్స్ యొక్క మొదటి n వ మూలకాన్ని ముద్రించాలి.

ఉదాహరణ

n = 6
4
n = 10
6

వివరణ

అవుట్పుట్ మూలకాలు న్యూమాన్-కాన్వే సీక్వెన్స్ యొక్క ఆరవ మరియు పదవ మూలకాన్ని సూచిస్తాయి కాబట్టి. అవుట్పుట్ ఖచ్చితంగా సరైనది.

న్యూమాన్-కాన్వే సీక్వెన్స్ కనుగొనే విధానం

న్యూమాన్-కాన్వే సీక్వెన్స్ అనేది ప్రతి పదం క్రింది పునరావృత సంబంధాన్ని సంతృప్తిపరుస్తుంది.
పి (1) = పి (2) = 1

న్యూమాన్-కాన్వే సీక్వెన్స్

 

ఇప్పుడు మనం సీక్వెన్స్ నుండి n వ సంఖ్యను ప్రింట్ చేయాలి. రెండు పద్ధతులు ఉండవచ్చు ఎందుకంటే క్రమం యొక్క ప్రతి మూలకం గతంలో ఉత్పత్తి చేసిన మూలకాలపై ఆధారపడి ఉంటుంది. కాబట్టి, ఒక మార్గం ఉపయోగించడం సూత్రం కానీ ఈ పద్ధతి అసమర్థమైనది. ఎందుకంటే మేము ప్రతి మూలకం కోసం చాలాసార్లు పరిష్కరిస్తాము, ఎందుకంటే మేము శ్రేణిలో అధిక పదాల కోసం లెక్కిస్తూనే ఉంటాము. అందువల్ల మనం చాలా ఎక్కువ గణనలను చేయవలసి ఉంది. కాబట్టి తిరిగి గణన యొక్క ఈ సమస్యను పరిష్కరించడానికి. మేము ఉపయోగించవచ్చు డైనమిక్ ప్రోగ్రామింగ్ ఇది అల్గోరిథం యొక్క సామర్థ్యాన్ని బాగా మెరుగుపరుస్తుంది. ప్రస్తుతం, పునరావృత అల్గోరిథంకు ఘాతాంక సమయ సంక్లిష్టత అవసరం. ఒకే స్థితి మాత్రమే ఉన్నందున మేము దానిని సరళ పరిష్కారానికి తగ్గించవచ్చు.

కాబట్టి, లో డైనమిక్ ప్రోగ్రామింగ్ పరిష్కారం. మేము n వ మూలకానికి ముందు వచ్చే మూలకాలను నిల్వ చేసే శ్రేణిని సృష్టిస్తాము. మొదటి మూలకం నుండి (n-1) వ మూలకం వరకు ఉన్న అన్ని అంశాలు. ఈ ముందస్తు కంప్యూటెడ్ ఉపయోగించి మన n వ మూలకం కనిపిస్తుంది. N వ సంఖ్యకు ముందు ముందస్తు కంప్యూట్ చేయవలసిన అన్ని సంఖ్యలు మన దగ్గర ఉన్నందున. అవసరమైన అంశాలను మళ్లీ మళ్లీ లెక్కించకుండా మనం ఈ విలువలను సులభంగా ఉపయోగించవచ్చు. సమయం సంక్లిష్టతను తగ్గించడానికి ఈ సాంకేతికత ఉపయోగించబడుతుంది

కోడ్

N వ న్యూమాన్-కాన్వే సీక్వెన్స్ మూలకాన్ని కనుగొనడానికి C ++ కోడ్

#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

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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై), ఎందుకంటే మేము క్రమం యొక్క n వ మూలకాన్ని కనుగొనడానికి ఒకే లూప్‌ను నడిపాము. అందువలన సమయం సంక్లిష్టత సరళంగా ఉంటుంది.

అంతరిక్ష సంక్లిష్టత

పై), n వ మూలకం యొక్క గణన కోసం అవసరమైన ఇంటర్మీడియట్ ఫలితాలను నిల్వ చేయడానికి మేము DP శ్రేణిని ఉపయోగించాము. స్థల సంక్లిష్టత కూడా సరళంగా ఉంటుంది.

ప్రస్తావనలు