M で割り切れる有効なシーケンスがあるかどうかを確認します。

シーケンスはオブジェクトのコレクションであり、この場合は整数のコレクションです。このタスクは、加算演算子と減算演算子を使用して一連の要素が M で割り切れるかどうかを判断することです。

＃＃＃問題文＃＃＃

整数 M と整数配列が与えられたとします。要素間の加算と減算のみを使用して、解が M で割り切れる有効な数列が存在するかどうかを確認します。

例 1

リーリー リーリー

説明

- 指定された配列には、2 で割り切れる有効なシーケンス {1 2 5} = {8} が存在する可能性があります。 例 2

リーリー リーリー

説明

- 指定された配列では、解が 4 で割り切れるシーケンスは存在できません。 方法 1: 暴力的な方法

この問題を解決する簡単な方法は、再帰関数を使用して配列の可能なシーケンスをすべて検索し、M で割り切れるシーケンスがあるかどうかを確認することです。

疑似コード

リーリー

例: C 実装

次のプログラムでは、再帰的方法を使用してすべての有効なシーケンスを検索し、有効なシーケンスが M で割り切れるかどうかを確認します。

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

時間計算量 - 再帰の使用により O(2^n)。

スペースの複雑さ - 再帰スタックスペースによる O(n)。

方法 2: バックトラッキング

この方法は、バックトラッキングを使用して検索空間をバックトラックして、M で割り切れる有効なシーケンスが存在しないことがわかっているパスをたどることを回避できる点を除いて、前の総当たり再帰的方法に似ています。

疑似コード

リーリー

例: C 実装

次のプログラムでは、バックトラッキングを使用して検索スペースを取り除き、問題の解決策を見つけます。

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

時間計算量

- 最悪の場合の時間計算量は O(2^n) ですが、実際には、検索空間の枝刈りにより総当たり法よりも優れています。

スペースの複雑さ

- 再帰的なスタックスペースのため、O(n)。 方法 3: 貪欲な方法

この問題に対する貪欲な解決策は、まず配列を昇順に並べ替えてから、合計が M を超えない場合に貪欲に加算関数を適用することです。この方法では、全体的に最適な解決策は得られない可能性がありますが、局所的な最適な解決策は得られます。 疑似コード

リーリー

例: C 実装

次のプログラムでは、配列をソートして、M で割り切れる最適なローカル部分配列を見つけます。

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

方法 4: 動的プログラミング

動的プログラミングの概念を使用して、このソリューションでは評価の中間結果を保存します。 N 1 行と M 列を持つテーブルを作成します。配列要素を使用しない場合、基本ケースの結果は % M == 0 になります。次に、M を法として考えられるすべての剰余を反復処理して、テーブルを更新します。

疑似コード

リーリー

例: C 実装

次のプログラムでは、問題を部分問題に分解し、それらを解決します。

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

要約すると、M で割り切れる有効なシーケンスを見つけるには、ブルート フォースの場合の O(2^n) から動的ケースの O(NM) まで、複数の方法とさまざまな関係解析および空間解析を適用できます。プログラミングは次のとおりです。最も効率的な方法。

以上がM で割り切れる有効なシーケンスがあるかどうかを確認します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。