### 10455 - Gray Code

Posted:

**Mon Apr 12, 2004 8:10 pm**Copied from the problem:

# 1st n-bit gray code has its leftmost bit fixed and it uses 1st (n-1)-bit gray code for upper half and also 1st (n-1)-bit gray code for lower half.

# G(n-1)'th n-bit gray code has its leftmost bit fixed and it uses 1st (n-1)-bit gray code for upper half and G(n-1)'th (n-1)-bit gray code for lower half.

# [G(n-1)+1]'th n-bit gray code has its leftmost bit fixed and it uses 2nd (n-1)-bit gray code for upper half and 1st (n-1)-bit gray code for lower half.

# G(n)'th n-bit gray code has its rightmost bit fixed and it uses G(n-1)'th (n-1)-bit gray code for both halves.

I am not sure if I get the correct meaning of these sentences.....

Does "upper half" means first 2^(n-1) rows?

As I understand, for any n-bit gray code, it should have its leftmost(or rightmost) bit fixed for first 2^(n-1) rows, but it doesn't hold in the sample input:
sample output:
Could anyone kindly explain to me? Thanks!

# 1st n-bit gray code has its leftmost bit fixed and it uses 1st (n-1)-bit gray code for upper half and also 1st (n-1)-bit gray code for lower half.

# G(n-1)'th n-bit gray code has its leftmost bit fixed and it uses 1st (n-1)-bit gray code for upper half and G(n-1)'th (n-1)-bit gray code for lower half.

# [G(n-1)+1]'th n-bit gray code has its leftmost bit fixed and it uses 2nd (n-1)-bit gray code for upper half and 1st (n-1)-bit gray code for lower half.

# G(n)'th n-bit gray code has its rightmost bit fixed and it uses G(n-1)'th (n-1)-bit gray code for both halves.

I am not sure if I get the correct meaning of these sentences.....

Does "upper half" means first 2^(n-1) rows?

As I understand, for any n-bit gray code, it should have its leftmost(or rightmost) bit fixed for first 2^(n-1) rows, but it doesn't hold in the sample input:

Code: Select all

```
111 5
```

Code: Select all

```
111
110
010
011
001
000
100
101
```