3. An n-bit Gray code is a sequence of n-bit strings constructed according to ce

Question

3. An n-bit Gray code is a sequence of n-bit strings constructed according to certain rules.
For example, n = 1: C(1) = ['0','1']. n = 2: C(2) = ['00','01','11','10']. n = 3: C(3) = ['000','001','011','010','110','111','101','100'].
A possible recursive algorithm is: The base case is 1 bit, which results in G = {0,1}.
To go to n = 2, reflect the bits (it becomes {1,0}), concatenate that list with the original list to get 0 1 1 0 . Then prepend 0 to the original list and the 1 to the reflected list, resulting in G = {{00},{01},{11},{10}}.

Write a Prolog predicate with the following specification: % gray(N,C) :- C is the N-bit Gray code

Explanation / Answer

1)gray(1,['0','1']).

gray(N,C) :- N > 1, N1 is N-1,

   gray(N1,C1), reverse(C1,C2),

   prepend('0',C1,C1P),

   prepend('1',C2,C2P),

   append(C1P,C2P,C).

prepend(_,[],[]) :- !.

prepend(X,[C|Cs],[CP|CPs]) :- atom_concat(X,C,CP), prepend(X,Cs,CPs).

2)

gray_c(1,['0','1']) :- !.

gray_c(N,C) :- N > 1, N1 is N-1,

   gray_c(N1,C1), reverse(C1,C2),

   prepend('0',C1,C1P),

   prepend('1',C2,C2P),

   append(C1P,C2P,C),

   asserta((gray_c(N,C) :- !)).

gray_alt(N,C) :- N > 1, N1 is N-1,

   gray_alt(N1,C1),

   postpend(['0','1'],C1,C).  

postpend(_,[],[]).

postpend(P,[C|Cs],[C1P,C2P|CsP]) :- P = [P1,P2],

   atom_concat(C,P1,C1P),

   atom_concat(C,P2,C2P),

   reverse(P,PR),

   postpend(PR,Cs,CsP).

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.