ಟೈಲಿಂಗ್ ಸಮಸ್ಯೆ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ 24 * 7 ಇನ್ನೋವೇಶನ್ ಲ್ಯಾಬ್‌ಗಳು ಅಮೆಜಾನ್ ಡಿಇ ಶಾ ದೆಹಲಿ ಪೇಪಾಲ್
ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಫಿಬೊನಾಕಿ ಮಠ

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

ನೀವು ಗಾತ್ರದ ಗ್ರಿಡ್ ಹೊಂದಿದ್ದೀರಿ ಎಂದು “ಟೈಲಿಂಗ್ ಸಮಸ್ಯೆ” ಹೇಳುತ್ತದೆ 2 x ಎನ್ ಮತ್ತು ಗಾತ್ರದ ಟೈಲ್ 2 x 1. ಆದ್ದರಿಂದ, ಕೊಟ್ಟಿರುವ ಗ್ರಿಡ್ ಅನ್ನು ಟೈಲ್ ಮಾಡುವ ಮಾರ್ಗಗಳ ಸಂಖ್ಯೆಯನ್ನು ಹುಡುಕಿ.

ಉದಾಹರಣೆ

3
2

ವಿವರಣೆ: ಟೈಲಿಂಗ್ ಸಮಸ್ಯೆ

ಟೈಲಿಂಗ್ ಸಮಸ್ಯೆಗೆ ಅನುಸಂಧಾನ

ಪುನರಾವರ್ತನೆಯನ್ನು ಬಳಸಿಕೊಂಡು ನಾವು ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಬಹುದು. ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಾವು 2xN ನ ಗ್ರಿಡ್ ಅನ್ನು ಟೈಲ್ ಮಾಡಬೇಕಾಗಿದೆ. ಆದ್ದರಿಂದ ಇದು 2x (N-1) ಮತ್ತು 2x (N-2) ಗಾತ್ರದ ಗ್ರಿಡ್ ಅನ್ನು ಟೈಲ್ ಮಾಡುವ ಮಾರ್ಗಗಳ ಸಂಖ್ಯೆಯನ್ನು ಅವಲಂಬಿಸಿರುತ್ತದೆ. ನಾವು ಅದನ್ನು ಹೇಗೆ ಹೇಳಬಹುದು?

ಕಾರಣ ಸರಳವಾಗಿದೆ, ಗ್ರಿಡ್‌ನಲ್ಲಿ ಮೊದಲ ಕಾಲಮ್ ಅನ್ನು ಟೈಲ್ ಮಾಡಲು ಯೋಚಿಸುವ ಬದಲು ಎರಡನೆಯದು ಮತ್ತು ಹೀಗೆ. ನಾವು ಮೊದಲು Nth ಕಾಲಮ್ ಅನ್ನು ಟೈಲ್ ಮಾಡಲು ಪ್ರಯತ್ನಿಸುತ್ತಿದ್ದೇವೆ, ನಂತರ N-1 ಮತ್ತು ಹೀಗೆ. N ನೇ ಕಾಲಂನಲ್ಲಿ ನಾವು 2 × 1 ಟೈಲ್ ಅನ್ನು ಇರಿಸಿದರೆ ಈ ರೀತಿ ತಿಳಿಯಿರಿ. ಸಮಸ್ಯೆಯನ್ನು ಈಗ 2x (N-1) ಗಾತ್ರದ ಟೈಲಿಂಗ್ ಗ್ರಿಡ್‌ನ ಉಪ-ಸಮಸ್ಯೆಯಾಗಿ ಪರಿವರ್ತಿಸಲಾಗಿದೆ. ಅಂತೆಯೇ, ನಾವು 1xN ಗ್ರಿಡ್‌ನಲ್ಲಿ ಎರಡು 2 × 2 ಅಂಚುಗಳನ್ನು ಇರಿಸಿದರೆ, ಸಮಸ್ಯೆಯನ್ನು 2x (N-2) ಗಾತ್ರಕ್ಕೆ ಪರಿವರ್ತಿಸಲಾಗುತ್ತದೆ. ಈಗ ನಾವು ಈ ಸಮಸ್ಯೆಗಳನ್ನು ಹೇಗಾದರೂ ಪರಿಹರಿಸಬಹುದಾದರೆ, ನಾವು ಉತ್ತರವನ್ನು ಪಡೆಯಬಹುದು.

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

ಟೈಲಿಂಗ್ ಸಮಸ್ಯೆ

ಕೋಡ್

ಟೈಲಿಂಗ್ ಸಮಸ್ಯೆಗೆ ಸಿ ++ ಕೋಡ್

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

int main(){
  int n;cin>>n;
  // create an array to store number of ways to tile a grid of size 2xi
  int tile[n+1];
  // base case
  tile[0] = 0; tile[1] = 1;
  for(int i=2;i<=n;i++)
    tile[i]  = tile[i-1] + tile[i-2]; // use recursive formula
  cout<<tile[n];
}
3
2

ಟೈಲಿಂಗ್ ಸಮಸ್ಯೆಗೆ ಜಾವಾ ಕೋಡ್

import java.util.*;

class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    // create an array to store number of ways to tile a grid of size 2xi
    int tile[] = new int[n+1];
    // base case
    tile[0] = 0; tile[1] = 1;
    for(int i=2;i<=n;i++)
      tile[i]  = tile[i-1] + tile[i-2]; // use recursive formula
    System.out.println(tile[n]);
  }
}
3
2

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

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

ಒ (ಎನ್), ಏಕೆಂದರೆ ಟೈಲಿಂಗ್ ಗ್ರಿಡ್ 2xN ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು. N ಗಿಂತ ಕಡಿಮೆ ಗಾತ್ರದ ಗ್ರಿಡ್ ಅನ್ನು ಟೈಲಿಂಗ್ ಮಾಡಲು ನೀವು ಉತ್ತರವನ್ನು ಲೆಕ್ಕ ಹಾಕಬೇಕು.

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

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

ಗಮನಿಸಿ: ಕೊನೆಯ ಮತ್ತು ಎರಡನೆಯ ಎರಡು ಅಸ್ಥಿರಗಳನ್ನು ಬಳಸುವ ಮೂಲಕ ನಾವು ಒ (1) ಸ್ಥಳ ಮತ್ತು ಒ (ಎನ್) ಸಮಯದಲ್ಲಿ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಬಹುದು, ಇದು ಕ್ರಮವಾಗಿ ಟೈಲ್ [ಎನ್ -1] ಮತ್ತು ಟೈಲ್ [ಎನ್ -2] ಮೌಲ್ಯಗಳನ್ನು ಸಂಗ್ರಹಿಸುತ್ತದೆ. ಈಗ ಕರೆಂಟ್ = ಲಾಸ್ಟ್ + ಸೆಕೆಂಡ್ ಲಾಸ್ಟ್ ಮತ್ತು ನಂತರ ಅಸ್ಥಿರ ಮೌಲ್ಯಗಳನ್ನು ನವೀಕರಿಸಿ. ಪುನರಾವರ್ತಿತ ಸೂತ್ರವು Nth Fibonacci ಸಂಖ್ಯೆಯಂತೆಯೇ ಇರುತ್ತದೆ. ಆದ್ದರಿಂದ ನೀವು ಫೈಬೊನಾಕಿ ಸಂಖ್ಯೆಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸೂತ್ರವನ್ನು ಬಳಸಿಕೊಂಡು ಒ (ಲಾಗ್ ಎನ್) ಸಮಯವನ್ನು ಸಹ ಪರಿಹರಿಸಬಹುದು.