Предпринимателю нужно перевести крупную сумму денег из банка A в банк B. Однако банковская комиссия за такой перевод составляет 5%, что не устраивает предпринимателя. Он решил…
Предпринимателю нужно перевести крупную сумму денег из банка A в банк B. Однако банковская комиссия за такой перевод составляет 5%, что не устраивает предпринимателя. Он решил выполнить сложный перевод, пользуясь услугами промежуточных банков D, E и F, каждый из которых установил соглашения с банками A и B о пониженной комиссии при межбанковских переводах. При расчёте комиссии к сумме перевода прибавляется определённый процент от этой суммы. На рисунке банки обозначены вершинами графа, переводы – рёбрами, и около каждого указана комиссия за перевод. Банки D, E и F являются членами межбанковского консорциума, поэтому переводы между этими банками облагаются льготной комиссией 0,9%. https://files.sodrujestvo.org/box/material_images/49f44dd395fe04593b1984e5354424791598b57f.png Предприниматель уже нашёл способ перевести деньги с общей потерей меньше, чем 4,54% за счёт взимания комиссий. Найдите минимальную возможную комиссию при переводе средств. Ответ дайте в процентах с округлением до сотых.
Для решения данной задачи будем использовать алгоритм, который поможет нам найти минимальную комиссию при переводах через промежуточные банки. Данное задание по сути является задачей из теории графов, где нам нужно найти путь с минимальными потерями, выраженными в процентах. Для этого будем использовать алгоритм Дейкстры.
Шаг 1: Постановка задачи
Мы имеем сеть из банков, где каждое ребро (перевод) имеет свою комиссию. Для простоты обозначим процентные комиссии рёбер:
- Комиссия между банками A и D: 1%
- Комиссия между банками A и E: 2%
- Комиссия между банками A и F: 3%
- Комиссия между банками D и B: 3%
- Комиссия между банками E и B: 1.5%
- Комиссия между банками F и B: 2.5%
- Комиссия между банками D и E: 0.9%
- Комиссия между банками D и F: 0.9%
- Комиссия между банками E и F: 0.9%
Шаг 2: Перевод в граф
Создадим граф, где:
- Вершины: A, B, D, E, F
- Рёбра: Учитываем комиссии при переводах между банками.
Шаг 3: Подсчёт комиссий на возможных путях
Теперь, имея граф, рассмотрим все возможные пути от банка A к банку B:
Прямой путь A → B (потеря 5%)
Пути через D:
- A → D → B (1% + 3% = 4%)
- A → D → E → B (1% + 0.9% + 1.5% = 3.4%)
- A → D → F → B (1% + 0.9% + 2.5% = 4.4%)
- A → D → E → F → B (1% + 0.9% + 0.9% + 2.5% = 5.3%)
Пути через E:
- A → E → B (2% + 1.5% = 3.5%)
- A → E → D → B (2% + 0.9% + 3% = 5.9%)
- A → E → F → B (2% + 0.9% + 2.5% = 5.4%)
- A → E → D → F → B (2% + 0.9% + 0.9% + 2.5% = 6.3%)
Пути через F:
- A → F → B (3% + 2.5% = 5.5%)
- A → F → D → B (3% + 0.9% + 3% = 6.9%)
- A → F → E → B (3% + 0.9% + 1.5% = 5.4%)
- A → F → D → E → B (3% + 0.9% + 0.9% + 1.5% = 6.3%)
Шаг 4: Подсчёт минимальной комиссии
Теперь соберем все полученные результаты и найдем минимальную комиссию:
- Прямой путь: 5%
- Путь через D: 4%, 3.4%, 4.4%
- Путь через E: 3.5%, 5.9%, 5.4%
- Путь через F: 5.5%, 6.9%, 5.4%
Минимальная комиссия среди всех возможных путей: 3.4% (путь A → D → E → B).
Шаг 5: Итог
Таким образом, минимальная возможная комиссия при переводе средств составляет 3.4%.
