Java에서 정수 넘침

인터뷰에서이 질문을 받았습니다. 내가 이런 식으로 뭔가에 내려와 // 그래서Java에서 정수 넘침

class Iterator { 
    bool hasNext; 
    int getNext(); 
}

XN 번호 X1, X2, X3, ...의 평균을 계산하도록 요청 받았다 :

double average (Iterator & it) { 

double average = 0; 
double sum = 0; 
int len = 0; 

while (it.hasNext == true) { 

    sum += it.getNext(); 
} 

if (len > 0) 
    average = sum/len; 
}

면접관이 목록은 말했다 크기는 알 수없고 매우 클 수 있으므로 합계가 넘칠 수 있습니다. 그는 오버플로 문제를 해결하는 방법을 물었고 최대 횟수를 초과 할 때가 얼마나 될지를 추적하여 대답했습니다. 그는 스택과 평균 및 길이에 관해서 뭔가를 말했습니다. 어떤 종류의 목록에 2 개의 변수? 누구나 단서가 있습니까?

출처

2014-04-23 user1529412

관련 질문 : http://stackoverflow.com/questions/1657834/how-can-i-check-if overflow-two-numbers-in-java-will-cause-an-overflow http://stackoverflow.com/questions/12226634/how-to-prevent-integer-overflow-in-java-code –

당신은 " 합계를 계산하려면 "평균을 의미하셨습니까? – icza

스택 사용에 대해서는 잘 모르겠지만 대수에서 도움을 받으면 이전 평균을 사용하여 새 평균에 대한 수식을 도출 할 수 있습니다.

이미 평균이 n - 1이고, 평균이 oldAvg이라고 가정 해 보겠습니다.

oldAvg = (X ₁ + X ₂ + .. +는 _{N X - 1})/(N - 1)

새로운 평균 newAvg 의해 표현 될 것이다 :

newAvg = (X 1_{_{+ X + 2} ... + X _{N - 1 + X} N)/N}

일부 대수 조작을 통해 이전 평균을 사용하여 평균화 된 항목 수와 다음 항목을 사용하여 새 평균을 나타낼 수 있습니다.

newAvg = (X 1_{_{+ X + 2} ... + X _{N - 1})/N + X N/N}

= ((N - 1)/(N - 1)) * (X ₁ + X ₂ + ... + X _{N - 1})/N + X _N/N

= oldAvg/N의 * (N - 1) + x _n/n

n - 1을 곱하기 전에 n으로 나눔으로써 넘침을 피할 수 있습니다. 다음 항목을 추가하려면 x _n을 n으로 나눈 값을 입력하면됩니다.

첫 번째 루프는 평균을 첫 번째 요소와 동일하게 설정하지만 이후의 각 루프는 위의 수식을 사용하여 새 평균을 유도합니다.

n++; 
newAvg = oldAvg/n * (n - 1) + it.next()/n;

출처

2014-04-23 19:55:23 rgettman

아마도 평균을 계산할 때 모든 용어가 필요하지는 않지만 그는 moving average을 추적 할 수 있습니다. 이것은 용어의 수와 함께 지금까지 사용 된 용어의 합계를 고려한 것으로 사용할 수 있습니다.

총계가 너무 길어서 길게 저장할 수 없으므로 총을 보유하려면 BigInteger과 같은 것을 사용하고 싶을 것입니다.

출처

2014-04-23 19:46:59 azurefrog

BigDecimal에 대해 언급 한 다음 그의 다음 질문에 대해 movingAverage로 이동했기 때문에 더 자세히 설명해 주실 수 있습니까? – user1529412

당신이 rgettman의 공식을 단순화하면 더 당신은 다음과 같은 얻을 것이다 :

len++; 
average = average + (it.next() - average)/len;

출처

2014-04-23 20:02:25 hoaz

Java에서 정수 넘침

답변

관련 문제