Решение проблем рекурсивно в C
Наш преподаватель дал нам следующее присвоение:
"Корректный" ряд - тот, в котором сумма его участников равняется индексу своего первого участника.
Программа, как предполагается, находит длину САМОГО ДЛИННОГО "корректного" ряда в серии 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);
}
Что я делаю неправильно здесь?
Мы не предполагаемся нам циклы на этом присвоении.
3 ответа
Хм, с этой программой есть несколько проблем.
Наиболее очевидное: «return maxwithout; return 0;» должен выдать ошибку компиляции: нет способа добраться до последнего оператора возврата.
Во-вторых, вы возвращаетесь к решению по пути "maxwith", пока не достигнете конца массива. Затем вы собираетесь рекурсивно перейти к maxwithout, впервые нажав на него с index = 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 ...
}
Списки параметров не обязательно являются полными. Как я уже сказал, я не хочу делать за вас домашнее задание, просто дам вам подсказку, чтобы начать.
Сначала напишите функцию, которая проверяет ряд с заданным начальным индексом и заданной длиной на условие "сумма его членов". Затем напишите вторую функцию, которая ищет самую длинную серию в вашем массиве, где задан только начальный индекс (перебор длины подсерий в порядке убывания); эта функция может вызывать первую. Наконец, напишите третью функцию, перебирающую все начальные индексы и вызывающую функцию номер два.
О, подождите, рекурсия больше не нужна, так что много мозгов не нужно... :-)
.Мне кажется, что проблема здесь:
if(sum_so_far+arr[index]==index)
Вы сравниваете полученную сумму с текущим индексом, но вы должны сравнивать ее с первым индексом в сериале. Мне кажется, было бы лучше, если бы вы начали с последнего элемента arr по направлению к первому, вместо того, чтобы идти в естественном порядке. Таким образом вы начнете суммировать элементы до тех пор, пока сумма не станет равной текущему индексу.