Блог

Главная - Вопросы по программированию - Как найти заданное число путем сложения чисел из списка чисел и возврата использованных чисел?

Как найти заданное число путем сложения чисел из списка чисел и возврата использованных чисел?

#c# #list #recursion #numbers #add

Вопрос:

«Прошу всех, я пытался решить проблему, которая довольно странная. Я собираюсь привести пример, чтобы объяснить, чего я пытаюсь достичь.

У меня есть массив uint. Учитывая определенное число «n», как мне найти единственное решение, которое дает мне числа, суммируемые до «n»? Я говорю о «единственном решении», потому что есть только решение для достижения этого числа.

 // This is not my array, but it's pretty similar.
// Given number: 96
// Used numbers to reach it: 32, 64

uint[] values = new uint[]
{
    1,
    2,
    4,
    8,
    16,
    32,
    64,
    128,
    256,
    512,
    1024,
    2048,
};

Ответ №1:

If values — это список всех степеней числа (в вашем примере степени 2). Затем вы можете просто просмотреть список степеней от конца к началу, чтобы найти значения, которые выше числа, которое вы разбиваете на части, и вычесть их из числа (жадный метод):

 private static IEnumerable<uint> FindParts(uint number, uint []powers)
{
    for (var i = powers.Length - 1; i >= 0; i--)
    {
        if (number >= powers[i])
        {
            yield return powers[i];
            number -= powers[i];
        }
    }
}

и используйте его как

 uint randomNumber = (uint)new Random().Next(4095);
var parts = FindParts(randomNumber, values);

Console.WriteLine($"{randomNumber}={string.Join(' ', parts)}");

Смотрите вживую

Ответ №2:

Ваша проблема — довольно простое математическое уравнение, поскольку все ваши числа равны степеням 2, вам лучше перейти на веб-сайт математики, чтобы изучить эти варианты

Однако, вот комбинаторный общий подход грубой силы для любого списка чисел

Учитывая

расширения unit sum

 public static uint Sum(this IEnumerable<uint> source)
{
   uint sum = 0;
   checked
   {
      return source.Aggregate(sum, (current, v) => current   v);
   }
}

Способ получения комбинаций

 public static IEnumerable<T[]> GetCombinations<T>(T[] source)
{
   for (var i = 0; i < (1 << source.Length); i  )
      yield return source
         .Where((t, j) => (i amp; (1 << j)) != 0)
         .ToArray();
}

Способ фильтрации целей

 public static IEnumerable<uint[]> GetTargets(IEnumerable<uint> source, uint target) 
   => GetCombinations(source.ToArray())
      .Where(items => items.Sum() == target);

Использование

 uint[] values = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, };

foreach (var found in GetTargets(values,96))
   Console.WriteLine(string.Join(", ", found));

Вывод

 32, 64

Полная демонстрация здесь

Примечание. если вы используете это с любым списком произвольного размера, ожидайте, что ответ будет ждать много жизней

Метки: ,