算法得到哪些值使数组中的给定数字的总和

Question

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

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

现在我给一些例如26.我要去找其总和将使这个数字的号码，在这种情况下[2,8,16]

了许多20这将是[4,16]

40是[8,32]

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

的

什么是适当的算法呢？

我知道严格的说这个数字是前一个数值的两倍。 以及只有来自给定数组的数字将总结到给定的数字，每个数字将只用于一次或不使用

如果它将在C＃方法中获取ints和int值的数组，返回包含整数的int整数，这些整数将从给定的数组中总结出来。

谢谢

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; 
    } 
} 

此方法将检查设置了什么样的位并返回它们作为一个IEnumerable。 （其可转化为列表的阵列）

---

用法：

// 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循环做柜台。

---

一些额外的无感：

如果你喜欢拉姆达的，你可以用这个代替FindBits：

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

但它更好地保持它simpel /可读。

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()); 
    }