Жанр: Учеба
Программирование в теоремах и задачах
...N+1, то числа, представимые в виде суммы элементов
a[1]..a[k+1], заполняют отрезок от 1 до N+a[k+1].
k := 0; N := 0;
{инвариант: числа, представимые в виде суммы элементов массива
a[1]..a[k], заполняют отрезок 1..N}
while (k "" n) and (a[k+1] "= N+1) do begin
| N := N + a[k+1];
| k := k + 1;
end;
{(k = n) или (a[k+1] " N+1); в обоих случаях ответ N+1}
writeln (N+1);
(Снова тот же дефект: в условии цикла при ложном первом условии
второе не определено.)
1.2.29. (Для знакомых с основами алгебры) В целочисленном
массиве a[1]..a[n] хранится перестановка чисел 1..n (каждое из
чисел встречается по одному разу).
(а) Определить четность перестановки. (И в (а), и в (б) количество
действий порядка n.)
(б) Не используя других массивов, заменить перестановку на
обратную (если до работы программы a[i]=j, то после должно быть
a[j]=i).
Указание. (а) Четность перестановки определяется количеством
циклов. Чтобы отличать уже пройденные циклы, у их элементов
можно, например, менять знак. (б) Обращение производим по
циклам.
1.2.30. Дан массив a[1..n] и число b. Переставить числа в
массиве таким образом, чтобы слева от некоторой границы стояли
числа, меньшие или равные b, а справа от границы - большие или
равные b.
Решение.
l:=0; r:=n;
{инвариант: a[1]..a[l]"=b; a[r+1]..a[n]"=b}
while l "" r do begin
| if a[l+1] "= b then begin
| | l:=l+1;
| end else if a[r] "=b then begin
| | r:=r-1;
| end else begin {a[l+1]"b; a[r]"b}
| | поменять a[l+1] и a[r]
| | l:=l+1; r:+r-1;
| end;
end;
1.2.31. Та же задача, но требуется, чтобы сначала шли элементы,
меньшие b, затем равные b, а лишь затем большие b.
Решение. Теперь потребуются три границы: до первой будут
идти элементы, меньшие b, от первой до второй - равные b, затем
неизвестно какие до третьей, а после третьей - большие b. (Более
симметричное решение использовало бы четыре границы, но вряд ли
игра стоит свеч.) В качестве очередного рассматриваемого элемента
берем элемент справа от средней границы.
l:=0; m:=0; r:=n;
{инвариант: a[1..l]"b; a[l+1..m]=b; a[r+1]..a[n]"b}
while m "" r do begin
| if a[m+1]=b then begin
| | m:=m+1;
| end else if a[m+1]"b then begin
| | обменять a[m+1] и a[r]
| | r:=r-1;
| end else begin {a[m+1]"b}
| | обменять a[m+1] и a[l+1]
| | l:=l+1; m:=m+1;
end;
1.2.32. (вариант предыдущей задачи, названный в книге
Дейкстры задачей о голландском флаге) В массиве стоят числа 0, 1
и 2. Переставить их в порядке возрастания, если единственной
разрешенной операцией (помимо чтения) над массивом является перестановка
двух элементов.
1.2.33. Дан массив a[1]..a[n] и число m"=n. Для каждой
группы из m стоящих рядом членов (таких групп, очевидно, n-m+1)
вычислить ее сумму. Общее число действий должно быть порядка n.
Решение. Переходя от группы к соседней, мы добавляем один
член, а другой вычитаем.
1.2.34. Дана квадратная таблица a[1..n][1..n] и число m"=n.
Для каждого квадрата размера m на m в этой таблице вычислить
сумму стоящих в нем чисел. Общее число действий должно быть порядка
n*n.
Решение. Сначала для каждого горизонтального прямоугольника
размером n на 1 вычисляем сумму стоящих в нем чисел. (При сдвиге
такого прямоугольника по горизонтали на 1 нужно добавить одно
число и одно вычесть.) Затем, используя эти суммы, вычисляем
суммы в квадратах. (При сдвиге квадрата по вертикали добавляется
полоска, а другая полоска убавляется.)
1.3. Индуктивные функции (по А.Г.Кушниренко).
Пусть M - некоторое множество. Функция f, аргументами которой
являются последовательности элементов множества M, а значениями
- элементы некоторого множества N, называется индуктивной,
если ее значение на последовательности x[1]..x[n] можно восстановить
по ее значению на последовательности x[1]..x[n-1] и по
x[n], т. е. если существует функция F из N*M (множество пар
"n,m", где n - элемент множества N, а m - элемент множества M) в
N, для которой
f("x[1],...,x[n]") = F (f ("x[1],...,x[n-1]"), x[n]).
Схема алгоритма вычисления индуктивной функции:
k := 0; f := f0;
{инвариант: f - значение функции на "x[1],...,x[k]"}
while k"" n do begin
| k := k + 1;
| f := F (f, x[k]);
end;
Здесь f0 - значение функции на пустой последовательности
(последовательности длины 0). Если функция f определена только
на непустых последовательностях, то первая строка заменяется на
"k := 1; f := f ("x[1]");".
Индуктивные расширения.
Если функция f не является индуктивной, полезно искать ее
индуктивное расширение - такую индуктивную функцию g, значения
которой определяют значения f (это значит, что существует такая
функция t, что f ("x[1]...x[n]") = t (g ("x[1]...x[n]")) при
всех "x[1]...x[n]"). Можно доказать, что среди всех индуктивных
расширений существует минимальное расширение F (минимальность
означает, что для любого индуктивного расширения g значения F
определяются значениями g).
1.3.1. Указать индуктивные расширения для следующих
функций:
а) среднее арифметическое последовательности вещественных
чисел;
б) число элементов последовательности целых чисел, равных ее
максимальному элементу;
в) второй по величине элемент последовательности целых чисел
(тот, который будет вторым, если переставить члены в неубывающем
порядке);
г) максимальное число идущих подряд одинаковых элементов;
д) максимальная длина монотонного (неубывающего или невозрастающего)
участка из идущих подряд элементов в последовательности
целых чисел;
е) число групп из единиц, разделенных нулями (в последовательности
нулей и единиц).
Решение.
а) "сумма всех членов последовательности; длина";
б) "число элементов, равных максимальному; значение макси-
мального";
в) "наибольший элемент последовательности; второй по величине
элемент";
г) "максимальное число идущих подряд одинаковых элементов; чис-
ло идущих подряд одинаковых элементов в конце последова-
тельности; последний элемент последовательности";
д) "максимальная длина монотонного участка; максимальная длина
неубывающего участка в конце последовательности; макси-
мальная длина невозрастающего участка в конце последова-
тельности; последний член последовательности";
е) "число групп из единиц, последний член".
1.3.2. (Сообщил Д.Варсонофьев.) Даны две последовательности
x[1]..x[n] и y[1]..y[k] целых чисел. Выяснить, является ли вторая
последовательность подпоследовательностью первой, т. е. можно
ли из первой вычеркнуть некоторые члены так, чтобы осталась
вторая. Число действий порядка n+k.
Решение. (1 вариант) Будем сводить задачу к задаче
меньшего размера.
n1:=n;
k1:=k;
{инвариант: искомый ответ "=" возможность из x[1]..x[n1] по-
лучить y[1]..y[k1] }
while (n1 " 0) and (k1 " 0) do begin
| if x[n1] = y[k1] then begin
| | n1 := n1 - 1;
| | k1 := k1 - 1;
| end else begin
| | n1 := n1 - 1;
| end;
end;
{n1 = 0 или k1 = 0; если k1 = 0, то ответ - да, если k1 "" 0
(и n1 = 0), то ответ - нет}
answer := (k1 = 0);
Мы использовали то, что если x[n1] = y[k1] и y[1]..y[k1] -
подпоследовательность x[1]..x[n1], то y[1]..y[k1-1] - подпоследовательность
x[1]..x[n1-1].
(2 вариант) Функция x[1]..x[n1] |-" (максимальное k1, для
которого y[1]..y[k1] есть подпоследовательность x[1]..x[n1]) индуктивна.
1.3.3. Даны две последовательности x[1]..x[n] и y[1]..y[k]
целых чисел. Найти максимальную длину последовательности, являющейся
подпоследовательностью обеих последовательностей. Количество
операций порядка n*k.
Решение (сообщено М.Н.Вайнцвайгом, А.М.Диментманом). Обозначим
через f(n1,k1) максимальную длину общей подпоследовательности
последовательностей x[1]..x[n1] и y[1]..y[k1]. Тогда
x[n1] "" y[k1] =" f(n1,k1) = max (f(n1,k1-1), f(n1-1,k1));
x[n1] = y[k1] =" f(n1,k1) = max (f(n1,k1-1), f(n1-1,k1),
f(n1-1,k1-1)+1 );
(Поскольку f(n1-1,k1-1)+1 "= f(n1,k1-1), f(n1-1,k1), во втором
случае максимум трех чисел можно заменить на третье из них.)
Поэтому можно заполнять таблицу значений функции f, имеющую
размер n*k. Можно обойтись и памятью порядка k (или n), если индуктивно
(по n1) выписать "f(n1,0), ..., f(n1,k)" (как функция
от n1 этот набор индуктивен).
1.3.4 (из книги Д.Гриса) Дана последовательность целых чисел
x[1],..., x[n]. Найти максимальную длину ее возрастающей
подпоследовательности (число действий порядка n*log(n)).
Решение. Искомая функция не индуктивна, но имеет следующее
индуктивное расширение: в него входит помимо максимальной длины
возрастающей подпоследовательности (обозначим ее k) также и числа
u[1],...,u[k], где u[i] = (минимальный из последних членов
возрастающих подпоследовательностей длины i). Очевидно, u[1] "=
... "= u[k]. При добавлении нового члена x значения u и k корректируются.
n1 := 1; k := 1; u[1] := x[1];
{инвариант: k и u соответствуют данному выше описанию}
while n1 "" n do begin
| n1 := n1 + 1;
| ...
| {i - наибольшее из тех чисел отрезка 1..k, для кото-
| рых u[i] " x[n1]; если таких нет, то i=0 }
| if i = k then begin
| | k := k + 1;
| | u[k+1] := x[n1];
| end else begin {i " k, u[i] " x[n1] "= u[i+1] }
| | u[i+1] := x[n1];
| end;
end;
Фрагмент ... использует идею двоичного поиска; в инварианте
условно полагаем u[0] равным минус бесконечности, а u[k+1]
- плюс бесконечности; наша цель: u[i] " x[n1] "= u[i+1].
i:=0; j:=k+1;
{u[i] " x[n1] "= u[j], j " i}
while (j - i) "" 1 do begin
| s := i + (j-i) div 2; {i " s " j}
| if u[s] "= x[n1] then begin
| | j := s;
| end else begin {u[s] " x[n1]}
| | i := s;
| end;
end;
{u[i] " x[n1] "= u[j], j-i = 1}
Замечание. Более простое (но не минимальное) индуктивное
расширение получится, если для каждого i хранить максимальную
длину возрастающей подпоследовательности, оканчивающейся на
x[i]. Это расширение приводит к алгоритму с числом действий порядка
n*n.
1.3.5. Какие изменения нужно внести в решение предыдущей
задачи, если надо искать максимальную неубывающую последовательность?
Глава 2. Порождение комбинаторных объектов.
Здесь собраны задачи, в которых требуется получить один за
другим все элементы некоторого множества.
2.1. Размещения с повторениями.
2.1.1. Напечатать все последовательности длины k из чисел
1..n.
Решение. Будем печатать их в лексикографическом порядке
(последовательность a предшествует последовательности b, если
для некоторого s их начальные отрезки длины s равны, а (s+1)-ый
член последовательности a меньше). Первой будет последовательность
"1, 1, ..., 1", последней - последовательность "n, n,
..., n". Будем хранить последнюю напечатанную последовательность
в массиве x[1]...x[k].
...x[1]...x[k] положить равным 1
...напечатать x
...last[1]...last[k] положить равным n
while x "" last do begin
| ...x := следующая за x последовательность
| ...напечатать x
end;
Опишем, как можно перейти от x к следующей последовательности.
Согласно определению, у следующей последовательности
первые s членов должны быть такими же, а (s+1)-ый - больше. Это
возможно, если x[s+1] было меньше n. Среди таких s нужно выбрать
наибольшее (иначе полученная последовательность не будет непосредственно
следующей). Соответствующее x[s+1] нужно увеличить на
1. Итак, надо, двигаясь с конца последовательности, найти самый
правый член, меньший n (он найдется, так как по предположению
x""last), увеличить его на 1, а идущие за ним члены положить
равными 1.
p:=k;
while not (x[p] " n) do begin
| p := p-1;
end;
{x[p] " n, x[p+1] =...= x[k] = n}
x[p] := x[p] + 1;
for i := p+1 to k do begin
| x[i]:=1;
end;
Замечание. Если членами последовательности считать числа не
от 1 до n, а от 0 до n-1, то переход к следующему соответствует
прибавлению 1 в n-ичной системе счисления.
2.1.2. В предложенном алгоритме используется сравнение двух
массивов x "" last. Устранить его, добавив булевскую переменную
l и включив в инвариант соотношение l "=" последовательность x -
последняя.
2.1.3. Напечатать все подмножества множества {1...k}.
Решение. Подмножества находятся во взаимно однозначном соответствии
с последовательностями нулей и единиц длины k.
2.1.4. Напечатать все последовательности из k положительных
целых чисел, у которых i-ый член не превосходит i.
2.2. Перестановки.
2.2.1. Напечатать все перестановки чисел 1..n (то есть последовательности
длины n, в которые каждое из чисел 1..n входит
по одному разу).
Решение. Перестановки будем хранить в массиве x[1],...,
x[n] и печатать в лексикографическом порядке. (Первой при этом
будет перестановка "1 2...n", последней - "n...2 1".) Для составления
алгоритма перехода к следующей перестановке зададимся
вопросом: в каком случае k-ый член перестановки можно увеличить,
не меняя предыдущих? Ответ: если он меньше какого-либо из следующих
членов (членов с номерами больше k). Мы должны найти наибольшее
k, при котором это так, т. е. такое k, что x[k] "
x[k+1] " ... " x[n]. После этого x[k] нужно увеличить минимальным
возможным способом, т. е. найти среди x[k+1], ..., x[n]
наименьшее число, большее его. Поменяв x[k] с ним, остается расположить
числа с номерами k+1, ..., n так, чтобы перестановка
была наименьшей, то есть в возрастающем порядке. Это облегчается
тем, что они уже расположены в убывающем порядке.
Алгоритм перехода к следующей перестановке.
{"x[1],...,x[n-1], x[n]" "" "n,...,2, 1".}
k:=n-1;
{последовательность справа от k убывающая: x[k+1] "..." x[n]}
while x[k] " x[k+1] do begin
| k:=k-1;
end;
{x[k] " x[k+1] " ... " x[n]}
t:=k+1;
{t "=n, x[k+1] " ... " x[t] " x[k]}
while (t " n) and (x[t+1] " x[k]) do begin
| t:=t+1;
end;
{x[k+1] " ... " x[t] " x[k] " x[t+1] " ... " x[n]}
... обменять x[k] и x[t]
{x[k+1] " ... " x[n]}
... переставить участок x[k+1] ... x[n] в обратном порядке
Замечание. Программа имеет знакомый дефект: если t = n, то
x[t+1] не определено.
2.2.2. Модифицировать алгоритм перехода к следующей перестановке
так, чтобы он сам проверял, не является ли данная перестановка
последней.
2.3. Подмножества.
2.3.1. Перечислить все k-элементные подмножества множества
{1..n}.
Решение. Будем представлять каждое подмножество последовательностью
x[1]..x[n] нулей и единиц длины n, в которой ровно k
единиц. (Другой способ представления разберем позже.) Такие последовательности
упорядочим лексикографически (см. выше). Очевидный
способ решения задачи - перебирать все последовательности
как раньше, а затем отбирать среди них те, у которых k единиц -
мы отбросим, считая его неэкономичным (число последовательностей
с k единицами может быть много меньше числа всех последовательностей).
Будем искать такой алгоритм, чтобы получение очередной
последовательности требовало порядка n действий.
В каком случае s-ый член последовательности можно увеличить,
не меняя предыдущие? Если x[s] меняется с 0 на 1, то для
сохранения общего числа единиц нужно справа от х[s] заменить 1
на 0. Таким образом, х[s] - первый справа нуль, за которым стоят
единицы. Легко видеть, что х[s+1] = 1 (иначе х[s] не первый).
Таким образом надо искать наибольшее s, для которого х[s]=0,
x[s+1]=1;
______________________
x |________|0|1...1|0...0|
s
За х[s+1] могут идти еще несколько единиц, а после них несколько
нулей. Заменив х[s] на 1, надо выбрать идущие за ним члены так,
чтобы последовательность была бы минимальна с точки зрения нашего
порядка, т. е. чтобы сначала шли нули, а потом единицы. Вот
что получается:
первая последовательность 0...01...1 (n-k нулей, k единиц)
последняя последовательность 1...10...0 (k единиц, n-k нулей)
алгоритм перехода к следующей за х[1]...x[n] последовательнос-
ти (предполагаем, что она есть):
s := n - 1;
while not ((x[s]=0) and (x[s+1]=1)) do begin
| s := s - 1;
end;
{s - член, подлежащий изменению с 0 на 1}
num:=0;
for k := s to n do begin
| num := num + x[k];
end;
{num - число единиц на участке x[s]...x[n], число нулей
равно (длина - число единиц), т. е. (n-s+1) - num}
x[s]:=1;
for k := s+1 to n-num+1 do begin
| x[k] := 0;
end;
for k := n-num+2 to n do begin
| x[k]:=1;
end;
Другой способ представления подмножеств - это перечисление
их элементов. Чтобы каждое подмножество имело ровно одно
представление, договоримся перечислять элементы в возрастающем
порядке. Приходим к такой задаче.
2.3.2. Перечислить все возрастающие последовательности длины
k из чисел 1..n в лексикографическом порядке. (Пример: при
n=5, k=2 получаем 12 13 14 15 23 24 25 34 35 45.)
Решение. Минимальной будет последовательность 1, 2, ..., k;
максимальной - (n-k+1),..., (n-1), n. В каком случае s-ый член
последовательности можно увеличить? Ответ: если он меньше n-k+s.
После увеличения s-го элемента все следующие должны возрастать с
шагом 1. Получаем такой алгоритм перехода к следующему:
s:=n;
while not (x[s] " n-k+s) do begin
| s:=s-1;
end;
{s - элемент, подлежащий увеличению};
x[s] := x[s]+1;
for i := s+1 to n do begin
| x[i] := x[i-1]+1;
end;
2.3.3. Пусть мы решили представлять k-элементные подмножества
множества {1..n} убывающими последовательностями длины k,
упорядоченными по-прежнему лексикографически. (Пример : 21 31 32
41 42 43 51 52 53 54.) Как выглядит тогда алгоритм перехода к
следующей?
Ответ. Ищем наибольшее s, для которого х[s]-x[s+1]"1. (Если
такого s нет, полагаем s = 0.) Увеличив x [s+1] на 1, кладем остальные
минимально возможными (x[t] = k+1-t для t"s).
2.3.4. Решить две предыдущие задачи, заменив лексикографический
порядок на обратный (раньше идут те, которые больше в
лексикографическом порядке).
2.3.5. Перечислить все вложения (функции, переводящие разные
элементы в разные) множества {1..k} в {1..n} (предполагается,
что k "= n). Порождение очередного элемента должно требовать
порядка k действий.
Указание. Эта задача может быть сведена к перечислению
подмножеств и перестановок элементов каждого подмножества.
2.4. Разбиения.
2.4.1. Перечислить все разбиения целого положительного числа
n на целые положительные слагаемые (разбиения, отличающиеся
лишь порядком слагаемых, считаются за одно). (Пример: n=4, разбиения
1+1+1+1, 2+1+1, 2+2, 3+1, 4.)
Решение. Договоримся, что (1) в разбиениях слагаемые идут в
невозрастающем порядке, (2) сами разбиения мы перечисляем в лексикографическом
порядке. Разбиение храним в начале массива
x[1]...x[n], при этом количество входящих в него чисел обозначим
k. В начале x[1]=...=x[n]=1, k=n, в конце x[1]=n, k=1.
В каком случае x[s] можно увеличить не меняя предыдущих?
Во-первых, должно быть x[s-1] " x[s] или s = 1. Во-вторых, s
должно быть не последним элементом (увеличение s надо компенсировать
уменьшением следующих). Увеличив s, все следующие элементы
надо взять минимально возможными.
s := k - 1;
while not ((s=1) or (x[s-1] " x[s])) do begin
| s := s-1;
end;
{s - подлежащее увеличению слагаемое}
x [s] := x[s] + 1;
sum := 0;
for i := s+1 to k do begin
| sum := sum + x[i];
end;
{sum - сумма членов, стоявших после x[s]}
for i := 1 to sum-1 do begin
| x [s+i] := 1;
end;
k := s+sum-1;
2.4.2. Представляя по-прежнему разбиения как невозрастающие
последовательности, перечислить их в порядке, обратном лексикографическому
(для n=4, например, должно получиться 4, 3+1, 2+2,
2+1+1, 1+1+1+1).
Указание. Уменьшать можно первый справа член, не равный 1;
найдя его, уменьшим на 1, а следующие возьмем максимально возможными
(равными ему, пока хватает суммы, а последний - сколько
останется).
2.4.3. Представляя разбиения как неубывающие последовательности,
перечислить их в лексикографическом порядке. Пример
для n=4: 1+1+1+1, 1+1+2, 1+3, 2+2, 4;
Указание. Последний член увеличить нельзя, а предпоследний
- можно; если после увеличения на 1 предпоследнего члена за счет
последнего нарушится возрастание, то из двух членов надо сделать
один, если нет, то последний член надо разбить на слагаемые,
равные предыдущему, и остаток, не меньший его.
2.4.4. Представляя разбиения как неубывающие последовательности,
перечислить их в порядке, обратном лексикографическому.
Пример для n=4: 4, 2+2, 1+3, 1+1+2, 1+1+1+1.
Указание. Чтобы элемент x[s] можно было уменьшить, необходимо,
чтобы s = 1 или x[s-1] " x[s]. Если x[s] не последний, то
этого и достаточно. Если он последний, то нужно, чтобы x[s-1] "=
(целая часть (x[s]/2)) или s=1.
2.5. Коды Грея и аналогичные задачи.
Иногда бывает полезно перечислять объекты в таком порядке,
чтобы каждый последующий минимально отличался от предыдущего.
Рассмотрим несколько задач такого рода.
2.5.1. Перечислить все последовательности длины n из чисел
1..k в таком порядке, чтобы каждая следующая отличалась от предыдущей
в единственной цифре, причем не более, чем на 1.
Решение. Рассмотрим прямоугольную доску ширины n и высоты
k. На каждой вертикали будет стоять шашка. Таким образом, положения
шашек соответствуют последовательностям из чисел 1..k длины
n (s-ый член последовательности соответствует высоте шашки на
s-ой горизонтали). На каждой шашке нарисуем стрелочку, которая
может быть направлена вверх или вниз. Вначале все шашки поставим
на нижнюю горизонталь стрелочкой вверх. Далее двигаем шашки по
такому правилу: найдя самую правую шашку, которую можно подвинуть
в направлении (нарисованной на ней) стрелки, двигаем ее на
одну клетку в этом направлении, а все стоящие правее ее шашки
(они уперлись в край) разворачиваем кругом.
Ясно, что на каждом шаге только одна шашка сдвигается, т.е.
один член последовательности меняется на 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 -стрелке вниз).
Начальное состояние: x[1] =...= x[n] = 1; d[1] =...= d[n] = 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 {i=1}
| 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;
Замечание. Для последовательностей нулей и единиц возможно
другое решение, использующее двоичную систему. (Именно оно связывается
обычно с названием "коды Грея".)
Запишем подряд все числа от 0 до (2 в степени n) - 1 в двоичной
системе. Например, для n = 3 напишем:
000 001 010 011 100 101 110 111
Затем каждое из чисел подвергнем преобразованию, заменив каждую
цифру, кроме первой, на ее сумму с предыдущей цифрой (по модулю
2). Иными словами, число
a[1], a[2],...,a[n] преобразуем в
a[1], a[1] + a[2], a[2] + a[3],...,a[n-1] + a[n]
(сумма по модулю 2). Для n=3 получим:
000 001 011 010 110 111 101 100.
Легко проверить, что описанное преобразование чисел обратимо
(и тем самым дает все последовательности по одному разу).
Кроме того, двоичные записи соседних чисел отличаются заменой
конца 011...1 на конец 100...0, что - после преобразования -
приводит к изменению единственной цифры.
Применение кода Грея. Пусть есть вращающаяся ось, и мы хотим
поставить датчик угла поворота этой оси. Насадим на ось барабан,
выкрасим половину барабана в черный цвет, половину в белый
и установим фотоэлемент. На его выходе будет в половине случаев
0, а в половине 1 (т. е. мы измеряем угол "с точностью до
180").
Развертка барабана:
0 1
-" |_|_|_|_|*|*|*|*| "- (склеить бока).
Сделав рядом другую дорожку из двух черных и белых частей и
поставив второй фотоэлемент, получаем возможность измерить угол
с точностью до 90 градусов:
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
_ _ _ _
|_|_|_|_|*|*|*|*|
|_|_|*|*|_|_|*|*|
|_|*|_|*|_|*|_|*|
мы измерим угол с точностью до 45 градусов и т.д. Эта идея имеет,
однако, недостаток: в момент пересечения границ сразу несколько
фотоэлементов меняют сигнал, и если эти изменения произойдут
не одновременно, на какое-то время показания фотоэлементов
будут бессмысленными. Коды Грея позволяют избежать этой
опасности. Сделаем так, чтобы на каждом шаге менялось показание
лишь одного фотоэлемента (в том числе и на последнем, после целого
оборота).
0 0 0 0 1 1 1 1
0 0 1 1 1 1 0 0
0 1 1 0 0 1 1 0
_ _ _ _
|_|_|_|_|*|*|*|*|
|_|_|*|*|*|*|_|_|
|_|*|*|_|_|*|*|_|
Написанная нами формула позволяет легко преобразовать да
...Закладка в соц.сетях
