Как управлять рекурсивной функцией?

Question

Мне нужно написать рекурсивную функцию, которая получает 4 параметра.

Первый - это массив. второй - левый индекс, третий - правый индекс и индекс «K». Индекс «K» - это ячейка в массиве, а индекс lrft указывает на начало и справа указывает на конец.

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

Вот пример результата, что мне нужно получить:

public static void main(String[] args) { 
    int[] A = {1,1,1,0,1,1,0,1,1,1,1,1,0,1,1}; 
    System.out.println(floodOnes(A,0, A.length-1, 9)); // 5 output 
    System.out.println(floodOnes(A,0, A.length-1, 3)); // 0 output 
    System.out.println(floodOnes(A,0, A.length-1, 0)); // 3 output 
    System.out.println(floodOnes(A,0, A.length-1, 14)); // 2 output 
} 

public static int floodOnes(int [] A,int left, int right, int k){ 
    //some logic 
} 

Вот моя реализация:

public class Program { 
    public static void main(String[] args) { 
     int[] A = {1,1,1,0,1,1,0,1,1,1,1,1,0,1,1}; 
     System.out.println(floodOnes(A,0,A.length-1, 9)); 
    } 

    public static int floodOnes(int [] A,int left, int right, int k){   
     if (left != k) left+=1; 
     if (right != k) right-=1; 

     if (left == k && right == k) return A[k]; //condition when the recursive call stops 

     int res = floodOnes(A, left, right, k); 

     if (A[left] == 1 && A[right] == 1) 
      return res = A[left] + A[right]; //count ones  

     else return res; 
    } 
} 

Но мое решение не работает должным образом.

В этой строке:

if (A[left] == 1 && A[right] == 1) 
     return res = A[left] + A[right]; //count ones 

Если один из условий `t isn выполняются один раз, следующие доходы не должны добавлять те, чтобы привести переменными.

И я не знаю, как это сделать.

Answer 1

Поскольку вы ищете - the maximum length of a sequence of ones that contain the cell k. Простой и сжатый код для достижения этого может быть следующим.

public static void main(String[] args) { 
    int[] A = {1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1}; 
    System.out.println(floodOnes(A, 0, A.length - 1, 9)); // prints 5 
    System.out.println(floodOnes(A, 0, A.length - 1, 3)); // prints 0 
    System.out.println(floodOnes(A, 0, A.length - 1, 0)); // prints 3 
    System.out.println(floodOnes(A, 0, A.length - 1, 14)); // prints 2 
} 

public static int checkLeft(int[] A, int k) { 
    return (k < 0 || A[k] != 1) ? 0 : 1 + checkLeft(A, k - 1); 
} 

public static int checkRight(int[] A, int k) { 
    return (k > (A.length - 1) || A[k] != 1) ? 0 : 1 + checkRight(A, k + 1); 
} 

public static int floodOnes(int[] A, int left, int right, int k) { 
    return (A[k] != 1) ? 0 : checkLeft(A, k - 1) + 1 + checkRight(A, k + 1); 
} 

Он выводит желаемый результат.

5 
0 
3 
2 

Answer 2

Вы можете разложить эту проблему на две функции. Первый будет считать элементы с левой стороны, последний - с правой стороны. Обе используют рекурсию.

public static int floodOnes(int[] A, int left, int right, int k) { 
    return checkLeft(A, left, k-1, A[k]) + 1 + checkRight(A, right, k+1, A[k]); 
} 

public static int checkLeft(int[] A, int leftBoundary, int k, int number) { 
    if (k < 0 || A[k] != number || k < leftBoundary) 
     return 0; 
    return 1 + checkLeft(A, leftBoundary, k-1, number); 
} 

public static int checkRight(int[] A, int rightBoundary, int k, int number) { 
    if(k >= A.length || A[k] != number || k > rightBoundary) 
     return 0; 
    return 1 + checkRight(A, rightBoundary, k+1, number); 
} 

Я предполагаю:
что 0 <= left <= k <= right < A.length;
, что одиночное число должно считаться 1 (последовательность длины 1) в отличие от вашего примера. Если вы хотите, чтобы его считали равным 0, добавьте if(A[k] != 1) return 0; или аналогичное условие в свой метод floodOnes.

Поэтому:

System.out.println(floodOnes(A, 0, A.length - 1, 9)); // prints 5 
System.out.println(floodOnes(A, 0, A.length - 1, 3)); // prints 1 
System.out.println(floodOnes(A, 0, A.length - 1, 0)); // prints 3 
System.out.println(floodOnes(A, 0, A.length - 1, 14)); // prints 2 

left Кроме того, и right параметры могут быть использованы для некоторых входных исключений (например k > A.length).

Answer 3

Я доказал свой комментарий неправильно. Вот рекурсивный метод с 4 параметрами, упомянутыми в вопросе, который действительно решает проблему.

public static int floodOnes(int[] a, int left, int right, int k) { 
    if (0 <= left && left <= k && k <= right && right < a.length) { 
     // is there a 0 between left (inclusive) and k (exclusive)? 
     int i = left; 
     while (i < k && a[i] == 1) { 
      i++; 
     } 
     if (i < k) { 
      assert a[i] == 0; 
      return floodOnes(a, i + 1, right, k); 
     } 
     // is there a 0 between k (exclusive) and right (inclusive)? 
     i = right; 
     while (i > k && a[i] == 1) { 
      i--; 
     } 
     if (i > k) { 
      assert a[i] == 0; 
      return floodOnes(a, left, i - 1, k); 
     } 
     // no zero found, a[k] not checked, though 
     if (a[k] == 0) { 
      return 0; 
     } else { 
      return right - left + 1; 
     } 
    } else { 
     throw new IllegalArgumentException("Expected " + left + " <= " + k + " <= " + right + " < " + a.length); 
    } 
} 

С помощью этого метода, первый main метод в вашем вопросе печатает ожидаемый:

5 
0 
3 
2 

Я действительно не вижу смысла в решении этой проблемы на этом пути, так что я нахожусь далеко от конечно, это было то, что было предназначено. Я бы предпочел нерекурсивное решение, или если он просто должен быть рекурсивным каким-то образом, то решение в Grzegorz Górkiewicz’ answer.