次の記事を読んでいて、第4段落の背後にあるロジックを理解できませんでした
N 個のランプと 4 つのスイッチが与えられます。最初のスイッチはすべてのランプを切り替え、2 番目は偶数ランプ、3 番目は奇数ランプを切り替え、最後のスイッチはランプ 1、4、7、10、... を切り替えます。
ランプの数 N、ボタンが押された回数 (最大 10,000)、およびいくつかのランプの状態 (たとえば、ランプ 7 がオフ) が与えられると、ランプが取り得るすべての状態を出力します。
単純に、ボタンを押すたびに、合計 4^10000 (約 10^6020 ) の 4 つの可能性を試す必要があります。つまり、完全な検索を実行する方法はありません (この特定のアルゴリズムは再帰を悪用します)。
ボタンを押す順序が重要ではないことに気付くと、この数は約 10000^4 (約 10^16 ) まで下がりますが、それでも完全に検索するには大きすぎます (ただし、確かに 10^6000 倍以上近くなります)。
ただし、ボタンを 2 回押すことは、ボタンを 1 回も押さないことと同じであるため、実際に確認する必要があるのは、各ボタンを 0 回または 1 回押すことだけです。それは 2^4 = 16 通りの可能性であり、制限時間内に解決可能な反復回数です。
順序が問題にならない場合、構成の総数は 10000^4 になりますか?