算法得到哪些值使數組中的給定數字的總和

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