Задача 1.
Построить алгоритм, выдающий без повторений все перестановки
N чисел.
Задача 2.
Сгенерировать все подмножества данного n-элементного множест-
ва {0, ..., n-1}.
Задача 3.
Сгенерировать все k-элементные подмножества множества A из N
чисел, A={1, 2, ..., N}.
Пример: N=3, k=2,
подмножества {1,2}, {1,3}, {2,3}.
Задача 4.1.
Во время поездки на поезде девочка заменила в названии поезда
каждую букву ее номером в русском алфавите и получила запись из
единиц и двоек "211221-21221". Определить откуда и куда идет по-
езд?
Задача 4.2.
Дана строка S и набор A слов А[1], ..., A[k]. Разбить строку
S на слова набора всеми возможными способами.
Пример: S=ABBC
A[1]=A, A[2]=AB, A[3]=BC, A[4]=BBC, A[5]=H, A[6]=B
S = A B BC
= A BBC
= AB BC
Задача 5.
Данные N косточек домино по правилам игры выкладываются в
прямую цепочку, начиная с косточки, выбранной произвольно,в оба
конца до тех пор, пока это возможно. Построить алгоритм, позволяю-
щий определить такой вариант выкладывания заданных косточек, при
котором к моменту, когда цепочка не может быть продолжена, "на ру-
ках" останется максимальное число очков.
Задача 6.
a) В написанном выражении ((((1?2)?3)?4)?5)?6 вместо каждого
знака ? вставить знак одной из 4 арифметических операций +,-,*,/
так, чтобы результат вычислений равнялся 35 (при делении дробная
часть в частном отбрасывается). Найти все решения.
б) Вводится строка не более чем из 6 цифр и некоторое целое
число R. Расставить знаки арифметических операций ("+", "-", "*",
"/"; минус не является унарным, т.е. не может обозначать отрица-
тельность числа; деление есть деление нацело, т.е. 11/3=3) и отк-
рывающие и закрывающие круглые скобки так, чтобы получить в ре-
зультате вычисления получившегося выражения число R. Лишние круг-
лые скобки ошибкой не являются.
Например: Строка 505597, R=120: ((5+0)*((5*5)-(9/7)))=120.
Задача 7.
Построить все слова длины n>0 в алфавите скобок "(" и ")",
представляющие правильные скобочные записи.
Задача 8.
Составить программу, которая печатает все различные
представление числа N в виде всевозможных произведений (сумм) K
натуральных чисел (N, K-вводятся, 1<K<N ). Если К=0, то выдать все
возможные произведения (суммы). Представления чисел, отличающихся
только порядком сомножителей (слагаемых), считаются одинаковыми.
ПЕРЕБОРНЫЕ ЗАДАЧИ.
Задача 1.
Этот алгоpитм хорошо известен и достаточно подробно изло-
жен.Опишем его (при N=5), от чего рассуждения не утратят общности.
Алгоритм составлен так, что в процессе его исполнения перестановки
N чисел располагаются лексикографически (в словарном порядке). Это
значит, что перестановки сравниваются слева направо поэлементно.
Больше та, у которой раньше встретился элемент, больше соот-
ветствующего ему элемента во второй перестановке.(Например, если
S=(3,5,4,6,7),а L=(3,5,6,4,7), то S<L).
Принцип работы алгоритма разъясним на примере. Допустим, не-
обходимо воспpоизвести все перестановки цифр 3,4,5,6,7. Первой пе-
рестановкой считаем перестановку (3,4,5,6,7). Последней воспроиз-
водимой перестановкой будет (7,6,5,4,3).
Предположим, что на некотором шаге работы алгоритма получена
перестановка
P=(5,6,7,4,3).
Для того чтобы определить непосредственно следующую за ней пе-
рестановку, необходимо, пересматривая данную перестановку справа
налево, следить за тем, чтобы каждое следующее число было больше
предыдущего, и остановиться сразу же, как только это правило нару-
шится. Место останова указано стрелкой:
(5,6,7,4,3).
^
│
Затем вновь просматриваем пройденный путь ( справа налево ) до
тех пор, пока не дойдем до первого числа, которое уже больше отме-
ченного. Ниже место второго останова отмечено двойной стрелкой.
(5,6,7,4,3).
^ ^
│ ║
Поменяем местами отмеченные числа:
(5,7,6,4,3).
^ ^
║ │
Теперь в зоне, расположенной справа от двойной стрелки, упорядо-
чим все числа в порядке возрастания. Так как до сих пор они были
упорядочены по убыванию , то это легко сделать, перевернув указан-
ный отрезок. Получим:
Q=(5,7,3,4,6).
Q и есть та перестановка, которая должна воспроизводиться не-
посредственно после P.
Действительно, P<Q, так как, пересматривая эти перестановки
слева направо, (P(2)=6,Q(2)=7). Пусть существует такая перестановка
R, что P<R<Q. Тогда P(1)=R(1)=Q(1). По построению же Q(2) -- это
наименьшее во множестве Q\Q(1)={3,4,6,7} число, такое, что
Q(2)>P(2). Поэтому для R(2) верно одно из двух равенств: R(2)=Q(2)
или R(2)=P(2). Но так как в P элементы, начиная с P(3), убывают,
то из P<R следует, что если P(2)=R(2), то и P=R. Аналогично, так
как в Q элементы, начиная с Q(3), возрастают, то из R<Q следует,
что если R(2)=Q(2), то и R=Q.
Задача 2.
Заведем массив B[0..n] из (n+1) элемента. B[i]=0, если i-ый
элемент в подмножество не входит, и B[i]=1 иначе. Т.о. пустому
подмножеству будет соответствовать набор из n нулей, а n-элемент-
ному подмножеству - набор из n единиц. Тут явно заметна связь
подмножества с двоичным представлением числа.
Алгоритм: будем генерировать числа от 0 до 2^n-1, находить их
двоичное представление, и формировать подмножество из элементов с
индексами единичных битов в этом представлении.
Но число 2^n-1 может не поместиться в разрядную сетку машины.
Поэтому генерацию будем проводить, используя массив B:
Сначала B[i]=0 для всех i, что соответствует пустому подмно-
жеству.
Будем рассматривать массив B как запись двоичного числа
B[N]...B[1]B[0],
и моделировать операцию сложения этого числа с единицей. При сло-
жении будем просматривать число справа налево заменяя единичные
биты нулями до тех пор, пока не найдем нулевой бит, в который за-
несем 1. Генерация подмножеств заканчивается, как только B[N]=1
(предыдущая конфигурация была 1...1 = 2^n-1).
2
while B[N]<>0 do begin
i:=0; { индекс бита двоичного числа }
while (B[i]=1) do begin
B[i]:=0; { моделируем перенос в следующий разряд, }
i:=i+1 { возникающий при сложении }
end;
B[i]:=1;
{ Распечатываем индексы единичных элементов массива B --
новое сгенерированное подмножество }
For i:=0 to N-1 do
if B[i]=1 then write(i);
writeln; { переход на новую строку при печати }
end;
Задача 3.
Воспользуемся следующим алгоритмом генерации сочетаний по k
элементов из множества A:
В массиве B будут находиться индексы используемых на данном
шаге элементов из A (общее их число k). В качестве начальной кон-
фигурацией возьмем следующую: B[j]=j, j=1,...,k.
Ищем B[j] с максимальным индексом j такое, что
B[j]<n+j-k,
увеличиваем это B[j] на 1, а для всех m>j полагаем B[m]=B[m-1]+1
(B[j] растут с ростом j, и мы ищем и увеличиваем на 1 такое B[j] с
максимальным номером j, чтобы при заполнении возрастающими значе-
ниями элементов массива B[m], m>j, последний элемент B[k] не пре-
восходил бы n). Если такого B[j] не существует, то генерация соче-
таний для данного k закончена.
Задача 4.2.
Эта задача реализуется следующим рекурсивным алгоритмом по-
иска с возвращением (все слова набора A упорядочены по номерам):
а) Если строка пустая, то одна из возможных дешифровок найде-
на, иначе при разборе текста мы проверяем А[i] (при изменении i от
1 до n) на вхождение в начало дешифруемой в данный момент строки.
б) Если какое-то A[i] входит в строку как префикс, то запоми-
наем номер i этого слова, затем выделяем слово из строки, а с
остатком текста производим операцию разбора по пункту а).
Если ни одно из A[i] не входит в качестве префикса в дешифруе-
мую сейчас строку, то осуществляем возврат на пункт а), предвари-
тельно добавляя в начало строки последнее удаленное оттуда слово,
и пытаемся выделить из текста слово с большим номером в A. Если
возврат осуществить невозможно (т. к. мы находимся в начале исход-
ной строки), то алгоритм заканчивает свою работу. Все возможные
дешифровки найдены.
Задача 5.
Решается используя перебор с возвратом (Backtracking), изло-
женный в задаче 4.
Задача 6.
а) Всего может быть 4 арифметических операции - "+","-","*",
"/". Занумеруем их от 0 до 3. Вместо каждого из пяти знаков "?"
может стоять один из знаков операции. Заведем массив A из 5 целых
чисел, в i-ом элементе массива будет храниться код соответствующей
i-му знаку "?" операции, т.е. число от 0 до 3. Начальная конфигу-
рация - все элементы массива нулевые, конечная - все они равны 3.
Генерация очередной конфигурации знаков равносильна прибавлению
единицы в четверичной системе счисления, в которой разрешается
пользоваться только цифрами от 0 до 3 (подобный метод решения мы
уже встречали в задаче 2).
Приведем программный фрагмент генерации конфигураций.
Для удобства возьмем массив A не из 5, а из 6 элементов.
О получении последней конфигурации знаков будет свидетельствовать
появление 1 в шестом разряде (если к 33333 прибавить 1, то полу-
4
чим 100000 ).
4
for i:=1 to 6 do A[i]:=0;
while A[6]=0 do
begin
....
{ проверка, получили ли мы нужный результат }
....
i:=1;
while A[i]=3 do { Перенос в следующий разряд при }
begin { прибавлении единицы }
A[i]:=0;
i:=i+1;
end;
A[i]:=A[i]+1;
end;
Задача 7.
Можно воспользоваться вторым способом решения задачи 22 главы
"Разное" и написать рекурсивный алгоритм перечисления всех путей
из начальной вершины в конечную.
Задача 8.
Предложим простой способ построения всех разбиений числа
на слагаемые. Разбиения будут строится в порядке, обратном
лексикографическому. Очевидно, что первым разбиением в таком
порядке будет разбиение, содержащее одно слагаемое, равное , а
последним - разбиение из слагаемых, равных 1.
Как выглядит разбиение, следующее непосредственно за раз-
биением
n=с[1]+...+с[к] (1)
Будем искать разбиение,которое имеет самое большое число
начальных слагаемых, равных начальным слагаемым разбиения (1)
- обозначим эти слагаемые а[1],...,а[t-1] - и оставшиеся сла-
гаемые которого определяются разбиением, непосредственно сле-
дующим за разбиением
s=a[t]+a[t+1]+...+a[k].
Легко видеть, что эти условия однозначно определяют зна-
чение t
t=max{i:a[i]>1}.
Таким образом, задача свелась к нахождению разбиения,
непосредственно следующего за разбиением s=a[t]+1+...+1, где
a[t]>1, а количество единиц равно k-t.Таким разбиением явля-
ется разбиение s1=p+p+...+p+(s mod p), где p=a[t]-1.
Задача 1.
Этот алгоpитм хорошо известен и достаточно подробно изло-
жен.Опишем его (при N=5), от чего рассуждения не утратят общности.
Алгоритм составлен так, что в процессе его исполнения перестановки
N чисел располагаются лексикографически (в словарном порядке). Это
значит, что перестановки сравниваются слева направо поэлементно.
Больше та, у которой раньше встретился элемент, больше соот-
ветствующего ему элемента во второй перестановке.(Например, если
S=(3,5,4,6,7),а L=(3,5,6,4,7), то S<L).
Принцип работы алгоритма разъясним на примере. Допустим, не-
обходимо воспpоизвести все перестановки цифр 3,4,5,6,7. Первой пе-
рестановкой считаем перестановку (3,4,5,6,7). Последней воспроиз-
водимой перестановкой будет (7,6,5,4,3).
Предположим, что на некотором шаге работы алгоритма получена
перестановка
P=(5,6,7,4,3).
Для того чтобы определить непосредственно следующую за ней пе-
рестановку, необходимо, пересматривая данную перестановку справа
налево, следить за тем, чтобы каждое следующее число было больше
предыдущего, и остановиться сразу же, как только это правило нару-
шится. Место останова указано стрелкой:
(5,6,7,4,3).
^
│
Затем вновь просматриваем пройденный путь ( справа налево ) до
тех пор, пока не дойдем до первого числа, которое уже больше отме-
ченного. Ниже место второго останова отмечено двойной стрелкой.
(5,6,7,4,3).
^ ^
│ ║
Поменяем местами отмеченные числа:
(5,7,6,4,3).
^ ^
║ │
Теперь в зоне, расположенной справа от двойной стрелки, упорядо-
чим все числа в порядке возрастания. Так как до сих пор они были
упорядочены по убыванию , то это легко сделать, перевернув указан-
ный отрезок. Получим:
Q=(5,7,3,4,6).
Q и есть та перестановка, которая должна воспроизводиться не-
посредственно после P.
Действительно, P<Q, так как, пересматривая эти перестановки
слева направо, (P(2)=6,Q(2)=7). Пусть существует такая перестановка
R, что P<R<Q. Тогда P(1)=R(1)=Q(1). По построению же Q(2) -- это
наименьшее во множестве Q\Q(1)={3,4,6,7} число, такое, что
Q(2)>P(2). Поэтому для R(2) верно одно из двух равенств: R(2)=Q(2)
или R(2)=P(2). Но так как в P элементы, начиная с P(3), убывают,
то из P<R следует, что если P(2)=R(2), то и P=R. Аналогично, так
как в Q элементы, начиная с Q(3), возрастают, то из R<Q следует,
что если R(2)=Q(2), то и R=Q.
Задача 2.
Заведем массив B[0..n] из (n+1) элемента. B[i]=0, если i-ый
элемент в подмножество не входит, и B[i]=1 иначе. Т.о. пустому
подмножеству будет соответствовать набор из n нулей, а n-элемент-
ному подмножеству - набор из n единиц. Тут явно заметна связь
подмножества с двоичным представлением числа.
Алгоритм: будем генерировать числа от 0 до 2^n-1, находить их
двоичное представление, и формировать подмножество из элементов с
индексами единичных битов в этом представлении.
Но число 2^n-1 может не поместиться в разрядную сетку машины.
Поэтому генерацию будем проводить, используя массив B:
Сначала B[i]=0 для всех i, что соответствует пустому подмно-
жеству.
Будем рассматривать массив B как запись двоичного числа
B[N]...B[1]B[0],
и моделировать операцию сложения этого числа с единицей. При сло-
жении будем просматривать число справа налево заменяя единичные
биты нулями до тех пор, пока не найдем нулевой бит, в который за-
несем 1. Генерация подмножеств заканчивается, как только B[N]=1
(предыдущая конфигурация была 1...1 = 2^n-1).
2
while B[N]<>0 do begin
i:=0; { индекс бита двоичного числа }
while (B[i]=1) do begin
B[i]:=0; { моделируем перенос в следующий разряд, }
i:=i+1 { возникающий при сложении }
end;
B[i]:=1;
{ Распечатываем индексы единичных элементов массива B --
новое сгенерированное подмножество }
For i:=0 to N-1 do
if B[i]=1 then write(i);
writeln; { переход на новую строку при печати }
end;
Задача 3.
Воспользуемся следующим алгоритмом генерации сочетаний по k
элементов из множества A:
В массиве B будут находиться индексы используемых на данном
шаге элементов из A (общее их число k). В качестве начальной кон-
фигурацией возьмем следующую: B[j]=j, j=1,...,k.
Ищем B[j] с максимальным индексом j такое, что
B[j]<n+j-k,
увеличиваем это B[j] на 1, а для всех m>j полагаем B[m]=B[m-1]+1
(B[j] растут с ростом j, и мы ищем и увеличиваем на 1 такое B[j] с
максимальным номером j, чтобы при заполнении возрастающими значе-
ниями элементов массива B[m], m>j, последний элемент B[k] не пре-
восходил бы n). Если такого B[j] не существует, то генерация соче-
таний для данного k закончена.
Задача 4.2.
Эта задача реализуется следующим рекурсивным алгоритмом по-
иска с возвращением (все слова набора A упорядочены по номерам):
а) Если строка пустая, то одна из возможных дешифровок найде-
на, иначе при разборе текста мы проверяем А[i] (при изменении i от
1 до n) на вхождение в начало дешифруемой в данный момент строки.
б) Если какое-то A[i] входит в строку как префикс, то запоми-
наем номер i этого слова, затем выделяем слово из строки, а с
остатком текста производим операцию разбора по пункту а).
Если ни одно из A[i] не входит в качестве префикса в дешифруе-
мую сейчас строку, то осуществляем возврат на пункт а), предвари-
тельно добавляя в начало строки последнее удаленное оттуда слово,
и пытаемся выделить из текста слово с большим номером в A. Если
возврат осуществить невозможно (т. к. мы находимся в начале исход-
ной строки), то алгоритм заканчивает свою работу. Все возможные
дешифровки найдены.
Задача 5.
Решается используя перебор с возвратом (Backtracking), изло-
женный в задаче 4.
Задача 6.
а) Всего может быть 4 арифметических операции - "+","-","*",
"/". Занумеруем их от 0 до 3. Вместо каждого из пяти знаков "?"
может стоять один из знаков операции. Заведем массив A из 5 целых
чисел, в i-ом элементе массива будет храниться код соответствующей
i-му знаку "?" операции, т.е. число от 0 до 3. Начальная конфигу-
рация - все элементы массива нулевые, конечная - все они равны 3.
Генерация очередной конфигурации знаков равносильна прибавлению
единицы в четверичной системе счисления, в которой разрешается
пользоваться только цифрами от 0 до 3 (подобный метод решения мы
уже встречали в задаче 2).
Приведем программный фрагмент генерации конфигураций.
Для удобства возьмем массив A не из 5, а из 6 элементов.
О получении последней конфигурации знаков будет свидетельствовать
появление 1 в шестом разряде (если к 33333 прибавить 1, то полу-
4
чим 100000 ).
4
for i:=1 to 6 do A[i]:=0;
while A[6]=0 do
begin
....
{ проверка, получили ли мы нужный результат }
....
i:=1;
while A[i]=3 do { Перенос в следующий разряд при }
begin { прибавлении единицы }
A[i]:=0;
i:=i+1;
end;
A[i]:=A[i]+1;
end;
Задача 7.
Можно воспользоваться вторым способом решения задачи 22 главы
"Разное" и написать рекурсивный алгоритм перечисления всех путей
из начальной вершины в конечную.
Задача 8.
Предложим простой способ построения всех разбиений числа
на слагаемые. Разбиения будут строится в порядке, обратном
лексикографическому. Очевидно, что первым разбиением в таком
порядке будет разбиение, содержащее одно слагаемое, равное , а
последним - разбиение из слагаемых, равных 1.
Как выглядит разбиение, следующее непосредственно за раз-
биением
n=с[1]+...+с[к] (1)
Будем искать разбиение,которое имеет самое большое число
начальных слагаемых, равных начальным слагаемым разбиения (1)
- обозначим эти слагаемые а[1],...,а[t-1] - и оставшиеся сла-
гаемые которого определяются разбиением, непосредственно сле-
дующим за разбиением
s=a[t]+a[t+1]+...+a[k].
Легко видеть, что эти условия однозначно определяют зна-
чение t
t=max{i:a[i]>1}.
Таким образом, задача свелась к нахождению разбиения,
непосредственно следующего за разбиением s=a[t]+1+...+1, где
a[t]>1, а количество единиц равно k-t.Таким разбиением явля-
ется разбиение s1=p+p+...+p+(s mod p), где p=a[t]-1.