在Python中查找货币套汇的程序

假设我们有一个N x N的货币汇率表。 我们必须检查是否存在一些交易序列。 现在从任何一种货币的一些金额A开始，我们可以以比A更大的某种货币金额结束。不存在交易成本，我们还可以交易分数数量。

矩阵中的条目[I，j]的值表示我们可以用一种货币i购买多少数量的货币j。现在假设货币0为美元，1为加元，2为欧元。我们可以通过以下方式进行套汇 −

• 将1加元卖出0.65欧元

• 将0.65欧元卖出0.7865美元（0.65 * 1.21）

• 将0.7865美元卖出1.00672加元（0.65 * 1.21 * 1.28）

因此，如果输入如下所示

那么输出将是True。

要解决此问题，我们将遵循以下步骤−

• 对于大小为矩阵的范围中的i，执行以下操作
  • 对于矩阵[0]的范围中的j，执行以下操作
    • 矩阵[i，j]：= −log 2的值(base) （matrix[I，j]）的值
• v：=矩阵的行数

• 对于k在范围0到v中，执行以下操作

  • 对于范围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