టైలింగ్ సమస్య


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది 24 * 7 ఇన్నోవేషన్ ల్యాబ్స్ అమెజాన్ డిఇ షా Delhivery పేపాల్
డైనమిక్ ప్రోగ్రామింగ్ ఫైబొనాక్సీ మఠం

సమస్యల నివేదిక

“టైలింగ్ సమస్య” మీకు పరిమాణ గ్రిడ్ ఉందని పేర్కొంది 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] కోసం ఫలితాన్ని నిల్వ చేయడం మంచిది, ఎందుకంటే ఇది రెండుసార్లు ఉపయోగించబడుతోంది. మేము ఫలితాన్ని నిల్వ చేస్తే, మేము దానిని రెండుసార్లు లెక్కించము మరియు సమయ సంక్లిష్టతను గణనీయంగా తగ్గిస్తాము. ఈ విధంగా మేము ఉపయోగిస్తాము డైనమిక్ ప్రోగ్రామింగ్ సమస్యను పరిష్కరించడానికి.

టైలింగ్ సమస్య

కోడ్

టైలింగ్ సమస్య కోసం సి ++ కోడ్

#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 సంఖ్యకు సమానం. కాబట్టి మీరు ఫైబొనాక్సీ సంఖ్యలను కనుగొనడానికి ఫార్ములా ఉపయోగించి ఓ (లాగ్ ఎన్) సమయాన్ని కూడా పరిష్కరించవచ్చు.