时间戳

首页 > 解决方案 > 如何通过将数字列表中的数字相加并返回使用的数字来找到给定的数字？

c# - 如何通过将数字列表中的数字相加并返回使用的数字来找到给定的数字？

问题描述

“大家好，我试图解决一个非常奇怪的问题。我将举一个例子来解释我想要实现的目标。

我有一个 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,
};

标签： c#listrecursionnumbersadd

解决方案

Ifvalues是一个数字的所有幂的列表（在您的示例中，是 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)}");

看直播

推荐阅读