процесс рекурсии в пустотной функции - PullRequest
Новая
       7

процесс рекурсии в пустотной функции

0 голосов
/ 02 февраля 2020

Я только что нашел фрагмент кода кода (python) в stackoverflow. Из-за увлечения я перевел фрагмент кода на C язык (ошибка, конечно).

Мой фрагмент кода 

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

int top = 0;

void print(int *partial)
{
        int j =0;
        while(partial[j] != 0)
        {
                printf("%d ",partial[j]);
                j++;
        }
}
void subset(int *nos,int *partial,int reqvalue,int maxvalue) {
        int par_sum = 0,i = 0,count=0;
        while(partial[i] != 0)
        {
                par_sum += partial[i];
                i++;
        }

        if(par_sum == reqvalue)
        {
                print(partial);

        }
        if(par_sum > reqvalue)
        {
                 return ;
        }
        while(nos[count]!= 0)
        {
                count++;
        }
        for(int j =0; j < count; j++)
        {
                  int n;
                  int remaining[count+1];
                  n = nos[j];
                  for(int k = j+1; k < count+1; k++) {
                        remaining[k-(j+1)] = nos[k];
                  }
                  partial[top] = n;
                  top++;
                  subset(remaining,partial,reqvalue,maxvalue);
                  top--;
        }

}
int main()
{
        int reqvalue,no_count,sum = 0;
        int *nos;
        int *partial;
        scanf("%d %d",&reqvalue,&no_count);
        nos = calloc(( no_count+1),sizeof(int));
        partial = calloc(no_count, sizeof(int));
        for(int i =no_count-1; i>=0; i--)
        {
                scanf("%d",&nos[i]);
                sum += nos[i];

        }
        subset(nos,partial,reqvalue,sum);
        return 0;
}

#Input
#100 10
#4 14 15 18 29 32 36 82 95 95

#Output
#82 18 82 14 4 82 14 4 36 32 18 14

Мне просто интересно Как я могу напечатать только первое подмножество вместо печати всех подмножеств?
Как я могу немедленно отключиться от механизма рекурсии после печати первого подмножества?
Ожидаемый вывод 

82 18

Оригинал python Фрагмент 

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        print "sum(%s)=%s" % (partial, target)
    if s >= target:
        return  # if we reach the number why bother to continue

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n]) 


if __name__ == "__main__":
    subset_sum([3,9,8,4,5,7,10],15)

    #Outputs:
    #sum([3, 8, 4])=15
    #sum([3, 5, 7])=15
    #sum([8, 7])=15
    #sum([5, 10])=15

Заранее спасибо

1 Ответ

0 голосов
/ 02 февраля 2020

Предполагая, что перевод в c правильный, вы выводите только подмножество в предложении 

if(par_sum == reqvalue)
    print(partial);

Следовательно, вы можете напечатать только первое, которое вы можете вернуть в конце этого предложения, и убедитесь, что что for l oop также ломается, например, с помощью кода возврата subset (например, изменив его на int), например: 

#define BREAK_LOOP 1    // before subset 

int subset(int *nos,int *partial,int reqvalue,int maxvalue) 
{
...

Изменить вывод условие для возврата BREAK_LOOP и возврата 0 в другом случае: 

if(par_sum == reqvalue)
{
    print(partial);
    return BREAK_LOOP; 
}        

if(par_sum > reqvalue)
    return 0;

Измените для l oop, чтобы проверить subset возвращаемое значение, и верните 0 в противном случае. 

int subset_ret_val = 0; 
for(int j =0; j < count; j++)
{
   ...
   subset_ret_val = subset(remaining,partial,reqvalue,maxvalue);
   if (subset_ret_val)
       return subset_ret_val; 
   top--;
}
return 0;

Если вы можете / не можете изменить тип возвращаемого значения функции на int, вы можете эквивалентно передать другой аргумент-указатель. Если вы вообще не можете изменить сигнатуру функции, вы все равно, возможно, совершите некоторый хак, злоупотребляя существующими аргументами, но вы, похоже, не запрашивали решения для этого.

...