Bài 41: Đổi tiền 1

Bài 41:
Cho N (đồng). muốn đổi tiền chỉ gồm các tờ tiền mệnh giá 500, 200 và 100.Hãy liệt kê các cách rút tiền. Nếu không các cách đổi tiền nào thì ghi ra “NONE”.
BAI41.INP BAI41.OUT
600 0 0 6
0 1 4
0 2 2
0 3 0
1 0 1
❖ Thuật toán:
Thuật toán: Vét cạn
Cách 1: Độ phức tạp của thuật toán O(N3/107)
Gọi a là số lượng tờ tiền 500 rút được (0 ≤ a ≤  N/500)
Gọi b là số lượng tờ tiền 200 rút được (0 ≤ b ≤  N/200)
Gọi c là số lượng tờ tiền 100 rút được (0 ≤ c ≤  N/100)
Đổi N đồng theo yêu cầu đề bài: 500*a + 200*b + 100*c = N
For(a, 0, N/500)
  For(b,0, N/200)
    For(c,0,N/100)
        If (500*a + 200*b + 100*c == N)
                 Cout << a << b << c;
Cách 2: Độ phức tạp của thuật toán O(N2/105)
Gọi a là số lượng tờ tiền 500 rút được (0 ≤ a ≤  N/500)
Gọi b là số lượng tờ tiền 200 rút được (0 ≤ b ≤  N/200)
Gọi c là số lượng tờ tiền 100 rút được.
Đổi N đồng theo yêu cầu đề bài: Điều kiện (N – (500*a + 200*b)) % 100 == 0)
For(a, 0, N/500)
  For(b,0, N/200)
             p = N – (500*a + 200*b);            
             If (p % 100 == 0)
                 cout << a << b << p/100

Video bài giảng:

Code:

n = int(input())
p = False
for a in range(n // 500 + 1):
   for b in range(n // 200 + 1):
       for c in range(n // 100 + 1):
           if a * 500 + b * 200 + c * 100 == n:
               p = True
               print(a, b, c)
if not p:
   print('NONE')

Code:

n = int(input())
p = False
for a in range(n // 500 + 1):
   for b in range(n // 200 + 1):
       m = n - (500 * a + 200 * b)
       if m % 100 == 0 and m > 0 or m == 0:
           p = True
           print(a, b, m // 100)
if not p:
  print('NONE')