货币兑换Altorith（Android/Java /Pseudocode）

Question

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

声明：

我们有一些汇率，比如。。。

• 欧元兑美元-

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

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

最好的情况是，如果你的汇率是直接的（出现在清单上），在最坏的情况下，你应该在中间汇率上跳很多次。

注：考虑到欧元对美元，你可以假设美元对欧元是相反的。

我希望问题很清楚。

有什么想法吗？？

Answer 1

我基本上同意帕特里夏的观点。但这个问题肯定也与避免套利有关。因此，它可以归结为从a货币到B货币的“最短路径”（最低成本）。最短路径算法得到了充分的研究和记录。在cormen和rivest查找它们。

Answer 2

构造一个加权有向图，每个顶点都标有货币名称。如果你有货币a到B的汇率，用汇率作为权重添加一个边（a，B）。

如果有（A，B）边，但没有（B，A）边，则将权重为1的（B，A）边加上（A，B）权重。

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

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

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

要找到交换次数最少的交换路径，请为每个与直接交换匹配的边赋予权重1。