[java] 3 개의 변수 쌍을 비교하는 메이트 방식

Program / 글쓴이

Java에서 순서를 무시하면서 3 개의 양수 이중 변수 쌍을 비교하도록 할당되었습니다. 나는 다음을 수행했다.

if ((a1 == a2 && b1 == b2 && c1 == c2) ||
    (a1 == a2 && b1 == c2 && c1 == b2) ||
    (a1 == b2 && b1 == a2 && c1 == c2) ||
    (a1 == b2 && b1 == c2 && c1 == a2) ||
    (a1 == c2 && b1 == a2 && c1 == b2) ||
    (a1 == c2 && b1 == b2 && c1 == a2))
    // if true

선생님으로부터이 3 가지 숫자 쌍을 비교하는 수학적 방법이 있다고 들었습니다.

지금까지 나는 그들의 덧셈, 뺄셈, 힘의 합을 2로 비교하려고 시도했지만 항상 쌍이 다르고 진술이 사실 인 경우를 발견했습니다.

어떤 아이디어?

편집하다:

나는 이미 과제를 보냈고 교사는 나의 대답이 사실이라고 말했다. 호기심을 요구하고 있습니다.

답변

TL; DR

각 삼중 항의 합, 각 삼중 항의 곱 및 각 삼중 항의 가능한 모든 조합의 곱의 합을 비교합니다.

니티 그리 티

대수 의 기본 정리에 따르면 N의 다항식에 대해 N 개의 근을 가져야합니다.

이 사실을 사용하여 우리는 0을 제로로 만들었습니다 a1, a2, and a3. 이제이 다항식의 계수를 찾습니다.

(x - a1) * (x - a2) * (x - a3)
(x^2 - (a1 + a2) * x + a1a2) * (x - a3) 
x^3 - (a1 + a2) * x^2 + (a1a2) * x - a3 * x^2 + (a1a3 + a2a3) * x - a1a2a3

x^3 + (-1 * (a1 + a2 + a3)) * x^2 + (a1a2 + a1a3 + a2a3) * x + (-1 * a1a2a3)

두 개의 다항식이 동일하면 FTA에 의해 같은 뿌리를 가져야합니다. 따라서 생성 된 다항식의 계수를 비교하기 만하면됩니다.

그래서 만약,

(-1 * (a1 + a2 + a3) == (-1 * (b1 + b2 + b3))
      ---equivalently---
a1 + a2 + a3 == b1 + b2 + b3

과

(a1a2 + a1a3 + a2a3) == (b1b2 + b1b3 + b2b3)

과

-1 * a1a2a3 == -1 * b1b2b3
      ---equivalently---
a1a2a3 == b1b2b3

그런 다음 우리는 세 쌍둥이를 결론을 내릴 수 a1, a2, a3와 b1, b2, b3동일합니다.

그만한 가치가 있습니까?

실제적인 관점에서 보면 이것이 OP에 의해 설명 된 것처럼 무차별 대입 검사보다 실제로 효율적인지 살펴 보자.

먼저 확인 : 합계 및 비교 이를 위해서는 총 4 개의 추가와 1 개의 평등 검사가 필요합니다.

총계 확인 = 5; 누적 합계 = 5

두 번째 확인 : 제품, 합계 및 비교 이를 위해서는 6 곱하기, 4 더하기 및 1 등식이 필요합니다.

총계 확인 = 11; 총계 = 16

세 번째 확인 : 제품 및 비교. 이를 위해서는 총 4 개의 곱셈과 1 개의 평등 검사가 필요합니다.

총계 확인 = 5; 총계 = 21

두 개의 논리 AND 연산을 추가하면 “생성 된 다항식 접근법의 계수”에 대한 총 이진 연산 수에는 다음이 필요합니다.

이진 연산 23 개

무차별 대입 검사에는 총 18 개의 전체 동등 검사, 12 개의 논리 AND 비교 및 ​​5 개의 논리 OR 비교가 필요합니다.

이진 연산 35 개

그래서, 엄밀히 말하면 , 대답은 ‘예, “생성 다항식 접근 방식의 계수”참으로 더 효율적입니다. 그러나 @WJS가 지적한 바와 같이 무차별 대입 방식은 단락 가능성이 더 많기 때문에 수학 방식보다 효율적으로 실행 됩니다.

철저한 철저

각 삼중 항의 가능한 모든 조합의 곱의 합계를 건너 뛸 수는 없습니다. 우리가 이것을 생략하면, 이것이 실패하는 수많은 예가 있습니다. 고려 (23, 32, 45)하고 (24, 30, 46)* :

23 + 32 + 45 = 100
24 + 30 + 46 = 100

23 * 32 * 45 = 33120
24 * 30 * 46 = 33120

그것들은 동등하지 않지만 동일한 합계와 제품을 제공합니다. 그러나 가능한 모든 조합의 제품에 대해 동일한 합계를 제공하지는 않습니다.

23 * 32 + 23 * 45 + 32 * 45 = 3211
24 * 30 + 24 * 46 + 30 * 46 = 3204

* 위의 예제와 유사한 예제를 얻는 방법이 궁금한 경우 먼저 길이가 3 인 정수 M 의 모든 정수 파티션을 생성하고 해당 제품을 가져 와서 중복을 찾고 쌍을 선택하십시오.

답변

정렬 할 수 있다면 (a1 <= b1 <= c1 및 a2 <= b2 <= c2) 2 ^ a1 * 3 ^ b1 * 5 ^ c1과 2 ^ a2 * 3 ^ b2 * 5 ^ c2를 비교해보십시오 (기본으로 소수 2, 3, 5 사용)

답변