ಗೋಲೋಂಬ್ ಅನುಕ್ರಮ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಕ್ಯಾಡೆನ್ಸ್ ಇಂಡಿಯಾ ವಾಸ್ತವವಾಗಿ ಟೈಮ್ಸ್ ಇಂಟರ್ನೆಟ್ ಯಾತ್ರೆ
ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಅನುಕ್ರಮ

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

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

ಉದಾಹರಣೆ

n = 8
1 2 2 3 3 4 4 4

ವಿವರಣೆ
ಗೊಲೋಂಬ್ ಅನುಕ್ರಮದ ಮೊದಲ 8 ಪದಗಳು ಕಂಡುಬರುತ್ತವೆ ಮತ್ತು ಮುದ್ರಿಸಲ್ಪಡುತ್ತವೆ. Gol ಟ್‌ಪುಟ್ ಗೋಲೋಂಬ್ ಅನುಕ್ರಮದ ಮೊದಲ 8 ಅಂಶಗಳನ್ನು ಸೂಚಿಸುವುದರಿಂದ, output ಟ್‌ಪುಟ್ ಸರಿಯಾಗಿದೆ.

ಅಪ್ರೋಚ್

ಗಣಿತದಲ್ಲಿ, ಕೊಟ್ಟಿರುವ ಅನುಕ್ರಮವನ್ನು ಸಿಲ್ವರ್‌ಮ್ಯಾನ್ಸ್ ಸೀಕ್ವೆನ್ಸ್ ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ. ಈ ಅನುಕ್ರಮಕ್ಕೆ ಸೊಲೊಮನ್ ಡಬ್ಲ್ಯೂ. ಗೊಲೋಂಬ್ ಹೆಸರಿಡಲಾಗಿದೆ. ಇದು ಕಡಿಮೆಯಾಗದ ಪೂರ್ಣಾಂಕ ಅನುಕ್ರಮವಾಗಿದೆ, ಅಲ್ಲಿ a (n) ಎಂಬುದು ಅನುಕ್ರಮದಲ್ಲಿ n ಸಂಭವಿಸುವ ಬಾರಿ. ಗೊಲೋಂಬ್ ಅನುಕ್ರಮದ ಮೊದಲ ಅಂಶ 1. ಉದಾಹರಣೆಗೆ, 1 ಅನುಕ್ರಮದಲ್ಲಿ 1 ಮಾತ್ರ ಸಂಭವಿಸುತ್ತದೆ ಎಂದು ಎ 1 = 2 ಹೇಳುತ್ತದೆ, ಆದ್ದರಿಂದ ಎ 1 ಕೂಡ 2 ಆಗಿರಬಾರದು, ಆದರೆ ಅದು ಆಗಿರಬಹುದು ಮತ್ತು ಆದ್ದರಿಂದ XNUMX ಆಗಿರಬೇಕು.

ಅನುಕ್ರಮದ ಮೊದಲ ಕೆಲವು ಪದಗಳು 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12.

ಗೊಲೋಂಬ್ ಅನುಕ್ರಮದ ಅಂಶಗಳನ್ನು ಉತ್ಪಾದಿಸುವ ಪುನರಾವರ್ತಿತ ಸಂಬಂಧವನ್ನು ನಾವು ತಿಳಿದಿದ್ದೇವೆ. ಪುನರಾವರ್ತಿತ ಸೂತ್ರ

ಗೋಲೋಂಬ್ ಅನುಕ್ರಮ
ಪುನರಾವರ್ತಿತ ಸೂತ್ರವನ್ನು ಬಳಸಿಕೊಂಡು ನಾವು ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುತ್ತೇವೆ. ಪುನರಾವರ್ತನೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವುದು ಒಂದು ಮಾರ್ಗವಾಗಿದೆ. ಆದರೆ ಅದು ನಮಗೆ ಘಾತೀಯ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ವೆಚ್ಚ ಮಾಡುತ್ತದೆ ಏಕೆಂದರೆ ನಾವು ಅದೇ ಮೌಲ್ಯಗಳನ್ನು ಮತ್ತೆ ಮತ್ತೆ ಲೆಕ್ಕ ಹಾಕುತ್ತೇವೆ. ಏಕೆಂದರೆ ನಾವು ಪುನರಾವರ್ತಿತ ಸಂಬಂಧದಿಂದ ನೋಡುವಂತೆ ಅನುಕ್ರಮದ n ನೇ ಅಂಶವು ಹಿಂದೆ ಲೆಕ್ಕಾಚಾರ ಮಾಡಿದ ಪದಗಳ ಮೇಲೆ ಅವಲಂಬಿತವಾಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ ಸಮಸ್ಯೆಯನ್ನು ಬಳಸಿದ ನಂತರ ಅದನ್ನು ಪರಿಹರಿಸಲು ನಾವು ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಅನ್ನು ಬಳಸುತ್ತೇವೆ, ನಾವು ಇತರ ಮೌಲ್ಯಗಳನ್ನು ಮರು ಲೆಕ್ಕಾಚಾರ ಮಾಡಬೇಕಾಗಿಲ್ಲ.

ಕೋಡ್

ಗೊಲಾಂಬ್ ಅನುಕ್ರಮಕ್ಕಾಗಿ ಸಿ ++ ಕೋಡ್

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

int main(){
  // number of elements of Golomb sequence which are required
  int n;cin>>n;

  cout<<1<<" ";
  int dp[n+1];
  dp[1] = 1;
  for(int i=2;i<=n;i++){
    dp[i] = 1 + dp[i-dp[dp[i-1]]];
    cout<<dp[i]<<" ";
  }
}
10
1 2 2 3 3 4 4 4 5 5

ಗೊಲಾಂಬ್ ಅನುಕ್ರಮಕ್ಕಾಗಿ ಜಾವಾ ಕೋಡ್

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    // number of elements of Golomb sequence which are required
    int n = sc.nextInt();

    System.out.print("1 ");
    int dp[] = new int[n+1];
    dp[1] = 1;
    for(int i=2;i<=n;i++){
      dp[i] = 1 + dp[i-dp[dp[i-1]]];
      System.out.print(dp[i]+" ");
    }
  }
}
10
1 2 2 3 3 4 4 4 5 5

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

O (N), ಏಕೆಂದರೆ n ನೇ ಅಂಶವು ಈ ಹಿಂದೆ ಲೆಕ್ಕಹಾಕಿದ ಒಂದು ಅಂಶವನ್ನು ಅವಲಂಬಿಸಿರುತ್ತದೆ, ಇದು ಈ ಕಾರ್ಯಾಚರಣೆಯನ್ನು O (1) ಪ್ರತಿ ಅಂಶಕ್ಕೂ ಸಮಯ ಸಂಕೀರ್ಣಗೊಳಿಸುತ್ತದೆ. N ಅಂಶಗಳು ಇರುವುದರಿಂದ, ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿರುತ್ತದೆ.

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

O (N), ನಾವು n ಅಂಶಗಳನ್ನು ಸಂಗ್ರಹಿಸುತ್ತಿರುವುದರಿಂದ, ಸ್ಥಳದ ಸಂಕೀರ್ಣತೆಯು ಸಹ ರೇಖೀಯವಾಗಿರುತ್ತದೆ.