สมมติว่ามีตัวเลข N และเหรียญมูลค่า 1, 10 และ 25 ใช้ไม่จำกัด หาจำนวนเหรียญน้อยที่สุดที่ต้องใช้จ่ายให้ได้จำนวน N อย่างแน่นอน สมมติว่า N คือ 14 จำนวนเหรียญจะเป็น 5 คือ เหรียญมูลค่า 10 หนึ่งเหรียญ และเหรียญมูลค่า 1 สี่เหรียญ
เพื่อแก้ปัญหานี้ เราต้องใช้ขั้นตอนเหล่านี้:
- ถ้า N < 10 ให้คืนค่า N เหรียญมูลค่า 1
- ถ้า N > 9 และ N < 25 ให้หารค่าด้วย 10 และได้ผลลัพธ์ ส่วนที่เหลือจะใช้เหรียญมูลค่า 1 รวมจำนวนเพื่อได้ผลลัพธ์
- ถ้า N > 25 ให้หารด้วย 25 รับผลลัพธ์ เมื่อผลลัพธ์ < 25 ให้ทำซ้ำขั้นตอนที่สอง และต่อไป
ตัวอย่าง
#include <iostream>
using namespace std;
int countMinCoins(int n) {
if (n < 10)
return n;
else if (n > 9 && n < 25) {
int count = n / 10;
count += n % 10;
return count;
} else {
int count = n / 25;
return count + countMinCoins(n % 25);
}
}
int main() {
int n = 88;
cout << "Minimum number of coins required: " << countMinCoins(n);
}
ผลลัพธ์
Minimum number of coins required: 7
