У меня есть функция в Java, которая написана с помощью рекурсивного алгоритма, который должен быть написан в итерационной форме. Дело в том, что я не знаю, с чего начать обдумывать новый алгоритм для этого. Это задание, над которым я работаю.
Рассмотрим следующую вычислительную задачу:
Предположим, вы работаете в качестве консультанта, и у вас есть последовательность n потенциальных консультационных работ, которые платят соответственно A[0],A[1],..,A[n-1] долларов (таким образом, работа 0 оплачивается A[0] долларов, работа 1 оплачивается A[1] долларов и т. д.).
Кроме того, задание i начинается в день i (i = 0 ; : : : ; n 1 ).
Однако для каждого задания требуется 2 дня, поэтому вы не можете выполнять любые два последовательных задания. Цель состоит в том, чтобы определить максимальную сумму денег, обозначаемую F(n); Вы можете заработать на действительном расписании, выбранном из n рабочих мест A[0] до A[n-1]
:
В качестве примера рассмотрим следующий входной массив:
0 1 2 3 4 5
A 5 6 8 6 2 4
Оптимальным графиком является выполнение заданий 0 ; 2 ; и 5; за что сумма денег
заработано F(6) = A[0] + A [2] + A [5] = 17; настолько велика, насколько это возможно. Обратите внимание, что это
является допустимым расписанием, так как не включены две последовательные работы.
Моя функция для рекурсивной версии, которая решает это следующим образом:
public static int jobScheduleRecursive(int[] A, int n)
{
n = A.length;
if(n == 0){return 0;}
else if(n == 1){return A[0];}
else if(n >= 2){return max(jobScheduleRecursive(A, (n-1)), (A[n-1])
+ jobScheduleRecursive(A, n-2));}
else return -1;
}
Подводя итог, я должен придумать итерационный алгоритм, который выполняет эту работу. Единственная проблема в том, что я понятия не имею, как поступить. Буду признателен за любой совет, чтобы привести меня в правильном направлении.