Giải pascal

Để giải bài toán này, ta có thể sử dụng phương pháp tham lam (greedy algorithm).

Bước 1: Sắp xếp các mệnh giá tiền từ lớn đến nhỏ: 100, 50, 20, 10, 5, 2, 1.

Bước 2: Với mỗi mệnh giá tiền, ta lấy số lượng tối đa có thể sao cho tổng số tờ tiền không vượt quá x.

Bước 3: Tính tổng số tờ tiền đã lấy và kiểm tra xem tổng số tờ tiền đã lấy có bằng x không. Nếu bằng, kết thúc. Nếu không, quay lại bước 2.

Ví dụ: Giả sử x = 123.

Bước 1: Sắp xếp các mệnh giá tiền từ lớn đến nhỏ: 100, 50, 20, 10, 5, 2, 1.

Bước 2:
- Lấy số lượng tờ tiền mệnh giá 100: 1 (123 - 100 = 23).
- Lấy số lượng tờ tiền mệnh giá 50: 0 (23 không vượt quá 50).
- Lấy số lượng tờ tiền mệnh giá 20: 1 (23 - 20 = 3).
- Lấy số lượng tờ tiền mệnh giá 10: 0 (3 không vượt quá 10).
- Lấy số lượng tờ tiền mệnh giá 5: 0 (3 không vượt quá 5).
- Lấy số lượng tờ tiền mệnh giá 2: 1 (3 - 2 = 1).
- Lấy số lượng tờ tiền mệnh giá 1: 1 (1 - 1 = 0).

Bước 3: Tổng số tờ tiền đã lấy là 1 + 0 + 1 + 0 + 0 + 1 + 1 = 4. Tổng số tờ tiền đã lấy không bằng x, nên ta quay lại bước 2.

Bước 2:
- Lấy số lượng tờ tiền mệnh giá 100: 0 (123 không vượt quá 100).
- Lấy số lượng tờ tiền mệnh giá 50: 2 (123 - 2 * 50 = 23).
- Lấy số lượng tờ tiền mệnh giá 20: 1 (23 - 20 = 3).
- Lấy số lượng tờ tiền mệnh giá 10: 0 (3 không vượt quá 10).
- Lấy số lượng tờ tiền mệnh giá 5: 0 (3 không vượt quá 5).
- Lấy số lượng tờ tiền mệnh giá 2: 1 (3 - 2 = 1).
- Lấy số lượng tờ tiền mệnh giá 1: 1 (1 - 1 = 0).

Bước 3: Tổng số tờ tiền đã lấy là 0 + 2 + 1 + 0 + 0 + 1 + 1 = 5. Tổng số tờ tiền đã lấy bằng x, kết thúc.

Vậy, số lượng tờ tiền ít nhất mà Nam cầm trên tay là 5.