Найти формулу для подсчёта всех вариантов троек значений валютных пар

Question

В первой строке вводятся три целых числа - курс валют. Во второй строке вводится три целых чилса - кол-во первой второй и третьей валюты соответственно.Допутим у нас есть три валюты A, B и С и каждая из них имеет свою ценность a b и c соответственно: если мы хотим обменять валюту A на валюту B, то мы должны отдать ровно a единиц валюты А и получить взамен ровно b единиц валюты B. Требуется подсчитать количество разных троек значений, которые мы можем получить путем обменных операций. Желательно на языке java, но можно и просто формулу вывести.

Пример 1:

 1 1 1
 1 0 2

Вывод: 10

Пример 2:
 1 2 3
 3 4 5

Вывод: 28

Answer 1

Если готовая формула не приходит на ум, но можно разложить задачу на элементарные подзадачи – время использовать рекурсию :)

Набросал код на C#, показать идею:

static List<(int, int, int)> results;

static void MakeExchange(int[] currencyValues, int[] currencyAmounts)
{
    // инициализация рекурсии
    results = new();
    results.Add((currencyAmounts[0], currencyAmounts[1], currencyAmounts[2]));
    MakeExchangeStep(currencyValues, currencyAmounts, currencyAmounts);
}

static void MakeExchangeStep(int[] currencyValues, int[] currencyAmounts, int[] currentAmounts)
{
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
        {
            if (i == j) continue;
            if (currentAmounts[i] < currencyValues[i]) continue; // если валюты I (которую "отдаем") "мало" - то пропускаем ее

            var newAmounts = new int[3]; // создаем копию массива остатков валют, т.к. массивы передаются по ссылке
            currentAmounts.CopyTo(newAmounts, 0);
            newAmounts[i] -= currencyValues[i]; // отдаем i единиц валюты I
            newAmounts[j] += currencyValues[j]; // получаем "взамен" j единиц валюты J

            // формируем комбинацию остатков и смотрим, получали ли мы ее ранее
            var result = (newAmounts[0], newAmounts[1], newAmounts[2]);
            if (!results.Contains(result))
            {
                // если нет - добавляем комбинацию в список результатов и запускаем по ней шаг рекурсии
                results.Add(result);
                MakeExchangeStep(currencyValues, currencyAmounts, newAmounts);
            }
        }
}

Идея в том, что на вход шага рекурсии мы получаем комбинацию остатков валют и пытаемся совершать всевозможные обмены каждой валюты на каждую по "одной" единице с соблюдением ограничений (имеется в виду минимальное количество валюты исходя из ее ценности). Если после очередного обмена мы получили новую комбинацию - запускаем по ней рекурсию. Явного выхода из рекурсии нет, т.к. она закончится естественным образом найдя все возможные комбинации остатков валют и не запустит более сама себя. Можно даже формально довольно несложно доказать останов и полноту рекурсии.

Небольшая ремарка: для упрощения кода я использовал структуру ValueTuple (синтаксис (newAmounts[0], newAmounts[1], newAmounts[2])), которая сама умеет сравнивать себя по значениям своих полей. В целом, здесь будет лучше написать, например, обертку на массивом, оставив индексацию и реализовав Equals() так, чтобы он сравнивал массивы поэлементно (хотя в Java вроде именно это делает Arrays.equals() - поправьте, если не прав). Тогда получим универсальное решение для любой длины входных данных.

Тест:

MakeExchange(new[] { 1, 1, 1 }, new[] { 1, 0, 2 });
Console.WriteLine(results.Count); // 10

MakeExchange(new[] { 1, 2, 3 }, new[] { 3, 4, 5 });
Console.WriteLine(results.Count); // 28

Answer 2

В общем случае нам нужно решить уравнение: ax + by + cz = sum, где sum = ax + by + cz (из исходных данных), a,b,c - константы (курс валют). По сути нужен тройной цикл для перебора всех подходящих x,y,z - количество валюты (наши ответы). Однако для второго примера: 1 2 3 3 4 5 Ответ будет 65, что вроде как неверно, но может они опечатались, потому что логика сходится.

БЛОГ НА HUSL

Найти формулу для подсчёта всех вариантов троек значений валютных пар

Ответы (2 шт):