0

C 中的代码使用分而治之找到数组的最大值，但它不断抛出“堆栈溢出异常”。帮助将不胜感激！

int a[10];
int find(int l,int h)
{
    int x;

    if(h==0)
    {
        x=0;
        return x;
    }
    else
    {
        if(h==1)
        {
            if(a[0]>a[1])
            {
                x=0;
                return x;
            }
            else
            {
                x=1;
                return x;
            }
        }
        else
        { 
            int mid,z,y;
            mid=(l+h)/2;
            y=find(0,mid);
            z=find(mid+1,h);
            if(a[y]<a[z])
            {
                x=z;
            }
            else
            {
                x=y;
            }
            return x;
        }
    }
}

只有有限的变量，我看不出函数可以在哪里进入无限递归。 

int main()
{
    int i,n,max,min,ans;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    ans=find(0,n-1);

    printf("the maximum element is- %d\n",ans);

    getch();
    return 0;
}
4

3 回答 3

1

考虑您调用find(0, 2). 由于h > 1，您输入第二个else子句，并且midis 1。然后在第二次递归调用中，它是 to find(2, 2)。在这个递归调用中，您再次输入 second else，因为h仍然是 2。但是midis 也是2。现在，第一个递归调用转到find(0, 2)，进入一个无限循环。

find(0, 2)
   h not 0
       h not 1
           mid = 1
           find(0, 1)
           find(2, 2)
               h not 0
                   h not 1
                       mid = 2
                       find (0, 2) <-- loop

似乎if检查的目的h是防止mid计算与 相同l。如果是这样，那么您可以计算mid函数顶部的变量，并将其用作停止条件。

看起来这是一次尝试使用分治法来定位数组中最大元素的位置a。如果是这样，那么您的第一个递归调用应该将自身限制在范围内[l..mid]而不是返回到0.

把它们放在一起：

int find(int l,int h)
{
    int mid = (l+h)/2;

    if (mid == l)
    {
        return (a[l] > a[h]) ? l : h;
    }
    else
    {
        int y = find(l, mid);
        int z = find(mid+1, h);
        return (a[y] > a[z]) ? y : z;
    }
}
于 2013-06-19T15:42:12.063 回答
0

这是您修改的代码，它正在成功运行。问题是您没有检查和之间的区别，l而h只是检查h...的值

#include <iostream>
using namespace std;
int a[10];


int find(int l,int h)
{
int x;



if(h-l==0)
{

    return h;
}
else
{


    if(h-l==1)
    {
        if(a[l]>a[l+1])
        {

            return l;
        }
        else
            {

                return l+1;
            }
    }
    else
    { 
        int mid,z,y;
        mid=(l+h)/2;
        y=find(0,mid);
        z=find(mid+1,h);



        if(a[y]<a[z])
        {
            x=z;
        }
        else
        {
            x=y;
        }

        return x;
    }}}
int main()
{
a[0]=3;
a[1]=7;
a[2]=5;
cout<<find(0,2)<<endl;
return 0;
}
于 2013-06-19T15:51:11.557 回答
0

您使用了错误的条件，请尝试：

first if: if(h==l)

second if: if(h-l==1)

third if:  
      if(a[h]>a[l])  {
         return h;
      } else {
         return l;
      }
于 2013-06-19T15:56:13.620 回答