## 10455 - Gray Code

Moderator: Board moderators

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

### 10455 - Gray Code

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:

Code: Select all

``````111 5
``````
sample output:

Code: Select all

``````111
110
010
011
001
000
100
101
``````
Could anyone kindly explain to me? Thanks!
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
After someone taught me, I've the following interpretation:

G(n) represents the number of ways to form the n-bit gray code.

For n-bit, you can fix 1st bit, 2nd bit, ..., n-th bit.
After each bit fixed, you can have G(n-1) ways to generate the upper half, and G(n-1) ways to generate the lower half.

Index is the i-th way to generate n-bit gray code according the description...

Maybe I 'm not stating clear enough. Hope this helps.

marthapfhui
New poster
Posts: 7
Joined: Sat Mar 10, 2007 7:03 pm
wyvmak wrote:After someone taught me, I've the following For n-bit, you can fix 1st bit, 2nd bit, ..., n-th bit.
After each bit fixed, you can have G(n-1) ways to generate the upper half, and G(n-1) ways to generate the lower half.
I have no idea on the meaning of "upper half" and "lower half". What do these terms mean?

Thanks a lot.

Stefan_Bialucha
New poster
Posts: 5
Joined: Mon Mar 31, 2008 12:49 am
upper half is the block of first half count of rows (in the sample output above: half of 8 rows = 4) and
lower half accordingly the remaining block of the same size (in the sample output above: last 4 rows).