మోజర్-డి బ్రూయిన్ సీక్వెన్స్


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

ఈ సమస్యలో, మీకు పూర్ణాంక ఇన్పుట్ n ఇవ్వబడుతుంది. ఇప్పుడు మీరు మోజర్-డి బ్రూయిన్ సీక్వెన్స్ యొక్క మొదటి n అంశాలను ముద్రించాలి.

ఉదాహరణ

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 మాత్రమే కలిగి ఉన్న కొన్ని అవసరాలను అనుసరించాలి. కాబట్టి ఇప్పుడు మనకు ఏ రకమైన సంఖ్యలు క్రమాన్ని ఏర్పరుస్తాయో తెలుసు. కానీ మేము అలాంటి సంఖ్యలను ఎలా ఉత్పత్తి చేస్తాము?

ఒక సాధారణ మార్గం ఏమిటంటే, క్రమం యొక్క సంఖ్యలను రూపొందించడానికి ఉపయోగించే పునరావృత సూత్రాన్ని ఉపయోగించడం. కానీ క్యాచ్ ఉంది.

పునరావృత సంబంధం

మోజర్-డి బ్రూయిన్ సీక్వెన్స్

బేస్ కేసు n = 0, S (0) = 0 కోసం. ఇప్పుడు, మేము పునరావృత సంబంధాన్ని ఉపయోగిస్తే, మేము కొన్ని విలువలను ఒకటి కంటే ఎక్కువసార్లు లెక్కిస్తాము. ఈ ప్రక్రియ సమయం సంక్లిష్టతను పెంచడానికి మాత్రమే జోడించబడుతుంది. మా అల్గోరిథం మెరుగుపరచడానికి, మేము ఈ విలువలను నిల్వ చేస్తాము, ఇది గణనలను తగ్గిస్తుంది. గణన సమయంలో తరువాత ఉపయోగించగల డేటాను మేము నిల్వ చేసే ఈ పద్ధతిని సాధారణంగా సూచిస్తారు డైనమిక్ ప్రోగ్రామింగ్. యొక్క ప్రాథమికాలను చూడండి డైనమిక్ ప్రోగ్రామింగ్ <span style="font-family: Mandali; ">ఇక్కడ క్లిక్ చేయండి .

కోడ్

మోజర్-డి బ్రూయిన్ సీక్వెన్స్ ఉత్పత్తి చేయడానికి సి ++ కోడ్

#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

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

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

పై), ఎందుకంటే ఒక సంఖ్యను లెక్కించిన తర్వాత, గణనలో తరువాత ఉపయోగించడానికి సమయం అవసరం లేదు. ప్రీ-కంప్యూటేషన్‌కు O (N) సమయం అవసరం కాబట్టి. సమయం, సంక్లిష్టత సరళమైనది.

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

పై), ఎందుకంటే మేము క్రొత్తదాన్ని సృష్టించాము DP ఇన్పుట్ మీద ఆధారపడి ఉండే శ్రేణి. సమస్యకు స్థలం సంక్లిష్టత సరళమైనది.