1 から n までのすべての組み合わせの積の合計

1 から n までの数字を 1 つずつ取り出してみると、多くの組み合わせが考えられます。

たとえば、一度に 1 つの数値だけを取る場合、組み合わせの数は nC1 になります。

一度に 2 つの数値を取る場合、組み合わせの数は nC2 になります。したがって、組み合わせの総数は nC1 nC2 … nCn となります。

すべての組み合わせの合計を求めるには、効率的な方法を使用する必要があります。そうしないと、時間と空間の複雑さが非常に高くなります。

＃＃＃問題文＃＃＃

1 から N までの毎回の数値のすべての組み合わせの積の合計を求めます。

N は指定された数値です。

＃＃＃例＃＃＃ ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃説明＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー

ブルートフォースアプローチ

強引な方法では、すべての組み合わせを再帰的に生成し、それらの積を見つけて、対応する合計を見つけます。

再帰的 C プログラムの例

以下は、すべての組み合わせ (1 から N まで) で毎回取得される積の合計を求めるために使用される再帰 C プログラムです。 リーリー ＃＃＃出力＃＃＃ リーリー

このアプローチの再帰ツリーを作成すると、時間計算量が指数関数的に増加することがわかります。また、多くのステップが繰り返されるため、プログラムが冗長になります。したがって、非常に非効率的です。 効率的なアプローチ (動的プログラミング)

効果的な解決策は、動的プログラミングを使用して冗長性を削除することです。 動的プログラミングは、問題を部分問題に分割する手法です。部分問題が解決され、その結果は繰り返しを避けるために保存されます。

動的プログラミングを使用した C プログラムの例 以下は、動的プログラミングを使用して、一度にすべての組み合わせ (1 から N) の合計を求める C プログラムです。

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

この記事では、1 から N までのすべての組み合わせの積の和を求める問題について説明しました。 私たちは、指数関数的な時間計算量を伴う総当りアプローチから開始し、次に動的プログラミングを使用して修正しました。両方の方法のための C プログラムも提供されています。

以上が1 から n までのすべての組み合わせの積の合計の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。