10455 - Gray Code

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10455 - Gray Code

Post by .. »

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:
  • Please make discussion about the algorithm BRFORE posting source code.
    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

Post by wyvmak »

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

Post by marthapfhui »

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

Post by Stefan_Bialucha »

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).

Post Reply

Return to “Volume 104 (10400-10499)”