C 蛮力递归函数

Question

所以我在使用递归函数时遇到麻烦，我的问题是我有一个代表金币的数组，它是一个[]这个数组有需要与两个用户共享的硬币，方式是每个用户长期使用run 获得相同数量的黄金或最佳解决方案......就像这样

Gold
10 6 5 2
User A : gets 10 2
User B : gets 6 5

用户 A 和用户 B 之间的绝对值给了我差异。 在这种情况下，它将是 1

为了解决这个问题，我需要遍历所有可能的组合，这就是为什么我使用暴力破解和递归函数......为此，我必须运行每个组合，并查看两者之间的绝对差异(如果它比它更好)以前的我将其保存在全局变量 best 中...

问题是该功能根本无法正常工作..如果您帮助我，我将不胜感激......

代码如下:

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

int best = 0; // keeps the best option



int share_friends_recursive(int nelems,int a[],int friend_a,int friend_b,int i){
    int sub = 0;
    friend_a += a[i];
    friend_b += a[i+1];
    if(i+1 == nelems){

        return 0;
    }else{
        sub = abs(friend_a - friend_b);
        if(sub < best){
            best = sub;
        }
        i++;
        share_friends_recursive(nelems,a,friend_a,friend_b,i);
    }

}

int main(int argc, char *argv[]) {
    //
    int nelems = 4;
    int a[] = {10,6,5,2};



    //friend A can get the first value
    // friend B gets the second one ...
    share_friends_recursive(nelems,a,0,1,0);
    printf("%d \n",best);

    return 0;
}

Answer 1

你需要考虑一下你在做什么。例如:

int share_friends_recursive(int nelems,int a[],int friend_a,int friend_b,int i){
    int sub = 0;
    friend_a += a[i];
    friend_b += a[i+1];

因此，您将第一堆交给 friend A，将第二堆交给 friend B。但是稍后您将使用 i 递增 1 进行递归，因此您将给出尽管您已经将第二堆给了 A，但它还是给了 B。这毫无意义。

你想要做的是尝试将第一堆给A，然后递归给出其余的堆，然后重新开始，尝试将第一堆给B并递归给出其余的堆并比较它们两种情况看看哪个最好。

编辑

好的，让我们一步一步来。你有你的递归函数:

int share_friends_recursive(int nelems,int a[],int friend_a,int friend_b,int i){

这里 nelems 是堆的总数，a 是每个堆的大小，i 是已经分配了多少堆，friend_a 和 friend_b 是给每个 friend 的金额。那么首先，如果我们已经分发了所有的桩怎么办？这是一个多好的解决方案？调用者需要知道这一点，因此我们将返回它。

    if (i == nelems) {
        return abs(friend_a - friend_b);

当我们完成时，它告诉我们做得有多好(或多差)。如果我们还没完成怎么办？好吧，那么我们需要尝试将一堆 i 分别赋予 a 和 b，看看哪个更好。

    } else {
        int toA = share_friends_recursive(nelems, a, friend_a + a[i], friend_b, i+1);
        int toB = share_friends_recursive(nelems, a, friend_a, friend_b + a[i], i+1);

那么这两个哪个更好呢？好吧，我们只是比较并返回较低的那个:

        if (toA <= toB)
            return toA;
        else
            return toB;
    }
}

..这告诉我们最佳分割有多好。