二項展開系列を出力するプログラムを作成する

二項展開は、(a b)^n の形式の式を展開するために使用される数式です。n は正の整数、a と b は任意の実数または複素数です。展開により、展開内の各項の係数が得られます。

二項展開は次のように表現できます

$$\mathrm{(a b)^n= ^nC_0a^nb^0 ^nC_1a^{n-1}b^1 ^nCa^{n-2}b^2 ... ^nC_ra^{n-r }b^r ... ^nC_na^0b^n}$$

$\mathrm{^nC_r}$ は次の式で与えられる二項係数です

$\mathrm{^nC_r=\frac{n!}{r!\times(n−r)!}}$、ここで n! n

の階乗を表します

展開を使用すると、上記の式を使用してすべての二項項を計算し、それらを展開方程式に代入できます。

＃＃＃問題文＃＃＃

3 つの整数 a、b、n が与えられます。 (a b)^n の二項展開の項を求めます。

例 例 1

＃＃＃＃＃＃入力 -＃＃＃＃＃＃ リーリー

出力 -

リーリー 説明

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

説明 二項展開 (1 2)^3 は次のとおりです

$\mathrm{(1 2)^3 = C(3,0)a^3b^0 C(3,1)a^2b^1 C(3,2)a^1b^2 C(3 ,3)a^0b^3}$

= 1*1*1 3*1*2 3*1*4 1*1*8

したがって、[1, 6, 12, 8] は二項展開の項です。

例 例 2

＃＃＃＃＃＃入力 -＃＃＃＃＃＃ リーリー

出力 -

リーリー

方法 1: 再帰的二項展開

二項展開式 を使用します。 $$\mathrm{(a b)^n= ^nC_0a^nb^0 ^nC_1a^{n-1}b^1 ^nCa^{n-2}b^2 ... ^nC_ra^{n-r }b^r ... ^nC_na^0b^n}$$

二項係数を再帰的に計算することで、各項の値を見つけることができます。 疑似コード

リーリー

例: C 実装

次のプログラムでは、binomialCoeff() 関数は r 番目の二項係数の値を再帰的に計算し、binomialTerms() 関数は展開内の二項項の値を計算します。

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

時間計算量

- O(2^n)。 binomialCoeff() 関数の時間計算量は O(2^n (再帰ツリーと binomialTerms() の 2^n ノードのため)ネストされたループは binomialCoeff() n を 1 回呼び出すため、関数の複雑さは O(n^2) です。したがって、全体的な複雑さは O(2^n) になります。

空間複雑度

- 再帰呼び出しスタックにより、空間複雑度は O(n) です。

方法 2: 反復二項展開

二項展開式

を使用します。

$$\mathrm{(a b)^n= ^nC_0a^nb^0 ^nC_1a^{n-1}b^1 ^nCa^{n-2}b^2 ... ^nC_ra^{n-r }b^r ... ^nC_na^0b^n}$$ 反復と除算を組み合わせることで、この展開の各項の値を求めることができます。

2 つの関数を作成します。最初の関数は二項係数を計算し、2 番目の関数は a と b のべき乗を乗算して目的の二項項を取得します。 疑似コード

リーリー

例: C 実装

次のプログラムでは、binomialCoeff() 関数は r 番目の二項係数を計算し、binomialTerms() 関数は、a、b、および n が与えられた場合の二項展開のすべての項を計算します。

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

時間計算量

- O(n^2)、binomialCoeff() 関数の時間計算量は O(r)、r は r と n-r および binomialTerms() の小さい方です。ネストされたループにより binomialCoeff() n を 1 回呼び出し、複雑さは O(n^2) です。したがって、全体的な複雑さは O(n^2) になります。

空間複雑度

- ベクトルは二項項を格納するため、O(n) になります。

＃＃＃結論は＃＃＃

要約すると、二項展開の二項項を見つけるには、時間計算量が O(2^n) から O(n^2) の範囲で、上記の 2 つの方法のいずれかを使用できます。再帰メソッドよりも優れており、より最適化されています。

以上が二項展開系列を出力するプログラムを作成するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。