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)

所以，如果输入类似于：

那么输出将为 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

Arnab Chakraborty

更新于: 2020年12月15日

1K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

立即开始