|
Решение задачи 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 до 2n-1, находить их двоичное представление, и формировать подмножество из элементов с индексами единичных битов в этом представлении.
Но число 2n-1 может не поместиться в разрядную сетку машины. Поэтому генерацию будем проводить, используя массив B:
Сначала B[i]=0 для всех i, что соответствует пустому подмножеству.
Будем рассматривать массив B как запись двоичного числа
B[N]...B[1]B[0],
и моделировать операцию сложения этого числа с единицей. При сложении будем просматривать число справа налево заменяя единичные биты нулями до тех пор, пока не найдем нулевой бит, в который занесем 1. Генерация подмножеств заканчивается, как только B[N]=1
(предыдущая конфигурация была 1...12 = 2n-1).
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 в шестом разряде (если к 333334 прибавить 1, то получим 1000004 ).
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.
[Назад]
|
