ಮೋಸರ್-ಡಿ ಬ್ರೂಯಿನ್ ಅನುಕ್ರಮ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಫ್ರೀಚಾರ್ಜ್ ಸ್ನ್ಯಾಪ್ಡಿಯಲ್ ಟೈಮ್ಸ್ ಇಂಟರ್ನೆಟ್
ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಅನುಕ್ರಮ

ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಿಮಗೆ ಪೂರ್ಣಾಂಕ ಇನ್ಪುಟ್ n ನೀಡಲಾಗುತ್ತದೆ. ಈಗ ನೀವು ಮೋಸರ್-ಡಿ ಬ್ರೂಯಿನ್ ಅನುಕ್ರಮದ ಮೊದಲ n ಅಂಶಗಳನ್ನು ಮುದ್ರಿಸಬೇಕಾಗಿದೆ.

ಉದಾಹರಣೆ

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

ವಿವರಣೆ

Sequ ಟ್‌ಪುಟ್ ಅನುಕ್ರಮವು ಮೋಸರ್-ಡಿ ಬ್ರೂಯಿನ್ ಅನುಕ್ರಮದ ಮೊದಲ ಏಳು ಅಂಶಗಳನ್ನು ಹೊಂದಿದೆ. ಹೀಗಾಗಿ 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) ಸಮಯ ಬೇಕಾಗುತ್ತದೆ. ಸಮಯ, ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ಏಕೆಂದರೆ ನಾವು ಹೊಸದನ್ನು ರಚಿಸಿದ್ದೇವೆ DP ಇನ್ಪುಟ್ ಅನ್ನು ಅವಲಂಬಿಸಿರುವ ಅರೇ. ಸಮಸ್ಯೆಯ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿದೆ.