สมมติว่าเรามีหมายเลข N และไม่จำกัดจำนวนเหรียญที่มีมูลค่า 1, 10 และ 25 เหรียญสกุลเงิน ค้นหาจำนวนเหรียญขั้นต่ำที่เราต้องใช้เพื่อจ่ายจำนวน N ให้ตรงกัน สมมติว่า N คือ 14 จากนั้นจำนวนเหรียญจะเป็น 5 เป็นเหรียญมูลค่า 10 เหรียญ 1 เหรียญและเหรียญมูลค่า 1 เหรียญ 4 เหรียญ
เพื่อแก้ปัญหานี้ เราต้องใช้ขั้นตอนเหล่านี้ -
- ถ้า 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
