确定汇率的算法
给定一个包含各种货币对的数据集，我该如何高效地计算一个在数据集中没有提供的货币对的隐含汇率呢？
举个例子，假设我的数据库/表格看起来是这样的（这些数据是虚构的）：
GBP x USD = 1.5
USD x GBP = 0.64
GBP x EUR = 1.19
AUD x USD = 1.1
注意，(GBP,USD) 不等于 1/(USD,GBP)。
我期望得到以下结果：
print rate('GBP','USD')
> 1.5
print rate('USD','GBP')
> 0.64
print rate('GBP','EUR')
> 1.19
#now in the absence of an explicit pair, we imply one using the inverse
print rate('EUR','GBP')
> 0.84
这些是简单的情况，接下来会更有趣：
#this is the implied rate from (GBP,EUR) and (GBP,USD)
print rate('EUR','USD')
> 1.26
或者一个更复杂的例子是使用三个或更多的货币对来找到最有效的转换：
print rate('EUR','AUD')
> 1.38
我认为这描述了这个问题的编程相关方面。我想这里应该有一个高效或聪明的递归方法可以使用。唯一的要求是使用最少的货币对来得到所需的货币对（这样可以减少错误）。如果没有明确的反向汇率，那么反转一个货币对是没有成本的。
动机
在理想的金融世界里，货币市场是高效的。实际上，这大约有99%的准确性。很多时候，奇怪的货币对没有报价，或者报价很少。如果有明确的报价，我们必须在我们的任意计算中使用它。如果没有，我们必须推导出最准确的货币对，尽可能多保留小数位。此外，它们的乘积并不总是等于1（实际上，它们从来不会等于1）；这反映了市场中的买卖差价。因此，我们尽可能保留多个方向的货币对，但希望能够为所有货币编写通用的代码。
我认为我有一个不错的暴力解决方案已经实现了。它能工作，但我觉得这个问题很有趣，想知道是否还有其他人觉得它有趣或具有挑战性。我个人在用Python工作，但这更多是一个练习而不是实现，所以伪代码“足够好了”。
1 个回答
16
你想在一个有方向的图里找到最短的路径。在这个图里，货币就是点，而给定的汇率就是连接这些点的线。如果某个汇率只给出了一个方向的值，你可以为相反的方向添加一个汇率，但这个汇率的成本要更高。