我一直在尝试使用递归解决问题:
商店中的商品有以下费用:
- 球: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
是编号。晶体数量
但是,当我运行此代码时,它永远不会结束。
最佳答案
您的实现很糟糕,因为您忽略了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()
以避免长输出。
关于c - 使用递归的解决方案数量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48055375/