배열에 음수를 구문 분석 할 때 프로그램 오류가 발생했습니다.

Question

과제 중 하나에 이상한 문제가 있습니다. 사용자 입력에서 정수를 가져 와서 배열에 저장하려고합니다. 그 후, 그 숫자의 다른 특성을 찾기 위해 4 개의 재귀 메소드가 실행됩니다. 그러나 인덱스에서 음수를 사용하여 프로그램을 실행하려고하면 프로그램이 응답을 중지합니다.

import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
public class Assignment9 { 
    public static void main(String[] args) throws IOException { 
     int index = 0; 
     int[] numbers; 
     numbers = new int[100]; 
    InputStreamReader inRead = new InputStreamReader(System.in); 
    BufferedReader buffRead = new BufferedReader(inRead); 
    String line = buffRead.readLine(); 

    try { 
     while (!line.equals("0") && index < 100) { 
      numbers[index] = Integer.parseInt(line); 
      index++; 
      line = buffRead.readLine(); 

     } 
    } catch (IOException exception) { 
     System.out.println("Array index out of bound"); 
    } 
`  int min = findMin(numbers, 0, numbers.length - 1); 
     int sumAtEven = computeSumAtEvenIndexes(numbers, 0, numbers.length - 1); 
     int divByThree = countDivisibleBy3(numbers, 0, numbers.length - 1); 
     System.out.println("The minimum number is " + min); 
     System.out.println("The sum of numbers at even indexes is " + sumAtEven); 
     System.out.println("The count of numbers that are divisible by 3 is " + divByThree); 
     System.out.println("The maximum number among numbers that are less than the first number is " + maxLessThanFirst); 


    } 

    public static int findMin(int[] numbers, int startIndex, int endIndex) { 
     if (startIndex == endIndex) { 
      return numbers[startIndex]; 
     } else if (findMin(numbers, startIndex, endIndex - 1) < numbers[endIndex]) { 
      return findMin(numbers, startIndex, endIndex - 1); 
     } else { 
      return numbers[endIndex]; 
     } 

    } 

    public static int computeSumAtEvenIndexes(int[] numbers, int startIndex, int endIndex) { 
     if (startIndex == endIndex) { 
      if (startIndex % 2 == 0) { 
       return numbers[startIndex]; 
      } else return 0; 
     } else { 
      if (endIndex % 2 == 0) { 
       return computeSumAtEvenIndexes(numbers, startIndex, endIndex - 1) + numbers[endIndex]; 
      } else { 
       return computeSumAtEvenIndexes(numbers, startIndex, endIndex - 1); 
      } 
     } 
    } 

    public static int countDivisibleBy3(int[] numbers, int startIndex, int endIndex) { 
     if (startIndex == endIndex) { 
      if (numbers[startIndex] % 3 == 0) { 
       return 1; 
      } else { 
       return 0; 
      } 
     } else { 
      if (numbers[endIndex] == 0) { 
       return countDivisibleBy3(numbers, startIndex, endIndex - 1); 
      } 
      if (numbers[endIndex] % 3 == 0) { 
       return countDivisibleBy3(numbers, startIndex, endIndex - 1) + 1; 
      } else { 
       return countDivisibleBy3(numbers, startIndex, endIndex - 1); 
      } 
     } 
    } 

} 

이것은 문제를 이해하는 데 필요한 유일한 관련 섹션입니다. 추가 코드가 필요하면 그냥 물어보십시오. 고맙습니다!

Answer 1

findMin 메소드를 바꾸십시오. 배열에 전달하고 인덱스에 대해 0을 전달합니다.

public static int findMin(int[] numbers, int index) { 
    if (index == numbers.length - 1) 
    { 
     return numbers[index]; 
    } 
    else 
    { 
     return Math.min(numbers[index], findMin(numbers, index + 1)); 
    }  
} 

Answer 2

내 findMin 방법은 이중 재귀 :

가

public static int findMin(int[] numbers, int startIndex, int endIndex) { 
    if (startIndex == endIndex) { 
     return numbers[startIndex]; 
     // in the next line, we recurse looking for the minimum 
    } else if (findMin(numbers, startIndex, endIndex - 1) < numbers[endIndex]) { 
     // we've found the minimum, but now we must recurse again to get it! 
     return findMin(numbers, startIndex, endIndex - 1); 
    } else { 
     return numbers[endIndex]; 
    } 
} 

이 기하 급수적으로 한 선형 알고리즘되어야 하는지를 변환한다. findMin을 입력 할 때마다 로그하면 배열 크기에 따라 빠르게 증가합니다. 실험에 의하면 2^(x-1) + 2^(x-2) - 1 번 호출됩니다. 여기서 x는 배열의 길이입니다.

크기가 10 인 배열은 767 번 호출됩니다. 크기가 20 인 배열의 경우 786,431 번 호출됩니다. 크기 30, 25,165,823 번. 크기 100 수율 :

950737950171172051122527404031 통화 (950x950, 9.5 x 10^29).

없기 때문에 시간에 StackOverflowError가와 충돌하지 않습니다 귀하의 프로그램 스택 깊이 배열 (플러스 주 하나)의 대략 길이를 초과하지만 실행하는 우주의 수명보다 더 오래 걸릴 것입니다 않습니다 .

이에 findMin 변경 : 이제 알고리즘은 크기 100 이미에 반복적으로 findMin을 불렀다는 사실에 대한 크기 50, 100 사이즈 20, 50의 배열 20 개 통화를합니다

public static int findMin(int[] numbers, int startIndex, int endIndex) { 
    if (startIndex == endIndex) { 
     return numbers[startIndex]; 
    } 
    // there's no need for an else since the if ended with a return 
    int r = findMin(numbers, startIndex, endIndex - 1); // only recurse once 
    if (r < numbers[endIndex]) { 
     // we've found the minimum, return it without recursing again 
     return r; 
    } 
    // again, no need for else, here 
    return numbers[endIndex]; 
} 

비교할 값을 얻었지만 을 다시 호출하면 같은 값을 반환하는 데는 빨간색 플래그가 있어야합니다. 많은 경우에, 그러한 불필요한 반복은 단지 사소한 성가심 일뿐입니다. 이 경우에, 그것은 파국적이었다.

오, 언급하는 것을 잊었습니다. 음수 인 번호를 입력하는 이유는 다음과 같은 문제를 야기했습니다. 아마도 프로그램을 시도했을 때 나는 결코 숫자를 입력하지 않았을 것입니다. 너무 지루하고, 0을 입력하면 목록을 끝낼 수 있습니다. 배열을 할당 할 때 :

int[] numbers = new int[100]; 

배열은 0으로 채워집니다. 그래서, 당신은 열 개 번호를 입력하면, 배열의 나머지 부분은 제로가 될 것이며, 우리가이 선에 도달 할 때 첫 전화 findMin에 :

는

if (findMin(numbers, startIndex, endIndex - 1) < numbers[endIndex]) 

끝의 수는 0이 될 것이다 또한 분입니다. 그래서 우리는 한 번만 반복하고 두 번 반복하지는 않습니다. 대부분의 재귀 호출에서도 이러한 현상이 발생합니다. 배열의 끝에있는 0의 긴 꼬리에서 모든 것들에 대해 일어날 것입니다.사용자가 이중으로 재귀적인 동작을 볼 수있는 값을 실제로 입력 한 항목에 들어가는 경우에만 해당됩니다. 사용자가 약 10 개의 숫자 만 입력하면 안전합니다.

그러나 사용자가 단 한 번의 부정적인 번호를 입력하는 경우, 그 최소가되고 제로는 우리를 보호하지 않습니다

. numbers[endIndex]에 해당 음수가있는 경우를 제외하고는 번 호에서 이중 회귀를 받았습니다. 2^x-1 대신 2^(x-1) + 2^(x-2) - 1을 얻은 이유는 제가 항상 음수를 두 번째 위치에 넣었 기 때문입니다. 배열 그래서, 최소값이 어디에 있느냐에 따라 위에서 설명한 것보다 더 나은 성능을 얻을 수 있습니다.