C语言 递归打印出每个数组的组成部分之和等于给定数

zed5wv10  于 2023-10-16  发布在  其他
关注(0)|答案(2)|浏览(98)

所以我们给出一个数组v[]={2,6} and d=10,我们必须打印出每个子数组,以便总和等于d
例如,对于给予d和v[],我们应该打印出这些数组

2 2 2 2 2
6 2 2
2 6 2 
2 2 6

这是我目前的程序,但我似乎不能打印任何东西。
我假设问题是当我回到跟踪,但我没有任何目前的想法

#include <stdio.h>
#include <stdlib.h>
void findSolutions(int v[], int n, int d, int current[], int index) {

    if(index>n)
    {
        current=realloc(current,index*sizeof (int));
    }
    if (d == 0) {
        
        for (int i = 0; i < index; i++) {
            printf("%d ", current[i]);
        }
        printf("\n");
        return;
    }
    if (d < 0 || index >= n) {
        return;
    }

    current[index] = v[index];
    findSolutions(v, n, d - v[index], current, index + 1);

    findSolutions(v, n, d, current, index + 1);
}

int main() {
    int v[] = {2, 6};
    int n = 2;
    int d = 10;
    int *current= malloc(n*sizeof(int));
    findSolutions(v, n, d, current, 0);
    
    
    return 0;
}
64jmpszr

64jmpszr1#

下面的注解似乎解决了您的代码中的几个问题。一致的格式将使您的生活更轻松。

if(index>n) // We'll see this never is true...
    {
        current=realloc(current, index*sizeof (int)); // so this never happens.
        /* Never happening is actually good.
         * realloc() may return a new address of heap memory
         * You don't pass 'current' back up to higher levels, so their stale copy of
         * the pointer 'current' could point to de-allocated memory. (UB awaits!)
         */
    }
    if (d == 0) { // 'd' is not a descriptive variable name
        for (int i = 0; i < index; i++) // remove unnecessary braces
            printf("%d ", current[i]);

        printf("\n");
        return;
    }

    if (d < 0 || index >= n) // Once index = 2, game over. Data requires at least 3
        return;

    current[index] = v[index]; // probably want "index - 1" for base 0 indexing

    findSolutions(v, n, d - v[index], current, index + 1); // close!!!

    findSolutions(v, n, d, current, index + 1); // Looks like vestigial attempt
}

int main() {
    int v[] = {2, 6}; // Not the best variable names!
    int n = 2;
    int d = 10;
    int *current= malloc(n*sizeof(int)); // could be NULL and let realloc() do the work

    findSolutions(v, n, d, current, 0);
    
    return 0;
}

很明显,这段代码正在将目标值(从10)向零(或更低)(即 * 基本情况 *)收缩。聪明,因为这意味着少了一个参数!
下面是一个注解版本。我希望这有助于澄清一些事情。

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

/* Helper function to find minimum value in array */
int arrMinVal( const unsigned arr[], const size_t a_sz ) {
    size_t minInd = 0;
    for( size_t i = 1; i < a_sz; i++ )
        if( arr[ minInd ] > arr[ i ] )
            minInd = i;
    return arr[ minInd ];
}

/* The recursive function.
 * Notice the sequence of parameters:
 * - remaining balance of target
 * - source array and its size
 * - array of values (incl. duplicates) used so far (and its size)
 */
int solve_ex( const int remain, const unsigned arr[], const size_t a_sz, int soln[], int len ) {
    if( remain < 0 ) // Overshoot! No good, so return...
        return 0;

    if( !remain ) { // Bull's eye! Print (in reverse) the working combination found
        while( len-- )
            printf( "%d ", soln[ len ] );
        putchar( '\n' );
        return 1; // return 1 to increase tally of found combinations
    }

    // Recurse trying out each value of the source array one at a time
    int cnt = 0;
    for( size_t i = 0; i < a_sz; i++ ) {
        soln[ len ] = arr[ i ]; // Remember this value (for printing)
        // Tally the wanted combinations found at "lower levels"
        // First parameter 'shrinks' the target toward zero (as you had)
        // Last parameter indicates one more value has been added to "soln[]"
        cnt += solve_ex( remain - arr[ i ], arr, a_sz, soln, len + 1 );
    }
    // exhausted possibilities at this level, so return tally
    return cnt;
}

/* 'Bridging' function so that main() is less cluttered */
int solve( const int target, const unsigned arr[], const size_t a_sz ) {
    // determine max required size of solution array
    // For example: with { 2, 6 }, finding 10 requires at most 5 entries (5*2=10)
    // Add 1 to allow for "overshoot"...
    int n = target / arrMinVal( arr, a_sz ) + 1;
    int *soln = malloc( n * sizeof *soln ); // Could be VLA, instead.
    /* for brevity, malloc presumed to work */

    int cnt = solve_ex( target, arr, a_sz, soln, 0 ); // get into it...

    free( soln ); // clean up

    return cnt; // return
}

int main( void ) { // Uncluttered...
    const unsigned arr[] = { 2, 6 };
    const int target = 10;

    // Eventually, code to get user input may be added.
    // Sometimes, no solutions can be found. Give the user feedback.
    printf( "%d solutions found\n", solve( target, arr, sizeof arr/sizeof arr[0] ) );

    return 0;
}

我希望这对你有帮助。。

3phpmpom

3phpmpom2#

您的代码使用malloc(),但没有使用free()来释放内存,这将导致内存泄漏。
我不知道你为什么在findSolutions()中使用两次findSolutions(v, n, d - v[index], current, index + 1);findSolutions(v, n, d, current, index + 1);
所以我重写了一下,这是我的答案:

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

void findSolutions(int *a , int* current , int num , int minusResult , int len, int sum)
{
    if(sum > minusResult)
        return;
    else if(sum == minusResult){
        for(int i = 0; i < len; i++){
            printf("%d ", current[i]);
        }
        printf("\n");
        //printf("len is %d\n",len);
        return;
    }else{
        for(int j = 0; j < num; j++){
            sum = sum + a[j];
            current[len] = a[j];
            findSolutions(a, current, num, minusResult, len+1, sum);
            sum = sum - a[j];
        }
    }
}

int main() {
    int v[] = {2, 6};
    int n = 2;
    int d = 10;
    int sum = 0;
    int minusResult = 0;
    int *current= malloc(1000*sizeof(int));
    if(NULL == current){
        printf("malloc current failed\n");
        return -1;
    }
    memset(current, 0, 1000*sizeof(int));
    findSolutions(v, current, n, d, minusResult, sum);
    free(current);    
    current = NULL;
    return 0;
}

运行它将输出:

2 2 2 2 2 
2 2 6 
2 6 2 
6 2 2

如果你认为2 2 62 6 26 2 2是相同的结果,然后想立即输出2 2 6,你可以使用下面的代码:

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

void findSolutions(int *a , int* current , int num , int minusResult , int len, int sum , int loc)
{
    if(sum > minusResult)
        return;
    else if(sum == minusResult){
        for(int i = 0; i < len; i++){
            printf("%d ", current[i]);
        }
        printf("\n");
        return;
    }else{
        for(int j = loc; j < num; j++){
            sum = sum + a[j];
            current[len] = a[j];
            findSolutions(a, current, num, minusResult, len+1, sum, loc);
            sum = sum - a[j];
            loc++;
        }
    }
}

int main() {
    int v[] = {2, 6};
    int n = 2;
    int d = 10;
    int sum = 0;
    int loc = 0;
    int minusResult = 0;
    int *current= malloc(1000*sizeof(int));
    if(NULL == current){
    printf("malloc current failed\n");
    return -1;
    }
    memset(current, 0, 1000*sizeof(int));
    findSolutions(v, current, n, d, minusResult, sum, loc);
    free(current);    
    current = NULL;
    return 0;
}

运行它将输出:

2 2 2 2 2 
2 2 6

相关问题