7.6. Подсказки к задачам

Контрольный вопрос 7.1: Посмотрите, как будет заканчиваться цикл while.

Задача 7.4: а) Подумайте, почему некоторые ветки не находят решения и как это исправить.

Задача 7.8: б) Можно дописывать ноль, только если текущая последовательность заканчивается меньше, чем на \(k-1\) нулей. Можно каждый раз считать заново, на сколько нулей заканчивается текущая последовательность, а можно передавать в \(find\) дополнительный параметр — сколько нулей стоят в конце текущей последовательности. Попробуйте написать оба способа.

Задача 7.9: На самом деле вариант а) отличается от варианта б) только процедурой \(check\) и возможными отсечениями (см. раздел Отсечения). Основное в процедуре \(find\) у них одно и то же: перебор всех разбиений \(N\) объектов на пары. Пожалуй, основной нетривиальностью, над которой придётся подумать, тут будет то, что в \(find(i)\) может оказаться, что \(i\)-я вершина уже с кем-нибудь спарена. Можно предложить два варианта решения проблемы:

1. Можно в массиве хранить список выбранных рёбер (!): он тогда будет массивом пар чисел. Переменная \(i\) в \(find\) будет указывать, какое ребро мы хотим выбрать (в смысле, \(i=0\) значит, что мы ещё не выбрали ни одного ребра, \(i=1\) — что выбрали одно и т.д.).

В процедуре \(find\) теперь ищем первую вершину, которая ещё не «спарена», т.е. не является концом ни одного из взятых ещё рёбер, её обязательно берём, и перебираем ей пару. Для того, чтобы не тратить время на проверку, «спарена» ли вершина, можно завести массив \(was\), в котором отмечать, спарены ли вершины (и не забывать откатывать!)

Это решение довольно прямо идёт по естественной идеологии перебора: нам надо выбрать \(N\) рёбер — так и будем их последовательно выбирать, записывая номера выбранных в массив \(a\).

2. Но можно делать и, как мне кажется, проще. Можно в массиве \(a\) хранить номер «парной» вершины к данной вершине: т.е. \(a[i]\) — номер вершины, парной к \(i\), или -1, если вершина пока ещё не спарена. В частности, для уже спаренных вершин обязательно должно быть \(a[a[i]]==i\). Процедура \(find(i)\) будет перебирать пары к \(i\)-ой вершине. А именно, если она уже с кем-то спарена, то перебирать нечего, иначе перебираем все свободные вершины в качестве пары. Массив \(was\) тут не нужен, т.к. «спаренность» вершины можно проверять, проверяя \(a[i]==-1\). Обратите особое внимание на то, что здесь придётся откатывать изменения в массиве \(a\)! — это довольно редкий случай, но вот вам пример, когда это действительно нужно.

Задача 7.10: Можно ввести дополнительную глобальную переменную, в которой хранить текущую сумму слагаемых, в процедуре \(find\) увеличивать её на то слагаемое, которое поставили, и не забывать потом вернуть назад. Можно поступить по-другому: передавать в процедуру \(find\) дополнительный параметр, который обозначает, сколько ещё осталось разложить (т.е. N - (сумма уже выбранных слагаемых)). При этом тогда очередное слагаемое будет ограничено сверху значением этого параметра. Вариант 2: подумайте, какое должно быть условие выхода из рекурсии.

Задача 7.11: В массиве \(a\) будем хранить последовательность удалений (на самом деле, тут нам массив \(a\) практически не будет нужен). Стоит (в добавок к массиву \(a\)) хранить ещё один глобальный массив, в котором будет храниться текущее состояние чисел, и ещё глобальную переменную — текущий штраф. При удаление очередного числа надо откорректировать глобальный массив, удалив из него это число (и сдвинув другие числа), а также изменить текущий штраф. Не забудьте все отыгрывать назад.

Но более продвинутый вариант — хранить текущее состояние чисел связным списком, а не массивом, тогда удалять и добавлять элементы просто.

Задача 7.12: Простую программу перебора написать несложно, только лучше перебирать не последовательности из нулей и единиц, а сразу способы разбиения \(m\) нулей на данное количество групп. Т.е. написать функцию \(count(g,m)\), которая будет считать число способов разбиения \(m\) нулей на \(g\) групп с учётом второго условия, а в ответ выводить \(count(n-1,m)+2\cdot count(n,m)+count(n+1,m)\), поскольку возможны четыре варианта:

1. Первый и последний символы искомой последовательности — единицы, тогда групп нулей у нас \(n-1\) и потому таких последовательностей \(count(n-1,m)\).

2. Первый символ — единица, последний — ноль, тогда групп нулей \(n\) и таких последовательностей \(count(n,m)\).

3. Первый символ — ноль, последний — единица, тогда групп нулей \(n\) и таких последовательностей опять-таки \(count(n,m)\).

4. Первый и последний символы — ноли, тогда групп нулей \(n+1\) и таких последовательностей \(count(n+1,m)\).

Функция же \(count\) будет инициализировать и запускать перебор нужных разбиений (т.е. и будет той «главной программой», откуда мы запускаем \(find(0)\)). Массив \(a\) будет хранить количество нулей в очередной группе. Можно проверять отличие соседних групп на 1 только в \(check\), а можно и по ходу перебора.

Но интереснее постараться сделать так, чтобы (почти) все ветки заканчивались нахождением решения. Для этого надо, во-первых, сразу в переборе перебирать только те разбиения, где количества нулей в соседних группах или равно, или отличается на единицу, а во-вторых, проверять, хватит ли нам нулей на оставшиеся группы; это мы ещё будем обсуждать в разделе Пример на отсечения при подсчёте количества объектов.

Задача 7.14: Я вижу как минимум два варианта; в обоих для вычисления ответа при данных \(nn\) и \(m\) придётся запускать процедуру \(find\) несколько раз. Во-первых, можно в массиве \(a\) устанавливать нулевой элемент, типа того: в процедуре \(count\):

ans:=0;
nn:=n;
if n>0 then begin
   for i:=1 to nn do begin
       a[0]:=i;
       find(1,m);
   end;
count:=ans;

Можно передавать в процедуру \(find\) параметр, указывающий предыдущее число; в \(count\) опять потребуется цикл.

В обоих случаях появляется ещё проблема с тем, что некоторые решения будут считаться дважды (решения, начинающиеся на 3, будут считаться при \(a[0]=2\) и \(a[0]=3\)). Можете подумать, что с этим делать.

В общем, ответа на это задание я не привожу, если вы напишите что-нибудь, и оно будет правильно проходить тест 27 100 (на него ответ 94762), то круты :)

Задача 7.16: На самом деле это задание не на перебор, а на работу со связными списками. Процедура \(find\) останется той же, только теперь мы будем хранить текущую последовательность чисел не в массиве, а в списке (на массивах или в динамической памяти), т.к. так проще вставлять и удалять элементы.

Задача 7.18: В а) проверяйте наличие ребра — и больше сложно что-то придумать; в б) можно написать стандартное отсечение для задач оптимизации: сравнить текущий ответ с наилучшим. Придумайте в б) что-нибудь ещё! Например, к текущей сумме можно добавлять вес минимального оставшегося ребра, умноженный на количество рёбер, которые ещё надо добавить.

Задача 7.19: Проблема всех жадных решений в том, что, возможно, оптимальный первый шаг вынудит нас слишком много заплатить за последующие, при том, что неоптимальный первый шаг, возможно, позволил бы платить меньше. Соответственно, надо придумать тест, когда, выбрав минимальный штраф на первом ходу, на втором нам приходится платить очень много.

Задача 7.23: Ну, конечно, можно написать жадную эвристику: берём кратчайшее ребро, добавляем его в паросочетание. Берём следующее кратчайшее ребро, которое можно взять и добавляем и т.д. Попробуйте что-нибудь ещё придумать.