Python程式：查詢貨幣套利

假設我們有一個 N x N 的貨幣匯率表。我們需要檢查是否存在一些交易序列。現在，從任意貨幣的某個金額 A 開始，我們能否最終獲得大於 A 的該貨幣金額。假設沒有交易成本，並且可以交易小數數量。

該矩陣中 [I, j] 處的數值表示用一個單位的貨幣 i 可以購買的貨幣 j 的數量。現在考慮貨幣 0 是美元 (USD)，1 是加拿大元 (CAD)，2 是歐元 (EUR)。我們可以透過以下方式進行套利：

  • 出售 1 加拿大元，獲得 0.65 歐元

  • 出售 0.65 歐元，獲得 0.7865 美元 (0.65 * 1.21)

  • 出售 0.7865 美元，獲得 1.00672 加拿大元 (0.65 * 1.21 * 1.28)

所以，如果輸入類似於：

11.280.82
0.7810.65
1.211.551

那麼輸出將為 True。

為了解決這個問題，我們將遵循以下步驟：

  • 對於範圍從 0 到矩陣大小的 i，執行以下操作

    • 對於範圍從 0 到 matrix[0] 大小的 j，執行以下操作

      • matrix[i,j] := -log 以 2 為底 (matrix[I, j]) 的值

  • v := 矩陣的行數

  • 對於範圍從 0 到 v 的 k，執行以下操作

    • 對於範圍從 0 到 v 的 i，執行以下操作

      • 對於範圍從 0 到 v 的 j，執行以下操作

        • matrix[I, j] := matrix[I, j] 和 (matrix[I, k] + matrix[k, j]) 中的最小值

  • 如果矩陣對角線上任何元素非零，則返回 True。

讓我們看下面的實現來更好地理解：

Python

 即時演示

import math
class Solution:
   def solve(self, matrix):
      for i in range(len(matrix)):
         for j in range(len(matrix[0])):
            matrix[i][j] = −math.log(matrix[i][j], 2)
   v = len(matrix)
   for k in range(0, v):
      for i in range(0, v):
         for j in range(0, v):
            matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
   return any(matrix[i][i] < 0 for i in range(len(matrix)))
ob = Solution()
matrix = [
   [1, 1.28, 0.82],
   [0.78, 1, 0.65],
   [1.21, 1.55, 1]
]
print(ob.solve(matrix))

輸入

matrix = [
   [1, 1.28, 0.82],
   [0.78, 1, 0.65],
   [1.21, 1.55, 1]
]

輸出

True

更新於: 2020年12月15日

1K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告