Иногда бывает полезно перечислять объекты в таком порядке, чтобы каждый следующий минимально отличался от предыдущего. Рассмотрим несколько задач такого рода.
2.5.1. Перечислить все последовательности длины n из
чисел 1..k в таком порядке, чтобы каждая следующая
отличалась от предыдущей в единственной цифре, причем не более,
чем на 1.
Ясно, что на каждом шаге только одна шашка сдвигается, т.е. один член последовательности меняется на 1. Докажем индукцией по n, что проходятся все последовательности из чисел 1..k. Случай n=1 очевиден. Пусть n>1. Все ходы поделим на те, где двигается последняя шашка, и те, где двигается не последняя. Во втором случае последняя шашка стоит у стены, и мы ее поворачиваем, так что за каждым ходом второго типа следует k-1 ходов первого типа, за время которых последняя шашка побывает во всех клетках. Если мы теперь забудем о последней шашке, то движения первых n-1 по предположению индукции пробегают все последовательности длины n-1 по одному разу; движения же последней шашки из каждой последовательности длины n-1 делают k последовательностей длины n.
В программе, помимо последовательности x[1]..x[n], будем хранить массив d[1]..d[n] из чисел +1 и -1 (+1 соответствует стрелке вверх, -1 -- стрелке вниз).
Начальное состояние:
Приведем алгоритм перехода к следующей последовательности (одновременно выясняется, возможен ли переход -- ответ становится значением булевской переменной p).
{если можно, сделать шаг и положить p := true, если нет, положить p := false } i := n; while (i > 1) and | (((d[i]=1) and (x[i]=n)) | or ((d[i]=-1) and (x[i]=1))) | do begin | i:=i-1; end; if (d[i]=1 and x[i]=n) or (d[i]=-1 and x[i]=1) | then begin | p:=false; end else begin | p:=true; | x[i] := x[i] + d[i]; | for j := i+1 to n do begin | | d[j] := - d[j]; | end; end;`Замечание. Для последовательностей нулей и единиц возможно другое решение, использующее двоичную систему. (Именно оно связывается обычно с названием << коды Грея>>.)
Запишем подряд все числа от до 2n-1 в двоичной системе. Например, для n=3 напишем: Затем каждое из чисел подвергнем преобразованию, заменив каждую цифру, кроме первой, на ее сумму с предыдущей цифрой (по модулю 2 ). Иными словами, число преобразуем в (сумма по модулю 2). Для n=3 получим:
Легко проверить, что описанное преобразование чисел обратимо (и тем самым дает все последовательности по одному разу). Кроме того, двоичные записи соседних чисел отличаются заменой конца 011...1 на конец 100...0 , что -- после преобразования -- приводит к изменению единственной цифры.
Применение кода Грея. Пусть есть вращающаяся ось, и мы хотим поставить датчик угла поворота этой оси. Насадим на ось барабан, выкрасим половину барабана в черный цвет, половину в белый и установим фотоэлемент. На его выходе будет в половине случаев , а в половине 1 (т.е. мы измеряем угол << с точностью до 180>>).
Развертка барабана:
0 | 1 |
Сделав рядом другую дорожку из двух черных и белых частей и поставив второй фотоэлемент, получаем возможность измерить угол с точностью до :
0 | 0 | 1 | 1 |
0 | 1 | 0 | 1 |
Сделав третью,
0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
мы измерим угол с точностью до и т.д. Эта идея имеет, однако, недостаток: в момент пересечения границ сразу несколько фотоэлементов меняют сигнал, и если эти изменения произойдут не совсем одновременно, на какое-то время показания фотоэлементов будут бессмысленными. Коды Грея позволяют избежать этой опасности. Сделаем так, чтобы на каждом шаге менялось показание лишь одного фотоэлемента (в том числе и на последнем, после целого оборота).
0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
Написанная нами формула позволяет легко преобразовать данные от фотоэлементов в двоичный код угла поворота.
2.5.2. Напечатать все перестановки чисел 1..n так,
чтобы каждая следующая получалась из предыдущей перестановкой
(транспозицией) двух соседних чисел. Например, при n=3
допустим такой порядок:
Теперь вспомним решение задачи о перечислении всех последовательностей, на каждом шаге которого один член меняется на единицу. Заменив прямоугольную доску доской в форме лестницы (высота i-ой вертикали равна i) и двигая шашки по тем же правилам, мы перечислим все последовательности y, причем i-ый член будет меняться как раз только если все следующие шашки стоят у края. Надо еще уметь параллельно с изменением y корректировать перестановку. Очевидный способ требует отыскания в ней числа i; это можно облегчить, если помимо самой перестановки хранить функцию
program test; | const n=...; | var | x: array [1..n] of 1..n; {перестановка} | inv_x: array [1..n] of 1..n; | {обратная перестановка} | y: array [1..n] of integer; {y[i] < i} | d: array [1..n] of -1..1; {направления} | b: boolean; | | procedure print_x; | | var i: integer; | begin | | for i:=1 to n do begin | | | write (x[i], ' '); | | end; | | writeln; | end; | | procedure set_first;{первая: y[i]=0 при всех i} | | var i : integer; | begin | | for i := 1 to n do begin | | | x[i] := n + 1 - i; | | | inv_x[i] := n + 1 - i; | | | y[i]:=0; | | | d[i]:=1; | | end; | end; | | procedure move (var done : boolean); | | var i, j, pos1, pos2, val1, val2, tmp : integer; | begin | | i := n; | | while (i > 1) and (((d[i]=1) and (y[i]=i-1)) or | | | ((d[i]=-1) and (y[i]=0))) do begin | | | i := i-1; | | end; | | done := (i>1); | | {упрощение: первый член нельзя менять} | | if done then begin | | | y[i] := y[i]+d[i]; | | | for j := i+1 to n do begin | | | | d[j] := -d[j]; | | | end; | | | pos1 := inv_x[i]; | | | val1 := i; | | | pos2 := pos1 + d[i]; | | | val2 := x[pos2]; | | | {pos1, pos2 - номера переставляемых элементов; | | | val1, val2 - их значения; val2 < val1} | | | tmp := x[pos1]; | | | x[pos1] := x[pos2]; | | | x[pos2] := tmp; | | | tmp := inv_x[val1]; | | | inv_x[val1] := inv_x[val2]; | | | inv_x[val2] := tmp; | | end; | end; | begin | set_first; | print_x; | b := true; | {напечатаны все перестановки до текущей | включительно; если b ложно, то текущая - последняя} | while b do begin | | move (b); | | if b then print_x; | end; end;`