home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

โปรแกรมตรวจสอบ Currency Arbitrage ใน Python

ได้รับตารางอัตราแลกเปลี่ยน N×N ที่ matrix[i][j] = จำนวนสกุลเงิน j ที่ซื้อได้ด้วย 1 หน่วยสกุล i ตรวจสอบว่ามี Arbitrage opportunity หรือไม่ (เริ่ม A หน่วย สิ้นสุด > A หน่วยของสกุลเดิม)

ตัวอย่าง

    USD  CAD  EUR
USD  1   1.28 0.82
CAD 0.78  1   0.65
EUR 1.21 1.55  1

Output: True

CAD → EUR → USD → CAD: 1 × 0.65 × 1.21 × 1.28 = 1.00672 > 1

แนวทางแก้ปัญหา

Bellman-Ford Negative Cycle Detection:

  1. แปลงเป็นโจทย์ shortest path: weight = -log(rate)
  2. Arbitrage ⇔ มี negative cycle (ผลรวม weight < 0 ⇔ ผลคูณ rate > 1)
  3. รัน Floyd-Warshall หรือ Bellman-Ford หา negative cycle

การใช้งาน (Python - Floyd Warshall)


import math

class Solution:
    def solve(self, matrix):
        n = len(matrix)
        
        # แปลงเป็น -log2(rate)
        for i in range(n):
            for j in range(n):
                matrix[i][j] = -math.log2(matrix[i][j])
        
        # Floyd-Warshall
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if matrix[i][j] > matrix[i][k] + matrix[k][j]:
                        matrix[i][j] = matrix[i][k] + matrix[k][j]
        
        # ตรวจ diagonal: ถ้า < 0 = negative cycle = arbitrage
        return any(matrix[i][i] < 0 for i in range(n))

# ทดสอบ
ob = Solution()
matrix = [
    [1, 1.28, 0.82],
    [0.78, 1, 0.65],
    [1.21, 1.55, 1]
]
print(ob.solve(matrix))  # Output: True

ความซับซ้อน

  • Time Complexity: O(N³) (Floyd-Warshall)
  • Space Complexity: O(N²)

สามารถใช้ Bellman-Ford จากทุกโหนดได้ O(N²E) หรือ SPFA