टाइलिंग की समस्या


कठिनाई स्तर आसान
में अक्सर पूछा 24 * 7 इनोवेशन लैब्स वीरांगना डीई शॉ Delhivery पेपैल
गतिशील प्रोग्रामिंग फिबोनैकी मठ

समस्या का विवरण

"टाइलिंग समस्या" बताती है कि आपके पास आकार का एक ग्रिड है 2 एक्स एन और आकार की एक टाइल 2 X 1। तो, दिए गए ग्रिड को टाइल करने के तरीकों की संख्या का पता लगाएं।

उदाहरण

3
2

स्पष्टीकरण: टाइलिंग की समस्या

टाइलिंग समस्या के लिए दृष्टिकोण

हम पुनरावृत्ति का उपयोग करके इस समस्या को हल कर सकते हैं। समस्या में, हमें 2xN के एक ग्रिड को टाइल करने की आवश्यकता है। तो यह आकार 2x (N-1) और 2x (N-2) के टाइल ग्रिड के तरीकों की संख्या पर निर्भर करेगा। हम ऐसा कैसे कह सकते हैं?

इसका कारण सरल है, इसके बजाय ग्रिड में पहले कॉलम को टाइल करने के लिए सोचना और फिर दूसरा। हम पहले Nth कॉलम को टाइल करने की कोशिश कर रहे हैं, फिर N-1 इत्यादि। इस तरह से पता है कि अगर हम एन वें कॉलम पर 2 × 1 टाइल लगाते हैं। समस्या अब 2x (N-1) आकार के टाइलिंग ग्रिड की उप-समस्या में बदल गई है। इसी तरह, अगर हम 1xN ग्रिड में दो 2 × 2 टाइलें रखते हैं, तो समस्या 2x (N-2) के आकार में बदल जाती है। अब अगर हम किसी तरह इन समस्याओं को हल कर सकते हैं, तो हमें इसका जवाब मिल सकता है।

मान लें कि टाइल [N] आकार के टाइल ग्रिड के तरीकों की संख्या को दर्शाता है 2XN। फिर टाइल [N] = टाइल [N-१] + टाइल [N-२]। इसी तरह, टाइल [एन -1] = टाइल [एन -2] + टाइल [एन -3]। इस प्रकार समस्या इष्टतम सबस्ट्रक्चर को दर्शाती है। टाइल के लिए परिणाम को स्टोर करना बेहतर है [एन -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] के मूल्यों को संग्रहीत करेंगे। अब current = last + secondLast और फिर उसके अनुसार चर के मानों को अपडेट करें। पुनरावर्ती सूत्र Nth फाइबोनैचि संख्या के समान है। तो आप भी इस समस्या को हल कर सकते हैं O (लॉग एन) फार्म का उपयोग करके फाइबोनैचि संख्याओं को खोजने के लिए समय।