c - 使用递归的解决方案数量

Question

我一直在尝试使用递归解决问题:

商店中的商品有以下费用:

• 球:1
• 帽子:5
• 果酱:20
• Crystal :50

如果您想在这些商品上花费正好 300 单位，请查找您可以进行的所有购买组合。

使用 for 循环可以轻松解决这个问题，但我想做得更好并使用递归，因为所有迭代解决方案的问题也有相应的递归解决方案。

我的尝试是:

int recurse(int x, int y, int z, int w, int n)
{
 if(x > 300 || y > 60 || z > 15 || w > 6)
    return n;

 if(x + 5 * y + 20 * z + 50 * w == 300)
    return n + 1;

 recurse(x+1, y, z, w, n);
 recurse(x, y+1, z, w, n);
 recurse(x, y, z+1, w, n);
 recurse(x, y, z, w+1, n);
}

int main()
{

  int n;
  n = recurse(0,0,0,0,0);
  printf("Answer: %d", n);

  return 0;
}

其中n是解决方案的总数，x是编号。球数中，y 为否。帽子中，z 是 no。卡纸，w 是编号。晶体数量

但是，当我运行此代码时，它永远不会结束。

Answer 1

您的实现很糟糕，因为您忽略了recurse递归调用的返回值，很容易修复，只需返回返回值的加法即可:

#include <stdio.h>

int recurse(int x, int y, int z, int w, int n) {
  int value = x + 5 * y + 20 * z + 50 * w;
  if (value == 300) {
    return n + 1;
  } else if (value > 300) {
    return n;
  }

  return recurse(x + 1, y, z, w, n) + recurse(x, y + 1, z, w, n) +
         recurse(x, y, z + 1, w, n) + recurse(x, y, z, w + 1, n);
}

int main(void) {
  printf("Answer: %d", recurse(0, 0, 0, 0, 0));
}

但是您的实现需要时间...很多时间...来计算结果。

Antti Haapala - well, I made the ending condition tighter, and then started testing. 62 took1.32 seconds, 64 2.3 seconds, 66 4.039 seconds to finish. The ratio was 1.75 for each 2 added. so minimally, those 300 will need 1.75 ^ ((300 - 66) / 2) * 4.039 seconds .. so that's in the whereabouts

因为你没有将迭代实现转变为正确的递归函数。您的函数计算排列数量，而不是组合数量。换句话说，您可以对这些元素进行多少种不同的排序，最终得到 300 个。

<小时/>

每个迭代循环都可以转换为尾递归函数，C 标准不要求编译器优化尾递归函数以避免 stackoverflow 但大多数的编译器有此优化。

这很难解释如何将函数从迭代转换为递归，但作为规则，每个 for 循环都需要模拟函数递归。正如您所看到的，我需要创建四个函数来实现相同的行为。

剧透，这个答案给出了代码解决方案:

#include <stdio.h>

static int magic(int a, int b, int c, int d) {
  return a + b * 5 + c * 20 + d * 50;
}

static int recur_d(int a, int b, int c, int d, int n, int max) {
  int ret = magic(a, b, c, d);
  if (ret >= max) {
    if (ret == max) {
      // printf("%d %d %d %d\n", a, b, c, d);
      return n + 1;
    }
    return n;
  }
  return recur_d(a, b, c, d + 1, n, max);
}

static int recur_c(int a, int b, int c, int n, int max) {
  if (magic(a, b, c, 0) > max) {
    return n;
  }
  return recur_c(a, b, c + 1, recur_d(a, b, c, 0, n, max), max);
}

static int recur_b(int a, int b, int n, int max) {
  if (magic(a, b, 0, 0) > max) {
    return n;
  }
  return recur_b(a, b + 1, recur_c(a, b, 0, n, max), max);
}

static int recur_a(int a, int n, int max) {
  if (magic(a, 0, 0, 0) > max) {
    return n;
  }
  return recur_a(a + 1, recur_b(a, 0, n, max), max);
}

static int iter(int max) {
  int n = 0;
  for (int a = 0; magic(a, 0, 0, 0) <= max; a++) {
    for (int b = 0; magic(a, b, 0, 0) <= max; b++) {
      for (int c = 0; magic(a, b, c, 0) <= max; c++) {
        for (int d = 0; magic(a, b, c, d) <= max; d++) {
          if (magic(a, b, c, d) == max) {
            // printf("%d %d %d %d\n", a, b, c, d);
            n++;
          }
        }
      }
    }
  }
  return n;
}

int main(void) { printf("%d %d\n", iter(300), recur_a(0, 0, 300)); }

注意:我注释了 printf() 以避免长输出。