ನ್ಯೂಮನ್-ಕಾನ್ವೇ ಅನುಕ್ರಮದ n ನಿಯಮಗಳನ್ನು ಮುದ್ರಿಸಿ  


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಸಿಟಾಡೆಲ್ ಫ್ಯಾಕ್ಟ್‌ಸೆಟ್ ಫ್ಯಾನಟಿಕ್ಗಳು JP ಮೋರ್ಗಾನ್
ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಮಠ ಸರಣಿ

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

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

ಉದಾಹರಣೆ

n = 6
1 1 2 2 3 4

ವಿವರಣೆ
ಮುದ್ರಿಸಲಾದ ಎಲ್ಲಾ ಪದಗಳು ನ್ಯೂಮನ್-ಕಾನ್ವೇ ಅನುಕ್ರಮವನ್ನು ಅನುಸರಿಸುತ್ತವೆ ಮತ್ತು ಆದ್ದರಿಂದ ನಾವು ಅದೇ ರೀತಿ ಮಾಡಬೇಕಾಗಿದೆ. ನಾವು ಮೊದಲ n ಪದಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಪ್ರಯತ್ನಿಸುತ್ತೇವೆ.

ನ್ಯೂಮನ್-ಕಾನ್ವೇ ಅನುಕ್ರಮದ n ನಿಯಮಗಳನ್ನು ಮುದ್ರಿಸುವ ವಿಧಾನ  

ನ್ಯೂಮನ್-ಕಾನ್ವೇ ಸೀಕ್ವೆನ್ಸ್ ಒಂದು ಅನುಕ್ರಮವಾಗಿದ್ದು, ಇದರ ಪ್ರತಿಯೊಂದು ಪದವು ಈ ಕೆಳಗಿನ ಪುನರಾವರ್ತಿತ ಸಂಬಂಧವನ್ನು ಪೂರೈಸುತ್ತದೆ:

ಪಿ (1) = ಪಿ (2) = 1

ನ್ಯೂಮನ್-ಕಾನ್ವೇ ಅನುಕ್ರಮದ n ನಿಯಮಗಳನ್ನು ಮುದ್ರಿಸಿ

ಈಗ ನಾವು ಮಾಡಬೇಕಾಗಿರುವುದು ಅನುಕ್ರಮದ ಮೊದಲ n ಪದಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವುದು. ನಾವು ಈಗಾಗಲೇ ಇದೇ ರೀತಿಯ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಿದ್ದೇವೆ, ಅಲ್ಲಿ ನಾವು n ನ ಅಂಶವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕಾಗಿತ್ತು ನ್ಯೂಮನ್-ಕಾನ್ವೇ ಸೀಕ್ವೆಂಕ್ಇ. ಆ ಸಮಯದಲ್ಲಿ, ನಮಗೆ ಎರಡು ಆಯ್ಕೆಗಳಿವೆ. ಒಂದೋ ನಾವು ಪುನರಾವರ್ತನೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಬಹುದು ಅಥವಾ ನಾವು ಬಳಸಬಹುದಿತ್ತು ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್. ಪುನರಾವರ್ತನೆಯನ್ನು ಬಳಸುವುದು ಸಮಯದ ಮಿತಿಯನ್ನು ಮೀರುತ್ತದೆ ಎಂದು ನಾವು ಕಲಿತಿದ್ದೇವೆ. ಪುನರಾವರ್ತನೆಯ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಘಾತೀಯವಾಗಿದೆ. ಪುನರಾವರ್ತಿತ ಪರಿಹಾರಕ್ಕಾಗಿ, ನಾವು ಪುನರಾವರ್ತಿತ ಸೂತ್ರವನ್ನು ಬಳಸುತ್ತೇವೆ ಮತ್ತು ವಿಭಿನ್ನ ಅಂಶಗಳಿಗೆ ಮೌಲ್ಯಗಳನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುತ್ತಲೇ ಇರುತ್ತೇವೆ. ನೀವು ಪಿ (3) ಅನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು ಎಂದು ಪರಿಗಣಿಸಿ, ಆದ್ದರಿಂದ ನೀವು ಪಿ (ಪಿ (2)) ಮತ್ತು ಪಿ (3-ಪಿ (2)) ಅನ್ನು ಕಾಣುತ್ತೀರಿ. ಆದ್ದರಿಂದ ಪಿ (3) ಅನ್ನು ಕಂಡುಹಿಡಿಯಲು, ಮೊದಲು, ನೀವು ಪಿ (2) ಅನ್ನು ಲೆಕ್ಕ ಹಾಕಬೇಕು, ನಂತರ ಮತ್ತೆ ಅದೇ ಲೆಕ್ಕಾಚಾರಗಳನ್ನು ಮಾಡಿ. ಈ ಕಾರ್ಯವು ಬಹಳ ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ.

ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಅಪ್ರೋಚ್

ಆದ್ದರಿಂದ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಕಡಿಮೆ ಮಾಡಲು, ನಾವು ಬಳಸಿದ್ದೇವೆ ಡೈನಾಮಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್. ಏಕೆಂದರೆ ನಾವು ಕೆಲವು ಅಂಶಗಳನ್ನು ಅನೇಕ ಬಾರಿ ಲೆಕ್ಕ ಹಾಕುತ್ತಿದ್ದೆವು. ಅಂಶಗಳನ್ನು ಅನೇಕ ಬಾರಿ ಲೆಕ್ಕಾಚಾರ ಮಾಡುವ ಬದಲು, ನಾವು ಮಧ್ಯಂತರ ಅಂಶಗಳಿಗೆ ಉತ್ತರವನ್ನು ಸಂಗ್ರಹಿಸಿದ್ದೇವೆ. ತಂತ್ರವು ಪುನರಾವರ್ತನೆಗೆ ಹೋಲುತ್ತದೆ. ಆದರೆ ಒಂದು ಭಾಗದ ಸೇರ್ಪಡೆ ಇದೆ, ಅದು ಜ್ಞಾಪಕ ಕೋಷ್ಟಕವನ್ನು ಬಳಸುತ್ತಿದೆ. ಜ್ಞಾಪಕೀಕರಣವು ಪ್ರತಿ ಲೆಕ್ಕಾಚಾರದ ಅವಧಿಯ ಮೌಲ್ಯಗಳನ್ನು ಸಂಗ್ರಹಿಸುತ್ತದೆ.

ಸಹ ನೋಡಿ
ಹೊಸ 21 ಆಟ

ಆದ್ದರಿಂದ ನಮಗೆ ಕೆಲವು ಪದಗಳು ಬೇಕಾದಾಗ, ಅದನ್ನು ಈಗಾಗಲೇ ಲೆಕ್ಕಹಾಕಲಾಗಿದೆಯೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ನಾವು ಅದನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡದಿದ್ದರೆ, ಇಲ್ಲದಿದ್ದರೆ ಅದನ್ನು ಬಳಸಿ. ಮಧ್ಯಂತರ ಪದಗಳನ್ನು ಸಂಗ್ರಹಿಸುವ ಈ ತಂತ್ರವನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಕರೆಯಲಾಗುತ್ತದೆ ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್. ಹೀಗೆ ನಾವು ಮೌಲ್ಯಗಳನ್ನು ಹಿಡಿದಿಟ್ಟುಕೊಳ್ಳುತ್ತೇವೆ ಮತ್ತು ಕೊನೆಗೆ ನಾವು ಈ ಮೌಲ್ಯಗಳನ್ನು ಮುದ್ರಿಸುತ್ತೇವೆ.

ಕೋಡ್  

ಸಿ ++ ಕೋಡ್ ನ್ಯೂಮನ್-ಕಾನ್ವೇ ಸೀಕ್ವೆನ್ಸ್‌ನ ಪ್ರಿಂಟ್ ಎನ್ ನಿಯಮಗಳಿಗೆ

#include <bits/stdc++.h>
using namespace std;
int main(){
  // elements to be printed
  int n;cin>>n;
  int dp[n+1];
  dp[0] = 0;
  dp[1] = dp[2] = 1;
  for(int i=3;i<=n;i++)
    dp[i] = dp[dp[i-1]] + dp[i-dp[i-1]];
  for(int i=1;i<=n;i++)
  	cout<<dp[i]<<" ";
}
6
1 1 2 2 3 4

ನ್ಯೂಮನ್-ಕಾನ್ವೇ ಸೀಕ್ವೆನ್ಸ್‌ನ ಪ್ರಿಂಟ್ ಎನ್ ನಿಯಮಗಳಿಗೆ ಜಾವಾ ಕೋಡ್

import java.util.*;
class Main{
    public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
    // elemnts to be printed
    int n = sc.nextInt();
    int dp[] = new int[n+1];
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 1;
    for(int i=3;i<=n;i++)
      dp[i] = dp[dp[i-1]] + dp[i-dp[i-1]];
  	for(int i=1;i<=n;i++)
    	System.out.print(dp[i]+" ");
  }
}
6
1 1 2 2 3 4

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

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

ಒ (ಎನ್), ಏಕೆಂದರೆ ನಾವು ಡೈನಾಮಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ವಿಧಾನದಲ್ಲಿ ಲೂಪ್ ಅನ್ನು ಓಡಿಸಿದ್ದೇವೆ. ಪ್ರಸ್ತುತ ಅಂಶದ ಲೆಕ್ಕಾಚಾರಕ್ಕೆ ಅಗತ್ಯವಿರುವ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ನಾವು ಯಾವಾಗಲೂ ಮರುಸೃಷ್ಟಿಸಿದ್ದೇವೆ.

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

ಒ (ಎನ್), ಎಲ್ಲಾ n ಅಂಶಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ರೇಖೀಯ ಸ್ಥಳಾವಕಾಶ ಬೇಕಾಗುತ್ತದೆ ಮತ್ತು ಆದ್ದರಿಂದ ಸ್ಥಳದ ಸಂಕೀರ್ಣತೆಯು ಸಹ ರೇಖೀಯವಾಗಿರುತ್ತದೆ.