Форум программистов [Powered by Invision Power Board]

Код

Коды Грея    
...    
Этот алгоритм позволяет перебирать все наборы Bm так, чтобы каждый следующий набор    
отличался от предыдущего только в одном разряде. Построенная с помощью этого    
алгоритма последовательность наборов называется кодом Грея. Вообще, n-разрядный код    
Грея — это упорядоченная (возможно, циклическая) последовательность, состоящая из    
 2n n-разрядных кодовых слов, каждое из которых отличается от соседнего в одном разряде.    
Будем рассматривать бинарные коды Грея порядка n. Итак, на вход алгоритма подается    
единственное число n, которое указывает порядок кода Грея. По ходу выполнения    
алгоритма мы получим последовательность всех подмножеств n-элементного множества,    
в которой каждое последующее подмножество получается из предыдущего добавлением    
или удалением единственного элемента (наименьшим возможным изменением) — код Грея.    
При этом каждое подмножество будет представляться бинарной последовательностью    
B[1], …, B[n].    
Gray-Generation(n)    
 1  for i := 1 to n do B[i] := 0;    
 2  i := 0;    
 3  repeat    
 4      write (B[i], …, B[n]);    
 5      i := i + 1; p := 1; j := i;    
 6      while j mod 2 = 0 do    
 7          begin    
 8              j := j/2; p := p + 1;  // количество 2 в разложении числа на прост. множители + 1    
 9          end;    
10      if p ≤ n then B[p] := 1 − B[p];    
11  until p > n