프로젝트 오일러 # 201

Question

나는 잠시 동안 Problem 201을 풀려고 노력했지만 그런 큰 세트에 대한 해결책을 찾지 못했습니다. 가능한 도달 가능한 합계가 ~ 300,000을 초과하지 않는다는 것을 감안할 때 무작위 알고리즘을 시도했지만 막대한 계산 시간을 가진 더 작은 세트에만 적용되었습니다. 그렇다면 어떤 성공도없이 동적 프로그래밍 방식을 시도했습니다.

나는 이미 포기했지만,이 문제를 효과적으로 해결하는 방법이 궁금합니다.

Answer 1

스포일러 앞면! 수립 (또는 코드를 작성) A :

나는

두기 1 (은 이러한 문제를 접근하는 일반적인 방법으로 맞는 방법 및 표시하기 위해) 나는이 문제를 접근 방법에 대한 힌트를 몇 줄 생각 다음 함수 재귀

부울 existsRepresentation (INT 번호 INT maximalIntegerToSquare, INT numberOfSquares)

인수 번호 numberOfSquares의 합 같은 표현을 가지면 함수 true를 반환

형태의 이차 조건 X^2, 여기서 최대 x는 최대 값 알 수 있습니다. 따라서

존재 표현 5,2,2는 0 = 2^2 + 1^2이지만 이 있으므로 true를 반환합니다. 다른 x, y, z가 없으므로 Replay (5,2,3)가 거짓입니다. < = 2 되도록 5 = X^2 + y^2 + Z^2

HINT 2 : 제형 (또는 코드를 작성) 함수

부울 existsUniqueRepresentation (INT 번호 INT maximalIntegerToSquare, INT numberOfSquares)

하는 재귀

여기서 인수 번호가 UNIQUE 표현을 합계로 사용하면 true를 반환합니다. of n 최대 x가 maximalIntegerToSquare보다 작거나 같은 x^2 형식의 2 차항을 umberOfSquares (재귀에는 인수가 더 작은 값을 갖는 existsUniqueRepresentation과 함수 existsRepresentation (HINT 1 )가 모두 포함되어야합니다. 따라서

exists UniqueRepresentation (5,2,2)는 5 = 2^2 + 1^2이므로 true를 반환하고 두 개의 다른 제곱 x^2 + y^2 x <의 합으로 다른 표현은 5가 없습니다. (원하는 최대 y = 2 또는 다른 경우)

exists 3 개의 제곱의 합으로 5의 표현이없고 (따라서 고유 표현이 없기 때문에) UniqueRepresentation (5,2,3)이 거짓이므로 3 개 가지 숫자보다 작거나 같 2 (존재없이 X, Y, Z되는 1 < < = X, Y, Z < < = 2 ..)

existsUniqueRepresentation (89,8,3) 및 existsUniqu을 89 = 8^2 + 4^2 + 3^2 및 89 = 7^2 + 6^2 + 2^2이므로 eRepresentation (89,9,3)은 거짓입니다.

힌트 3 당신은 스스로를주었습니다 : existRepresentation() 또는 existsUniqueRepresentation() 에 의해 반환 된 모든 값을 캐싱해야한다는 점에서 동적 프로그래밍을 사용합니다 (실제로 이것을 교과서에서는 "memoization"이라고하고 동적 프로그래밍은 재귀 호출을하지 않고 계산하기 위해 캐시 된 값을 체계화하는 방법을 의미하지만, 문제는 항상 하위 문제에 대한 솔루션을 캐시하는 것입니다.

그래서 일반적인 접근법은 다음과 같습니다. 재귀로서 문제를 공식화 한 다음 이동하는 모든 것을 캐시합니다! (당신이 당신의 PC에 충분한 메모리를 가지고있는 모든 것이 ..)

그것은 (여기와 다른 많은 문제들에서) 작동합니다!