По индукции:
-* на первом шаге код отвечает условиям -* предположим, что получившийся код на шаге i есть Код Грея -* тогда на шаге i+1: первая половина кода будет корректна, так как она совпадает с кодом с шага i за исключением добавленного последнего бита 0. Вторая половина тоже соответствует условиям, так как она является зеркальным отражением первой половины, только добавлен везде бит 1. На стыке: первые i бит совпадают в силу зеркальности, последние различны по построению.
Таким образом этот код - Код Грея. Индукционное предположение доказано, алгоритм работает верно.
Код Грея применяется в:
-* датчиках-энкодерах ( устройства, преобразующие угол поворота вала в электрический сигнал );
-* как способ решения задачи о Ханойских башнях ( дано три стержня, на первом из них нанизано 8 колец разного размера в виде пирамиды; цель - перенести
пирамиду на другой стержень, сохранив упорядоченность );
-* в генетических алгоритмах;
-* в Картах Карно ( при передаче в карту переменные сортируются в Код Грея );
-* в кодах, исправляющих ошибки;
-* для связи систем с различной частотой работы.
== Источники ==
* [http://en.wikipedia.org/wiki/Gray_code] Gray code, From Wikipedia, the free encyclopedia]
* [http://ru.wikipedia.org/wiki/Код_Грея] Код Грея, Материал из Википедии — свободной энциклопедии]
