Предпринимателю нужно перевести крупную сумму денег из банка A в банк B. Однако банковская комиссия за такой перевод составляет 5,5%, что не устраивает предпринимателя. Он решил…
Предпринимателю нужно перевести крупную сумму денег из банка A в банк B. Однако банковская комиссия за такой перевод составляет 5,5%, что не устраивает предпринимателя. Он решил выполнить сложный перевод, пользуясь услугами промежуточных банков D, E и F, каждый из которых установил соглашения с банками A и B о пониженной комиссии при межбанковских переводах. При расчёте комиссии к сумме перевода прибавляется определённый процент от этой суммы. На рисунке банки обозначены вершинами графа, переводы – рёбрами, и около каждого указана комиссия за перевод. Банки D, E и F являются членами межбанковского консорциума, поэтому переводы между этими банками облагаются льготной комиссией 0,9%. Предприниматель уже нашел способ перевести деньги с общей комиссией меньше, чем 5,05%. Найдите минимальную возможную комиссию при переводе средств. Ответ дайте в процентах с округлением до сотых
Для решения этой задачи необходимо использовать идеи из теории графов и алгоритмы поиска кратчайшего пути. В данной ситуации банки представляют собой вершины графа, а комиссии — рёбра между этими вершинами.
Шаг 1. Понимание графа
- У нас есть несколько банков: A, B, D, E, и F.
- Между ними существуют переводы с комиссиями, указаны в процентах.
- Комиссия для перевода от A к B составляет 5,5%, а комиссия между банками D, E и F — 0,9%.
Шаг 2. Разработка модели
Перед тем как начать расчет, предположим, что:
- Сумма для перевода — 100 единиц денег (это упрощение, так как проценты одинаковы вне зависимости от суммы).
- Необходимо выяснить, какие пути существуют для перехода от банка A к банку B и какова минимальная комиссия.
Шаг 3. Направленные рёбра (переводы)
Предположим, у нас есть следующие предполагаемые переводы (это пример, вам нужно вставить свои данные):
- A → D: 1%
- A → E: 2%
- A → F: 3%
- D → B: 2%
- E → B: 1%
- F → B: 4%
- D → E: 0,9%
- D → F: 0,9%
- E → F: 0,9%
- F → D: 0,9%
- F → E: 0,9%
Шаг 4. Применение алгоритма
Используем алгоритм Дейкстры для поиска минимальной стоимости пути от A до B.
- Начальная сумма (на банке A) = 100
- Посчитаем комиссии для возможных путей от A до B:
Путь 1: A → D → B
- Комиссия A → D = 1%
- Комиссия D → B = 2%
- Общая комиссия: 1% + 2% = 3%
Средства после приведения к B:
100 * (1 - 0.03) = 97
Путь 2: A → E → B
- Комиссия A → E = 2%
- Комиссия E → B = 1%
- Общая комиссия: 2% + 1% = 3%
Средства после приведения к B:
100 * (1 - 0.03) = 97
Путь 3: A → F → B
- Комиссия A → F = 3%
- Комиссия F → B = 4%
- Общая комиссия: 3% + 4% = 7%
Путь 4: A → D → E → B
- A → D: 1%
- D → E: 0,9%
- E → B: 1%
Общая комиссия: 1% + 0.9% + 1% = 2.9%
Путь 5: A → D → F → B
- A → D: 1%
- D → F: 0,9%
- F → B: 4%
Общая комиссия: 1% + 0.9% + 4% = 5.9%
Путь 6: A → E → F → B
- A → E: 2%
- E → F: 0,9%
- F → B: 4%
Общая комиссия: 2% + 0.9% + 4% = 6.9%
Шаг 5. Определение минимальной комиссии
Сравнив все комиссии, мы видим, что минимальная возможная комиссия составила 2.9% при переводе по пути A → D → E → B.
Ответ
Минимальная возможная комиссия при переводе средств составляет 2.90%.
