我们给出一个数字数组[2,6]
,和应该是10,我们需要打印出任何迭代,以便该数组的和等于10,在这种情况下,这些是
2,2,2,2,2
6,2,2
2,6,2
2,2,6
这是我现在的代码
#include <stdio.h>
#include <stdlib.h>
typedef struct val_s {
int num_choice;
int *choices;
} val_t;
int sum(int *sol,int pos,int n) {
int s=0;
for (int i = 0; i < pos; ++i) {
s=s+sol[i];
}
if(s==n)
return 1;
return 0;
}
void mult_princ(val_t *val,int *sol, int n, int pos)
{
if(sum(sol,pos,n))
{
for (int i = 0; i< pos; i++) {
printf("%d ",sol[i]);
}
printf("\n");
return;
}
for (int i = 0; i < val[i].num_choice; ++i) {
sol[pos]=val[pos].choices[i];
mult_princ(val,sol,n,pos+1);
}
return;
}
int main() {
int *sol;
val_t *val;
int n=10;
val = malloc(n*sizeof(val_t));
if (val == NULL) {
exit(1);
}
for (int i = 0; i < n; ++i) {
val[i].num_choice=2;
val[i].choices = malloc(val[i].num_choice * sizeof(int));
if (val[i].choices == NULL) {
exit(1);
}
val[i].choices[0] = 2;
val[i].choices[1] = 6;
}
sol = malloc(n * sizeof(int));
if (sol == NULL)
{
exit(1);
}
mult_princ(val,sol,n,0);
return 0;
}
我对如何解决这个问题的想法是:
我们构建了一个递归函数,它将数字1乘以1相加,当提到给定条件时,它会打印出数组。每次我们重复时,我们都会检查退出条件,其中有另一个名为sum的函数,它接受当前数组和当前大小(在本例中为pos)并进行求和。如果和是我想要的,它将返回1,这将允许递归退出。
至少这是我试图去,但所有它打印的是一个2,2,2,2,2
和一个非常大的负数的出口号码,这意味着有一个问题的地方。
2条答案
按热度按时间bq3bfh9z1#
您有一个由相同的
val_t
结构组成的数组,这毫无意义。我认为最根本的问题是你混淆了 * 可用的选项 *(2,6),和 * 做出的选择 (例如:2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
有一个简单的解决方案,使用递归。
首先,你需要一个可用选项的向量。它在算法中不会改变。
您还需要第二个向量,其中包含您到目前为止所做的选择。它将需要多达 * floor(target/smallest_option) 个元素。它最初是空的。
递归解决方案如下所示:
1.如果目标为零,
1.打印出选择的向量。
1.返回。
1.对于每个选项,
1.如果选项小于或等于目标,
1.将选项追加到选项列表。
1.调用我们自己,但传递目标减去选项作为目标。
1.从选项列表中删除前面附加的选项。
就是这样,因为你已经知道了选择的最大数量,所以为选择分配内存可以提前完成,所以从选择中添加和删除元素是非常简单的。
vector的具体实现取决于您。你可以像现在这样使用一个结构体,或者大小和值数组可以是单独的参数。
bvhaajcl2#
代码的关键问题是,当
sum(sol,pos,n)
没有返回 true(找到的总和)时,即使总和超过n
,它也会继续。这导致了无限的逃避。快速修复只是防止过度递归。
输出量
一个更好的解决方案是让
sum(sol,pos,n)
返回-1,0,1来表示sum太小,sum正好,sum太大。