ਟਾਈਲਾਂ ਦੀ ਸਮੱਸਿਆ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ 24 * 7 ਇਨੋਵੇਸ਼ਨ ਲੈਬ ਐਮਾਜ਼ਾਨ ਡੀਈ ਸ਼ਾ ਦਿੱਲੀ ਵਾਸੀ ਪੇਪਾਲ
ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ ਫਿਬਾਗਣੀ ਗਣਿਤ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

“ਟਾਇਲਿੰਗ ਦੀ ਸਮੱਸਿਆ” ਦੱਸਦੀ ਹੈ ਕਿ ਤੁਹਾਡੇ ਕੋਲ ਅਕਾਰ ਦਾ ਗਰਿੱਡ ਹੈ 2 ਐਕਸ ਐਨ ਅਤੇ ਅਕਾਰ ਦਾ ਟਾਈਲ 2 x 1 ਇਸ ਲਈ, ਦਿੱਤੇ ਗਏ ਗਰਿੱਡ ਨੂੰ ਟਾਇਲ ਕਰਨ ਦੇ waysੰਗਾਂ ਦੀ ਗਿਣਤੀ ਕਰੋ.

ਉਦਾਹਰਨ

3
2

ਸਪਸ਼ਟੀਕਰਨ: ਟਾਈਲਾਂ ਦੀ ਸਮੱਸਿਆ

ਟਾਈਲਾਂ ਦੀ ਸਮੱਸਿਆ ਲਈ ਪਹੁੰਚ

ਅਸੀਂ ਦੁਹਰਾਓ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਇਸ ਸਮੱਸਿਆ ਦਾ ਹੱਲ ਕਰ ਸਕਦੇ ਹਾਂ. ਸਮੱਸਿਆ ਵਿੱਚ, ਸਾਨੂੰ 2xN ਦੀ ਇੱਕ ਗਰਿੱਡ ਟਾਇਲ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਇਸ ਲਈ ਇਹ ਆਕਾਰ 2x (N-1) ਅਤੇ 2x (N-2) ਦੇ ਗਰਿੱਡ ਨੂੰ ਟਾਇਲ ਕਰਨ ਦੇ ਤਰੀਕਿਆਂ ਦੀ ਗਿਣਤੀ 'ਤੇ ਨਿਰਭਰ ਕਰੇਗਾ. ਅਸੀਂ ਇਹ ਕਿਵੇਂ ਕਹਿ ਸਕਦੇ ਹਾਂ?

ਕਾਰਨ ਸਧਾਰਣ ਹੈ, ਗਰਿੱਡ ਵਿਚ ਪਹਿਲੇ ਕਾਲਮ ਨੂੰ ਫਿਰ ਟਾਈਲ ਕਰਨ ਦੀ ਸੋਚਣ ਦੀ ਬਜਾਏ ਦੂਸਰਾ ਅਤੇ ਹੋਰ. ਅਸੀਂ ਪਹਿਲਾਂ ਨੌਵਾਂ ਕਾਲਮ, ਫਿਰ ਐਨ -1 ਅਤੇ ਇਸ ਤਰਾਂ ਹੋਰ ਟਾਈਲਾਂ ਲਗਾਉਣ ਦੀ ਕੋਸ਼ਿਸ਼ ਕਰ ਰਹੇ ਹਾਂ. ਇਸ ਤਰੀਕੇ ਨਾਲ ਜਾਣੋ ਕਿ ਜੇ ਅਸੀਂ ਐਨ ਥਰੈਮ ਕਾਲਮ 'ਤੇ 2 × 1 ਟਾਈਲ ਲਗਾਉਂਦੇ ਹਾਂ. ਸਮੱਸਿਆ ਨੂੰ ਹੁਣ ਅਕਾਰ 2x (N-1) ਦੇ ਟਾਇਲਿੰਗ ਗਰਿੱਡ ਦੀ ਉਪ-ਸਮੱਸਿਆ ਵਿੱਚ ਬਦਲ ਦਿੱਤਾ ਗਿਆ ਹੈ. ਇਸੇ ਤਰ੍ਹਾਂ, ਜੇ ਅਸੀਂ 1xN ਗਰਿੱਡ ਵਿੱਚ ਦੋ 2 × 2 ਟਾਈਲਾਂ ਰੱਖਦੇ ਹਾਂ, ਤਾਂ ਸਮੱਸਿਆ ਨੂੰ 2x (N-2) ਅਕਾਰ ਵਿੱਚ ਬਦਲਿਆ ਜਾਂਦਾ ਹੈ. ਹੁਣ ਜੇ ਅਸੀਂ ਇਨ੍ਹਾਂ ਸਮੱਸਿਆਵਾਂ ਨੂੰ ਕਿਸੇ ਤਰ੍ਹਾਂ ਹੱਲ ਕਰ ਸਕਦੇ ਹਾਂ, ਤਾਂ ਅਸੀਂ ਜਵਾਬ ਪ੍ਰਾਪਤ ਕਰ ਸਕਦੇ ਹਾਂ.

ਦੱਸ ਦੇਈਏ ਕਿ ਟਾਈਲ [ਐਨ] ਅਕਾਰ 2 ਐਕਸ ਐਨ ਦੇ ਗਰਿੱਡ ਟਾਇਲ ਕਰਨ ਦੇ ਤਰੀਕਿਆਂ ਦੀ ਸੰਕੇਤ ਕਰਦਾ ਹੈ. ਫਿਰ ਟਾਈਲ [ਐਨ] = ਟਾਈਲ [ਐਨ -1] + ਟਾਈਲ [ਐਨ -2]. ਇਸੇ ਤਰ੍ਹਾਂ, ਟਾਈਲ [N-1] = ਟਾਈਲ [N-2] + ਟਾਈਲ [N-3]. ਇਸ ਪ੍ਰਕਾਰ ਸਮੱਸਿਆ ਅਨੁਕੂਲ ructureਾਂਚਾ ਦਰਸਾਉਂਦੀ ਹੈ. ਨਤੀਜੇ ਨੂੰ ਟਾਈਲ [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 ਤੋਂ ਘੱਟ ਆਕਾਰ ਦੇ ਟਾਈਲਡ ਗਰਿੱਡ ਲਈ ਜਵਾਬ ਦੀ ਗਣਨਾ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਕਿਉਂਕਿ ਅਸੀਂ ਸਾਰੇ ਸਬ-ਪ੍ਰੇਸ਼ਾਨੀਆਂ ਲਈ ਨਤੀਜਾ ਸਟੋਰ ਕਰ ਰਹੇ ਹਾਂ ਅਤੇ ਇਸ ਤਰ੍ਹਾਂ ਲੋੜੀਂਦੀ ਜਗ੍ਹਾ ਰੇਖਿਕ ਹੈ.

ਨੋਟ: ਅਸੀਂ ਓ (1) ਸਪੇਸ ਅਤੇ ਓ (ਐਨ) ਸਮੇਂ ਵਿਚ, ਦੋ ਵੇਰੀਏਬਲ ਆਖਰੀ ਅਤੇ ਸੈਕਿੰਡ ਲੈਸਟ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਸਮੱਸਿਆ ਦਾ ਹੱਲ ਕਰ ਸਕਦੇ ਹਾਂ ਜੋ ਕ੍ਰਮਵਾਰ ਟਾਈਲ [ਐਨ -1] ਅਤੇ ਟਾਈਲ [ਐਨ -2] ਦੇ ਮੁੱਲ ਸਟੋਰ ਕਰੇਗੀ. ਹੁਣ ਮੌਜੂਦਾ = ਆਖਰੀ + ਸਕਿੰਟ ਪਿਛਲਾ ਅਤੇ ਫਿਰ ਇਸਦੇ ਅਨੁਸਾਰ ਵੇਰੀਏਬਲ ਦੇ ਮੁੱਲ ਨੂੰ ਅਪਡੇਟ ਕਰੋ. ਆਵਰਤੀ ਫਾਰਮੂਲਾ ਐਨ ਐਨ ਫਿਬੋਨਾਚੀ ਨੰਬਰ ਦੇ ਸਮਾਨ ਹੈ. ਇਸ ਲਈ ਤੁਸੀਂ ਫਿਬੋਨਾਚੀ ਨੰਬਰ ਲੱਭਣ ਲਈ ਫਾਰਮੂਲੇ ਦੀ ਵਰਤੋਂ ਕਰਦਿਆਂ ਇਸ ਸਮੱਸਿਆ ਨੂੰ ਓ (ਲੌਗ ਐਨ) ਨੂੰ ਵੀ ਹੱਲ ਕਰ ਸਕਦੇ ਹੋ.