Обмен валюты Altorithm (Android / Java / Pseudocode)

У меня проблема с поиском хорошего решения проблемы валютной валюты. Я весь день думал об этом с помощью любого элегантного и быстрого решения для всех случаев.

Утверждение:

У нас есть обменные курсы валют, такие как …

  • EUR к доллару США -> 1,37
  • USD до AUD -> 0,7
  • MEX to CAD -> 1.8
  • LIB до YEN -> 2,3
  • (…..)

Эти ставки не являются реальными и могут меняться один раз в день. Количество ставок может быть таким же большим, как и валюты в мире (около 150).

Нам предлагается конвертировать сумму денег из любой валюты в другую, и мы должны дать ответ (если можно) с учетом обменных курсов валют.

Лучше всего, если вы обмениваетесь напрямую (отображается в списке), в худшем случае вы должны перепрыгивать много раз в промежуточные обменные курсы.

Примечание: с учетом EUR до USD вы можете предположить, что uSD в EUR является обратным.

Надеюсь, проблема ясна.

Есть идеи??

    Постройте взвешенный ориентированный граф с каждой вершиной, помеченной именем валюты. Если у вас есть курс для валюты A-B, добавьте кромку (A, B) с обменным курсом как вес.

    Если у вас есть край (A, B), но не край (B, A), добавьте край (B, A) с весом 1, разделенным на вес (A, B).

    Чтобы преобразовать валюту C в D, примените алгоритм кратчайшего пути, чтобы найти самый низкий путь веса от вершины C до вершины D. Если такого пути нет, преобразование невозможно. См. Ориентированный граф с неотрицательными весами .

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

    Это не обязательно найдет лучший обменный курс, потому что ставки умножаются. Его можно было бы найти, чтобы найти наилучшую скорость, используя логарифмы обменных курсов как веса кромки, и используя алгоритм кратчайшего пути, который может обрабатывать отрицательные веса ребер.

    Чтобы найти путь обмена с наименьшим количеством обменов, дайте каждому ребру, который соответствует прямому обмену весом 1.

    Я бы согласился в основном с Патрицией. Но эта проблема, безусловно, безусловно связана с тем, чтобы избежать арбитража. Таким образом, он сводится к «кратчайшему пути» (минимальная стоимость) от валюты A к валюте B. Самые короткие алгоритмы маршрута хорошо изучены и документированы. Посмотрите на них в кормене и наряда.