Lập trình chia số tiền sao cho có ít số tờ nhất bằng Python

Bài toán chia số tiền sao cho có ít số tờ nhất là bài toán rất được hay sử dụng trong thực tế.

Sau đây VniTeach sẽ giới thiệu bạn cách để thực hiện bài toán này đơn giản như sau:

Mô tả chi tiết của thuật toán tham lam (greedy algorithm) để chia số tiền thành các mệnh giá sao cho ít số tờ nhất.

Thuật toán chia số tiền thành các mệnh giá

Mục tiêu:

Chia một số tiền cho trước thành các mệnh giá tiền (ví dụ: 500 VNĐ, 200 VNĐ, 100 VNĐ, v.v.) sao cho số lượng tờ ít nhất có thể.

Các bước thực hiện:

Khởi tạo danh sách mệnh giá: Định nghĩa một danh sách các mệnh giá tiền, sắp xếp từ lớn đến nhỏ, chẳng hạn: [500, 200, 100, 50, 20, 10, 5, 2, 1].

Khởi tạo biến kết quả: Tạo một từ điển (hoặc danh sách) để lưu số lượng tờ của mỗi mệnh giá tiền.

Duyệt qua các mệnh giá: Lặp qua các mệnh giá tiền từ lớn đến nhỏ.

• Tính số lượng tờ cần thiết:
• Chia số tiền còn lại cho mệnh giá hiện tại để tìm số lượng tờ cần thiết (so_luong = tien // m).
• Cập nhật số tiền còn lại:
• Sử dụng phép chia dư (tien %= m) để tính số tiền còn lại sau khi đã trừ số tiền tương ứng với mệnh giá hiện tại.
• Lưu số lượng tờ vào kết quả:
• Nếu số lượng tờ của một mệnh giá là lớn hơn 0, lưu vào từ điển kết quả.

Kết Thúc: Sau khi đã lặp qua tất cả các mệnh giá, số lượng tờ của mỗi mệnh giá sẽ được lưu trong từ điển.

In kết quả: Hiển thị số lượng tờ của mỗi mệnh giá đã sử dụng.

Ví dụ: Giả sử bạn cần chia số tiền là 1237 VNĐ.

• Bắt đầu với mệnh giá lớn nhất (500 VNĐ):
• 1237 // 500 = 2 (2 tờ 500 VNĐ)
• Cập nhật số tiền còn lại: 1237 % 500 = 237 VNĐ.
• Tiếp tục với mệnh giá 200 VNĐ:
• 237 // 200 = 1 (1 tờ 200 VNĐ)
• Cập nhật số tiền còn lại: 237 % 200 = 37 VNĐ.
• Tiếp tục với mệnh giá 100 VNĐ:
• 37 // 100 = 0 (không có tờ 100 VNĐ)
• Tiếp tục với mệnh giá 50 VNĐ:
• 37 // 50 = 0 (không có tờ 50 VNĐ)
• Tiếp tục với mệnh giá 20 VNĐ:
• 37 // 20 = 1 (1 tờ 20 VNĐ)
• Cập nhật số tiền còn lại: 37 % 20 = 17 VNĐ.
• Tiếp tục với mệnh giá 10 VNĐ:
• 17 // 10 = 1 (1 tờ 10 VNĐ)
• Cập nhật số tiền còn lại: 17 % 10 = 7 VNĐ.
• Tiếp tục với mệnh giá 5 VNĐ:
• 7 // 5 = 1 (1 tờ 5 VNĐ)
• Cập nhật số tiền còn lại: 7 % 5 = 2 VNĐ.
• Tiếp tục với mệnh giá 2 VNĐ:
• 2 // 2 = 1 (1 tờ 2 VNĐ)
• Cập nhật số tiền còn lại: 2 % 2 = 0 VNĐ.
• Tiếp tục với mệnh giá 1 VNĐ:
• 0 // 1 = 0 (không có tờ 1 VNĐ)

Kết quả:

• 2 tờ 500 VNĐ
• 1 tờ 200 VNĐ
• 1 tờ 20 VNĐ
• 1 tờ 10 VNĐ
• 1 tờ 5 VNĐ
• 1 tờ 2 VNĐ

Phân tích độ phức tạp:

• Thời gian: O(n), với n là số lượng mệnh giá (hầu như cố định và nhỏ, nên thực tế là hằng số).
• Không gian: O(1), vì không sử dụng nhiều không gian phụ thuộc vào kích thước đầu vào.

Thuật toán này đảm bảo rằng số lượng tờ được sử dụng là ít nhất vì nó luôn chọn mệnh giá lớn nhất có thể trong mỗi bước.

Cách 1: Sử dụng cả danh sách và từ điển

def chia_menh_gia(tien):
    # Các mệnh giá tiền từ lớn đến nhỏ
    menh_gia = [500, 200, 100, 50, 20, 10, 5, 2, 1]
    ket_qua = {}  # Sử dụng từ điển để lưu số lượng tờ của mỗi mệnh giá

    for m in menh_gia:
        if tien >= m:
            so_luong = tien // m  # Tính số lượng tờ của mệnh giá hiện tại
            tien %= m  # Cập nhật số tiền còn lại
            ket_qua[m] = so_luong  # Lưu số lượng tờ vào từ điển

    return ket_qua

# Nhập số tiền từ người dùng
tien = 0
while tien<=0:
    tien = int(input("Nhập số tiền (VNĐ): "))
    if tien <= 0:
        print("Số tiền phải là số nguyên dương.")

ket_qua = chia_menh_gia(tien)

print("Số lượng tờ của mỗi mệnh giá:")
for m, so_luong in ket_qua.items():
    print(f"{m} VNĐ: {so_luong} tờ")

Cách 2: Chỉ sử dụng danh sách

def chia_menh_gia(tien):
    # Các mệnh giá tiền từ lớn đến nhỏ
    menh_gia = [500, 200, 100, 50, 20, 10, 5, 2, 1]
    so_luong_to = [0] * len(menh_gia)  # Mảng lưu số lượng tờ của mỗi mệnh giá

    # Lặp qua các mệnh giá từ lớn đến nhỏ
    for i in range(len(menh_gia)):
        m = menh_gia[i]
        if tien >= m:
            so_luong_to[i] = tien // m  # Tính số lượng tờ của mệnh giá hiện tại
            tien %= m  # Cập nhật số tiền còn lại

    return menh_gia, so_luong_toi

# Nhập số tiền từ người dùng
tien = 0
while tien<=0:
    tien = int(input("Nhập số tiền (VNĐ): "))
    if tien <= 0:
        print("Số tiền phải là số nguyên dương.")

menh_gia, so_luong_to = chia_menh_gia(tien)

print("Số lượng tờ của mỗi mệnh giá:")
for i in range(len(menh_gia)):
    if so_luong_to[i] > 0:
        print(f"{menh_gia[i]} VNĐ: {so_luong_to[i]} tờ")