டைலிங் சிக்கல்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது 24 * 7 கண்டுபிடிப்பு ஆய்வகங்கள் அமேசான் டி.இ ஷா Delhivery பேபால்
டைனமிக் புரோகிராமிங் பிபோனச்சி கணித

சிக்கல் அறிக்கை

“டைலிங் சிக்கல்” உங்களிடம் அளவு கட்டம் இருப்பதாகக் கூறுகிறது 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) அளவுக்கு மாற்றப்படுகிறது. இப்போது நாம் எப்படியாவது இந்த பிரச்சினைகளை தீர்க்க முடிந்தால், அதற்கான பதிலைப் பெறலாம்.

டைல் [என்] 2 எக்ஸ்என் அளவு கட்டத்தை டைல் செய்வதற்கான வழிகளின் எண்ணிக்கையைக் குறிக்கிறது என்று சொல்லலாம். பிறகு ஓடு [N] = ஓடு [N-1] + ஓடு [N-2]. இதேபோல், ஓடு [N-1] = ஓடு [N-2] + ஓடு [N-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 ஐ விட குறைவான அளவு டைலிங் கட்டத்திற்கான பதிலை நீங்கள் கணக்கிட்டிருக்க வேண்டும்.

விண்வெளி சிக்கலானது

ஓ (என்), ஏனென்றால் எல்லா துணை சிக்கல்களுக்கும் நாம் முடிவை சேமித்து வருகிறோம், இதனால் தேவையான இடம் நேரியல் ஆகும்.

குறிப்பு: கடைசி மற்றும் இரண்டாவது கடைசி இரண்டு மாறிகள் பயன்படுத்துவதன் மூலம் O (1) இடம் மற்றும் O (N) நேரத்தில் சிக்கலை தீர்க்க முடியும், இது முறையே டைல் [N-1] மற்றும் டைல் [N-2] இன் மதிப்புகளை சேமிக்கும். இப்போது நடப்பு = கடைசி + வினாடி கடைசியாக மாறிகளின் மதிப்புகளை அதற்கேற்ப புதுப்பிக்கவும். சுழல்நிலை சூத்திரம் Nth Fibonacci எண்ணைப் போன்றது. எனவே ஃபைபோனச்சி எண்களைக் கண்டுபிடிக்க சூத்திரத்தைப் பயன்படுத்தி O (log N) நேரத்தையும் நீங்கள் தீர்க்கலாம்.