ನ್ಯೂಮನ್-ಶ್ಯಾಂಕ್ಸ್-ವಿಲಿಯಮ್ಸ್ ಅವಿಭಾಜ್ಯ


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

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

ನ್ಯೂಮನ್-ಶ್ಯಾಂಕ್ಸ್-ವಿಲಿಯಮ್ಸ್ ಅವಿಭಾಜ್ಯ (ಎನ್‌ಎಸ್‌ಡಬ್ಲ್ಯು ಅವಿಭಾಜ್ಯ) ಒಂದು ಅವಿಭಾಜ್ಯ ಸಂಖ್ಯೆಯಲ್ಲದೆ, ಈ ಕೆಳಗಿನ ಸೂತ್ರವನ್ನು ನೀಡಿದ ನಿರ್ದಿಷ್ಟ ರೂಪದಲ್ಲಿ ಪ್ರತಿನಿಧಿಸಬಹುದು:

ಆದ್ದರಿಂದ ನಾವು nth NSW ಅವಿಭಾಜ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು.

ಉದಾಹರಣೆ

n = 3
7

ವಿವರಣೆ

S0 = 1, S1 = 1, S2 = 2 * S1 + S0 = 2 + 1 = 3, S3 = 2 * S2 + S1 = 2 * 3 + 1 = 7

ಅಪ್ರೋಚ್

ಎನ್ಎಸ್ಡಬ್ಲ್ಯೂ ಅವಿಭಾಜ್ಯಗಳನ್ನು ಮೊರಿಸ್ ನ್ಯೂಮನ್, ಡೇನಿಯಲ್ ಶ್ಯಾಂಕ್ಸ್ ಮತ್ತು ಹಗ್ ಸಿ. ವಿಲಿಯಮ್ಸ್ ಅವರು 1981 ರಲ್ಲಿ ಚದರ ಕ್ರಮದೊಂದಿಗೆ ಸೀಮಿತ ಸರಳ ಗುಂಪುಗಳ ಅಧ್ಯಯನದ ಸಮಯದಲ್ಲಿ ವಿವರಿಸಿದರು.

ಮೊದಲ ಕೆಲವು ಎನ್‌ಎಸ್‌ಡಬ್ಲ್ಯು ಅವಿಭಾಜ್ಯಗಳು 7, 41, 239, 9369319, 63018038201,… (ಒಇಐಎಸ್‌ನಲ್ಲಿ ಅನುಕ್ರಮ ಎ 088165), ಸೂಚ್ಯಂಕಗಳಿಗೆ ಅನುಗುಣವಾಗಿ 3, 5, 7, 19, 29,… (ಒಇಐಎಸ್‌ನಲ್ಲಿ ಅನುಕ್ರಮ ಎ 005850). Wikipedia ವಿಕಿಪೀಡಿಯಾದಿಂದ ತೆಗೆದುಕೊಳ್ಳಲಾಗಿದೆ}

ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಮಗೆ ಕೇವಲ ಒಂದು ಸಂಖ್ಯೆ n ನೀಡಲಾಗಿದೆ, ಅದು ನಾವು nth NSW ಅವಿಭಾಜ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು ಎಂದು ಸೂಚಿಸುತ್ತದೆ. ಪುನರಾವರ್ತಿತ ಸಂಬಂಧವನ್ನು ಬಳಸಿಕೊಂಡು ನಾವು ಎನ್ಎಸ್ಡಬ್ಲ್ಯೂ ಅವಿಭಾಜ್ಯವನ್ನು ಕಾಣಬಹುದು.

ಮರುಕಳಿಸುವ ಸಂಬಂಧ

ನ್ಯೂಮನ್-ಶ್ಯಾಂಕ್ಸ್-ವಿಲಿಯಮ್ಸ್ ಅವಿಭಾಜ್ಯ

ಆದ್ದರಿಂದ n ನೇ NSW ಅವಿಭಾಜ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಒಬ್ಬರು ನಿಷ್ಕಪಟ ವಿಧಾನವನ್ನು ಬಳಸಬಹುದು. ನಿಷ್ಕಪಟ ವಿಧಾನಕ್ಕಾಗಿ, ಪ್ರತಿ ಎನ್ಎಸ್ಡಬ್ಲ್ಯೂ ಅವಿಭಾಜ್ಯವು ಕೊನೆಯ ಎನ್ಎಸ್ಡಬ್ಲ್ಯೂ ಅವಿಭಾಜ್ಯವನ್ನು ಅವಲಂಬಿಸಿರುತ್ತದೆ ಮತ್ತು ಕೊನೆಯ ಎನ್ಎಸ್ಡಬ್ಲ್ಯೂ ಅವಿಭಾಜ್ಯವನ್ನು ಅವಲಂಬಿಸಿರುತ್ತದೆ. ಆದ್ದರಿಂದ ನಾವು ಬಳಸಿಕೊಳ್ಳಬಹುದು ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್, ಅಲ್ಲಿ ನಾವು ಕೊನೆಯ ಎರಡು NSW ಅವಿಭಾಜ್ಯಗಳನ್ನು ಸಂಗ್ರಹಿಸಬಹುದು. ನಾವು ಕೊನೆಯ ಎರಡು ಎನ್‌ಎಸ್‌ಡಬ್ಲ್ಯು ಅವಿಭಾಜ್ಯಗಳನ್ನು ಉಳಿಸದಿದ್ದರೆ ಕಾರಣ. ನಾವು ಸಮಸ್ಯೆಯನ್ನು ಪುನರಾವರ್ತಿತ ಶೈಲಿಯಲ್ಲಿ ಪರಿಹರಿಸುತ್ತೇವೆ ಅದು ಘಾತೀಯ ಸಮಯದ ಸಂಕೀರ್ಣತೆಗೆ ಕಾರಣವಾಗುತ್ತದೆ. ಆದ್ದರಿಂದ ಪ್ರಸ್ತುತ ಘಾತೀಯ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ರೇಖೀಯ ಸಮಯದ ಸಂಕೀರ್ಣತೆಗೆ ತಗ್ಗಿಸಲು. ನಾವು ಈ ಮೌಲ್ಯಗಳನ್ನು ಜ್ಞಾಪಕದಲ್ಲಿಟ್ಟುಕೊಳ್ಳುತ್ತೇವೆ.

ಕೋಡ್

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

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

int main(){
  // nth NSW prime which is wanted
  int n;cin>>n;

  if(n == 0 || n == 1)
    cout<<1;
  else{
    int lastToLast = 1, last = 1;
    int cur;
    for(int i=2;i<=n;i++){
      cur = 2*last + lastToLast;
      lastToLast = last;
      last = cur;
    }
    cout<<cur;
  }
}
4
17

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

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    // nth NSW prime which is wanted
    int n = sc.nextInt();

    if(n == 0 || n == 1)
      System.out.print(1);
    else{
      int lastToLast = 1, last = 1;
      int cur = 0;
      for(int i=2;i<=n;i++){
        cur = 2*last + lastToLast;
        lastToLast = last;
        last = cur;
      }
      System.out.print(cur);
    }
    }
}
4
17

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

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

ಒ (ಎನ್), ನಾವು n ನೇ NSW ಅವಿಭಾಜ್ಯವನ್ನು ಕಂಡುಕೊಳ್ಳುವವರೆಗೆ ನಾವು ಲೂಪ್ ಮಾಡಬೇಕಾಗಿದೆ. ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿದೆ.

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

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