2 ಅಸ್ಥಿರಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಫೈಬೊನಾಕಿ ಅನುಕ್ರಮವನ್ನು ಮುದ್ರಿಸಿ


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

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

“2 ಅಸ್ಥಿರಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಫೈಬೊನಾಕಿ ಅನುಕ್ರಮವನ್ನು ಮುದ್ರಿಸು” ಎಂಬ ಸಮಸ್ಯೆಯು ನೀವು ಫೈಬೊನಾಕಿ ಅನುಕ್ರಮವನ್ನು ಮುದ್ರಿಸಬೇಕಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ ಆದರೆ ಕೇವಲ 2 ಅಸ್ಥಿರಗಳನ್ನು ಬಳಸುವ ಮಿತಿ ಇದೆ.

ಉದಾಹರಣೆ

2 ಅಸ್ಥಿರಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಫೈಬೊನಾಕಿ ಅನುಕ್ರಮವನ್ನು ಮುದ್ರಿಸಿ

n = 5
0 1 1 2 3 5

ವಿವರಣೆ

Sequ ಟ್ಪುಟ್ ಅನುಕ್ರಮವು ಫೈಬೊನಾಕಿ ಸರಣಿಯ ಮೊದಲ ಐದು ಅಂಶಗಳನ್ನು ಹೊಂದಿದೆ.

ಅಪ್ರೋಚ್

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

ನಾವು ಯೋಚಿಸಬಹುದು ಡೈನಾಮಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್/ ಸಮಸ್ಯೆಗೆ ಜ್ಞಾಪಕ. ವಿಧಾನವು ಖಂಡಿತವಾಗಿಯೂ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಕಡಿಮೆ ಮಾಡುತ್ತದೆ. ಘಾತೀಯ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ರೇಖೀಯ ಸಮಯದ ಸಂಕೀರ್ಣತೆಗೆ ಇಳಿಸಲಾಗುತ್ತದೆ. ಆದರೆ ಈ ವಿಧಾನವು ಇನ್ನೂ ನಮಗೆ ರೇಖೀಯ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆಯ ಅಗತ್ಯವಿದೆ. ಈ ಜಾಗದ ಸಂಕೀರ್ಣತೆಯನ್ನು ನಾವು ಮತ್ತಷ್ಟು ಕಡಿಮೆ ಮಾಡಬೇಕಾಗಿದೆ. ನಾವು ಏನು ಮಾಡಬಹುದೆಂಬುದನ್ನು ಅತ್ಯುತ್ತಮವಾಗಿಸಲು ಪ್ರಯತ್ನಿಸುತ್ತೇವೆ ಡೈನಾಮಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ವಿಧಾನ.

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

ಕೋಡ್

2 ಅಸ್ಥಿರಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಫೈಬೊನಾಕಿ ಅನುಕ್ರಮವನ್ನು ಮುದ್ರಿಸಲು ಸಿ ++ ಕೋಡ್

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

int main()
{
    int n;cin>>n;
    int last = 1, lastToLast = 0;
    if(n>=0)
        cout<<lastToLast<<" ";
    if(n>=1)
        cout<<last<<" ";
    for(int i=2;i<=n;i++){
        int cur = last + lastToLast;
        cout<<cur<<" ";
        lastToLast = last;
        last = cur;
    }
}
5
0 1 1 2 3 5

2 ಅಸ್ಥಿರಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಫೈಬೊನಾಕಿ ಅನುಕ್ರಮವನ್ನು ಮುದ್ರಿಸಲು ಜಾವಾ ಕೋಡ್

import java.util.*;
class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    	int last = 1, lastToLast = 0;
      if(n>=0)
          System.out.print(lastToLast+" ");
      if(n>=1)
          System.out.print(last+" ");
      for(int i=2;i<=n;i++){
          int cur = last + lastToLast;
          System.out.print(cur+" ");
          lastToLast = last;
          last = cur;
      }
  	}
}
5
0 1 1 2 3 5

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

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

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

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

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