Var s : array [1..N] of 0..1;

I : integer;

procedure GRAY (m : integer);

begin

if m=0 then

begin

{1} for i:=1 to n do write( s[i] ); writeln;

end

else

begin

{2} GRAY (m-1);

{3} s[m]:=1-s[m];

GRAY (m-1)

end

end;

begin

for i:=1 to n do s[i]:=0;

GRAY (n)

end.

Упражнение. 1. Проверить, что при n=4 программа действительно генерирует требуемую последовательность.

2. Показать, что в процессе исполнения оператора строки {2} вызов процедуры GRAY происходит 2^m-1 раз.

3. Доказать корректность программы SET2.

4. Определить вычислительную сложность программы SET2.

Упорядоченную последовательность двоичных n-разрядных наборов обычно называют кодами Грея n-го порядка(происхождение этого названия см. [4]), если каждый набор в этой последовательности отличается от предыдущего изменением только одного разряда.

Пусть задана некоторая перестановка <a₁,...,a_n>. Нетрудно видеть, что если мы в строке {1} программы SET2 заменим оператор печати на write (s[a[i]]), то модернизируемая программа будет также строить коды Грея. Их обычно называют симметрично-отраженными. Можно показать, что существует n! различных симметрично-отраженных кодов Грея, начинающихся с нулевого кодового слова.

Упражнение. Для какого наименьшего n существует несимметрично отраженный код Грея, начинающийся с нулевого кодового слова.

Перейдем к построению итеративного варианта алгоритма SET2. Здесь достаточно учесть равенство I_n = P_n:

program SET3 ;

const n= ;

Var s : array [1..N] of 0..1;

I,j,k,p : integer;

begin

{0} for k:=1 to n do s[k]:=0;

i:=0; {i определяет число сгенерированных подмножеств}

repeat

for k:=1 to n do write( s[k] ); writeln;

{1} i:=i+1;

p:=1; j:=i;

{2} while j mod 2 = 0 do

begin {j*2^p-1 = i}

j:=j div 2;

p:= p+1

end; {p определяет номер изменяемого разряда}

if p <= n then

{3} s[p]:=1-s[p]

{4} until p>n

end.

Комментарий. Пусть после выполнения оператора {1} i имеет двоичное разложение b_m...b_p0...0, где b_p=1 (или до выполнения оператора {1} значение i в двоичной системе выглядело как b_m...b_p+101...1 (сравните с программой SET1)). Для определения p достаточно выполнить оператор {2}. Условие {4} означает, что уже сгенерировано 2ⁿ кодовых слов.

Упражнение. Определить вычислительную сложность программы SET3.

Улучшить временные характеристики приведенной программы можно за счет замены цикла {2} более совершенной конструкцией. Здесь возможны два подхода . Первый основан на непосредственном применении машинных команд, а второй - на использовании определенной закономерности в последовательности номеров изменяемых разрядов в текущем кодовом слове.

Перейдем к изложению первого способа. Предположим, что порядок генерируемых кодовых слов меньше чем длина машинного слова в арифметических и логических командах ЭВМ. Пусть знак  обозначает команду по разрядного сравнения двух слов (т.е. в результате получается новое слово, в котором единицы стоят только а тех разрядах, которые различны в заданных словах). Знак  обозначает поразрядную конъюнкцию двух слов. Применив эти команды, можно улучшить временные характеристики программы SET3. В самом деле s можно хранить в упакованном виде в одном слове. Пусть в i1 хранится значение i до выполнения оператора {1}, т.е. i1=i-1. Тогда оператор {0} эквивалентен s:=0; оператор {2} - p:=(ii1)i; оператор {3} - s:=sp; условие {4} записывается как i=2ⁿ.

Пример. Пусть длина машинного слова равна 16. После оператора {1} i=3984. Тогда машинное представление:

i=0000 1111 1001 0000

i1=i-1=0000 1111 1000 1111

ii1=0000 0000 0001 1111

p=(ii1)i=0000 0000 0001 0000

Случай когда n совпадает с длиной машинного слова, поддается подобной модификации, но требует учета ‘переполнения’ слов.

Упражнение. Используя равенство I_n = P_n показать, что если 0i<n и b_nb_n-1...b₀-двоичное представление i, записанное в n+1 позиции и G_i=g₁g₂...g_n i-ый по порядку код Грея, генерируемый программой SET3, то g_k = b_n-k+b_n-k+1, 1kn. Построить программу генерации кодов Грея на основе последнего равенства.

Второй способ [4] строится на хранении в памяти последовательности значений номеров изменяемых разрядов в текущем кодовом слове, т.е. на хранении значений последовательности P_n. Вследствие рекурсивного определения P_n естественно организовать хранение ее элементов в виде стека. В этом случае генерация ее элементов может быть описана по следующей итеративной схеме:

1. {инициализация стека} Вначале стек содержит элементы n,n-1,...,1 (с 1 в вершине).

2. Алгоритм выталкивает верхний элемент i и помещает его в последовательность.

3. В стек добавляются элементы i-1,i-2,...,1.

4. Повторяются выполнения с шага 2 до тех пор, пока стек не опустошится.

Упражнения. 1.Доказать корректность приведенного алгоритма.

2. Написать программу генерации P_n по этому алгоритму.

3. Оценить временную и емкостную сложность полученной программы.

Отметим, что занесение значений в стек фактически совпадает с занесением значений параметра m в стек исполняемой программы при вызовах процедуры GRAY из SET2, и поэтому не дает существенного выигрыша по сравнению с алгоритмами SET2 и SET3. Однако если организовать стек в виде списочной структуры особого типа, при которой действия по включению на шаге 3 элементов i-1,i-2,...,1 в стек выполняются за постоянное число операций, независящих от i, то можно заметно улучшить временные характеристики алгоритма.

Пусть стек хранится в массиве (t₀,t₁,...,t_n), при этом t₀ указывает на верхний элемент в стеке, и для каждого i>0 t_i определяет значение расположенное в стеке под элементом i, если i находится в стеке. Заметим, что элементы i-1,i-2,...,1 помещаются в стек после удаления элемента i за счет изменения значения t₀ на 1.Если i нет в стеке, то значение t_i может быть, вообще говоря, любым, так как не оказывает никакого влияния на вычисления. Однако его значение разумно установить равным i+1, т.к. по свойству алгоритма, в случае когда в следующий раз элемент i+1 будет помещен в стек, элементом, находящимся над ним, будет i. Удаление из стека элемента i в этом случае может быть осуществлено за счет пересылки t_i-1 в t_i. Алгоритм порождения последовательности P_n на языке Паскаль может быть записан так:

program PN ;

const n= ; n1 = ; {n1=n+1; }