โปรแกรม Python สำหรับเปลี่ยนเหรียญ

ในบทความนี้ เราจะเรียนรู้เกี่ยวกับวิธีแก้ปัญหาตามที่ระบุด้านล่าง

คำชี้แจงปัญหา − เราได้รับ N coins และเราต้องการทำการเปลี่ยนแปลงของเหรียญเหล่านั้น เพื่อให้มีอุปทานที่ไม่สิ้นสุดของแต่ละค่าใน S เราต้องแสดงให้เห็นว่าเราสามารถทำการเปลี่ยนแปลงได้หลายวิธีโดยไม่คำนึงถึงลำดับ

เราจะใช้แนวคิดของการเขียนโปรแกรมแบบไดนามิกเพื่อแก้ปัญหาคำสั่งเพื่อลดความซับซ้อนของเวลา

ทีนี้มาดูวิธีแก้ปัญหาในการใช้งานด้านล่าง -

ตัวอย่าง

# dynamic approach
def count(S, m, n):
   # base case
   table = [[0 for x in range(m)] for x in range(n+1)]
   # for n=0
   for i in range(m):
      table[0][i] = 1
   # rest values are filled in bottom up manner
   for i in range(1, n+1):
      for j in range(m):
         # solutions including S[j]
         x = table[i - S[j]][j] if i-S[j] >= 0 else 0
         # solutions excluding S[j]
         y = table[i][j-1] if j >= 1 else 0
         # total
         table[i][j] = x + y
   return table[n][m-1]
# main
arr = [1, 3, 2, 4]
m = len(arr)
n = 5
print(“Number of coins:”,end=””)
print(count(arr, m, n))

ผลลัพธ์

Number of coins:6

ตัวแปรทั้งหมดได้รับการประกาศในขอบเขตท้องถิ่นและการอ้างอิงของตัวแปรนั้นดูได้จากรูปด้านบน

บทสรุป

ในบทความนี้ เราได้เรียนรู้เกี่ยวกับวิธีการสร้างโปรแกรม Python สำหรับ Coin Change