四角錐数（平方和）

A 四角錐数は、自然数の二乗の和を指します。自然数には、1 から無限大までのすべての数が含まれます。たとえば、最初の 4 つの四角錐の数字は 1、5、14、および 30 です。

よりよく理解するために、次の事実を考慮してください。最初の数字の四角錐を取り出し、数字のボールを降順に積み重ねると、ピラミッドが形成されます。

＃＃＃問題文＃＃＃

与えられた数値の合計。 Sum が最初の n 個の自然数の二乗和の場合は n を返し、それ以外の場合は false を返します。

例 1

は次のように翻訳されます:

例 1

リーリー

説明 = 30 は、最初の 4 つの自然数の二乗の和です。

リーリー

したがって、出力は 4 になるはずです。

例 2

リーリー

説明 = 54 に等しい n 個の自然数の二乗和は存在しません。したがって、出力は -1 になるはずです。

問題文の解決策

この問題には 2 つの解決策があります。

方法 1: 暴力的な解決策

総当たりクラッキング手法は n = 1 から始まります。次の自然数の 2 乗を前の total 値に加算する変数 'total' を作成します。 total が Sum と等しい場合は n を返し、そうでない場合は total が Sum より大きい場合は false を返します。

疑似コード

リーリー ＃＃＃例＃＃＃

以下は、指定された数値が自然数の二乗和であるかどうかを確認する C プログラムです。

リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量 - O(sum)、ここで sum は指定された入力です。

スペースの複雑さ - O(1): 余分なスペースは使用されません。

ニュートン・ラフソン法を使用した方法 2

もう 1 つの方法は、ニュートン・ラフソン法です。

ニュートン・ラフソン法

指定された関数 f(x) の根とその根の初期推定を見つけるために使用されます。

リーリー

したがって、n はこの 3 次方程式の根であり、初期推定値 x0 から開始し、次の式を使用して次の値 x を見つけることを含むニュートン・ラフソン法を使用して計算できます。つまり、前の値 xn から xn を取得します。 1.

$$\mathrm{x_{1}=x_{0}-\frac{f(x_{0})}{f^{'}(x_{0})}}$$ 疑似コード

リーリー ＃＃＃例＃＃＃

次は、指定された数値が自然数の二乗和であるかどうかを確認するための C プログラムです。

リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量 - O((log n) F(n)) ここで、F(n) は、n 桁の精度で f(x)/f'(x) を計算するコストです。

スペースの複雑さ - O(1): 余分なスペースは使用されません。

＃＃＃結論は＃＃＃

この記事では、指定された合計の四角錐の数を求める問題を解決します。強引な方法と効率的な方法の2つを紹介します。どちらの方法でも C プログラムが提供されます。

以上が四角錐数（平方和）の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。