c - 一个程序，在整数数组中搜索 10 个数字，以确定它们的总和是否等于给定的 nb

Question

给定一个包含 100 个整数的数组 a 和一个整数 x，你需要编写一个程序来查找其中是否有 10 个整数，且它们的总和等于 x

我的方法是举例说明如何找到 3 个总和等于 x 的整数:

for(i=0;i<100;i++)
for(j=i+1;j<100;j++)
   for(k=j+1;j<100;j++)
      if(a[i]+a[j]+a[k]==x) {found=1;break;}
if(found==1) 
printf("+ve result\n"); 
else printf("-ve result\n");

问题是，如果我们想应用这个方法来找到 10 个与 x 相等的数字，那么如果我们按照这里写的嵌套循环方法来实现，那么它会非常大，所以任何人都有关于如何实现的想法这段代码？

Answer 1

问题不在于程序太大。实际上，它不会超过二十行，大多数人会称之为“小”。

问题是执行时间。您可以计算大约 20 万亿个不同的金额。这里有一个提示:由于您计算了 20 万亿个总和，您会期望其中大多数给出相同的结果。那么如何避免计算大多数时间相同的数字呢？

我将定义集合 S (i, j, x) = { 整数集 0 ≤ k ≤ x，其中 k 是前 j 个整数中至多 i 的总和}。如果 S (10, 100, x) 包含数字 x，则您有一个解决方案。 S (0, j, x) 是包含数字 0 的集合。i ≤ 10 和 j ≤ 100 的所有其他集合都很容易计算。

我假设你应该找到不同索引处的数字。如果这不是必需的，那就更简单了；您只需要找到最多包含 i 个数字之和的集合。