న్యూమాన్-కాన్వే సీక్వెన్స్ యొక్క n నిబంధనలను ముద్రించండి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ సిటాడెల్ ఫాక్ట్‌సెట్ ఇష్టపడేవారిని జెపి మోర్గాన్
డైనమిక్ ప్రోగ్రామింగ్ మఠం సిరీస్

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

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

ఉదాహరణ

n = 6
1 1 2 2 3 4

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

న్యూమాన్-కాన్వే సీక్వెన్స్ యొక్క n నిబంధనలను ముద్రించడానికి విధానం

న్యూమాన్-కాన్వే సీక్వెన్స్ అనేది ప్రతి పదం కింది పునరావృత సంబంధాన్ని సంతృప్తిపరిచే ఒక క్రమం:

పి (1) = పి (2) = 1

న్యూమాన్-కాన్వే సీక్వెన్స్ యొక్క n నిబంధనలను ముద్రించండి

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

డైనమిక్ ప్రోగ్రామింగ్ అప్రోచ్

సమయ సంక్లిష్టతను తగ్గించడానికి, మేము ఉపయోగించాము డైనమిక్ ప్రోగ్రామింగ్. ఎందుకంటే మేము కొన్ని అంశాలను చాలాసార్లు లెక్కిస్తున్నాము. మూలకాలను అనేకసార్లు లెక్కించడానికి బదులుగా, మేము ఇంటర్మీడియట్ మూలకాల కోసం జవాబును నిల్వ చేసాము. సాంకేతికత పునరావృతానికి చాలా పోలి ఉంటుంది. కానీ జ్ఞాపకశక్తి పట్టికను ఉపయోగిస్తున్న ఒకే భాగాన్ని చేర్చడం ఉంది. జ్ఞాపకం ప్రతి లెక్కించిన పదానికి విలువలను నిల్వ చేస్తుంది.

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

కోడ్

న్యూమాన్-కాన్వే సీక్వెన్స్ యొక్క నిబంధనలను ముద్రించడానికి సి ++ కోడ్

#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

న్యూమాన్-కాన్వే సీక్వెన్స్ యొక్క నిబంధనలను ముద్రించడానికి జావా కోడ్

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

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

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

పై), ఎందుకంటే మేము డైనమిక్ ప్రోగ్రామింగ్ విధానంలో లూప్‌ను నడిపించాము. ప్రస్తుత మూలకం యొక్క గణన కోసం అవసరమైన అన్ని అంశాలను తిరిగి లెక్కించినట్లు మేము ఎల్లప్పుడూ కలిగి ఉన్నాము.

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

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