Жанр: Учеба
Программирование в теоремах и задачах
...в x[k1+1]...x[k] и
x[l1+1]...x[l]. Теперь это придется делать сложнее.
end else begin {x[k1+1] = y[l1+1]}
| t := x [k1+1];
| while (k1"k) and (x[k1+1]=t) do begin
| | k1 := k1 + 1;
| end;
| while (l1"l) and (x[l1+1]=t) do begin
| | l1 := l1 + 1;
| end;
end;
Замечание. Эта программа имеет дефект: при проверке условия
(l1"l) and (x[l1+1]=t)
(или второго, аналогичного) при ложной первой скобке вторая окажется
бессмысленной (индекс выйдет за границы массива) и возникнет
ошибка. Некоторые версии паскаля, вычисляя (A and B), сначала
вычисляют A и при ложном A не вычисляют B. (Так ведет себя,
например, система Turbo Pascal, 5.0 - но не 3.0.) Тогда описанная
ошибка не возникнет.
Но если мы не хотим полагаться на такое свойство используемой
нами реализации паскаля (не предусмотренное его автором
Н.Виртом), то можно поступить так. Введем дополнительную переменную
b: boolean и напишем:
if k1 " k then b := (x[k1+1]=t) else b:=false;
{b = (k1"k) and (x[k1+1] = t}
while b do begin
| k1:=k1+1;
| if k1 " k then b := (x[k1+1]=t) else b:=false;
end;
Можно также сделать иначе:
end else begin {x[k1+1] = y[l1+1]}
| if k1 + 1 = k then begin
| | k1 := k1 + 1;
| | n := n + 1;
| end else if x[k1+1] = x [k1+2] then begin
| | k1 := k1 + 1;
| end else begin
| | k1 := k1 + 1;
| | n := n + 1;
| end;
end;
Так будет короче, хотя менее симметрично.
Наконец, можно увеличить размер массива в его описании,
включив в него фиктивные элементы.
1.2.18. Даны два неубывающих массива x: array [1..k] of
integer и y: array [1..l] of integer. Найти число различных элементов
среди x[1],...,x[k], y[1],...,y[l]. (Число действий порядка
k+l.)
1.2.19. Даны два массива x[1] "= ... "= x[k] и y[1] "= ...
"= y[l]. "Соединить" их в массив z[1] "= ... "= z[m] (m = k+l;
каждый элемент должен входить в массив z столько раз, сколько
раз он входит в общей сложности в массивы x и y). Число действий
порядка m.
Решение.
k1 := 0; l1 := 0;
{инвариант: ответ получится, если к z[1]..z[k1+l1] приписать
справа соединение массивов x[k1+1]..x[k] и y[l1+1]..y[l]}
while (k1 "" k) or (l1 "" l) do begin
| if k1 = k then begin
| | {l1 " l}
| | l1 := l1 + 1;
| | z[k1+l1] := y[l1];
| end else if l1 = l then begin
| | {k1 " k}
| | k1 := k1 + 1;
| | z[k1+l1] := x[k1];
| end else if x[k1+1] "= y[l1+1] then begin
| | k1 := k1 + 1;
| | z[k1+l1] := x[k1];
| end else if x[k1+1] "= y[l1+1] then begin
| | l1 := l1 + 1;
| | z[k1+l1] := y[l1];
| end else begin
| | { такого не бывает }
| end;
end;
{k1 = k, l1 = l, массивы соединены}
Этот процесс можно пояснить так. Пусть у нас есть две стопки
карточек, отсортированных по алфавиту. Мы соединяем их в одну
стопку, выбирая каждый раз ту из верхних карточек обеих стопок,
которая идет раньше в алфавитном порядке.
1.2.20. Даны два массива x[1] "= ... "= x[k] и y[1] "= ...
"= y[l]. Найти их "пересечение", т.е. массив z[1] "= ... "=
z[m], содержащий их общие элементы, причем кратность каждого
элемента в массиве z равняется минимуму из его кратностей в массивах
x и y. Число действий порядка k+l.
1.2.21. Даны два массива x[1]"=..."=x[k] и y[1]"=..."=y[l]
и число q. Найти сумму вида x[i]+y[j], наиболее близкую к числу
q. (Число действий порядка k+l, дополнительная память - фиксированное
число целых переменных, сами массивы менять не разрешается.)
Указание. Надо найти минимальное расстояние между элементами
x[1]"=..."=x[k] и q-y[l]"=.."=q-y[1], что нетрудно сделать в
ходе их слияния в один (воображаемый) массив.
1.2.22. (из книги Д.Гриса) Некоторое число содержится в
каждом из трех целочисленных неубывающих массивов x[1] "= ... "=
x[p], y[1] "= ... "= y[q], z[1] "= ... "= z[r]. Найти одно из
таких чисел. Число действий должно быть порядка p + q + r.
Решение.
p1:=1; q1=1; r1:=1;
{инвариант: x[p1]..x[p], y[q1]..y[q], z[r1]..z[r]
содержат общий элемент }
while not ((x[p1]=y[q1]) and (y[q1]=z[r1])) do begin
| if x[p1]"y[q1] then begin
| | p1:=p1+1;
| end else if y[q1]"z[r1] then begin
| | q1:=q1+1;
| end else if z[r1]"x[p1] then begin
| | r1:=r1+1;
| end else begin
| | { так не бывает }
| end;
end;
{x[p1] = y[q1] = z[r1]}
writeln (x[p1]);
1.2.23. Та же задача, только заранее не известно, существует
ли общий элемент в трех неубывающих массивах и требуется это
выяснить (и найти один из общих элементов, если они есть).
1.2.24. Элементами массива a[1..n] являются неубывающие
массивы [1..m] целых чисел (a: array [1..n] of array [1..m] of
integer; a[1][1] "= ... "= a[1][m], ..., a[n][1] "= ... "=
a[n][m]). Известно, что существует число, входящее во все массивы
a[i] (существует такое х, что для всякого i из [1..n]
найдётся j из [1..m], для которого a[i][j]=x). Найти одно из таких
чисел х.
Решение. Введем массив b[1]..b[n], отмечающий начало "остающейся
части" массивов a[1]..a[n].
for k:=1 to n do begin
| b[k]:=1;
end;
eq := true;
for k := 2 to n do begin
| eq := eq and (a[1][b[1]] = a[k][b[k]]);
end;
{инвариант: оставшиеся части пересекаются, т.е. существует
такое х, что для всякого i из [1..n] найдётся j из [1..m],
не меньшее b[i], для которого a[i][j] = х; eq "=" первые
элементы оставшихся частей равны}
while not eq do begin
| s := 1; k := 1;
| {a[s][b[s]] - минимальное среди a[1][b[1]]..a[k][b[k]]}
| while k "" n do begin
| | k := k + 1;
| | if a[k][b[k]] " a[s][b[s]] then begin
| | | s := k;
| | end;
| end;
| {a[s][b[s]] - минимальное среди a[1][b[1]]..a[n][b[n]]}
| b [s] := b [s] + 1;
| for k := 2 to n do begin
| | eq := eq and (a[1][b[1]] = a[k][b[k]]);
| end;
end;
writeln (a[1][b[1]]);
1.2.25. Приведенное решение предыдущей задачи требует порядка
m*n*n действий. Придумать способ с числом действий порядка
m*n.
Указание. Придется пожертвовать симметрией и выбрать одну
из строк за основную. Двигаясь по основной строке, поддерживаем
такое соотношение: во всех остальных строках отмечен максимальный
элемент, не превосходящий текущего элемента основной
строки.
1.2.26. (Двоичный поиск) Дана последовательность x[1] "=
... "= x[n] целых чисел и число a. Выяснить, содержится ли a в
этой последовательности, т. е. существует ли i из 1..n, для которого
x[i]=a. (Количество действий порядка log n.)
Решение. (Предполагаем, что n " 0.)
l := 1; r := n+1;
{если a есть вообще, то есть и среди x[l]..x[r-1], r " l}
while r - l "" 1 do begin
| m := l + (r-l) div 2 ;
| {l " m " r }
| if x[m] "= a then begin
| | l := m;
| end else begin {x[m] " a}
| | r := m;
| end;
end;
(Обратите внимание, что и в случае x[m] = a инвариант не нарушается.)
Каждый раз r-l уменьшается примерно вдвое, откуда и вытекает
требуемая оценка числа действий.
Замечание.
l + (r-l) div 2 = (2l + (r-l)) div 2 = (r+l) div 2.
1.2.27. (Из книги Д.Гриса) Дан массив x: array [1..n] of
array [1..m] of integer, упорядоченный по "строкам" и по
"столбцам":
x[i][j] "= x[i+1][j],
x[i][j] "= x[i][j+1]
и число a. Требуется выяснить, встречается ли a среди x[i][j].
Решение. Представляя себе массив a как матрицу (прямоугольник,
заполненный числами), мы выберем прямоугольник, в котором
только и может содержаться a, и будем его сужать. Прямоугольник
этот будет содержать x[i][j] при 1"=i"=l и k"=j"=m.
1 k m
-----------------------------------
1| |***********|
| |***********|
| |***********|
l| |***********|
|---------------------------------|
| |
n| |
-----------------------------------
(допускаются пустые прямоугольники при l = 0 и k = m+1).
l:=n; k:=1;
{l"=0, k"=m+1, если a есть, то в описанном прямоугольнике}
while (l " 0) and (k " m+1) and (x[l][k] "" a) do begin
| if x[l][k] " a then begin
| | k := k + 1; {левый столбец не содержит a, удаляем его}
| end else begin {x[l][k] " a}
| | l := l - 1; {нижняя строка не содержит a, удаляем ее}
| end;
end;
{x[l][k] = a или прямоугольник пуст }
answer:= (l " 0) and (k " m+1) ;
Замечание. Здесь та же ошибка: x[l][k] может оказаться неопределенным.
(Её исправление предоставляется читателю.)
1.2.28. (Московская олимпиада по программированию) Дан неубывающий
массив положительных целых чисел a[1] "= a[2] "=..."=
a[n]. Найти наименьшее целое положительное число, не представимое
в виде суммы нескольких элементов этого массива (каждый элемент
массива может быть использован не более одного раза). Число
действий порядка n.
Решение. Пусть известно, что числа, представимые в виде
суммы элементов a[1],...,a[k], заполняют отрезок от 1 до некоторого
N. Если a[k+1] " N+1, то N+1 и будет минимальным числом, не
представимым в виде суммы элементов массива a[1]..a[n]. Если же
a[k+1] "= 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 в лексикографическом порядке
...Закладка в соц.сетях
