2

假设我们需要列出四个数字 A、B、C、D。A+B+C+D 的和为 10，每个数字的值在 [0, 10] 范围内。

找出所有可能的组合。

蛮力方式如下：

for (int A = 0; A <=10; ++A)
  for (int B = 0; B <=10-A; ++B)
  {
   if (A + B > 10) break;    
   for (int C = 0; C <=10-A-B; ++C)
   {
    if (A + B + C > 10) break;
    for (int D = 0; D <=10-A-B-C; ++D)
    {
       if (A + B + C + D == 10)
       {
         cout << "A: " << A << ",B: " << B << ",C: " << C << ",D: " << D << endl;
         break;
       }
       else if (A + B + C + D > 10)
         break;
    }
   }
  }

Q> 有没有更好的解决方案？

仅供参考：根据@rici 的建议更新代码

4

2 回答 2

0

您要求一种枚举整数分区的方法。链接的维基百科页面列出了几种方法。

于 2013-03-14T04:01:06.083 回答
0

像这样的东西怎么样：

void print4Partitions(int num) {
    for (int A=1; A<num-3; A++) {
        for (int B=A+1; B<num-A-2; B++) {
            for (int C=B+1; C<num-(A+B)-1; C++) {
                int D = num-A-B-C;
                printf("%d %d %d %d\n", A, B, C, D);
            }
        }
    }
}

这里的主要思想是：

  • 你真的不需要循环最后一个数字：它可以简单地计算，正如@nci 提到的那样， as A, B, C，并且要作为分区的数字唯一地确定D。
  • 您可以限制循环而不是测试和使用break语句，这应该会导致更快的代码。
于 2013-03-14T16:48:09.817 回答