Hướng đi ở
Bạn cần đăng nhập để thấy link
do
Bạn cần đăng nhập để thấy link
là đúng rồi.
Bài toán sẽ phức tạp hơn nếu phải xử lý cả tiền giấy. Chẳng hạn với 1 triệu đồng, muốn đổi ra tiền giấy và tiền xu trong đó số lượng tiền xu không vượt quá 5 đồng. Khi đó phải liệt kê loại tiền giấy, vòng lặp sẽ mệt mỏi hơn. Do đó chấp nhận hướng giải quyết ở trên, tức là chỉ quan tâm tới tiền xu mà thôi.
Lời giải code ở trên của NhanSu có thể gây khó đọc cho một số bạn nên mình giải thích:
Các loại tiền 5000, 2000, 1000, 500, 200 đều chia hết cho 100. Do đó để tránh làm việc với số lớn, ta chia tất cả dữ kiện về tiền cho 100.
Như vậy số tiền xu quy ước thành 50, 20, 10, 5,2 và số tiền là N2 = N/100.
Lời giải ở trên là thực hiện liên tiếp các phép thử.
Số tiền 50 là từ 0 tới N2. Nhưng nếu N2 >M thì chỉ thử tới M.
Với mỗi đồng 50 trong phép thử thì số tiền còn lại được định nghĩa lại: N2i = N2 - 50*i
Và số tiền xu được thắt chặt lại còn Mi = M-i
Tương tự như thế cho các đồng tiền khác.
Cho tới đồng tiền cuối cùng là 2 thì không cần dùng vòng lặp For nữa, ta thử xem số tiền còn lại có là số chia hết cho 2 hay không.
Đây là bài toán cơ bản luyện tập nhiều vòng lặp For lồng vào nhau.
\[ \left\{\begin{matrix} 50a+20b+10c+5d+2e& =N_2\\ a+b+c+d+e & \leq M \end{matrix}\right. \]
Trong đó a,b,c,d,e là các số nguyên không âm.