C语言 递归打印出给定数的任何迭代,使其和等于给定数

mpgws1up  于 2023-06-28  发布在  其他
关注(0)|答案(2)|浏览(135)

我们给出一个数字数组[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和一个非常大的负数的出口号码,这意味着有一个问题的地方。

bq3bfh9z

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. solve(options,choices,target):
    1.如果目标为零,
    1.打印出选择的向量。
    1.返回。
    1.对于每个选项,
    1.如果选项小于或等于目标,
    1.将选项追加到选项列表。
    1.调用我们自己,但传递目标减去选项作为目标。
    1.从选项列表中删除前面附加的选项。
    就是这样,因为你已经知道了选择的最大数量,所以为选择分配内存可以提前完成,所以从选择中添加和删除元素是非常简单的。
    vector的具体实现取决于您。你可以像现在这样使用一个结构体,或者大小和值数组可以是单独的参数。
bvhaajcl

bvhaajcl2#

代码的关键问题是,当sum(sol,pos,n)没有返回 true(找到的总和)时,即使总和超过n,它也会继续。这导致了无限的逃避。
快速修复只是防止过度递归。

void mult_princ(val_t *val, int *sol, int n, size_t pos) {
  if (pos >= n) {
    return;
  }
  ...

输出量

2 2 2 2 2 
2 2 6 
2 6 2 
6 2 2

一个更好的解决方案是让sum(sol,pos,n)返回-1,0,1来表示sum太小,sum正好,sum太大。

// if(sum(sol,pos,n))
int result = sum(sol,pos,n);
if (result > 0) return;
if (result == 0) {
  // print solution, then return
}
// Continue on and recurse.

相关问题