Πρόβλημα πλακιδίων


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις 24 * 7 Εργαστήρια Καινοτομίας αμαζόνα DE Shaw Δελχί PayPal
Δυναμικός προγραμματισμός Fibonacci μαθηματικά

Δήλωση προβλήματος

Το "Πρόβλημα πλακιδίων" δηλώνει ότι έχετε ένα πλέγμα μεγέθους 2 x Β και ένα πλακίδιο μεγέθους 2 x 1. Λοιπόν, βρείτε τον αριθμό των τρόπων για να τοποθετήσετε το συγκεκριμένο πλέγμα.

Παράδειγμα

3
2

Επεξήγηση: Πρόβλημα πλακιδίων

Προσέγγιση για πρόβλημα πλακιδίων

Μπορούμε να λύσουμε αυτό το πρόβλημα χρησιμοποιώντας την επανάληψη. Στο πρόβλημα, πρέπει να πλακιδώσουμε ένα πλέγμα 2xN. Έτσι θα εξαρτηθεί από τον αριθμό των τρόπων τοποθέτησης πλέγματος μεγέθους 2x (N-1) και 2x (N-2). Πώς μπορούμε να το πούμε αυτό;

Ο λόγος είναι απλός, αντί να σκέφτεστε να τοποθετήσετε την πρώτη στήλη στο πλέγμα και μετά τη δεύτερη και ούτω καθεξής. Προσπαθούμε να δημιουργήσουμε πρώτα τη στήλη Nth, μετά N-1 και ούτω καθεξής. Με αυτόν τον τρόπο ξέρετε ότι αν τοποθετήσουμε ένα πλακίδιο 2 × 1 στη Β 'στήλη. Το πρόβλημα μετατρέπεται σε δευτερεύον πρόβλημα πλακιδίων πλέγματος μεγέθους 2x (N-1). Ομοίως, αν τοποθετήσουμε δύο πλακίδια 1 × 2 σε πλέγμα 2xN, το πρόβλημα μετατρέπεται σε μέγεθος 2x (N-2). Τώρα αν μπορούμε να λύσουμε αυτά τα προβλήματα, μπορούμε να πάρουμε την απάντηση.

Ας υποθέσουμε ότι το πλακάκι [N] υποδηλώνει τον αριθμό των τρόπων τοποθέτησης πλακιδίων πλέγματος μεγέθους 2XN. Επειτα Πλακάκι [N] = Πλακάκι [N-1] + Πλακάκι [N-2]. Ομοίως, Πλακάκι [N-1] = Πλακάκι [N-2] + Πλακάκι [N-3]. Έτσι, το πρόβλημα δείχνει τη βέλτιστη υποδομή. Είναι καλύτερο να αποθηκεύσετε το αποτέλεσμα για Tile [N-2] επειδή χρησιμοποιείται δύο φορές. Εάν αποθηκεύσουμε το αποτέλεσμα, δεν θα το υπολογίσουμε δύο φορές και θα μειώσουμε σημαντικά την πολυπλοκότητα του χρόνου. Έτσι θα χρησιμοποιήσουμε Δυναμικός προγραμματισμός για να λυθει το προβλημα.

Πρόβλημα πλακιδίων

Κώδικας

Κωδικός 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

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

ΕΠΙ), γιατί για την επίλυση του προβλήματος πλακάκια πλέγματος 2xN. Πρέπει να έχετε υπολογίσει την απάντηση για πλακάκια πλέγματος μεγέθους μικρότερο από Ν.

Διαστημική πολυπλοκότητα

ΕΠΙ), γιατί αποθηκεύουμε το αποτέλεσμα για όλα τα υποπροβλήματα και έτσι ο απαιτούμενος χώρος είναι γραμμικός.

Σημείωση: Μπορούμε να λύσουμε το πρόβλημα στο διάστημα O (1) και στο χρόνο O (N), χρησιμοποιώντας δύο μεταβλητές τελευταίο και δεύτερο τελευταίο που θα αποθηκεύσουν τις τιμές των πλακιδίων [N-1] και πλακιδίων [N-2] αντίστοιχα. Τώρα τρέχουσα = τελευταία + δευτερόλεπτο Τελευταία και στη συνέχεια ενημερώστε τις τιμές των μεταβλητών ανάλογα. Ο αναδρομικός τύπος είναι ίδιος με αυτόν του Nth Fibonacci number. Έτσι μπορείτε επίσης να λύσετε αυτό το πρόβλημα O (log N) χρόνο χρησιμοποιώντας τον τύπο για να βρείτε αριθμούς Fibonacci.