मॉसर-डी ब्रुइजन सिक्वेन्स  


अडचण पातळी मध्यम
वारंवार विचारले फ्रीचार्ज Snapdeal टाइम्स इंटरनेट
डायनॅमिक प्रोग्रामिंग अनुक्रम

या समस्येमध्ये, आपल्याला पूर्णांक इनपुट एन दिले जाईल. आता आपल्याला मॉसर-डी ब्रुइजन सीक्वेन्सचे प्रथम एन घटक मुद्रित करण्याची आवश्यकता आहे.

उदाहरण  

7
0, 1, 4, 5, 16, 17, 20

स्पष्टीकरण

आउटपुट अनुक्रमात मॉसर-डी ब्रुइजन सिक्वेंसचे पहिले सात घटक आहेत. हे आऊटपुट अगदी बरोबर आहे.

दृष्टीकोन  

In संख्या सिद्धांतमॉसर-डी ब्रुइजन अनुक्रम एक आहे पूर्णांक क्रम नंतर नाव दिले लिओ मॉसर आणि निकोलस गोवर्ट डी ब्रुइजन4.. च्या वेगळ्या शक्तींच्या बेरजेचा समावेश आहे. तर याचा अर्थ असा आहे की त्यामध्ये सर्व संख्या असतील ज्यांचे प्रतिनिधित्व 4 च्या भिन्न शक्तींचा वापर करुन केले जाऊ शकते.

आम्ही मोजेर-डी ब्रुइजन सिक्वेन्सेस जरा वेगळ्या पद्धतीने बनवतो अशा संख्या देखील परिभाषित करू शकतो. बेस -4 क्रमांकाच्या सिस्टममध्ये रूपांतरित केलेल्या संख्येत फक्त 0 किंवा 1 असेल तर आम्ही असे म्हणू की संख्या मोसर-डी ब्रुइजन सीक्वेन्समध्ये विद्यमान आहे. याचा अर्थ असा नाही की बेस -4 नंबर सिस्टममध्ये फक्त 0 आणि 1 अंक आहेत. बेस -4 च्या प्रतिनिधित्वामध्ये 0, 1, 2 आणि 3 असते. परंतु संख्या आपल्या अनुक्रमात असल्यास. यासाठी काही पूर्व-शर्तींचे अनुसरण करणे आवश्यक आहे ज्यात बेस -0 प्रतिनिधित्वामध्ये फक्त 1 किंवा 4 असणे आवश्यक आहे. आता कोणत्या क्रमांकाचा क्रम तयार होतो याची आपल्याला माहिती आहे. परंतु आपण अशा संख्या कशा निर्माण करू?

एक सोपा मार्ग म्हणजे पुनरावृत्ती फॉर्म्युलाचा वापर करणे जो क्रमांची संख्या निर्माण करण्यासाठी वापरला जातो. पण एक झेल आहे.

हे सुद्धा पहा
बायनरी झाडाचे शीर्ष दृश्य

पुनरावृत्ती संबंध

मॉसर-डी ब्रुइजन सिक्वेन्स

बेस केस एन = ०, एस (०) = ० साठी आहे. आता जर आपण फक्त रिकरन्स रिलेशन वापरल्यास आपण एकापेक्षा जास्त मूल्यांची गणना करू. ही प्रक्रिया वेळेची जटिलता वाढवेल. आपला अल्गोरिदम सुधारण्यासाठी आम्ही ही व्हॅल्यूज ठेवू ज्यामुळे संगणना कमी होतील. हे तंत्र जिथे आम्ही डेटा संग्रहित करतो जो संगणनाच्या दरम्यान नंतर वापरला जाऊ शकतो डायनॅमिक प्रोग्रामिंग. ची मुलभूत माहिती पहा डायनॅमिक प्रोग्रामिंग येथे.

कोड  

मोसर-डी ब्रुइजन सिक्वेन्सेस व्युत्पन्न करण्यासाठी सी ++ कोड

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

int main(){
  // number of elements to be generated
  int n;cin>>n;
  if(n >= 1)cout<<0<<" ";
  if(n >= 2)cout<<1<<" ";
  if(n >= 3) {
    int dp[n];
    dp[0] = 0,dp[1] = 1;
    for(int i=2; i<n;i++){
      if(i%2 == 0)
        dp[i] = 4*dp[i/2];
      else
        dp[i] = 4*dp[i/2] + 1;
      cout<<dp[i]<<" ";
    }
  }
}
6
0 1 4 5 16 17

जासर कोड मोसर-डी ब्रुइजन सिक्वेन्स व्युत्पन्न करण्यासाठी

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    // number of elements to be generated
    int n = sc.nextInt();
    if(n >= 1)System.out.print("0 ");
    if(n >= 2)System.out.print("1 ");
    if(n >= 3) {
      int dp[] = new int[n];
      dp[0] = 0;dp[1] = 1;
      for(int i=2; i<n;i++){
        if(i%2 == 0)
          dp[i] = 4*dp[i/2];
        else
          dp[i] = 4*dp[i/2] + 1;
        System.out.print(dp[i]+" ");
      }
    }
  }
}
6
0 1 4 5 16 17

गुंतागुंत विश्लेषण  

वेळ कॉम्प्लेक्सिटी

ओ (एन), कारण एकदा अंक काढले की संगणकात नंतर त्याचा वापर करायला वेळ लागणार नाही. पूर्व-गणनासाठी ओ (एन) वेळ आवश्यक आहे. वेळ, गुंतागुंत रेषात्मक आहे.

स्पेस कॉम्प्लेक्सिटी

ओ (एन), कारण आपण नवीन तयार केले आहे DP इनपुटवर अवलंबून असलेला अ‍ॅरे. समस्येसाठी अवकाश अवघडपणा रेषात्मक आहे.