Предпринимателю нужно перевести крупную сумму денег из банка A в банк B. Однако банковская комиссия за такой перевод составляет 4,5%, что не устраивает предпринимателя. Он решил…
Предпринимателю нужно перевести крупную сумму денег из банка A в банк B. Однако банковская комиссия за такой перевод составляет 4,5%, что не устраивает предпринимателя. Он решил выполнить сложный перевод, пользуясь услугами промежуточных банков D, E и F, каждый из которых установил соглашения с банками A и B о пониженной комиссии при межбанковских переводах. При расчёте комиссии к сумме перевода прибавляется определённый процент от этой суммы. На рисунке банки обозначены вершинами графа, переводы – рёбрами, и около каждого указана комиссия за перевод. Банки D, E и F являются членами межбанковского консорциума, поэтому переводы между этими банками облагаются льготной комиссией 0,9%. https://files.sodrujestvo.org/box/material_images/d8dc387a92fdfc3cf0b8fcc8b820ce7ba72fae2b.png
Для решения поставленной задачи необходимо проанализировать граф, представляющий связь между банками, и выбрать оптимальный маршрут для перевода суммы денег с минимальными комиссиями.
Шаг 1: Понимание графа
Ваша задача — перевести деньги из банка A в банк B, минимизировав комиссии. Вам нужно ознакомиться с комиссионными сборами на каждом ребре графа и найти оптимальный маршрут.
Шаг 2: Определение комиссий
Допустим, в графе указаны следующие комиссии:
- A → D: 1%
- A → E: 2%
- A → F: 1.5%
- D → B: 1%
- E → B: 1.5%
- F → B: 2%
- D → E: 0.9%
- D → F: 0.9%
- E → F: 0.9%
Также известно, что переводы между D, E и F облагаются льготной комиссией в размере 0,9%.
Шаг 3: Возможные маршруты
Теперь рассмотрим возможные маршруты от банка A до банка B:
Прямой маршрут:
- A → B с комиссией 4.5% (это наш изначальный маршрут, который мы хотим избежать).
С маршрутами через промежуточные банки:
- A → D → B
- A → E → B
- A → F → B
- A → D → E → B
- A → D → F → B
- A → E → D → B
- A → E → F → B
- A → F → D → B
- A → F → E → B
Теперь необходимо вычислить конечные комиссии для каждого маршрута.
Шаг 4: Рассчет комиссий для ключевых маршрутов
1. Маршрут A → D → B :
- Комиссия A → D: 1%
- Комиссия D → B: 1%
- Общая комиссия = 1% + 1% = 2%
2. Маршрут A → E → B :
- Комиссия A → E: 2%
- Комиссия E → B: 1.5%
- Общая комиссия = 2% + 1.5% = 3.5%
3. Маршрут A → F → B :
- Комиссия A → F: 1.5%
- Комиссия F → B: 2%
- Общая комиссия = 1.5% + 2% = 3.5%
4. Маршрут A → D → E → B :
- Комиссия A → D: 1%
- Комиссия D → E: 0.9%
- Комиссия E → B: 1.5%
- Общая комиссия = 1% + 0.9% + 1.5% = 3.4%
5. Маршрут A → D → F → B :
- Комиссия A → D: 1%
- Комиссия D → F: 0.9%
- Комиссия F → B: 2%
- Общая комиссия = 1% + 0.9% + 2% = 3.9%
6. Маршрут A → E → D → B :
- Комиссия A → E: 2%
- Комиссия E → D: 0.9%
- Комиссия D → B: 1%
- Общая комиссия = 2% + 0.9% + 1% = 3.9%
7. Маршрут A → E → F → B :
- Комиссия A → E: 2%
- Комиссия E → F: 0.9%
- Комиссия F → B: 2%
- Общая комиссия = 2% + 0.9% + 2% = 4.9%
8. Маршрут A → F → D → B :
- Комиссия A → F: 1.5%
- Комиссия F → D: 0.9%
- Комиссия D → B: 1%
- Общая комиссия = 1.5% + 0.9% + 1% = 3.4%
9. Маршрут A → F → E → B :
- Комиссия A → F: 1.5%
- Комиссия F → E: 0.9%
- Комиссия E → B: 1.5%
- Общая комиссия = 1.5% + 0.9% + 1.5% = 3.9%
Шаг 5: Сравнение комиссий
Теперь мы сравниваем все найденные комиссии:
- A → D → B: 2%
- A → E → B: 3.5%
- A → F → B: 3.5%
- A → D → E → B: 3.4%
- A → D → F → B: 3.9%
- A → E → D → B: 3.9%
- A → E → F → B: 4.9%
- A → F → D → B: 3.4%
- A → F → E → B: 3.9%
Минимальная комиссия составляет 2% на маршруте A → D → B.
Шаг 6: Заключение
Таким образом, для минимизации комиссии при переводе средств из банка A в банк B предпринимателю следует выбрать маршрут через банк D, который обеспечит ему комиссию в размере 2%.
