คำตอบของทีม
ไม่ได้ส่งคำตอบ
ไม่ได้ส่งคำตอบ
คะแนน + โบนัสทำเร็ว
0.0
0.0
แชร์
ไม่ได้ส่งคำตอบ 
ในประเทศแห่งหนึ่ง มีการใช้เหรียญ 4 แบบ คือ เหรียญ 1 บาท, 2 บาท, 3 บาท และ 5 บาท ด้วยเหรียญ 4 แบบนี้ ถ้าต้องการรวมกันให้เป็นเงิน 6 บาท สามารถทำได้ทั้งสิ้น 8 แบบ ดังนี้ (เขียนเป็นการบวกกันของมูลค่าของเหรียญต่าง ๆ)
5+1
3+3
3+2+1
3+1+1+1
2+2+2
2+2+1+1
2+1+1+1+1
1+1+1+1+1+1
ให้หาว่าถ้าต้องการรวมกันให้เป็นเงิน 100 บาท สามารถทำได้กี่วิธี
5+1
3+3
3+2+1
3+1+1+1
2+2+2
2+2+1+1
2+1+1+1+1
1+1+1+1+1+1
ให้หาว่าถ้าต้องการรวมกันให้เป็นเงิน 100 บาท สามารถทำได้กี่วิธี
เฉลย
ตอบ 6518
คำาอธิบาย
ความยากของโจทย์ข้อนี้คือทำอย่างไรไม่ให้มีการนับซ้ำ ถ้าเราเขียนโปรแกรมแบบตรงไปตรงมา เราอาจจะสร้างรูปแบบของการรวมเงินเหรียญทุกรูปแบบ และนำทุกรูปแบบที่หาได้มาตัดตัวที่ซ้ำออก แต่วิธีนี้จะใช้เวลาการทำงานนานมาก เพราะว่าจะมีตัวที่ซ้ำซ้อนกันเยอะเกินไป
วิธีที่ป้องกันไม่ให้นับซ้ำ สามารถทำได้โดยระบุมูลค่าเหรียญที่มากที่สุดที่ใช้ได้ ยกตัวอย่าง เช่น ถ้าเราใช้เหรียญ 3 บาทไปแล้ว เราจะใช้เหรียญ 5 บาทอีกไม่ได้ เราก็จะไม่มีการสร้างรูปแบบที่ซ้ำเลย โปรแกรมภาษา Pythln เป็นดังนี้
def generate(v, mx, prefix):
$\quad$if v == 0:
$\quad$$\quad$return [prefix]
$\quad$a = []
$\quad$for c in coins:
$\quad$$\quad$if (c <= v) and (c <= mx):
$\quad$$\quad$$\quad$a += generate(v - c, c, prefix + [c])
$\quad$return a
print(len(generate(100, 5, []))
ถ้าเราไม่ต้องการรายการของการรวมเหรียญ เราอาจจะเขียนฟังก์ชันเรียกตัวเองที่คำนวณจำนวนรูปแบบเท่านั้นก็ได้ เช่น
def count(v,mx):
$\quad$if v == 0:
$\quad$$\quad$return 1
$\quad$t = 0
$\quad$for c in coins:
$\quad$$\quad$if (c <= mx) and (c <= v):
$\quad$$\quad$$\quad$t += count(v-c, c)
$\quad$return t