न्यूमैन-कॉनवे अनुक्रम के एन शब्द प्रिंट करें


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना गढ़ FactSet कट्टरपंथियों जेपी मॉर्गन
गतिशील प्रोग्रामिंग मठ कई

समस्या का विवरण

समस्या "न्यूमैन-कॉनवे सीक्वेंस के प्रिंट एन शब्द" बताते हैं कि आपको एक पूर्णांक "एन" दिया गया है। न्यूमैन-कॉनवे सीक्वेंस के पहले एन शब्द खोजें और फिर उन्हें प्रिंट करें।

उदाहरण

n = 6
1 1 2 2 3 4

व्याख्या
मुद्रित किए गए सभी शब्द न्यूमैन-कॉनवे अनुक्रम का अनुसरण करते हैं और इस प्रकार हमें भी ऐसा करने की आवश्यकता है। हम पहले n शब्द खोजने की कोशिश करेंगे।

न्यूमैन-कॉनवे सीक्वेंस के एन शब्द प्रिंट करने के लिए दृष्टिकोण

न्यूमैन-कॉनवे अनुक्रम एक अनुक्रम है जिसका प्रत्येक शब्द निम्नलिखित पुनरावृत्ति संबंध को संतुष्ट करता है:

पी (1) = पी (2) = 1

न्यूमैन-कॉनवे अनुक्रम के एन शब्द प्रिंट करें

अब हमें जो करने की आवश्यकता है वह अनुक्रम के पहले n शब्दों को खोजने के लिए है। हम पहले से ही एक ऐसी समस्या का हल कर चुके हैं, जहाँ हमें nth तत्व का पता लगाना था न्यूमैन-कॉनवे Sequencइ। उस समय, हमारे पास दो विकल्प थे। या तो हम पुनरावृत्ति का उपयोग करके समस्या को हल कर सकते थे या हम उपयोग कर सकते थे गतिशील प्रोग्रामिंग। हमने सीखा कि पुनरावृत्ति का उपयोग समय सीमा से अधिक होगा। चूंकि रिकर्सन की समय जटिलता घातीय है। पुनरावर्तन समाधान के लिए, हम पुनरावृत्ति सूत्र का उपयोग करेंगे और विभिन्न तत्वों के लिए मूल्यों की गणना करते रहेंगे। विचार करें कि आपको P (3) खोजने की आवश्यकता है, इसलिए आपको P (P (2)) और P (3-P (2)) मिलेंगे। तो पी (3) को खोजने के लिए, पहले, आपको पी (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 तत्वों को संग्रहीत करने के लिए रैखिक स्थान की आवश्यकता होती है और इस प्रकार अंतरिक्ष की जटिलता भी रैखिक होती है।