Tiling ပြProbleနာ


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် 24 * 7 တီထွင်မှု Labs အမေဇုံ DE Shaw ဒေလီ PayPal က
Dynamic Programming Fibonacci သင်္ချာ

ပြProbleနာဖော်ပြချက်

“ Tiling Problem” ကသင်၏အရွယ်အစားဇယားကွက်ရှိသည်ဟုဖော်ပြသည် 2 x က N နှင့်အရွယ်အစားတစ် tile ကို X ကို 2 1 ။ ဒါကြောင့်ပေးထားသောဇယားကွက်ကို tile လုပ်ရန်နည်းလမ်းများစွာရှာပါ။

နမူနာ

3
2

ရှင်းလင်းချက်: Tiling ပြProbleနာ

Tiling ပြmနာအတွက်ချဉ်းကပ်နည်း

ကျွန်ုပ်တို့သည်ဤပြproblemနာကိုပြန်လည်အသုံးချခြင်းအားဖြင့်ဖြေရှင်းနိုင်သည်။ ပြtheနာမှာ 2xN ရှိတဲ့ဇယားကွက်တစ်ခုကိုကြွေပြားကပ်ဖို့လိုတယ်။ ထို့ကြောင့်၎င်းသည်အရွယ်အစား 2x (N-1) နှင့် 2x (N-2) အပြားကွက်ကွက်ကွက်ကွင်းကွက်များ၏အရေအတွက်ပေါ်တွင်မူတည်သည်။ ဒါကိုကျွန်ုပ်တို့ဘယ်လိုပြောနိုင်သလဲ။

အကြောင်းပြချက်မှာပထမ ဦး ဆုံးကော်လံကိုဒုတိယနေရာတွင်ထည့်ရန်စဉ်းစားမည့်အစားရိုးရှင်းပါသည်။ ကျနော်တို့ပထမ ဦး ဆုံး Nth ကော်လံ, ထို့နောက် N-1 tile ဖို့ကြိုးစားနေကြတယ်။ ဤနည်းဖြင့်ကျွန်ုပ်တို့သည် 2 × 1 tile ကို N th ကော်လံတွင်ထားပါက၊ ယခုပြproblemနာသည်အရွယ်အစား 2x (N-1) ၏ tiling grid ၏ပြsubနာတစ်ခုသို့ပြောင်းလဲသွားသည်။ အလားတူစွာကျွန်ုပ်တို့သည် 1x2 tiles နှစ်ခုကို 2xN ဇယားကွက်ထဲတွင်နေရာချပါကထိုပြproblemနာကို 2x (N-2) အရွယ်သို့ပြောင်းသည်။ ယခုကျွန်ုပ်တို့သည်ဤပြproblemsနာများကိုတစ်နည်းနည်းဖြင့်ဖြေရှင်းနိုင်လျှင်အဖြေရနိုင်သည်။

Tile [N] သည် 2XN အရွယ်ရှိ tile grid သို့သွားရန်နည်းလမ်းများစွာကိုဖော်ပြသည်ဆိုပါစို့။ ထိုအခါ Tile [N] = ကြွေပြား [N-1] + Tile [N-2]။ အလားတူပင်ကြွေပြား [N-1] = ကြွေပြား [N-2] + ကြွေပြား [N-3] ။ ထို့ကြောင့်ပြtheနာကအကောင်းဆုံးဖွဲ့စည်းတည်ဆောက်ပုံကိုပြသည်။ ရလဒ်ကို Tile [N-2] အတွက်သိမ်းဆည်းထားခြင်းက၎င်းကိုနှစ်ကြိမ်အသုံးပြုသောကြောင့်ဖြစ်သည်။ ရလဒ်ကိုကျွန်ုပ်တို့သိမ်းဆည်းပါက၊ ၎င်းသည်နှစ်ကြိမ်တွက်ချက်မည်မဟုတ်ဘဲအချိန်ရှုပ်ထွေးမှုကိုသိသိသာသာလျှော့ချလိမ့်မည်။ ထို့ကြောင့်ငါတို့သုံးပါလိမ့်မယ် Dynamic Programming ပြtheနာကိုဖြေရှင်းဖို့။

Tiling ပြProbleနာ

ကုဒ်

Tiling ပြforနာအတွက် C ++ Code

#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

Tiling ပြmနာအတွက် Java ကုဒ်

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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N)၊ ဘာဖြစ်လို့လဲဆိုတော့ 2xN tiling grid ပြtheနာကိုဖြေရှင်းနိုင်ဖို့ပါ။ tiling grid အတွက် N. ထက်နည်းသောအဖြေကိုသင်တွက်ချက်ရန်လိုအပ်သည်။

အာကာသရှုပ်ထွေးမှု

အို (N)ဘာဖြစ်လို့လဲဆိုတော့ကျွန်တော်တို့ subproblems အားလုံးအတွက်ရလဒ်ကိုသိုလှောင်ထားသည့်အတွက်လိုအပ်သောနေရာသည် linear ဖြစ်သည်။

မှတ်ချက်။ ။ T (N-1) နှင့် Tile [N-1] အသီးသီး၏တန်ဖိုးများကိုသိမ်းဆည်းမည့်နောက်ဆုံးနှင့် secondLast နှစ်ခုကို သုံး၍ O (2) space နှင့် O (N) အချိန်၌ပြtheနာကိုကျွန်ုပ်တို့ဖြေရှင်းနိုင်သည်။ အခု current = last + secondLast ပြီးရင် variable ရဲ့တန်ဖိုးကိုလိုက်ပြောင်းပါ။ recursive ဖော်မြူလာသည် Nth Fibonacci နံပါတ်နှင့်အတူတူဖြစ်သည်။ ဒီတော့မင်းကဒီပြproblemနာကို O (log N) အချိန်မှာဖီဘိုနာချီဂဏန်းတွေရှာဖို့ပုံသေနည်းကိုသုံးပြီးဖြေရှင်းနိုင်တယ်။