ٹائلنگ کا مسئلہ


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے 24 * 7 انوویشن لیبز ایمیزون ڈی ای شا دہلی پے پال
متحرک پروگرامنگ فیبوناکی ریاضی

مسئلہ یہ بیان

"ٹائلنگ کا مسئلہ" بیان کرتا ہے کہ آپ کے سائز کا ایک گرڈ ہے 2 ایکس این اور سائز کا ایک ٹائل 2 ایکس 1. لہذا ، دیئے ہوئے گرڈ کو ٹائل کرنے کے طریقے معلوم کریں۔

مثال کے طور پر

3
2

وضاحت: ٹائلنگ کا مسئلہ

ٹائلنگ دشواری کے ل Appro اپروچ

ہم تکرار کا استعمال کرکے اس مسئلے کو حل کر سکتے ہیں۔ پریشانی میں ، ہمیں 2xN گرڈ ٹائل کرنے کی ضرورت ہے۔ لہذا یہ سائز 2x (N-1) اور 2x (N-2) کے گرڈ کو ٹائل کرنے کے طریقوں کی تعداد پر منحصر ہوگا۔ ہم یہ کیسے کہہ سکتے ہیں؟

اس کی وجہ آسان ہے ، اس کے بجائے کہ پہلے کالم کو گرڈ میں ٹائل کرنے کے بارے میں سوچیں اور دوسرے نمبر پر۔ ہم پہلے نویں کالم کو ٹائل کرنے کی کوشش کر رہے ہیں ، پھر این -1 اور اسی طرح کی۔ اس طرح جانتے ہیں کہ اگر ہم N ویں کالم پر 2 × 1 ٹائل رکھتے ہیں۔ اس مسئلے کو اب سائز 2x (N-1) کے ٹائلنگ گرڈ کے ذیلی مسئلہ میں تبدیل کردیا گیا ہے۔ اسی طرح ، اگر ہم 1xN گرڈ میں دو 2 × 2 ٹائل رکھیں ، تو مسئلہ 2x (N-2) سائز میں تبدیل ہوجاتا ہے۔ اب اگر ہم ان مسائل کو کسی طرح حل کرسکتے ہیں تو ، ہم اس کا جواب حاصل کرسکتے ہیں۔

آئیے کہتے ہیں کہ ٹائل [N] سائز 2XN کے گرڈ کو ٹائل کرنے کے متعدد طریقوں کی نشاندہی کرتا ہے۔ پھر ٹائل [N] = ٹائل [N-1] + ٹائل [N-2]. اسی طرح ، ٹائل [N-1] = ٹائل [N-2] + ٹائل [N-3]۔ اس طرح مسئلہ زیادہ سے زیادہ ساخت کو ظاہر کرتا ہے۔ ٹائل [N-2] کے لئے نتیجہ ذخیرہ کرنا بہتر ہے کیونکہ یہ دو بار استعمال ہورہا ہے۔ اگر ہم نتیجہ ذخیرہ کرتے ہیں تو ، ہم اس کی دو مرتبہ حساب نہیں کریں گے اور وقت کی پیچیدگی کو نمایاں طور پر کم کردیں گے۔ اس طرح ہم استعمال کریں گے متحرک پروگرامنگ مسئلہ حل کرنے کے لئے.

ٹائلنگ کا مسئلہ

ضابطے

ٹائلنگ دشواری کا C ++ کوڈ

#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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N) ، کیونکہ ٹائلنگ گرڈ 2xN کے مسئلے کو حل کرنے کے ل.۔ آپ کو N سے کم سائز کے ٹائلنگ گرڈ کے ل the جواب کا حساب لگانا ہوگا۔

خلائی پیچیدگی

O (N)، کیونکہ ہم سب سب پریشیموں کے لئے نتیجہ اسٹور کر رہے ہیں اور اس طرح درکار جگہ لکیری ہے۔

نوٹ: ہم O (1) جگہ اور O (N) وقت میں ، آخری اور دوسرا آخری استعمال کرنے والے دو متغیرات کا استعمال کرکے مسئلہ حل کرسکتے ہیں جو بالترتیب ٹائل [N-1] اور ٹائل [N-2] کی قیمتوں کو محفوظ کرے گا۔ اب موجودہ = آخری + سیکنڈ آخری اور پھر اسی کے مطابق متغیر کی اقدار کو اپ ڈیٹ کریں۔ تکرار کرنے والا فارمولا وہی ہے جو Nth Fibonacci نمبر کی طرح ہے۔ لہذا آپ فیبونیکی نمبر تلاش کرنے کے لئے فارمولے کا استعمال کرتے ہوئے O (log N) وقت کو بھی اس مسئلے کو حل کرسکتے ہیں۔