Решение проблем рекурсивно в C

Question

Наш профессор дал нам следующее задание:

«Правильный» ряд - это тот, в котором сумма его членов равна индексу первого члена.

Предполагается, что программа найдет длину самого длинного «правильного» ряда в серии из n чисел.

Например: если серия ввода будет arr[4]={1, 1, 0, 0} выход (самый длинный «правильный» ряд) будет 3.
arr[0]=1. 0!=1 поэтому самая длинная серия здесь - 0.
arr[1]=1,and 1=1. но следующие члены также суммируют до 1, как показано ниже:
1=arr[1]+arr[2]+arr[3] = 1+ 0 + 0, поэтому самая длинная серия здесь 3.

Выходные данные в этом примере: 3.

Это то, что я имею до сих пор:

int solve(int arr[], int index, int length,int sum_so_far)
{
     int maxwith,maxwithout;

     if(index==length)
         return 0;

     maxwith = 1+ solve(arr,index+1,length,sum_so_far+arr[index]);
     maxwithout = solve(arr,index+1,length,arr[index+1]);

     if(sum_so_far+arr[index]==index)
         if(maxwith>maxwithout) 
            return maxwith;

     return maxwithout;

     return 0;
}



int longestIndex(int arr[], int index,int length)
{
     return solve(arr,0,length,0);
}

Что я здесь не так делаю?

Мы не должны делать петли в этом задании.

Answer 1

Хм, есть несколько проблем с этой программой.

Наиболее очевидно: «верните maxwithout; верните 0;» должен выдать ошибку компиляции: нет способа добраться до этого последнего оператора return.

Во-вторых, вы возвращаетесь к решению по пути "maxwith", пока не достигнете конца массива. Затем вы вернетесь в maxwithout, впервые поразив его с индексом = 4. Я не думаю, что это сработает.

Честно говоря, я не думаю, что эта проблема действительно требует рекурсии. Наиболее естественным решением будет вложенный цикл:

for (int start=0;start<length;++start)
{
  for (int end=start;end<length;++end)
  {
    // calculate the sum of arr[start]->arr[end] and compare to start
  }
}

Или что-то на этот счет.

Требовала ли проблема решить ее с помощью рекурсии, или это была ваша первая идея для хорошего решения?

Редактировать

Хорошо, так что вы должны использовать рекурсию. Я предполагаю, что смысл урока в том, чтобы научиться использовать рекурсию, а не обязательно решать проблему наиболее естественным или эффективным способом. (Лично я думаю, что учитель должен был придумать проблему, когда рекурсия была естественным решением, но я думаю, что мы здесь не для того, чтобы критиковать учителя сегодня.)

Я не хочу делать твою домашнюю работу за тебя, но я дам тебе подсказку. Вы можете использовать рекурсию для имитации цикла, поместив условие останова в начало функции и поместив рекурсивный вызов в конец функции с параметром +1. То есть вместо написания

for (int x=0;x<10;++x) { ... whatever ...}

вы можете написать

void forx(int x)
{
  if (x>=10)
    return;
  ... whatever ...
  forx(x+1);
}

Так что в этом случае я бы сделал что-то вроде:

void endloop(int start, int end)
{
  if (end>=arrayLength)
    return;
  ... work on running total ...
  endloop(start, end+1);
}

void startloop(int start)
{
  if (start>=arrayLength)
    return;
  endloop(start, start);
}
int main()
{
  ... setup ...
  startloop(0);
  ... output ...
}

Списки параметров не обязательно являются полными. Как я уже сказал, я не хочу делать вашу домашнюю работу за вас, просто дать вам подсказку, чтобы начать.

Answer 2

Сначала напишите функцию, которая проверяет серию заданного начального индекса и заданной длины для условия «сумма его членов». Затем напишите вторую функцию, которая ищет самые длинные ряды в вашем массиве, в которых задан только начальный индекс (это следует делать по длине подсерии в порядке убывания); эта функция может вызывать первую. Наконец, напишите третью функцию, которая перебирает все начальные индексы, вызывая функцию номер два.

Ой, подождите, больше нет необходимости в рекурсии, так что много искажений мозга исчезло ...: -)

Answer 3

Мне кажется, что проблема заключается здесь:

if(sum_so_far+arr[index]==index)

Пока вы сравниваете сумму с текущим индексом, но вы должны сравнивать ее с первым индексом в серии. Мне кажется, что было бы лучше, если бы вы начали с последнего элемента arr в направлении первого, а не в естественном порядке. Таким образом, вы начинаете суммировать элементы до тех пор, пока сумма не станет равной текущему индексу.