ටයිල් කිරීමේ ගැටලුව


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ 24 * 7 නවෝත්පාදන විද්‍යාගාර ඇමේසන් ඩී ෂෝ දිල්ලි පේපෑල්
ගතික වැඩසටහන්කරණය ෆිබොනාච්චි ගණිතය

ගැටළු ප්රකාශය

“ටයිල් කිරීමේ ගැටලුව” සඳහන් කරන්නේ ඔබට ප්‍රමාණයේ ජාලයක් ඇති බවයි 2 x එන් සහ ප්‍රමාණයේ ටයිල් එකක් 2 x 1 කි. එබැවින්, දී ඇති ජාලකය ටයිල් කිරීමට ක්‍රම ගණන සොයා ගන්න.

උදාහරණයක්

3
2

පැහැදිලි කිරීම: ටයිල් කිරීමේ ගැටලුව

ටයිල් කිරීමේ ගැටලුව සඳහා ප්‍රවේශය

පුනරාවර්තනය භාවිතා කිරීමෙන් අපට මෙම ගැටළුව විසඳා ගත හැකිය. ගැටලුවේදී, අපට 2xN ජාලයක් ටයිල් කළ යුතුය. එබැවින් එය 2x (N-1) සහ 2x (N-2) ප්‍රමාණයේ ජාලක ටයිල් කිරීමේ ක්‍රම ගණන මත රඳා පවතී. අපි කොහොමද ඒක කියන්නේ?

හේතුව සරල ය, පළමු තීරුව ග්‍රිඩ් ටයිල් කිරීමට සිතීම වෙනුවට දෙවන හා එසේ ය. අපි පළමුව N වන තීරුව ටයිල් කිරීමට උත්සාහ කරමු, පසුව N-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] සඳහා ප්‍රති result ලය ගබඩා කිරීම වඩා හොඳය, මන්ද එය දෙවරක් භාවිතා වන බැවිනි. අපි ප්‍රති result ලය ගබඩා කරන්නේ නම්, අපි එය දෙවරක් ගණනය නොකරන අතර කාල සංකීර්ණතාව සැලකිය යුතු ලෙස අඩු කරන්නෙමු. මේ අනුව අපි භාවිතා කරමු ගතික වැඩසටහන්කරණය ගැටලුව විසඳීමට.

ටයිල් කිරීමේ ගැටලුව

කේතය

ටයිල් කිරීමේ ගැටළුව සඳහා සී ++ කේතය

#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 ට වඩා අඩු ප්‍රමාණයේ ග්‍රිල් ටයිල් කිරීම සඳහා ඔබ පිළිතුර ගණනය කළ යුතුය.

අභ්‍යවකාශ සංකීර්ණතාව

මත), මන්දයත් අපි සියලු උපප්‍රශ්න සඳහා ප්‍රති result ලය ගබඩා කර ඇති නිසා අවශ්‍ය අවකාශය රේඛීය වේ.

සටහන: අවසාන හා දෙවන විචල්‍යයන් දෙකක් භාවිතා කිරීමෙන් අපට O (1) අවකාශයේ සහ O (N) වේලාව තුළ ගැටළුව විසඳා ගත හැකි අතර එමඟින් පිළිවෙලින් ටයිල් [N-1] සහ ටයිල් [N-2] හි අගයන් ගබඩා වේ. දැන් current = last + secondLast ඉන්පසු විචල්‍යයන්ගේ අගයන් ඒ අනුව යාවත්කාලීන කරන්න. පුනරාවර්තන සූත්‍රය Nth Fibonacci අංකයට සමාන වේ. එබැවින් ඔබට ෆිබොනාච්චි අංක සොයා ගැනීම සඳහා සූත්‍රය භාවිතා කරමින් O (ලොග් එන්) කාලයද විසඳිය හැකිය.