Wymiana walut Altorithm (Android/Java/Pseudocode)

Question

Mam problem ze znalezieniem dobrego rozwiązania problemu wymiany walut. Cały dzień zastanawiałam się nad tym z każdym eleganckim i szybkim rozwiązaniem dla wszystkich przypadków.

komunikat:

Mamy kilka kursów walutowych jak ...

• EUR na USD -> 1.37
• USD AUD -> 0,7
• MEX CAD -> 1.8
• LIB Yen -> 2,3
• (.....)

Podane ceny nie są rzeczywiste i mogą ulec zmianie raz dziennie. Liczba stawek może być tak duża, jak waluty na świecie (około 150).

Jesteśmy wezwani do konwersji kwoty pieniędzy z dowolnej walucie na inną i powinniśmy dać odpowiedź (jeśli to możliwe), biorąc pod uwagę kursy walut.

Najlepszym przypadkiem jest, jeśli wymiana jest bezpośredni (pojawia się na liście), w gorszym przypadku należy przejść wiele razy w pośrednich giełdach cenach.

Uwaga: Ze względu EUR do USD można założyć USD do EUR jest odwrotna.

Mam nadzieję, że problem jest jasny.

Jakieś pomysły?

Answer 1

Skonstruuj wykres ważony skierowany z każdym wierzchołkiem oznaczonym nazwą waluty. Jeśli masz kurs dla waluty A do B, dodaj krawędź (A, B) z kursem wymiany jako wagą.

Jeśli posiadasz krawędź (A, B), ale nie krawędź (B, A), dodaj krawędź (B, A) o wadze 1 podzielonej przez masę (A, B).

Aby przeliczyć walutę C do D, stosuje się algorytm najkrótszej ścieżki, aby znaleźć najniższe ścieżkę masy od wierzchołka C do D's wierzchołka. Jeśli nie ma takiej ścieżki, konwersja nie może być wykonana. Zobacz directed graph with non-negative weights.

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

To niekoniecznie znaleźć najlepszy kurs wymiany, ponieważ stawki się mnożą. Można go znaleźć, aby znaleźć najlepszą stawkę za pomocą logarytmów kursów walutowych jako ciężarów krawędzi i używając algorytmu o najkrótszej ścieżce, który może obsłużyć ujemne grubości krawędzi.

Aby znaleźć drogę wymiany z najmniejszą ilością wymian dać każdą krawędź, która pasuje do bezpośredniej wymiany masy 1.

Answer 2

Zgadzam się w dużej mierze z Patricia. Ale ten problem z pewnością ma również związek z unikaniem arbitrażu. Sprowadza się to do "najkrótszej ścieżki" (najniższy koszt) z waluty A do waluty B. Najkrótsze algorytmy ścieżki są dobrze zbadane i udokumentowane. Sprawdź ich w kormen i nity.