മോസർ-ഡി ബ്രൂയിൻ സീക്വൻസ്


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ഫ്രീചാർജ് സ്നാപ്ഡേൽ ടൈംസ് ഇന്റർനെറ്റ്
ഡൈനാമിക് പ്രോഗ്രാമിംഗ് അനുക്രമം

ഈ പ്രശ്‌നത്തിൽ‌, നിങ്ങൾ‌ക്ക് ഒരു ഇൻ‌റിജർ‌ ഇൻ‌പുട്ട് നൽ‌കി. ഇപ്പോൾ നിങ്ങൾ മോസർ-ഡി ബ്രൂയ്ൻ സീക്വൻസിന്റെ ആദ്യ n ഘടകങ്ങൾ പ്രിന്റുചെയ്യേണ്ടതുണ്ട്.

ഉദാഹരണം

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

വിശദീകരണം

Season ട്ട്‌പുട്ട് ശ്രേണിയിൽ മോസർ-ഡി ബ്രൂയിൻ സീക്വൻസിന്റെ ആദ്യ ഏഴ് ഘടകങ്ങളുണ്ട്. അങ്ങനെ output ട്ട്‌പുട്ട് തികച്ചും ശരിയാണ്.

സമീപനം

In സംഖ്യ സിദ്ധാന്തംമോസർ-ഡി ബ്രൂയിൻ സീക്വൻസ് ഒരു ആണ് പൂർണ്ണസംഖ്യ പേരിട്ടു ലിയോ മോസർ ഒപ്പം നിക്കോളാസ് ഗവർട്ട് ഡി ബ്രൂയ്ൻ, 4 ന്റെ വ്യതിരിക്ത ശക്തികളുടെ ആകെത്തുക ഉൾക്കൊള്ളുന്നു. അതിനാൽ ഇതിനർത്ഥം 4 ന്റെ വ്യതിരിക്തമായ ശക്തികൾ ഉപയോഗിച്ച് പ്രതിനിധീകരിക്കാൻ കഴിയുന്ന എല്ലാ അക്കങ്ങളും അതിൽ അടങ്ങിയിരിക്കുമെന്നാണ്.

മോസർ-ഡി ബ്രൂയ്ൻ സീക്വൻസ് സൃഷ്ടിക്കുന്ന അക്കങ്ങളെ അല്പം വ്യത്യസ്തമായ രീതിയിൽ നിർവചിക്കാനും ഞങ്ങൾക്ക് കഴിയും. ബേസ് -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), കാരണം ഒരു സംഖ്യ കണക്കുകൂട്ടിയാൽ, പിന്നീട് കണക്കുകൂട്ടലിൽ അത് ഉപയോഗിക്കാൻ സമയമില്ല. പ്രീ-കമ്പ്യൂട്ടിംഗിന് O (N) സമയം ആവശ്യമുള്ളതിനാൽ. സമയം, സങ്കീർണ്ണത രേഖീയമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N), കാരണം ഞങ്ങൾ പുതിയത് സൃഷ്ടിച്ചു DP ഇൻപുട്ടിനെ ആശ്രയിച്ചിരിക്കുന്ന അറേ. പ്രശ്നത്തിന്റെ സ്ഥല സങ്കീർണ്ണത രേഖീയമാണ്.