货币交换算法(Android / Java /Pseudocode)

Question

我很难找到一个很好的办法来解决汇率问题。我花了一整天的时间来思考这个问题，并为所有情况提供了一个优雅而快速的解决方案。

声明：

我们有一些汇率，比如.

• 欧元兑美元-> 1.37
• 美元兑澳元-> 0.7
• 从MEX到CAD -> 1.8
• 日元兑日元-> 2.3
• (.)

这一比率不是真实的，可能每天变化一次。利率的数量可能和世界上的货币一样大(约150种)。

我们被要求将一笔钱从任何一种货币兑换成另一种货币，如果可以的话，我们应该给出汇率的答案。

最好的情况是，如果您的汇率是直接的(出现在列表中)，那么在更糟糕的情况下，您应该在中间汇率中跳过很多次。

注意:如果欧元兑美元，你可以假设USD对欧元是相反的。

我希望问题是清楚的。

有什么主意吗？

Answer 1

构造一个加权有向图，每个顶点都标记有一个货币名称。如果您有货币A到B的汇率，则添加以汇率为权重的边(A，B)。

如果有(A，B)边，但没有(B，A)边，则添加(B，A)边，其权重1除以(A，B)权重。

为了将货币C转换为D，应用最短路径算法求出从C的顶点到D的顶点的最小权路径。如果没有这样的路径，则无法进行转换。见具有非负权的有向图。

=======================================================================================

这并不一定能找到最佳的汇率，因为汇率会成倍增长。利用汇率对数作为边权值，采用最短路径算法处理负边权值，可以找到最优汇率。

若要用最少的交换找到交换路径，请给每个与直接交换匹配的边一个权重1。

Answer 2

我基本上同意帕特里夏的看法。但这个问题当然也与避免套利有关。因此，它归结为“最短路径”(最低成本)从货币A到货币B。到警卫室和里弗特去查一下。