Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
46.
Коды Грея и алгоритмы их порождения
В целях минимизации вычислительной сложности построения всех подмножеств множества следует использовать алгоритм с наименьшим количеством преобразований при переходе от одного подмножества к другому. Естественно, это будет алгоритм, в котором при построении следующего подмножества из текущего производится операция либо добавления, либо удаления всего лишь одного элемента множества. В этом случае векторы-индикаторы текущего и порождаемого подмножеств должны различаться всего в одном разряде. Такие последовательности двоичных наборов известны как коды Грея .
Определение 1. Упорядоченный циклический набор 2n различных n-разрядных двоичных векторов, в котором любые два рядом расположенных вектора различаются только в одном разряде, называется n-разрядным кодом Грея и обозначается G(n).
Из всего многообразия двоичных кодов Грея в данном разделе будут рассматриваться только так называемые двоично-отраженные коды Грея. Эти коды обладают рядом свойств, опишем их. Пусть G(n) – n-разрядный код Грея, записанный в форме двоичной 2^n x n-матрицы так, что i-я строка матрицы является i-м вектором кода Грея:
Тогда двоичный (n+1)-разрядный код Грея задаётся следующим образом:
Листинг 2. Алгоритм порождения n-разрядного двоично-отражённого кода Грея
void CodеGrey(int n) {
int * Stack = new int [n]; // Стек
int top = -1; // Вершина стека
int * G = new int[n]; // Массив для текущего
// вектора кода Грея
int i, j, k, m;
// Инициализация кода Грея и заполнение рабочего стека
for (i = n - 1; i >=0; --i) {
G[i] = 0;
Stack[++top] = i+1;
}
// Формирование кода Грея
while (top >= 0) {
// Готовый вектор выводим на экран
for (i = 0; i < n; ++i) cout << G[i] << " ";
cout << endl;
// Определяем позицию, в которой следующий вектор
// отличается от текущего
i = Stack[top--];
// Инвертируем значение булевой переменной
G[n - i] = (G[n - i] + 1) % 2;
// Заносим в стек индексы позиций для дальнейших
// преобразований
for (j = i - 1; j > 0; --j)
Stack[++top] = j;
}
for (i = 0; i < n; ++i) cout << G[i] << " ";
cout << endl;
}
Вычислительная сложность алгоритма
Оценим вычислительную сложность предложенного алгоритма порождения двоично-отражённого кода Грея. Заметим, что реализация стека в основном алгоритме требует выполнения внутреннего цикла, в котором i – 1, ..., 1 заносятся в стек при чтении из него элемента i. Поскольку , то на каждом шаге число выполняемых операций не будет превосходить n. Число итераций внешнего цикла равно 2^n, следовательно, для выполнения алгоритма потребуется не более O(n*2^n) операций.