Newman-Conway अनुक्रम का n सर्तहरू प्रिन्ट गर्नुहोस्  


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन Citadel तथ्य कट्टरपन्थी जेपी मोर्गन
डायनामिक प्रोग्रामिंग गणित शृंखला

समस्या वक्तव्य  

समस्या "Newman-Conway अनुक्रम को n सर्तहरू" भन्छ कि तपाईं एक पूर्णांक "एन" दिइएको छ। Newman-Conway Sequence को पहिलो n सर्तहरू फेला पार्नुहोस् र तिनीहरूलाई प्रिन्ट गर्नुहोस्।

उदाहरणका

n = 6
1 1 2 2 3 4

स्पष्टीकरण
सबै सर्तहरू जुन मुद्रित हुन्छन् न्यूम्यान-कन्वे अनुक्रमको अनुसरण गर्दछन् र त्यसैले हामीले पनि त्यस्तै गर्नुपर्दछ। हामी पहिलो n सर्तहरू फेला पार्न प्रयास गर्नेछौं।

Newman-Conway अनुक्रम का n सर्तहरू प्रिन्ट गर्न दृष्टिकोण  

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

पी (१) = पी (२) = १

Newman-Conway अनुक्रम का n सर्तहरू प्रिन्ट गर्नुहोस्पिन

अब हामीले के गर्नु पर्छ यो अनुक्रमको पहिलो एन सर्तहरू फेला पार्नु हो। हामीले पहिले नै त्यस्तै समस्या समाधान गरिसकेका छौं जहाँ हामीले nth एलिमेन्ट फेला पार्नु पर्ने थियो न्यूम्यान-कन्वे सेक्वेन्कe त्यतिबेला हामीसँग दुई विकल्पहरू थिए। या त हामी पुनरावृत्ति प्रयोग गरेर समस्या समाधान गर्न सक्छौं वा हामीले प्रयोग गर्न सक्दछौं डायनामिक प्रोग्रामिंग। हामीले सिक्यौं कि पुनरावृत्ति प्रयोग गर्दा समय सीमा नाघ्छ। समय आवर्ती को जटिलता घातीय छ। पुनरावृत्ति समाधानको लागि, हामी पुनरावृत्ति सूत्र प्रयोग गर्नेछौं र विभिन्न तत्वहरूको लागि मानहरूको गणना गर्न जारी राख्नेछौं। विचार गर्नुहोस् तपाईंले P ()) खोज्नु आवश्यक छ, त्यसैले तपाईं P (P (२)) र P (--P (२)) फेला पार्नुहुनेछ। त्यसोभए P ()) खोज्न, पहिले तपाईले P (२) गणना गर्नु आवश्यक छ, फेरि फेरि यस्तै गणना गर्नुहोस्। यो कार्य धेरै समय खपत हुने छ।

पनि हेर्नुहोस्
नयाँ २१ खेल

गतिशील प्रोग्रामिंग दृष्टिकोण

समय जटिलता कम गर्न को रूप मा, हामी प्रयोग गतिशील प्रोग्रामिंग। किनकि हामी केहि एलिमेन्ट्स को धेरै पटक गणना गर्दै थियौं। धेरै पटक एलिमेन्ट्स गणना गर्नको साटो हामीले मध्यवर्ती तत्वहरूको लागि उत्तर भण्डार गर्‍यौं। प्रविधि पुनरावृत्ति जस्तै समान छ। तर त्यहाँ एकल अंशको थप छ जुन मेमोमाइज तालिका प्रयोग गर्दैछ। मेमोमाइजेशनले प्रत्येक गणना अवधिको लागि मानहरू भण्डार गर्दछ।

त्यसोभए जब हामीलाई केहि शब्द चाहिन्छ, हामी केवल जाँच गर्छौं कि यो पहिले नै गणना गरिएको छ कि छैन। यदि होइन भने हामी यसको हिसाब गर्दैनौं। मध्यवर्ती सर्तहरू भण्डारण गर्ने यस प्राविधिकलाई सामान्य रूपमा चिनिन्छ डायनामिक प्रोग्रामिंग। यसरी हामी मानहरू क्यास गर्दैछौं र अन्तमा हामी यी मानहरू प्रिन्ट गर्नेछौं।

कोड  

C ++ कोड प्रिन्ट गर्न न्यूम्यान-कन्वे अनुक्रमको सर्तहरू

#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

जावा कोड Newman-Conway सीक्वेन्स को 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

जटिलता विश्लेषण  

समय जटिलता

O (N), किनभने हामीले भर्खर एउटा डायनामिक प्रोग्रामिंग दृष्टिकोणमा एउटा लुप दियौ। जस्तो कि हामी जहिले पनि सबै एलिमेन्टहरू पुन: गणना गरेका थियौं जुन वर्तमान तत्वको गणनाका लागि आवश्यक थियो।

ठाउँ जटिलता

O (N), सबै एन तत्वहरू भण्डारण गर्न रेखीय ठाउँ चाहिन्छ र यसरी अन्तरिक्ष जटिलता पनि रैखिक हुन्छ।