Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
3 / 3 / 0
Регистрация: 28.05.2012
Сообщений: 23
1

Упрощение графа денежных переводов

14.10.2018, 18:47. Показов 619. Ответов 4

Допустим, имеется следующий лог переводов денежных сумм с одного счета на другой:

Код
A -> B 800
A -> B 800
B -> D 700
B -> C 800
C -> D 800
Мне нужен алгоритм, который минимизирует этот лог до вот такого:

Код
A -> D 1500
A -> B 100
У меня мозгов не очень хватает, чтобы в лоб самому придумать решение, но я вижу, что скорее всего это что-то про графы (эти записи в логе явно образуют однонаправленный граф), и наверняка есть готовые алгоритмы оптимизации таких графов, сжатия их до минимально возможных, чтобы

Код
        A
        | 1600
        v
        B
       / \
  800 /   \ 700
     /     \
    C--800->D
превратился в

Код
        A
       / \
  100 /   \ 1500
     /     \	
    B       D
Поделитесь полезной ссылью или своими мыслями по проблеме пжлст.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.10.2018, 18:47
Ответы с готовыми решениями:

Разработать систему денежных переводов банка
Задание 1 Создайте модель данных для следующей задачи: Разработать систему денежных переводов...

На сколько лет необходимо положить в банк сумму Х денежных единиц, чтобы получить сумму N денежных единиц (N> X)
Здравствуйте помогите пожалуйста сделать эту задачу в которой нужно использовать цикли. На...

Нахождение фактора графа и остова графа для некоторого произвольного графа (5-6 вершин)
Форумчане прошу помощь в выполнение задания по деск. мат. Задание: Нахождение фактора графа и...

Упрощение цикла сортировки элементов массивов. Упрощение цикла поиска нужного элемента в массиве
Уверен, что данный код можно написать компактнее чем есть сейчас. /*Опишите, используя...

4
1077 / 987 / 146
Регистрация: 19.02.2010
Сообщений: 3,027
14.10.2018, 20:02 2
PitMagnum, гуглите про клиринг (не клининг!).
0
399 / 278 / 78
Регистрация: 03.12.2015
Сообщений: 658
14.10.2018, 20:44 3
1. На первом шаге вычисляете итоговые результаты всех операций.

Пробегаетесь по всем операциям и прибавляете или отнимаете суммы на счетах.

A -> B 800 => A-=800, B+=800
A -> B 800 => A-=800, B+=800
B -> D 700 => B-=700, D+=700
B -> C 800 => B-=800, C+=800
C -> D 800 => C-=800, D+=800

Получаете итоговые изменения счетов, когда все операции будут выполнены.

Итого:
A = -800-800 = -1600
B = +800+800-700-800 = +100
C = +800-800 = 0
D = +700+800 = +1500

2. Решаете транспортную задачу

У Вас появились "производители" (счета, у которых отрицательный результат, в данном случае А) и "потребители" (счета, у которых положительный результат, в данном случае B и D). Оптимизируете потоки между ними
1
3331 / 2704 / 733
Регистрация: 25.03.2012
Сообщений: 9,787
Записей в блоге: 1
14.10.2018, 20:53 4
что-то вообще не понимаю, где тут нужен особый алгоритм. Что может быть неоптимального в решении "в лоб"?
0
3 / 3 / 0
Регистрация: 28.05.2012
Сообщений: 23
14.10.2018, 20:57  [ТС] 5
Мне не нужен особый алгоритм, мне нужен любой алгоритм. Под "в лоб" я имел ввиду, что я не смог сходу придумать решение и обратился за помощью. Которую мне, в общем-то, уже оперативно предоставил уважаемый vrm2.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.10.2018, 20:57

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

1c 7.7 Тарифы Почтовых Переводов
Друзья! Помогите... Где в 1С 7.7 ЗиК изменить тарифы на почтовый сбор, т.к. в марте месяце они...

Можно ли сделать хранение переводов в файле?
Очередной вопрос о реализации, можно ли сделать так с помощью php и можно ли вообще: прочитать...

Подсчитать сумму переводов на заданный расчетный счет
Помогите исправить ошибку, программа не счет. Задание : Написать программу о сумме переводов на...

Контент из переводов текста и картинок с англоязычного сайта
Приветствую всех! Появилась идея сделать сайт на тематику обзоров электроники. Так как...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.