获取哪些值使数组中给定数字的总和的算法

Question

我不知道搜索或google所以我在这里问。我有一个固定大小的整数数组，完全符合这个逻辑。

sample [1,2,4,8,16,32]

现在我得到一个数字，例如 26。我将找到其总和等于该数字的数字，在本例中为 [2,8,16]

对于 20 的数字，它将是 [4,16]

对于 40 是 [8,32]

对于 63，它是所有这些数字 [1,2,4,8,16,32]

正确的算法是什么？

我很清楚，总有这个数字是前一个值的两倍的延续。以及只有给定数组中的数字总和为给定数字，并且每个数字将仅使用一次或 none

如果在 C# 方法中采用整数数组和一个整数值，并且 returns 包含对给定数组中此数字求和的整数的整数数组将是首选。

谢谢

Answer 1

如您所见，数字是以 2 为底，这意味着您可以轻松使用 shift。

你可以试试这个：

private IEnumerable<int> FindBits(int value)
{
    // check for bits.
    for (int i = 0; i < 32; i++)
    {
        // shift 1 by i
        var bitVal = 1 << i;   // you could use (int)Math.Pow(2, i); instead
        // check if the value contains that bit.
        if ((value & bitVal) == bitVal)
            // yep, it did.
            yield return bitVal;
    }
}

此方法将检查设置了哪些位并将它们 return 作为可枚举的。（可以转换为列表数组）

用法：

// find the bits.
var res = FindBits(40).ToArray();

// format it using the string.join
var str = $"[{string.Join(",", res)}]";

// present the results
Console.WriteLine(str);

结果 [8,32]

额外信息：

                          counter
00000001 =   1     = 1 << 0
00000010 =   2     = 1 << 1 
00000100 =   4     = 1 << 2
00001000 =   8     = 1 << 3
00010000 =  16     = 1 << 4
00100000 =  32     = 1 << 5
01000000 =  64     = 1 << 6
10000000 = 128     = 1 << 7

不用编写所有组合，而是创建一个用于计数器的 for 循环。

一些多余的废话：

如果你喜欢 lambda，你可以用这个替换 FindBits：

private Func<int, IEnumerable<int>> FindBits = (int value) => Enumerable
    .Range(0, 31)
    .Select(i => 2 << i).Where(i => (value & i) == i);

但最好保留它simpel/readable。

Answer 2

首先你应该注意到

 ( 1    2    4    8    16 ... ) = (2^0  2^1  2^2  2^3  2^4 ... )

这与查找十进制数的二进制编码相同。您正在寻找的是一种将十进制或 10 进制数转换为二进制或 2 进制数的算法。

算法非常简单：

public List<int> dec_to_bin(int num)
{
    List<int> return_list = new List<int>();
    int index = 0; 
    int remainder = num;
    int bit = 0;

    while (remainder > 0)
    {
        bit = remainder % 2;

        if (bit == 1 )
        {
            return_list.Add((int)Math.Pow(2, index));
        }

        remainder = remainder / 2; 
        index = index + 1;
   }

   return return_list;
}

不过，还有一种更好的方法，那就是使用已经是二进制的数字的底层编码。

public List<int> dec_to_bin(int num)
{
    List<int> return_list = new List<int>();
    int value = 1; 

    while( value < num )
    {
         if( (value & num) == value )
         {
             return_list.Add(value);
         }
         value = value * 2; 
    }
    return return_list;
}

Answer 3

我不太明白“采用整数数组”部分，因为这种求和的创建仅适用于 2 的幂数。

    private int[] count (int num)
    {

        int factor = 0;
        List<int> facts = new List<int>();
        while (num > 0)
        {
            int counter = 0;
            int div = num;
            int remainder = 0;
            while (remainder == 0)
            {
                remainder = div % 2;
                div = div / 2;
                counter++;
            }
            factor = 1;
            for (int i = 1; i < counter; i++) 
                factor *= 2;
            num = num - factor;
            facts.Add(factor);
        }

        return (facts.ToArray());
    }

Answer 4

另一种表达您的要求的方法是 "What are the unique powers of 2 that sum to a given integer?" 由于计算机本身以 2 的幂工作，因此大多数语言都有内置的好东西可以非常简洁地做到这一点.

作为奖励，您可以使用现有的 .Net 类型和方法来消除编写自己的循环的需要。

这是一种方法：

IEnumerable<int> GetCompositePowersOf2(int input) =>
    //convert to enumerable of bools, one for each bit in the 
    //input value (true=1, false=0)
    new BitArray(new[] { input }).Cast<bool>()
    // get power of 2 corresponding to the position in the enumerable 
    // for each true value, gets 0 for false values.
    .Select((isOne, pos) => isOne ? (1 << pos) : 0)
    //filter out the 0 values
    .Where(pow => pow > 0);

获取哪些值使数组中给定数字的总和的算法

Algorithm to get which values make sum of a given number from array

c#

arrays

algorithm

math

linear-algebra