Altorithm trao đổi tiền tệ (Android/Java/Pseudocode)

Question

Tôi gặp sự cố khi tìm giải pháp tốt cho vấn đề tiền tệ trao đổi. Tôi đã dành tất cả các ngày suy nghĩ về điều này với bất kỳ giải pháp thanh lịch và nhanh chóng cho tất cả các trường hợp.

Bản Tuyên Bố:

Chúng tôi có một số tỷ giá hối đoái như ...

• EUR sang USD -> 1,37
• USD AUD -> 0,7
• MEX để CAD -> 1.8
• LIB đến YEN -> 2.3
• (.....)

Mức giá này không thực tế và có thể thay đổi mỗi ngày một lần. Số lượng lãi suất có thể lớn bằng tiền tệ trên thế giới (khoảng 150).

Chúng tôi được yêu cầu chuyển đổi một số tiền từ bất kỳ đơn vị tiền tệ nào sang loại tiền tệ khác và chúng tôi sẽ cung cấp câu trả lời (nếu có) cho tỷ giá hối đoái.

Trường hợp tốt nhất là nếu bạn trao đổi trực tiếp (xuất hiện trong danh sách), trong trường hợp xấu hơn, bạn nên nhảy nhiều lần trong tỷ giá trung gian.

Lưu ý: Với EUR đến USD, bạn có thể giả định uSD là EUR là nghịch đảo.

Tôi hy vọng vấn đề là rõ ràng.

Bất kỳ ý tưởng nào ??

Answer 1

Tạo biểu đồ có trọng số được chỉ định với mỗi đỉnh được gắn nhãn bằng tên tiền tệ. Nếu bạn có một tỷ giá cho loại tiền tệ A đến B, hãy thêm một cạnh (A, B) với tỷ giá hối đoái như trọng lượng.

Nếu bạn có cạnh (A, B) nhưng không cạnh (B, A) thêm cạnh (B, A) có trọng số 1 chia cho trọng số (A, B).

Để chuyển đổi đơn vị tiền tệ từ C sang D, hãy áp dụng thuật toán đường đi ngắn nhất để tìm đường trọng số thấp nhất từ ​​đỉnh C đến đỉnh D. Nếu không có đường dẫn như vậy, việc chuyển đổi không thể thực hiện được. Xem directed graph with non-negative weights.

============================================== =========================================

Điều này sẽ không nhất thiết tìm tỷ giá hối đoái tốt nhất, bởi vì tỷ lệ nhân lên. Nó có thể được thực hiện để tìm tỷ lệ tốt nhất bằng cách sử dụng logarit của tỷ giá hối đoái như trọng lượng cạnh, và sử dụng một thuật toán đường đi ngắn nhất có thể xử lý trọng lượng cạnh tiêu cực.

Để tìm ra con đường trao đổi với các sàn giao dịch ít nhất, cung cấp cho mỗi cạnh phù hợp với một cuộc trao đổi trực tiếp một trọng lượng 1.

Answer 2

tôi sẽ đồng ý chủ yếu với Patricia. Nhưng vấn đề này chắc chắn chắc chắn phải làm với việc tránh chênh lệch. Vì vậy, nó tóm tắt thành một 'con đường ngắn nhất' (chi phí thấp nhất) từ tiền tệ A sang tiền tệ B. Các thuật toán đường đi ngắn nhất được nghiên cứu và ghi chép đầy đủ. Nhìn chúng trong cormen và rivest.