ปัญหาการปูกระเบื้อง


ระดับความยาก สะดวกสบาย
ถามบ่อยใน ห้องทดลองนวัตกรรม 24 * 7 อเมซอน เดอชอว์ เดลี บัตรเครดิต/เดบิต หรือ PayPal
การเขียนโปรแกรมแบบไดนามิก ฟีโบนักชี คณิตศาสตร์

คำชี้แจงปัญหา

“ ปัญหาการปูกระเบื้อง” ระบุว่าคุณมีเส้นตารางขนาด 2 x น และกระเบื้องขนาด 2 x 1 ดังนั้นค้นหาจำนวนวิธีในการเรียงเส้นตารางที่กำหนด

ตัวอย่าง

3
2

คำอธิบาย: ปัญหาการปูกระเบื้อง

แนวทางสำหรับปัญหาการปูกระเบื้อง

เราสามารถแก้ปัญหานี้ได้โดยใช้การเรียกซ้ำ ในปัญหาเราต้องเรียงตาราง 2xN ดังนั้นจะขึ้นอยู่กับจำนวนวิธีในการเรียงตารางขนาด 2x (N-1) และ 2x (N-2) เราจะพูดอย่างนั้นได้อย่างไร?

เหตุผลนั้นง่ายมากแทนที่จะคิดที่จะเรียงคอลัมน์แรกในตารางจากนั้นที่สองไปเรื่อย ๆ เรากำลังพยายามไทล์คอลัมน์ Nth ก่อนแล้วตามด้วย N-1 และอื่น ๆ วิธีนี้จะรู้ว่าถ้าเราวางไทล์ 2 × 1 บนคอลัมน์ N ขณะนี้ปัญหาถูกแปลงเป็นปัญหาย่อยของตารางการปูกระเบื้องขนาด 2x (N-1) ในทำนองเดียวกันถ้าเราวางไพ่ 1 × 2 สองแผ่นในตาราง 2xN ปัญหาจะถูกแปลงเป็นขนาด 2x (N-2) ตอนนี้ถ้าเราสามารถแก้ปัญหาเหล่านี้ได้เราจะได้รับคำตอบ

สมมติว่า Tile [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 สำหรับ Tiling Problem

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] ตามลำดับ ตอนนี้ current = last + secondLast จากนั้นอัปเดตค่าของตัวแปรตามนั้น สูตรการเรียกซ้ำเหมือนกับของ Nth Fibonacci number ดังนั้นคุณยังสามารถแก้ปัญหานี้ O (log N) เวลาโดยใช้สูตรเพื่อค้นหาตัวเลข Fibonacci