મોઝર-દ બ્રુઇઝન સિક્વન્સ  


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે ફ્રીચાર્જ સ્નેપડીલ ટાઇમ્સ ઇન્ટરનેટ
ડાયનેમિક પ્રોગ્રામિંગ સિક્વન્સ

આ સમસ્યામાં, તમને પૂર્ણાંક ઇનપુટ n આપવામાં આવે છે. હવે તમારે મોઝર-દ બ્રુઇઝન સિક્વન્સના પ્રથમ n તત્વોને છાપવાની જરૂર છે.

ઉદાહરણ  

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

સમજૂતી

આઉટપુટ ક્રમમાં મોઝર-દ બ્રુઇઝન સિક્વન્સના પ્રથમ સાત તત્વો છે. આમ આઉટપુટ એકદમ સાચી છે.

અભિગમ  

In નંબર સિદ્ધાંતમોઝર – ડી બ્રુઇઝન ક્રમ એક છે પૂર્ણાંક ક્રમ પછી નામ આપવામાં આવ્યું લીઓ મોઝર અને નિકોલસ ગોવર્ટ ડી બ્રુઇઝન, 4.. ની વિશિષ્ટ શક્તિઓના સરવાળોનો સમાવેશ કરે છે. તેથી તેનો અર્થ એ કે તેમાં બધી સંખ્યાઓ હશે જે which ની અલગ શક્તિઓનો ઉપયોગ કરીને રજૂ કરી શકાય.

અમે સંખ્યાઓને પણ નિર્ધારિત કરી શકીએ છીએ જે મોઝર-દ બ્રુઇઝન સિક્વન્સને થોડી થોડી અલગ રીતે બનાવે છે. જો નંબર -4 નંબર સિસ્ટમમાં રૂપાંતરિત સંખ્યામાં ફક્ત 0 અથવા 1 શામેલ છે, તો પછી આપણે કહીએ કે નંબર મોઝર-દ બ્રુઇઝન સિક્વન્સમાં અસ્તિત્વમાં છે. તેનો અર્થ એ નથી કે બેઝ -4 નંબર સિસ્ટમમાં તેના અંકો તરીકે ફક્ત 0 અને 1 શામેલ છે. આધાર -4 રજૂઆતમાં 0, 1, 2 અને 3 શામેલ હોય છે. તેને કેટલીક પૂર્વજરૂરીયાતોને અનુસરવાની જરૂર છે જેમાં બેઝ -0 રજૂઆતમાં ફક્ત 1 અથવા 4 હોવું જોઈએ તેથી હવે આપણે પરિચિત છીએ કે કયા પ્રકારનાં સંખ્યા ક્રમ બનાવે છે. પરંતુ આપણે આવી સંખ્યાઓ કેવી રીતે પેદા કરી શકીએ?

એક સરળ રીત એ પુનરાવૃત્તિ સૂત્રનો ઉપયોગ કરવાની છે જેનો ઉપયોગ ક્રમની સંખ્યા બનાવવા માટે થાય છે. પરંતુ ત્યાં એક કેચ છે.

આ પણ જુઓ
દ્વિસંગી વૃક્ષનો ટોચનો દેખાવ

પુનરાવર્તન સંબંધ

મોઝર-દ બ્રુઇઝન સિક્વન્સ

આધાર કેસ n = 0, S (0) = 0. માટે છે. હવે, જો આપણે ફક્ત પુનરાવર્તન સંબંધનો ઉપયોગ કરીએ, તો આપણે કેટલાક મૂલ્યોની ગણતરી એક કરતા વધારે વાર કરીશું. આ પ્રક્રિયા ફક્ત સમયની જટિલતામાં વધારો કરશે. અમારા અલ્ગોરિધમનો સુધારવા માટે, અમે આ કિંમતો સંગ્રહ કરીશું જે ગણતરીઓને ઘટાડશે. આ તકનીક જ્યાં આપણે ડેટા સંગ્રહિત કરીએ છીએ જે ગણતરી દરમિયાન પાછળથી ઉપયોગમાં લઈ શકાય છે ડાયનેમિક પ્રોગ્રામિંગ. ની મૂળ બાબતો તપાસો ગતિશીલ પ્રોગ્રામિંગ અહીં.

કોડ  

મોઝર-દ બ્રુઇઝન સિક્વન્સ જનરેટ કરવા માટે સી ++ કોડ

#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 એરે જે ઇનપુટ પર આધારિત છે. સમસ્યા માટેની જગ્યાની જટિલતા રેખીય છે.