Код Грея | C++

Published
Кодом Грея называется такая система нумерования неотрицательных чисел, когда коды двух соседних чисел отличаются ровно в одном бите.
Например, для чисел длины 3 бита имеем такую последовательность кодов Грея: 000, 001, 011, 010, 110, 111, 101, 100. Например, G(4)=6.
Этот код был изобретен Фрэнком Грэем (Frank Gray) в 1953 году.

Применение Кода Грея

Коды Грея имеют несколько применений в различных областях, иногда достаточно неожиданных:
  • Коды Грея применяются в решении головоломки о Ханойской_башне
  • n-битный код Грея соответствует гамильтонову циклу по n-мерному кубу.
  • В технике, коды Грея используются для минимизации ошибок при преобразовании аналоговых сигналов в цифровые (например, в датчиках). В частности, коды Грея и были открыты в связи с этим применением.
  • Коды Грея также находят применение в теории генетических алгоритмов.

Нахождение Кода Грея

(+) - XOR или, как еще его называют «исключающее_или»
Рассмотрим биты числа n и биты числа G(n). Заметим, что i-ый бит G(n) равен единице только в том случае, когда i-ый бит n равен единице, а i+1-ый бит равен нулю, или наоборот (i-ый бит равен нулю, а i+1-ый равен единице).
Таким образом, имеем: G(n) = n (+) (n>>1):
int g (int n) {
	return n ^ (n >> 1);
}
Обратный Код Грея:
int rev_g (int g) {
	int n = 0;
	for (; g; g>>=1)
		n ^= g;
	return n;
}


Views: 647

Кристофер #1 - 1 year ago 0
Голосов: +0 / -0
А алгоритмы в рандомном порядке пишутся? Потом будет какая-нибудь зависимость от простых к сложным?
Msey #2 - 1 year ago 2
Голосов: +2 / -0
Кристофер, Когда общее количество алгоритмов будет порядка двадцати-тридцати - я приступлю к каталогизации по разделам (а-ля графы / геометрия / комбинаторика итд) и подразделам легкий / сложный.
2 комментария удалено