これは、アルゴリズムブックのタスクです。
問題は、どこから始めればよいかまったくわからないということです。
Trace the following non-recursive algorithm to generate the binary reflexive
Gray code of order 4. Start with the n-bit string of all 0’s.
For i = 1, 2, ... 2^n-1, generate the i-th bit string by flipping bit b in the
previous bit string, where b is the position of the least significant 1 in the
binary representation of i.
したがって、1ビットのグレーコードは0 1、200 01 11 10などの場合は .
たくさんの質問
1) n = 1 の場合、 から始めることができることを知ってい0 1ますか?
2) 「すべて 0 の n ビット文字列から始める」をどのように理解すればよいですか?
3)「前のビット列」？「前」はどの文字列ですか？前は下位nビットからですか？(たとえば、n=2 の場合、前は n=1 のものです)?
4) フリップする操作しかない場合、1 ビットの文字列を 2 ビットの文字列に変換するにはどうすればよいですか?
これは私をとても混乱させます。私がこれまでに理解している唯一の「人間」の方法は、下位nビットからセットを取得し、それらを複製し、2番目のセットを反転し、最初のセットのすべての要素に0を追加し、2番目のセットのすべての要素に1を追加することです。完了 (例: 0 1-> 0 1 | 0 1-> 0 1 | 1 0-> 00 01 | 11 10->11 01 11 10完了。
助けてくれてありがとう