Սալիկապատման խնդիր  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են 24 * 7 նորարարության լաբորատորիաներ Amazon ԴԵ Շոուն Առաքում PayPal
Դինամիկ ծրագրավորում Fibonacci Մաթեմատիկա

Խնդիրի հայտարարություն  

«Սալիկապատման խնդիրը» նշում է, որ դուք ունեք չափի ցանց 2 x N և չափի սալիկ 2 x 1: Այսպիսով, գտնեք տրված ցանցը սալիկապատելու եղանակների քանակը:

Օրինակ  

3
2

Բացատրությունը. Սալիկապատման խնդիրPin

Մոտեցում սալիկապատման խնդրին  

Մենք կարող ենք լուծել այս խնդիրը `օգտագործելով ռեկուրսիան: Խնդիրի մեջ մենք պետք է սալիկապատենք 2xN ցանց: Այսպիսով, դա կախված կլինի 2x (N-1) և 2x (N-2) չափերի ցանցը սալիկապատելու եղանակների քանակից: Ինչպե՞ս կարող ենք դա ասել:

Պատճառը պարզ է. Փոխարենը մտածել առաջին սյունը ցանցում սալիկապատել, ապա երկրորդ և այլն: Մենք փորձում ենք նախ սալիկապատել N- րդ սյունակը, ապա N-1 և այլն: Այս եղանակով գիտենք, որ եթե մենք 2-րդ 1 սալիկ տեղադրենք N սյունակի վրա: Խնդիրն այժմ վերածվում է 2x (N-1) չափի սալիկապատման ցանցի ենթախնդրի: Նմանապես, եթե մենք 1xN ցանցում տեղադրենք 2 × 2 սալիկ, խնդիրը վերածվում է 2x (N-2) չափի: Հիմա, եթե կարողանանք ինչ-որ կերպ լուծել այս խնդիրները, մենք կարող ենք ստանալ պատասխանը:

Ասենք, որ Սալիկը [N] նշանակում է 2XN չափի ցանցը սալիկապատելու եղանակների քանակը: Հետո Կղմինդր [N] = Կղմինդր [N-1] + Կղմինդր [N-2], Նմանապես, Սալիկ [N-1] = Կղմինդր [N-2] + Կղմինդր [N-3]: Այսպիսով, խնդիրը ցույց է տալիս օպտիմալ ենթակառուցվածք: Ավելի լավ է արդյունքը պահել Սալիկի համար [N-2], քանի որ այն օգտագործվում է երկու անգամ: Եթե ​​արդյունքը պահենք, ապա այն երկու անգամ չենք հաշվարկի և զգալիորեն կնվազեցնի ժամանակի բարդությունը: Այսպիսով մենք կօգտագործենք Դինամիկ ծրագրավորում խնդիրը լուծելու համար:

Տես նաեւ,
Fibonacci համարները

Սալիկապատման խնդիրPin

Կոդ  

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

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

Բարդության վերլուծություն  

Timeամանակի բարդություն

ՎՐԱ), քանի որ 2xN ցանցի սալիկապատման խնդիրը լուծելու համար: Դուք պետք է հաշվարկեք N- ից փոքր չափի սալիկապատման ցանցի պատասխանը:

Տիեզերական բարդություն

ՎՐԱ), քանի որ մենք պահպանում ենք արդյունքը բոլոր ենթածրագրերի համար, ուստի պահանջվող տարածքը գծային է:

Նշում. Մենք կարող ենք խնդիրը լուծել O (1) տարածության և O (N) ժամանակներում, օգտագործելով վերջին և երկրորդ վերջին փոփոխականները, որոնք կպահպանեն համապատասխանաբար սալիկի [N-1] և սալիկի [N-2] արժեքները: Այժմ ընթացիկ = վերջին + երկրորդՎերջին և համապատասխանաբար թարմացնել փոփոխականների արժեքները: Ռեկուրսիվ բանաձևը նույնն է, ինչ Nth- ի Ֆիբոնաչիի համարը: Այսպիսով, դուք կարող եք նաև լուծել այս խնդիրը O (տեղեկամատյան N) ժամանակը ՝ օգտագործելով բանաձև ՝ Ֆիբոնաչիի թվերը գտնելու համար: