如何使用递归解决 C 中的子集问题

Question

我是一个试图自学 C 的初学者，前几天我遇到了一个问题，我认为尝试用一个简短的程序来解决它会很酷。我发现它比我最初想象的要难一些。基本上问题是这样的。

我希望能够将 0..255 之间的单个 int 值（从不超出此范围）输入到函数中，并且函数内部有一个包含 8 个值的数组（1、2、4、8 , 16, 32, 64, 128), 可以通过加在一起得到单个 int 值。然后 return 可能的不同组合。即

目标 192

Returns 64、128

据我所知，这是一个子集问题，可以用递归来解决，但我真的很难将我发现的理论和例子付诸实践。如果有人可以帮助我，甚至让我朝着正确的方向尝试解决。

Answer 1

提示：尝试“按位与”运算符 (&)

Answer 2

首先，将 I/O 和算法分开是个好主意。所以你通常不应该设计接受用户输入的函数和同时执行一些算法。

接下来“可以递归解决”不是它自己的目标。递归是危险的、低效的并且难以阅读。在 C 编程中应该使用它的情况很少，初学者根本没有应该使用它的情况。大多数时候，C 中的递归简单地归结为：“我可以同时站在我的手上画这个谷仓”......好吧也许你可以，也许你可以做到而不会冒断脖子的风险，也许你甚至可以像直立一样快速完成（不太可能），但是为什么你会这样做？

撇开程序设计不谈，您要查找的算法与二进制数密切相关。任何基数中的任何数字都可以组成：

digit_n * baseⁿ + digit_n-1 * base^n-1... + digit₀ * base⁰.

如果是手动二进制（基数为 2）的数字，例如 111 可以手动解码为十进制为：

1 * 2² + 1 * 2¹ + 1 * 2⁰ = 4 + 2 + 1 位小数 = 7 位小数。

现在，如果我们将其与您的算法进行比较，上面以 2 为底数的乘数对应于 1、2、4、8...

方便的是，C 中的所有数字实际上都是原始二进制。他们只在做 user input/output 时被翻译到其他基地。因此，您的算法所需要的只是一种检查二进制数的各个数字是否已设置的方法。

这可以通过 &“按位与”和 <<“按位左移”运算符来完成。按位左移将值1左移得到各种乘数：0b=0、1b=1、10b=2、100b=4等。然后按位与从其余部分屏蔽掉一个单独的位，看看它是否被设置。如果未设置，那么通过上面的公式，我们得到该数字的 0*baseⁿ，因此它将为零，可以忽略。

为此编写实际的 C 代码实际上非常简单：

for(int i=0; i<8; i++)
{
  unsigned int mask = 1u << i; 
  if(mask & number)
  {
    printf("%u\n", mask);
  }
}

（这是使用无符号数来避免各种常见错误，但这是它自己的主题。）

如何使用递归解决 C 中的子集问题

How to use recursion for a sub set problem in C

recursion

dynamic