シーケンスはオブジェクトのコレクションであり、この場合は整数のコレクションです。このタスクは、加算演算子と減算演算子を使用して一連の要素が M で割り切れるかどうかを判断することです。
###問題文###例 1
リーリー リーリー 説明- 指定された配列には、2 で割り切れる有効なシーケンス {1 2 5} = {8} が存在する可能性があります。 例 2
リーリー リーリー 説明- 指定された配列では、解が 4 で割り切れるシーケンスは存在できません。 方法 1: 暴力的な方法
疑似コード
リーリー時間計算量 - 再帰の使用により O(2^n)。
方法 2: バックトラッキング
この方法は、バックトラッキングを使用して検索空間をバックトラックして、M で割り切れる有効なシーケンスが存在しないことがわかっているパスをたどることを回避できる点を除いて、前の総当たり再帰的方法に似ています。
例: C 実装
- 最悪の場合の時間計算量は O(2^n) ですが、実際には、検索空間の枝刈りにより総当たり法よりも優れています。
スペースの複雑さ- 再帰的なスタックスペースのため、O(n)。 方法 3: 貪欲な方法
この問題に対する貪欲な解決策は、まず配列を昇順に並べ替えてから、合計が M を超えない場合に貪欲に加算関数を適用することです。この方法では、全体的に最適な解決策は得られない可能性がありますが、局所的な最適な解決策は得られます。 疑似コード
リーリー次のプログラムでは、配列をソートして、M で割り切れる最適なローカル部分配列を見つけます。
リーリー ###出力### リーリー疑似コード
リーリー要約すると、M で割り切れる有効なシーケンスを見つけるには、ブルート フォースの場合の O(2^n) から動的ケースの O(NM) まで、複数の方法とさまざまな関係解析および空間解析を適用できます。プログラミングは次のとおりです。最も効率的な方法。
以上がM で割り切れる有効なシーケンスがあるかどうかを確認します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。