各ペアの積の合計

集合 X = {a, b, c} のペアごとの積は、すべての可能な集合ペアの積の合計として定義できます。セットのペアは Y = {a * a, a * b, a *c, b * b, b * c, c * c} で、積は可換です。したがって、集合 X の対積は、集合 Y の要素の合計であり、aa ab ac bb bc cc となります。

数学用語では、可能なペアごとの積の合計は次のように表すことができます:

$$\mathrm{\displaystyle\sum\limits_{i=1,j=i}^{i\leq n,j\leq n}\:(i,j)=i\time j}$$

＃＃＃問題文＃＃＃

数値 n を与えます。 n と 1 を含む範囲 (1, n) 内のペアごとの積の合計を求めます。

例 例 1

リーリー リーリー

説明

の中国語訳は次のとおりです:

説明

i の範囲は 1 ～ 4、j の範囲は i ～ 4 です。

1*1 1*2 1*3 1*4 2*2 2*3 2*4 3*3 3*4 4*4 = 1 2 3 4 4 6 8 9 12 16 = 65

例 例 2

リーリー リーリー

説明

の中国語訳は次のとおりです:

説明

i の範囲は 1 ～ 10、j の範囲は i ～ 10 です。

1*1 1*2 … 1*10 2*2 2*3 … 2*10 3*3 3*4 … 3*10 4*4 4 *5 … 4*10 5*5 5*6 … 5*10 6*6 6*7 … 6*10 7*7 7*8 … 7*10 8* 8 8*9 8*10 9*9 9*10 10*10 = 1705

方法 1: ブルート フォース クラッキング方法

この問題に対する強引な解決策は、2 つの for ループを使用して範囲内のすべての可能な数値のペアを反復することです。最初のループは 1 から n まで反復し、2 番目のループは最初の数値から n まで反復します。

疑似コード

リーリー

例: C 実装

次のプログラムでは、考えられるすべてのペアを見つけて、積の合計を求めます。

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

時間計算量 - O(n^2)

空間の複雑さ - O(1)

方法 2

n = 4 を例に挙げます。

I = 1*1 1*2 1*3 1*4 2*2 2*3 2*4 3*3 3*4 4*4

上記を単純化すると、

I = 1*1 (1 2)*2 (1 2 3)*3 (1 2 3 4)*4

prefix_sum[1] = 1,

とします。

プレフィックス合計[2] = 1 2,

プレフィックス合計[3] = 1 2 3,

プレフィックス合計[2] = 1 2,

疑似コード

リーリー

例: C 実装

以下のプログラムでは、各反復の合計、つまりプレフィックスの合計を求め、それに反復数を掛けて、各ステップの最終合計に加算します。

リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃

つまり、1 から n の範囲の数値のペアの積の和を解くには、上記の 2 つの方法のいずれかを使用できます。1 つ目の方法は総当たり法で、時間計算量は O です。 (n^ 2)、2 番目の方法は、プレフィックス合計を使用してペアごとの積の合計を計算する最適化方法であり、時間計算量は O(n) です。

以上が各ペアの積の合計の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。