โปรแกรมนับจำนวนลายอิฐแนวนอน ทำได้จากชุดอิฐใน Python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่าอิฐ และค่าความกว้างและความสูงอีกสองค่า แต่ละองค์ประกอบในอิฐ[i] หมายถึงอิฐที่มีความยาวเป็นหน่วยอิฐ[i] และความกว้างคือ 1 หน่วย เราต้องหาหลายวิธีในการวางอิฐเพื่อให้ได้อิฐที่มีความกว้างและความสูงที่กำหนด อิฐนำกลับมาใช้ใหม่ได้แต่วางในแนวนอนเท่านั้น

ดังนั้น ถ้าอินพุตเหมือนอิฐ =[2, 1] width =3 height =2 ผลลัพธ์จะเป็น 9 เพราะ −

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

w :=รายการขนาดเท่ากับความกว้าง และแทรก 1 ที่ตำแหน่งแรก ส่วนที่เหลือเป็น 0
สำหรับ i ในช่วง 0 ถึงความกว้าง ทำ
- ถ้า w[i] ไม่ใช่ศูนย์ แล้ว
  - สำหรับแต่ละ x ในอิฐ ทำ
    - ถ้า i + x <=width แล้ว
      - w[i + x] :=w[i + x] + w[i]
ส่งคืน w[width]^height

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(bricks, width, height):
   w = [1] + [0] * width
   for i in range(width):
      if w[i]:
         for x in bricks:
            if i + x <= width:
               w[i + x] += w[i]
   return w[width] ** height

bricks = [2, 1]
width = 3
height = 2
print(solve(bricks, width, height))

อินพุต

[2, 1], 3, 2