[짐꾼] 논리 문제 하나. - 제 가 뭘 가 져 갔 죠?

원본 링크:http://www.cnblogs.com/baiyanhuang/archive/2010/06/23/1763981.html
1 부터 10000 까지 모두 10000 개의 수가 있 는데, 만약 내 가 그 중에서 무 작위 로 한 개의 수 를 가 져 가면, 너 는 내 가 무엇 을 가 져 갔 는 지 어떻게 알 겠 니?
많은 사람들 이 이 문 제 를 보고 답 을 알 고 있 을 것 이 라 고 믿 습 니 다. 요 며칠 동료 들 과 이 야 기 를 나 누 면서 이 문 제 를 들 었 습 니 다. 자신의 사고 과정 이 있 었 기 때문에 기록 하 는 것 도 좋 습 니 다.논리 문제 라 고 할 수 있 지만 사실은 알고리즘 문제 라 고 할 수 있 습 니 다. 그 는 면접 에서 의 사고 과정 을 미리 말 했 습 니 다.

먼저 10000 개의 수 를 곱 한 다음 에 한 개의 수 를 가 져 간 후의 9999 개의 수 를 곱 하면 둘 을 나 누 면 된다.이 알고리즘 은 정확 하지만 두 가지 잠재 적 인 문제 가 있 을 수 있 습 니 다.

이렇게 많은 숫자 를 곱 하면 그 범 위 는 반드시 시스템 이 제공 하 는 데이터 형식 지원 을 초과 할 것 이다. 물론 당신 은 자신의 대수 표시 알고리즘 을 실현 할 수 있 지만 그 성능 은 반드시 영향 을 줄 것 이다.

문 제 를 확장 한다 고 가정 하면 제 공 된 배열 에 0 이 있 으 면 곱셈 을 사용 할 수 없습니다.

앞에서 제기 한 문제 에 대해 동료 들 은 덧셈 을 생각 하고 10000 개의 수의 합 을 구 한 다음 에 9999 개의 합 을 뺀 다.이렇게 하면 데이터 가 넘 치지 않 을 뿐만 아니 라 덧셈 의 효율 도 곱셈 보다 훨씬 높 아서 데이터 에 0 이 포함 되 어 있어 도 아무런 문제 가 없다.

그 다음 에 관문 을 넘 었 습 니 다. 자신 이 돌아 가서 생각해 보 니 확장 할 수 있다 고 생각 했 습 니 다. 모든 수 를 합치 면 넘 칠 것 이 라 고 가정 하면 어떻게 처리 해 야 할 지 생각 했 습 니 다. 예 를 들 어 1 부터 (2 ^ 64 - 1) 까지 비트 조작, 또는, 이상 또는 중 에 차이 가 있 거나 가장 신기 하 다 고 생각 했 습 니 다. 대 입 해 보 니 과연 적당 합 니 다. 먼저 모든 수 를 다 르 게 하거나 일어나 야 합 니 다.그리고 한 개의 숫자 를 가 져 간 후의 숫자 가 다 르 거나 일어나 면 둘 의 결과 가 다 르 거나 가 져 간 그 숫자 이다.
나 는 a, b, c, d4 개의 숫자 로 시범 을 보 였 다. 왜냐하면 이 또는 결합 율 과 교환 율 에 부합 되 기 때문이다. 그래서:

a^b^c^d = (a^b^c)^d
d = (a^b^c^d)^(a^b^c)

여기 서 이상 하거나 좋 은 점 은

넘 치지 않 습 니 다

이 또는 속도 가 덧셈

보다 빠르다.
문 제 를 확장 하 세 요. 정수 가 아니 라 부동 소수점 을 제공 하면 문제 가 있 습 니까?물론 없습니다. 재위 단계 에서 조작 하기 때문에 정수 든 부동 소수점 이 든 이 알고리즘 을 보면 모두 한 무더기 의 위치 이 고 처리 하 는 데 차이 가 없습니다.
문 제 를 좀 더 확장 하 겠 습 니 다. 제 공 된 숫자 자체 가 내 장 된 형식의 표시 범 위 를 초과 하면 1 부터 2 ^ 128 까지 어떻게 처리 해 야 합 니까?이 문 제 는 이 글 을 쓰 는 과정 에서 생각 한 것 으로 당분간 좋 은 방법 이 없다.