정사각형 피라미드 수(제곱합)

A 사각뿔수는 자연수의 제곱의 합을 말합니다. 자연수에는 1부터 무한대까지의 모든 숫자가 포함됩니다. 예를 들어 처음 4개의 정사각형 피라미드 숫자는 1, 5, 14, 30입니다.

더 나은 이해를 위해 다음 사실을 고려하십시오. 처음에 숫자의 정사각형 피라미드를 취하고 숫자 공을 내림차순으로 쌓으면 피라미드가 형성됩니다.

문제 설명

숫자 합계가 주어졌습니다. Sum이 처음 n개 자연수의 제곱의 합이면 n을 반환하고, 그렇지 않으면 false를 반환합니다.

예 1

은 다음과 같이 번역됩니다.

예 1

으아아아

설명 = 30은 처음 4개 자연수의 제곱의 합입니다.

으아아아

따라서 출력은 4가 되어야 합니다.

예 2

으아아아

설명 = 54와 같은 n 자연수의 제곱합은 없습니다. 따라서 출력은 -1이어야 합니다.

문제 설명에 대한 해결책

이 문제에는 두 가지 해결책이 있습니다.

방법 1: 폭력적인 해결

무차별 대입법은 n = 1부터 시작됩니다. 이전 total 값에 다음 자연수의 제곱을 더하는 변수 'total'을 만듭니다. 합계가 Sum과 같으면 n을 반환하고, 그렇지 않으면 합계가 Sum보다 크면 false를 반환합니다.

의사코드

으아아아

예

아래는 주어진 숫자가 자연수의 제곱의 합인지 확인하는 C++ 프로그램입니다.

으아아아

출력

으아아아

시간 복잡도 - O(sum), 여기서 합계는 주어진 입력입니다.

공간 복잡성 - O(1): 추가 공간이 사용되지 않습니다.

Newton-Raphson 방법을 사용한 방법 2

또 다른 방법은 Newton-Raphson 방법입니다. 뉴턴-랩슨 방법은 주어진 함수 f(x)의 근과 근의 초기 추측을 찾는 데 사용됩니다.

으아아아

그래서 n은 이 삼차 방정식의 근이며 초기 추측값 x0에서 시작하여 다음 공식을 사용하여 이전 값 xn xn+에서 얻은 다음 값 x를 찾는 Newton-Raphson 방법을 사용하여 계산할 수 있습니다. 1.

$$mathrm{x_{1}=x_{0}-frac{f(x_{0})}{f^{'}(x_{0})}}$$

의사코드

으아아아

예

아래는 주어진 숫자가 자연수의 제곱의 합인지 확인하는 C++ 프로그램입니다.

으아아아

출력

으아아아

시간 복잡도 - O((log n) F(n)) 여기서 F(n)은 f(x)/f'(x)를 n자리 정밀도로 계산하는 비용입니다.

공간 복잡성 - O(1): 추가 공간이 사용되지 않습니다.

결론

이 기사에서는 주어진 합계의 정사각뿔 수를 찾는 문제를 해결합니다. 두 가지 방법을 소개합니다. 하나는 무차별 대입 방법이고 다른 하나는 효율적인 방법입니다. 두 방법 모두 C++ 프로그램을 제공합니다.

위 내용은 정사각형 피라미드 수(제곱합)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!