ನ್ಯೂಮನ್-ಕಾನ್ವೇ ಅನುಕ್ರಮ


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

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

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

ಉದಾಹರಣೆ

n = 6
4
n = 10
6

ವಿವರಣೆ

Output ಟ್ಪುಟ್ ಅಂಶಗಳು ನ್ಯೂಮನ್-ಕಾನ್ವೇ ಅನುಕ್ರಮದ ಆರನೇ ಮತ್ತು ಹತ್ತನೇ ಅಂಶವನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತವೆ. Output ಟ್ಪುಟ್ ಸಂಪೂರ್ಣವಾಗಿ ಸರಿಯಾಗಿದೆ.

ನ್ಯೂಮನ್-ಕಾನ್ವೇ ಅನುಕ್ರಮವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಅನುಸಂಧಾನ

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

ನ್ಯೂಮನ್-ಕಾನ್ವೇ ಅನುಕ್ರಮ

 

ಈಗ ನಾವು ಅನುಕ್ರಮದಿಂದ nth ಸಂಖ್ಯೆಯನ್ನು ಮುದ್ರಿಸಬೇಕಾಗಿದೆ. ಎರಡು ವಿಧಾನಗಳು ಇರಬಹುದು ಏಕೆಂದರೆ ಅನುಕ್ರಮದ ಪ್ರತಿಯೊಂದು ಅಂಶವು ಹಿಂದೆ ಉತ್ಪತ್ತಿಯಾದ ಅಂಶಗಳ ಮೇಲೆ ಅವಲಂಬಿತವಾಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, ಒಂದು ಮಾರ್ಗವಾಗಿದೆ ಪುನರಾವರ್ತನೆ ಆದರೆ ಈ ವಿಧಾನವು ಅಸಮರ್ಥವಾಗಿದೆ. ಏಕೆಂದರೆ ನಾವು ಸರಣಿಯಲ್ಲಿ ಹೆಚ್ಚಿನ ಪದಗಳನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುತ್ತಲೇ ಇರುವುದರಿಂದ ನಾವು ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ ಹಲವು ಬಾರಿ ಪರಿಹರಿಸುತ್ತೇವೆ. ಹೀಗಾಗಿ ನಾವು ಹೆಚ್ಚಿನ ಸಂಖ್ಯೆಯ ಗಣನೆಗಳನ್ನು ನಿರ್ವಹಿಸಬೇಕಾಗಿದೆ. ಆದ್ದರಿಂದ ಮರು ಲೆಕ್ಕಾಚಾರದ ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು. ನಾವು ಬಳಸಬಹುದು ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಇದು ಅಲ್ಗಾರಿದಮ್ನ ದಕ್ಷತೆಯನ್ನು ಹೆಚ್ಚು ಸುಧಾರಿಸುತ್ತದೆ. ಪ್ರಸ್ತುತ, ಪುನರಾವರ್ತಿತ ಅಲ್ಗಾರಿದಮ್ಗೆ ಘಾತೀಯ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯ ಅಗತ್ಯವಿದೆ. ಒಂದೇ ಸ್ಥಿತಿ ಇರುವುದರಿಂದ ನಾವು ಅದನ್ನು ರೇಖೀಯ ಪರಿಹಾರಕ್ಕೆ ಇಳಿಸಬಹುದು.

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

ಕೋಡ್

N ನೇ ನ್ಯೂಮನ್-ಕಾನ್ವೇ ಸೀಕ್ವೆನ್ಸ್ ಅಂಶವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಿ ++ ಕೋಡ್

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

int main(){
  // element 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]];
  cout<<dp[n];
}
6
4

N ನೇ ನ್ಯೂಮನ್-ಕಾನ್ವೇ ಸೀಕ್ವೆನ್ಸ್ ಅಂಶವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಜಾವಾ ಕೋಡ್

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    // eleemnt 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]];
    System.out.print(dp[n]);
  }
}
6
4

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

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

ಒ (ಎನ್), ಏಕೆಂದರೆ ನಾವು ಅನುಕ್ರಮದ n ನೇ ಅಂಶವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಒಂದೇ ಲೂಪ್ ಅನ್ನು ಓಡಿಸಿದ್ದೇವೆ. ಹೀಗಾಗಿ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿರುತ್ತದೆ.

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

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

ಉಲ್ಲೇಖಗಳು