Chương trình tìm tỷ giá chuyển đổi giữa hai loại tiền tệ Python

Cho ba mảng curr_a, curr_b, conv_rate biểu diễn tỷ giá chuyển đổi từ curr_a[i] sang curr_b[i]. Cho tiền tệ nguồn src và đích dest. Tìm tỷ giá chuyển đổi từ src sang dest, trả về 0 nếu không thể.

Ví dụ: src="INR", dest="JPY", curr_a=["INR","GBP","EUR"], curr_b=["GBP","EUR","JPY"], conv_rate=[0.009,1.17,129.67] → 1.3654251.

Giải thuật (Bellman-Ford biến thể)

1. Khởi tạo temp[src] = 1, các giá trị khác = 0
2. Lặp tối đa len(temp) lần: cập nhật tỷ giá nếu tìm thấy đường tốt hơn
3. Nếu hội tụ trước khi hết vòng lặp thì trả về temp[dest]
4. Ngược lại trả về -1 (có chu kỳ arbitrage)

Ví dụ triển khai

from collections import defaultdict

def solve(src, dest, curr_a, curr_b, conv_rate):
    temp = defaultdict(int)
    temp[src] = 1
    i = 0
    updated = True
    while updated and i <= len(temp):
        updated = False
        for x, y, z in zip(curr_a, curr_b, conv_rate):
            if temp[x] * z > temp[y]:
                temp[y] = temp[x] * z
                updated = True
        i += 1
    return temp[dest] if i <= len(temp) else -1

print(solve("INR", "JPY", ["INR", "GBP", "EUR"], ["GBP", "EUR", "JPY"], [0.009, 1.17, 129.67]))

Đầu vào

"INR", "JPY", ["INR", "GBP", "EUR"], ["GBP", "EUR", "JPY"], [0.009, 1.17, 129.67]

Đầu ra

1.3654251