时间戳

首页 > 解决方案 > 递归：从袋子中挑选 8 个球。问题：如何避免相同的答案？

c - 递归：从袋子中挑选 8 个球。问题：如何避免相同的答案？

问题描述

我陷入了递归问题。问题：一个袋子里有3个红球、3个白球和6个黑球。需要从袋子里取出8个球。有多少种组合，它们是什么？

我已经在 C 中实现了这个问题。但问题是我不知道如何从我的答案中摆脱完全相同的解决方案。实际答案是 13 种组合，我已经使用 UNIX 的“uniq”运算符进行了验证。但是，我想就如何从我的程序中删除相同的组合获得一些帮助。

非常感谢 ！！！谢谢你。

// 3R 3W 6B, pick 8, how many possible combination

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

void func(int r, int w, int b, int total);


int main(void){
    printf("The result is\n");
    func(3, 3, 6, 0);
    return 0;
}


void func(int r, int w, int b, int total){
    if (r < 0 || w < 0 || b < 0){
        return;
    }
    else if (total >= 8){
        printf("R = %d, W = %d, B = %d\n", 3-r, 3-w, 6-b);
        return;
    }
    else{
        func(r-1, w, b, total+1);
        func(r, w-1, b, total+1);
        func(r, w, b-1, total+1);

        return;
    }
}

标签： crecursion

解决方案

通过从每种颜色中一次取一个球，您可以在不同的路径上得到相同的答案。例如，先拿一个红球，然后一个白球将导致与先拿一个白色球，然后是一个红球相同的计数。在您的代码中，每个递归级别对应于一个单独的球，如果球的顺序很重要，这是一个很好的方法。

您可以以不同的方式订购：

  • 考虑所有可能的红球（0、1、2或3）
    • 考虑所有获取白球的方法（再次从 0 到 3）
      • 考虑所有拿黑球的方法（0到6）
        • 如果我们有 8 个球，打印解决方案

（这个解决方案不是最优的：它会以一种蛮横的方式考虑所有的可能性。它可以通过不根据已经拿走多少球而减少可能性来进行优化。这里的关键是看到重新排序你的递归解决了这个问题。）

您可以将其硬编码到您的程序中，但让我们考虑一个更通用的解决方案，您可以在数组中指定每种颜色的可用球数和总数。

这个解决方案也是递归的，但是这里的每个递归级别都对应于一个球的颜色：

int take(int *ball,     // array of available balls of each colour
         int *taken,    // record of balls taken from each colour
         int n,         // size of ball and taken arrays
         int i,         // currently considered colour
         int total)     // balls taken, counting down from intended number
{
    int res = 0;
    int j;

    if (i < n) {
        // consider nexz colour

        for (j = 0; j < ball[i] + 1; j++) {
            taken[i] = j;

            res += take(ball, taken, n, i + 1, total - j);
        }
    } else {
        // all colours have been considered

        if (total == 0) {
            for (j = 0; j < n; j++) {
                if (j) printf(", ");
                printf("%d", taken[j]);
            }

            puts("");

            res = 1;
        }
    }

    return res;
}

对于您的测试用例，这样称呼它：

int main(void)
{
    int ball[] = {3, 3, 6};     // red, white and black balls
    int taken[3];               // will be filled in by "take"

    int res = take(ball, taken, 3, 0, 8);

    printf("(%d possibilities)\n", res);

    return 0;
}

推荐阅读