Sot*_*tti 6 java algorithm android currency pseudocode
我在找到兑换货币问题的良好解决方案时遇到了问题.我花了一整天的时间考虑所有案例的优雅和快速解决方案.
声明:
我们有一些汇率如...
这个比率不是真实的,可能每天都会改变一次.利率的数量可能与世界货币一样大(约150).
我们被要求将任何货币的金额转换为另一种货币,我们应该给出答案(如果可以的话)给出兑换货币汇率.
最好的情况是如果您直接交换(显示在列表中),在更糟糕的情况下,您应该以中间交换率跳转很多次.
注意:从EUR到USD,您可以假设uSD到EUR是反向的.
我希望问题很清楚.
有任何想法吗？？
构建一个加权有向图，每个顶点都标有货币名称。如果您有货币 A 到 B 的汇率，请添加一条边 (A,B)，并将汇率作为权重。
如果有 (A,B) 边但没有 (B,A) 边，则添加权重为 1 除以 (A,B) 权重的 (B,A) 边。
要将货币 C 转换为 D，请应用最短路径算法来查找从 C 的顶点到 D 的顶点的最低权重路径。如果没有这样的路径，则无法完成转换。请参阅具有非负权重的有向图。
=================================================== =======================================
这不一定能找到最佳汇率，因为汇率会成倍增加。可以通过使用汇率的对数作为边权重，并使用可以处理负边权重的最短路径算法来找到最佳汇率。
要找到交换次数最少的交换路径，请为与直接交换匹配的每条边赋予权重 1。