Простые ответы псевдокода на алгоритмы программирования
Проблема:
Группа друзей отправилась в отпуск и иногда одалживала друг другу деньги. Например, Алиса заплатила за обед Билла за 10 долларов. Позже Крис дал Алисе 5 долларов за поездку на такси. Мы можем смоделировать каждую транзакцию как кортеж (x, y, z), что означает, что человек x передал человеку y $z. Предполагая, что Алиса, Билл и Крис являются людьми 0, 1 и 2 соответственно (0, 1, 2 - это идентификатор человека), транзакции могут быть представлены как [[0, 1, 10], [2, 0, 5] ].
Учитывая список транзакций между группой людей, верните минимальное количество транзакций, необходимых для погашения долга.
Примечание:
Транзакция будет представлена в виде кортежа (x, y, z). Обратите внимание, что x ≠ y и z > 0. Идентификаторы людей могут быть нелинейными, например. у нас могут быть лица 0, 1, 2 или у нас также могут быть лица 0, 2, 6. Пример 1:
Input: [[0,1,10], [2,0,5]]
Output: 2
Explanation: Person #0 gave person #1 $10. Person #2 gave person #0 $5.
Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.
Пример 2:
Input: [[0,1,10], [1,0,1], [1,2,5], [2,0,5]]
Output: 1
Explanation: Person #0 gave person #1 $10. Person #1 gave person #0 $1. Person #1 gave person #2 $5. Person #2 gave person #0 $5.
Therefore, person #1 only need to give person #0 $4, and all debt is settled.
Постановка проблемы: Сторонний источник
Пример повторных итераций оператора
Из примера 1:
[[0,1,10], [2,0,5]]
#0 дает #1 $10
#2 дает #0 $5
0: -10 (+5) = -5
1: (+10) = 10
2: -5 = -5
№ 1 дает № 0 и № 2 по 5 долларов каждый
Из примера 2:
Человек №0 дал человеку №1 10 долларов.
Человек №1 дал человеку №0 1 доллар.
Человек №1 дал человеку №2 5 долларов.
Человек №2 дал человеку №0 5 долларов.
0: -10 (+1, +5) -4
1: -6 (+10) 4
2: -5 (+5) 0
Решение в псевдокоде
Решение:
- Общий баланс прибылей/убытков
- Распределить, чтобы погасить все долги
Плавник-