我一整天都在为以下问题而苦苦挣扎。我一开始就有问题。我不知道如何使用递归来解决这个特定问题。我将非常感谢您的帮助,因为我的期末考试还有几天。干杯
假设有一个包含“n”个元素的整数数组“a”。编写递归函数 sumExists
如果可以将 m
写为元素之和,则对于给定的数字 m
返回 1数组 a
的数组,如果不是,则为 0。数组“a”中的元素只能使用一次。函数 sumExists
的原型(prototype)是:int sumExists( int a[] , int n, int m );
示例:
a[5] = { 15, 9, 4, 2, 1 } , n=5, m=17. Function sumExists returns 1;
a[5] = { 15, 9, 4, 2, 1 } , n=5, m=8. Function sumExists returns 0;
代码:
int sumExists(int a[],int n, int m) {
int i;
if(m == 0) return 1;
for(i = n-1; i >= 0; i--) {
m = m - a[i];
if(sumExists(a,i,m)) return 1;
}
return 0;
}
最佳答案
试试这个:
int sumExists(int a[], int n, int m) {
if (n == 0)
return m == 0;
return sumExists(a, n - 1, m - a[n - 1]) || sumExists(a, n - 1, m);
}
递归检查:
是否存在与 n-1
元素的总和(因为使用大小 n-1
调用并减去 a来自
。就好像在总和 m
的 [n-1]m
中包含 a[n-1]
)。
或
如果 没有 n-1
元素的总和(跳过 a[n-1]
并使用 a 检查[1..n-1]
).
关于C练习任务(递归),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25796666/