Простые ответы псевдокода на алгоритмы программирования

Проблема:

Группа друзей отправилась в отпуск и иногда одалживала друг другу деньги. Например, Алиса заплатила за обед Билла за 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

Решение в псевдокоде

Решение:

  1. Общий баланс прибылей/убытков
  2. Распределить, чтобы погасить все долги

Плавник-