Валютные операции и математика
Честно говоря, я как-то не задумывался над следующим вопросом, а он интересный.
В мире есть куча разных валют, и больше суммы денег постоянно конвертируются из одной в другую. Курсы всех валют постоянно меняются.
Почему бы в какой-то момент не оказаться такой последовательности переводов из валюты в валюту - например франки -> фунты стерлингов -> тугрики -> рупии -> пиастры -> франки - так, что бы при последнем обмене получить больше, чем было исходно? Как проследить, что бы при любых изменениях курсов такое кольцо случайно не появилось бы?
Понятно, что просто просмативать все возможные цепочки - не лучшее решение. При полутора сотнях разных валют, возможных цепочек будет, мягко говоря, очень много.
Решение проблемы нашлось в теории графов - алгоритм Беллмана-Форда.
Вершины графа - валюты. Рёбра - переводы из валюты в валюту. Веса рёбер - минус логарифм от курса валют. После чего напускаем на полученный граф алгоритм поиска отрицательных колец. Если есть такое кольцо, то, найдя нужную сумму денег, можно неплохо заработать на пустом месте. :)
А самое главное - этот метод позволит получить решение уже сегодня, а не после следующего Большого Взрыва.
В мире есть куча разных валют, и больше суммы денег постоянно конвертируются из одной в другую. Курсы всех валют постоянно меняются.
Почему бы в какой-то момент не оказаться такой последовательности переводов из валюты в валюту - например франки -> фунты стерлингов -> тугрики -> рупии -> пиастры -> франки - так, что бы при последнем обмене получить больше, чем было исходно? Как проследить, что бы при любых изменениях курсов такое кольцо случайно не появилось бы?
Понятно, что просто просмативать все возможные цепочки - не лучшее решение. При полутора сотнях разных валют, возможных цепочек будет, мягко говоря, очень много.
Решение проблемы нашлось в теории графов - алгоритм Беллмана-Форда.
Вершины графа - валюты. Рёбра - переводы из валюты в валюту. Веса рёбер - минус логарифм от курса валют. После чего напускаем на полученный граф алгоритм поиска отрицательных колец. Если есть такое кольцо, то, найдя нужную сумму денег, можно неплохо заработать на пустом месте. :)
А самое главное - этот метод позволит получить решение уже сегодня, а не после следующего Большого Взрыва.