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

Question

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

A "correct" series is one in which the sum of its members equals to the index of its first member.

программа должна найти длину ДЛИННОГО «правильной» серии в серии из п чисел.

Например: если входная серия будет 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

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

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

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

Answer 2

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

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

Answer 3

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

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

Во-вторых, вы рекурсивно решаетесь по пути «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 
    } 
} 

Или что-то в этом направлении.

Не удалось ли решить проблему с рекурсией или это была ваша первая идея при хорошем решении?

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

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

Я не хочу делать домашнее задание для вы, но я дам вам подсказку. Вы можете использовать рекурсию для имитации цикла, поставив условие break в начале функции и положив рекурсивный вызов в конце функции с параметром +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 ... 
} 

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