-1

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

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

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

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

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

代码如下：

#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;
}
4

1 回答 1

2

你需要想想你在做什么。例如：

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];

所以你把第一堆给朋友A，第二堆给朋友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是给了每个朋友多少。那么首先，如果我们已经分配了所有的堆怎么办？这是一个多么好的解决方案？调用者需要知道这一点，所以我们会返回它。

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

..这告诉我们最好的分裂有多好。

于 2013-02-23T00:58:05.270 回答