c - 我的 C 递归有什么问题？

Question

我为我的作业编写了一个递归函数来执行以下计算:

对于输入:
1 2 3 4

它应该这样做:
((1*3)+2) + ((1*4)+3) = 13，即小于 ((2*4)+3) + ((1* 4)+2) = 17，因此返回 13。在字母中，它应该执行以下计算:((A*C)+B) + ((A*D)+C) 并将其与其他选项进行比较，在这种情况下有 2 个选项: ((B*D)+C) + ((A*D)+C)。

简而言之。这些数字表示段两端“螺钉”的数量。该段始终由 2 个数字组成。段 A {1 2}、B {2 3}、C {3 4}。

任务是连接所有 N 个段。我必须找到“最便宜”的方法来做到这一点。每次我连接两个段(例如 A 和 B)时，我都会这样做:

A 的“底部螺钉”(1 - 第一个数字)* B 的“顶部螺钉”(3 - 第三个数字)+“连接螺钉”(2 - 之间的数字)。

我必须按顺序加入它们，它总是必须以 ABCD 的顺序结束。但我可以选择从哪里开始。我可以将A连接到B，然后将AB连接到C，或者我可以将B连接到C，然后将A连接到BC。基本上在其中一种情况下，“成本”将是最低的，这就是要返回的值。

现在我已经做到了这一点，但我很困惑:

*help 是一个相互计算数组，我用它来存储递归中获得的新值。

int *help;

*mezi 是一个动态分配的数组，定义为:

int *mezi;

其内部看起来像{0,4,1,2,3,4,-1}。

mezi[0] = here is stored the total prize in the recursion.

mezi[1] = here is stored the number of values in the array, 4 for 4 values (3 segments).

mezi[n+2] = the last number (-1), its just an identifier to find out the number of values.

这是我的代码:

int findmin(int *mezi, int *pomocny)
{
    int i,j,k;
    int prize, prizemin, mini, minih;

    for (i=3;i<mezi[1];i++) {

        prize = mezi[i-1] * mezi[i+1] + mezi[i];
        if (i==3) { mini = i; minih = prize; }

        if (prize < minih) { mini = i; minih = prize; }

        if (mezi[1] > 3){

            k=2;
            for (j=2;j<mezi[1];j++) {
                if (j != mini) help[k] = mezi[j];
                k++;
            }
            help[1] = (mezi[1]-1);
        }
        help[0] += prize;

        findmin(help,help);
    }
    prizemin = help[0];

    return prizemin;
}

我是个新手，不久前我开始使用 C，递归函数让我很困惑。我非常感谢您的帮助。谢谢:)

Answer 1

您的程序逻辑存在不少问题。

int findmin(int *mezi, int *pomocny)
{
    int i,j,k;
    int prize, prizemin, mini, minih;

    for (i=3;i<mezi[1];i++) 
    {
        prize = mezi[i-1] * mezi[i+1] + mezi[i];
        if (i==3) { mini = i; minih = prize; } //This is a redundant test and 
        //initialization. i == 3 is true only in the first run of the loop. These
        //initialization should be done in the loop itself

        if (prize < minih) { mini = i; minih = prize; }

        if (mezi[1] > 3){  //This is also redundant as mezi[3] is always greater than 3 
        // otherwise the loop wont run as you check for this in your test expression

            k=2;
            for (j=2;j<mezi[1];j++) {
                if (j != mini) help[k] = mezi[j];
                k++;
            }
            help[1] = (mezi[1]-1);
        }
        help[0] += prize;

        //The only base case test you have is mezi[1]<3 which you should make sure is 
        // present in your data set

        findmin(help,help);
    }
    prizemin = help[0];

    return prizemin;
}