Giả sử chúng ta có một số N, và không giới hạn số lượng đồng tiền trị giá 1, 10 và 25 đồng tiền tệ. Tìm số xu tối thiểu chúng ta cần sử dụng để trả đúng số tiền N. Giả sử N là 14, khi đó số xu sẽ là 5, như một đồng 10 giá trị và bốn đồng giá trị 1.
Để giải quyết vấn đề này, chúng ta phải sử dụng các bước sau -
- Nếu N <10, thì trả về N số đồng tiền 1 giá trị
- Nếu N> 9 và N <25, thì chia giá trị cho 10 và nhận được kết quả, phần còn lại sẽ được bao gồm bằng 1 đồng giá trị, cộng số đếm để có kết quả
- Nếu N> 25, thì chia cho 25, lấy kết quả, khi kết quả <25, sau đó thực hiện lại nhiệm vụ tương tự cho điểm thứ hai, v.v.
Ví dụ
#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);
} Đầu ra
Minimum number of coins required: 7