בעיית רעפים


רמת קושי קַל
נשאל לעתים קרובות מעבדות חדשנות 24 * 7 אמזון בעברית דה שו מסירה פייפאל
תכנות דינמי פיבונאצ'י מתמטיקה

הצהרת בעיה

"בעיית הרעפים" קובעת שיש לך רשת בגודל 2 x N ואריח בגודל 2 x 1. לכן, מצא את מספר הדרכים לרצף את הרשת הנתונה.

דוגמה

3
2

הסבר: בעיית רעפים

גישה לבעיית אריחים

אנו יכולים לפתור בעיה זו באמצעות רקורסיה. בבעיה, עלינו לרצף רשת של 2xN. אז זה יהיה תלוי במספר הדרכים לרצפת רשת בגודל 2x (N-1) ו- 2x (N-2). איך נוכל לומר זאת?

הסיבה היא פשוטה, במקום לחשוב לרצף את העמודה הראשונה ברשת ואז השנייה וכן הלאה. אנו מנסים לרצף תחילה את העמודה ה- N, לאחר מכן את N-1 וכן הלאה. בדרך זו דעו שאם נציב אריח 2 × 1 על העמודה ה N. הבעיה מומרת כעת לבעיית משנה של רשת רעפים בגודל 2x (N-1). באופן דומה, אם אנו מציבים שני אריחים של 1 × 2 ברשת 2xN, הבעיה מומרת לגודל 2x (N-2). כעת אם נוכל איכשהו לפתור את הבעיות הללו, נוכל לקבל את התשובה.

נניח כי אריח [N] מציין את מספר הדרכים לרצף רשת בגודל 2XN. לאחר מכן אריח [N] = אריח [N-1] + אריח [N-2]. באופן דומה, אריח [N-1] = אריח [N-2] + אריח [N-3]. לפיכך הבעיה מראה תשתית אופטימלית. עדיף לאחסן את התוצאה עבור אריח [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

ניתוח מורכבות

מורכבות זמן

O (N) כי על מנת לפתור את הבעיה של רשת רעפים 2xN. אתה צריך לחשב את התשובה עבור רשת רעפים בגודל קטן מ- N.

מורכבות בחלל

עַל), מכיוון שאנו שומרים את התוצאה עבור כל תת-הבעיות ולכן המרחב הנדרש הוא ליניארי.

הערה: אנו יכולים לפתור את הבעיה במרחב O (1) ובזמן O (N), באמצעות שני משתנים last and secondLast אשר יאחסנו את הערכים של אריח [N-1] ושל אריח [N-2] בהתאמה. עכשיו הנוכחי = האחרון + השני האחרון ואז עדכן את ערכי המשתנים בהתאם. הנוסחה הרקורסיבית זהה לזו של מספר פיבונאצ'י Nth. אז אתה יכול גם לפתור בעיה זו זמן O (יומן N) באמצעות הנוסחה כדי למצוא מספרי פיבונאצ'י.