c - 如何编写一个程序来列出用户输入的数字的所有可能的三位数加法解决方案。 (不能使用零)

Question

我想编写一个 C 程序，它将为我提供所有可能的方法来添加三个数字(不使用零)以等于用户输入的任何内容。例如，如果用户输入 4，则解决方案将为 1+1+2。如果用户输入 3，则唯一的解决方案将是 1+1+1。据我观察，4之后，总是有另一个解决方案。所以，如果输入 5，就会有 2 个解..1+1+3,2+2+1...如果输入 6，就会有 3 个解，并且解数总是增加 1。我无法弄清楚如何每次都获得所有答案的逻辑。我当前的代码有点暴力，只给我 1+1+(无论剩下的数字)解决方案，另一部分仅适用于一个解决方案，并且仅当它是奇数时。我当前的代码如下:

 #include <stdio.h>

int main(void)
{
   int num;
   printf("Enter a number: ");
   scanf("%d",&num);
   if(num < 3)
     printf("No solution.\n");

   int p = num/2;
   int q = num%2;
   int v = num - (p+q);

   printf("%d+%d+%d\n",p,q,v);//prints a single solution but only works        for odd numbers

   int k = num - 2;
   printf("1+1+%d\n",k);
   //prints a single solution but only 1+1+whatever is left
   return 0;
}

任何建议或不同的方法来解决这个问题都会非常有帮助。有人告诉我可以执行 3 个嵌套 for 循环，但我正在寻找不同的方法。

Answer 1

这个解决方案使用 3 个嵌套的 for 循环(尽管我认为其他的东西会更好)。至少还有另一种方法:

• 使用递归
• 可能还有另一种:用数学方法解决问题(这将是最优雅的)

它仍然是蛮力，但不会尝试一些我们确信不会产生(好的)结果的组合。由于数字顺序并不重要，这意味着例如:

6 =

• 1 + 2 + 3
• 1 + 3 + 2
• 2 + 1 + 3
• 2 + 3 + 1
• 3 + 1 + 2
• 3 + 2 + 1

(1, 2, 3) 的所有 6 排列构成一个单一解决方案，这 3 个数字排列中只有一个变体很重要。
我们可以利用它来发挥我们的优势:我们选择了 3 个数字序列，其中 No1 <= No2 <= No3 (< em>No1 + No2 + No3 = N(由用户输入)。这意味着计算操作较少:而不是对于 3 个索引(i、j、k)中的每一个，它们对应于 ( No1、No2、No3)在整个 [1 .. n] 间隔上滑动:

1. 外部索引 (i) 只迭代[1 .. n/3](没有必要走得更高，因为其他 2 个数字大于或等于它，如果是的话，总和将大于n)。仅此一项就将操作数量减少到三分之一
2. 中间索引 (j) 仅迭代[i .. n/2](它不会低于前一个索引)因为 i <= j，并且高于 n/2 是没有意义的，因为另一个数字将大于或等于它，并且总和将再次大于n)
3. 内部索引 (k) 仅迭代[j .. n - 2](原因很明显)。

注释:

• 有可能(实际上，我很确定)可以进一步减少操作
• 声明的最后 3 个变量(具有虚假名称)是为了加快速度:它们在开始时计算一次(尽管我可能会在这里重新发明轮子，因为我很确定编译器正在优化这些类型)的情况)。
  但是，无论如何优化，该算法仍然O(n ** 3)，效率非常低。我觉得我遗漏了一些明显的东西，但我无法指出它
• 我检查了(虽然不是很彻底)，它似乎没有跳过解决方案

代码.c:

#include <stdio.h>

void generate(int n) {
    int i, j, k, count = 0, n_div_3 = n / 3, n_div_2 = n / 2, n_minus_1 = n - 1;
    for (i = 1; i <= n_div_3; i++)
        for (j = i; j <= n_div_2; j++)
            for (k = j; k < n_minus_1; k++)
                if (i + j + k == n) {
                    printf("Solution %d: %d %d %d\n", count++, i, j, k);
                    break;
                }
    printf("\n%d solutions\n", count);
}

int main () {
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);
    generate(num);
    return 0;
}