java - 货币兑换算法(Android/Java/伪代码)

Question

我在寻找兑换货币问题的良好解决方案时遇到了问题。我花了一整天的时间思考这个问题，想出适合所有情况的任何优雅而快速的解决方案。

声明:

我们有一些汇率，例如...

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

此费率不是真实的，并且可能每天更改一次。利率的数量可能与世界上的货币一样多(大约 150 种)。

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

最好的情况是如果您直接兑换(出现在列表中)，在最坏的情况下您应该在中间汇率中跳很多次。

注意:给定欧元兑美元，您可以假设美元兑欧元是相反的。

我希望问题很清楚。

有什么想法吗？？

Answer 1

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

如果您有 (A,B) 边但没有 (B,A) 边，请添加权重为 1 除以 (A,B) 权重的 (B,A) 边。

要将货币 C 转换为 D，请应用最短路径算法来找到从 C 的顶点到 D 的顶点的权重最低的路径。如果没有这样的路径，则无法进行转换。参见 directed graph with non-negative weights .

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

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

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