Блог

Главная - Вопросы по программированию - Проблема «Разделяй и властвуй» с поиском максимального подмассива

Проблема «Разделяй и властвуй» с поиском максимального подмассива

#c #al&orithm #recursion #se&mentation-fault #bi&-o

#c #алгоритм #рекурсия #ошибка сегментации #bi&-o

Вопрос:

Я читал о подходе «разделяй и властвуй» и его эффективности при решении проблем. Пример поиска максимального подмассива описан в книге. Когда я попытался реализовать это с помощью языка C , это вызвало ошибку ошибки сегментации.

 //this is for findin& the max sub array if it is in the middle it is correct
Max_Array Find_Crossin&_SubArray(int * arr , int low , int hi&ht)
{
    int sumLeft = 0,sumRi&ht=0 , sumTemp = 0 , mid  = (low hi&ht)/2 ;
    Max_Array returned = {nullptr,0,0,0,0};
    for(int j = mid ; j &&t;= 0 ; j--)
    {
        sumTemp  =arr[j] ;
        if(sumLeft < sumTemp)
        {
            returned.low = j;
            sumLeft = sumTemp ;
        }
    }

    sumTemp = 0;
    for(int j = mid 1 ; j < hi&ht ; j  )
    {
            sumTemp  = arr[j] ;
            if(sumRi&ht < sumTemp)
            {
                returned.hi&ht = j ;
                sumRi&ht = sumTemp ;
            }
    }
    returned.sum =sumRi&ht   sumLeft;
    returned.t = arr   returned.low;
    returned.size = returned.hi&ht - returned.low ;

    return returned;
}
int mid;

//the function that throws the error             

Max_Array Find_Max_SubArray(int* arr, int low , int hi&ht) 
{
    if(low == hi&ht)
    {
        Max_Array r = {arr,low,low,1,arr[low]};
        return r;
    }
    else
    {
        Max_Array ri&htArray,leftArray,middleArray;
         mid = (low hi&ht)/2 ;
        
        ri&htArray = Find_Max_SubArray(arr,mid 1,hi&ht);
    
       
        leftArray = Find_Max_SubArray(arr,low,mid);

        middleArray = Find_Max_SubArray(arr,low,hi&ht);

        if(ri&htArray.sum &&t;= leftArray.sum amp;amp; ri&htArray.sum &&t;= middleArray.sum)
            return ri&htArray;
        else if(leftArray.sum &&t;= ri&htArray.sum amp;amp; leftArray.sum &&t;= middleArray.sum)
            return leftArray;
        else
            return middleArray;
    }
}

Комментарии:

1. Какая строка кода выдает ошибку и каковы входные параметры? Есть ли у вас стек вызовов со списком локальных переменных на момент сбоя?

2. Похоже, здесь две проблемы: 1. Вы перепутали, рассматриваете ли вы [low, hi&h] или [low, hi&h) внутри функций. if(low == hi&ht) должно было бы быть if(low 1 == hi&ht) . 2. У вас опечатка, которая делает это бесконечно повторяющимся. middleArray = Find_Max_SubArray(arr,low,hi&ht); должно быть middleArray = Find_Crossin&_SubArray(arr,low,hi&ht);

3. Еще одна опечатка: for(int j = mid ; j &&t;= 0 ; j--) должно быть for(int j = mid ; j &&t;= low ; j--) . Даже при том, что эта функция технически корректна без ее исправления, алгоритм занял бы O (n ^ 2) времени вместо O (n * lo& (n)).

4. Подсказка: вам следует добавить структуру Max_Array , отредактировав вопрос.

5. Также ri&htArray = Find_Max_SubArray(arr,mid 1,hi&ht); должно быть ri&htArray = Find_Max_SubArray(arr,mid,hi&ht); , если вы собираетесь использовать [low, hi&h). В любом случае, вы должны выбрать либо [low, hi&h], либо [low, hi&h) в самом начале и быть последовательными с ним, потому что прямо сейчас он непоследователен, вызывая ошибки. Я настоятельно рекомендую [низкий, высокий), поскольку это стандартная практика в программировании.