Я не могу генерировать подмножества массива, основываясь на сумме - PullRequest
Новая
       7

Я не могу генерировать подмножества массива, основываясь на сумме

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

Я использую рекурсивную функцию для поиска подмножеств из массива символов на основе заданной суммы: 

str="1234567890"

n=2 (размер подмножества), m=9 (заданная сумма). Решение: {9,0},{0,9},{8,1},{1,8},{7,2},{2,7},,,,,{5,4},{4,5}. Мой код следующий. 

#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
void genrate(char*,int,int,int);
int main(){
    char str[20]="1234567890";
    genrate(str,2,9,10);
}
void genrate(char *str,int n,int m,int k){
    int i,j,sum;
    sum=0;
    if(sum==m){
        for(i=0; i<n; i++){
            printf("%c ",str[i]);
        }
        printf("\n");
    }
    sum+=(int)str[k]-48;
    genrate(str,n,m,k);
    genrate(str,n,m,k-1);
}

1 Ответ

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

Этот ответ не дает решения, но я просто хочу указать на некоторые ошибки, касающиеся рекурсии.

Прежде всего, локальные переменные не очень хорошая идея, например, переменная sum будет переопределена в следующий рекурсивный вызов, так как этот новый вызов выполнит int i,j,sum; initialisaion, я напечатал адрес суммы и проверил: 

Address of SUM : 5f7ac8
Address of SUM : 5f7a98
Address of SUM : 5f7a68
Address of SUM : 5f7a38
Address of SUM : 5f7a08

Он меняется при каждом вызове ...

и при втором вызове genrate(str, n, m, k - 1) никогда не будет вызван ... Так как он всегда застревает в бесконечном вызове -l oop {generate () -> generate () -> generate () ->).

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

Например, factoriel: 

long int fact(int n) {
    if (n>=1)
        return n*fact(n-1);
    else
        return 1; // Here the end of the recursivity !
}

С уважением.

...