Самый длинный индекс - рекурсия

Question

Мне нужно написать код для этого задания, предметом изучения являются рекурсивные методы:

Пример: рассмотрим arr = {0,5,1,1,2}. Индексы 0,2 и 3 хорошо расположены:

• Индекс 0 имеет хорошие позиции, так как P0 = 0.
• Индекс 1 плохо расположен, так как P1 = 5> 1. Поскольку все элементы положительны, невозможно найти последовательность, начинающуюся с индекса 1, которая может быть суммирована с 1.
• Индекс 2 имеет хорошие позиции, поскольку P2 + P3 = 2.
• Индекс 3 имеет хорошие позиции, так как P3 + P4 = 3.
• Индекс 4 расположен неправильно: мы не можем найти последовательность, начинающуюся с индекса, которая может быть суммирована до 4 - потому что P4 - последний элемент в массиве, а его всего 2.

Мы определяем «правильную длину» правильно расположенного индекса как j-i + 1 - длина последовательности, которая при суммировании показывает, что индекс расположен правильно. Вполне возможно, что индекс хорошо расположен с более чем одной последовательностью элементов. «Хорошо расположенная длина» в этом случае представляет собой максимальную длину различных последовательностей, определяющих индекс как «хорошо размещенные».

Пример: Глядя на предыдущий пример:

• Индекс 0 правильной длины равен 1 (i = 0, j = 0, j-i + 1 = 1).
• Индекс 2 имеет правильную длину 2 (i = 2, j = 3, j-i + 1 = 2).
• Индекс 3 имеет правильную длину 2 (i = 3, j = 4, j-i + 1 = 2).
• Для индексов 1 и 4 правильная длина не определена, поскольку индексы расположены неправильно.
• Рассмотрим arr = {0,5,1,1,2,0} - правильная длина индекса 3 теперь равна 3 (i = 3, j = 5, j-i + 1 = 3). Еще одна последовательность, которая определяет индекс 3 как правильно размещенный, - это (i = 3, j = 4, j-i + 1 = 2), как и раньше, но мы определили правильно расположенную длину как максимальное значение для индекса.

«Максимальная длина правильного размещения» - это максимум между длиной размещения всех хорошо размещенных индексов в обр. Если ни один индекс в массиве не находится в хорошем положении, максимальная длина в правильном положении считается равной нулю.

Функция должна возвращать максимальную правильную длину.

Пример. Для предыдущих примеров возвращаемое значение longestIndex должно быть равно 2, поскольку это максимальная корректная длина любого корректно расположенного индекса в массиве.

Ограничения: вы не можете изменять массив; Вам не разрешено использовать более 1 дополнительной (вспомогательной) функции, доступ к которой можно получить из longestIndex. Итерации не допускаются.

Это код, который я написал:

int longestIndexHelper(int arr[], int length, int old)
{
    if(length==0)
    return 0;
    if((arr[length]+arr[length-1]==length-1)||
       (arr[0]==0)&&(old!=0)&&(old-length==1))
      return (longestIndexHelper(arr, --length, length)+1);
}

int longestIndex(int arr[], int length)
{
    return longestIndexHelper(arr, length, length);
}

Очевидно, это не работает :) Может кто-нибудь попытаться помочь?

Answer 1

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

Вам необходимо подумать, как будет продолжаться рекурсия, если тест if () не пройден.

Answer 2

Итерация не допускается.

Это полностью искусственное ограничение, которое подталкивает нас к рекурсии, когда в данном случае это явно худшее решение. Когда профессора колледжа начнут искать то, что на самом деле хочет рекурсивное решение (скажем, обход дерева) для этих заданий?

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

В любом случае, ваша причина не работает в том, что он проверяет только правильные совпадения длины 2.

РЕДАКТИРОВАТЬ: Вот краткий план моего рекурсивного решения:

int longestIndex(int arr[], int length) {
    if(length == 0) return 0;
    int thisLongestIndex = longestIndexHelper(
        /*whatever parameters you need in order to call it on the first element
                  in the array*/
        );
    return max(thisLongestIndex, longestIndex(arr+1,length-1));
}

Где longestIndexHelper определит самое длинное совпадение для первого элемента в массиве.