Рекурсия: выбрать 8 шариков из сумки. Проблема: как избежать одних и тех же ответов? - PullRequest
Новая
       11

Рекурсия: выбрать 8 шариков из сумки. Проблема: как избежать одних и тех же ответов?

0 голосов
/ 09 марта 2020

Я застрял в проблеме рекурсии. Вопрос: в сумке 3 красных шарика, 3 белых шарика и 6 черных шариков. Нужно взять 8 шариков из сумки. Сколько комбинаций существует и что это такое?

Я реализовал вопрос в C. Но проблема в том, что я не знаю, как избавиться от точно таких же решений из моих ответов. Фактический ответ - 13 комбинаций, которые я проверил, используя оператор "uniq" UNIX. Однако я хотел бы получить некоторую помощь о том, как удалить ту же комбинацию из моей программы.

Очень ценю !!! Спасибо. 

// 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;
    }
}

1 Ответ

0 голосов
/ 09 марта 2020

Взяв один шарик за раз от каждого цвета, вы получите один и тот же ответ на разных путях. Например, если взять красный, то белый шар приведет к тому же счету, что и белый, а затем красный шар. В вашем коде каждый уровень рекурсии соответствует отдельному шару, что является хорошим подходом, если важен порядок шаров.

Вы можете заказать взятие по-другому:

  • рассмотреть все возможности взять красные шары (0, 1, 2 или 3)
    • рассмотреть все способы взять белые шары (снова от 0 до 3)
      • рассмотреть все способы взять черные шары (0 6)
        • если у нас есть 8 шаров, выведите решение

(Это решение не Оптимальный: он рассмотрит все возможности способом brute-froce-i sh. Он может быть оптимизирован, не уменьшая возможности в зависимости от того, сколько шаров уже было взято. Ключевой момент здесь заключается в том, чтобы увидеть, что переупорядочение вашей рекурсии решает проблема.)

Вы можете жестко запрограммировать это в своей программе, но давайте рассмотрим более общее решение, где вы указываете доступное количество шариков каждого цвета в массиве и общее количество.

это раствор on тоже рекурсивно, но здесь каждый уровень рекурсии соответствует цвету шара: 

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;
}
...