7.7. Ответы на задачи

Контрольный вопрос 7.1: На последней итерации цикла a[i] станет 1 << 29, оно обработается, потом удваивается, становится равным 1 << 30, и происходит окончание цикла. Значение 1 << 30 не обрабатывается.

Задача 7.2: Исключить повторный вывод одного и того же решения можно, потребовав, чтобы слагаемые неубывали:

for j in range(31):
    if (1 << j) >= a[i-1]:

Задача 7.3: Проверить неповторяемость можно, проверяя, что элементы в массиве идут в неубывающем порядке — т.е. идея та же, что и ниже в основном тексте.

Задача 7.4: а) Понятно, что в \(find(i)\) бессмысленно ставить \(a[i]=n-1\), если только \(i\) не равно \(k-1\). Вообще, ясно, что не имеет смысла ставить \(a[i]>n-(k-i)\) (вроде так, может быть \(\pm1\), подумайте), т.к. элементов на оставшиеся места не хватит. Поэтому стоит делать цикл от \(a[i-1]+1\) до \(n-(k-i)\).

Задача 7.5: То же, что и для перестановок, только проверка на выход из рекурсии будет if i>k, а не if i>n.

Задача 7.8: б) Ну понятно: будем ставить ноль только при условии, что среди предыдущих \(k-1\) символов есть единицы. Для \(k=2\) это написать просто:

def find(i):
    if...
        check()
        return
    a[i] = 1
    find(i + 1)
    if a[i - 1] == 1:  # ставим ноль, только если предыдущий символ -- 1
        a[i] = 0
        find(i + 1)

только тут надо будет убедиться, что \(i > 0\), чтобы не обратиться к последнему элементу массива.

Для больших \(k\) можно писать цикл, который будет считать, на сколько нулей заканчивается текущая последовательность (только аккуратно с \(a[-1]\), \(a[-2]\) и т.д., чтобы последовательности могли начинаться с нулей) — попробуйте это написать!, — а можно это не считать каждый раз заново, а передавать в \(find\) дополнительным параметром:

def find(i, l):
    if...
        check()
        return
    a[i] = 1
    find(i, 0)  # на конце текущей последовательности единица, т.е. ноль нулей :)
    if l < k - 1:  # можно дописать еще один ноль
        a[i] = 0
        find(i + 1, l + 1)  # стало на один ноль больше

в главной программе тогда надо вызывать \(find(1, 0)\) и никаких проблем с \(a[0]\) и т.п.

в) Закономерность обсудим в теме “Динамическое программирование”.

Задача 7.9: Общий текст для пунктов а) и б) (как уже было отмечено в подсказках, процедура \(find\) почти не отличается для них); в части II вам будет предложено придумать отсечения здесь.

В соответствии с вариантом 1 из подсказок:

def find(i):  # выбираем i-е ребро паросочетания
    if i>=n:
        check()  # процедура check разная в вариантах а и б
        return
    # найдем первую свободную вершину
    for j in range(2*n):  # в графе 2*n вершин!
        if not was[j]:
            break
    # теперь j --- номер первой свободной (не входящей в паросочетание) вершины.
    # Добавим ее в паросочетание и будем искать парную к ней.
    was[j] = True
    for k in range(2*n):  # можно range(j+1, 2*n), т.к. до j-ой все точно спарены
        if not was[k]:  # тут хочется проверить наличие ребра, но пока мы считаем, что это делаем в check
            was[k] = True
            a[i] = (j, k)
            find(i+1)
            was[k] = False
    was[j] = False  # обратите внимание, что именно здесь!
    # или надо was[j]=0 внутри цикла, но тогда и was[j]=1 тоже!

В соответствии с вариантом 2 из подсказок:

def find(i):  # выбираем парную к i-й вершине
    if i >= 2*n:  # количество вершин в графе --- 2*n, а не n
        check()
        return
    if a[i] != -1:  # парная вершина уже выбрана, перебирать нечего
        find(i+1)
    else:  # надо перебрать все варианты
        for j in range(i+1, 2*n):  # i+1 --- т.к. все до i-ой уже точно спарены
            if a[j] == -1:
                # спарим i-ую и j-ую вершины
                a[i] = j
                a[j] = i
                find(i+1)
                a[i] = 0
                a[j] = 0  # !!!обязательно, т.к. иначе i-я и j-я будут считаться еще спаренными

Задача 7.10: Варианты а, б, в различаются только тем, что в в) достаточно потребовать, чтобы слагаемые строго возрастали, в б) — неубывали, а в а) это все не имеет значения.

Разберём вариант 1в): заведём глобальную переменную \(s\), в которой храним текущую сумму.

def find(i):
    global s
    if i == k then
        check()
        return
    for j in range(a[i-1]+1, n-s+1):  # слагаемое должно быть больше предыдущего, но явно не больше, чем n-s
        a[i] = j
        s = s + j
        find(i + 1)
        s = s - j  # откатываем изменения !!!

Обратите внимание, что в процедуре \(check\) придётся проверять, что \(s=n\).

Варианты 1б и 1в отличаются только нижней границей цикла: \(a[i-1]\) и \(1\) соответственно.

Вариант 2 отличается, в первую очередь, условием выхода из рекурсии. Тут несложно видеть, что условие выхода из рекурсии будет if s==n, и в \(check\) проверять ничего не придётся.

Можно писать и по-другому, не вводя переменную \(s\), а в процедуру \(check\) передавая оставшуюся сумму \(rem\); теперь процедура \(find\) будет иметь смысл «разложить число \(rem\) на слагаемые» с какими-нибудь условиями. Например для 2а:

def find(i, rem):
    if rem == 0:  # если rem=0, то мы разложили уже всё N, т.е. нашли решение
        check()
        return
    for j in range(a[i-1]+1, rem+1):
        a[i] =j
        find(i + 1, rem - a[i])  # осталось разложить rem-a[i]

Можно в \(find\) передавать и текущую сумму, и т.д. — как вам приятнее.

Задача 7.11: Разберём в разделе Отсечения в задачах на оптимизацию.

Задача 7.12: Обсудим в разделе Пример на отсечения при подсчёте количества объектов.

Задача 7.13: Элементарно :) передаём \(s\)

procedure find(i:integer;s:integer);
var j:integer;
begin
if ....
end;
if s>=n then
   exit;
for j:=0 to 30 do  begin
    a[i]:=1 shl j;
    find(i+1,s+a[i]);
end;
end;

соответственно в главной программе вызываем \(find(1,0)\);

или передаём \(nn=n-s\)

procedure find(i:integer;nn:integer);
var j:integer;
begin
if ....
end;
if nn<=0 then
   exit;
for j:=0 to 30 do begin
    a[i]:=1 shl j;
    find(i+1,nn-a[i]);
end;
end;

Обратите внимание, что здесь \(find\) в главной программе вызываем \(find(1,n)\).

Задача 7.15: Ну, собственно, все в тексте было сказано.

procedure find;
var j:integer;
    ocur:...
    ob:..
begin
if nn=2 then begin
   check;
   exit;
end;
ocur:=cur;
ob:=b;
for j:=2 to nn-1 do begin
    cur:=cur+b[j]*(b[j-1]+b[j+1]);
    delete(j);
    find;
    b:=ob;
    cur:=ocur;
end;
end;

например (или через \(insert\) и не хранить \(ob\) и \(ocur\)).

Суть в осознании программы «с нуля». Действительно, что делает эта программа. Здесь процедура \(find\) по заданной в массиве \(b\) последовательности просто перебирает все варианты удаления этих чисел. Как она это делает? Если удалять нечего, то просто проверяем. Иначе перебираем, какое число будем удалять первым, удаляем его и вызовом \(find\) переберём все варианты удаления оставшихся чисел. Процедура \(find\) тут почти никак не учитывает предысторию, она просто смотрит на текущую позицию и думает, что бы с нею сделать…Может быть, это осознать даже проще, чем все мои рассуждения в части про перебор окончаний решений.

Задача 7.16: Я предпочитаю хранить списки в динамической памяти; может быть, вам приятнее хранить их в массиве record’ов или в нескольких массивах.

type pnode=^tnode;
     tnode=record prev,next:pnode; val:integer; end;
     {предыдущий и следующий элементы и значение}
var head:pnode {голова списка}

procedure find(i:integer);
var j:integer;
    ocur:...
    p:pnode;
begin
if nn=2 then begin
   check;
   exit;
end;
ocur:=cur;
p:=head^.next; {начинаем со второго элемента в списке}
j:=2;
while p^.next<>nil do begin
        {пока не дошли до конца списка;
        обратите внимание, что последний
        элемент списка не рассматриваем!}
    a[i]:=j;
    cur:=cur+p^.val*(p^.prev^.val+p^.next^.val);
    p^.prev^.next:=p^.next;
    p^.next^.prev:=p^.prev;  {удалили элемент p из списка}
    find(i+1);
    cur:=ocur;
    p^.prev^.next:=p;
    p^.next^.prev:=p;  {вставили его назад}
    p:=p^.next; {перешли к следующему}
    inc(j);
end;
end;

Обратите внимание на то, что элемент удаляется из списка, но не из памяти. Его адрес остаётся в переменной \(p\), благодаря чему мы можем его восстановить назад (в этом смысле роль переменной \(p\) в некотором смысле похоже на роль переменной \(x\) в первоначальной версии реализации). Обычно вставка элемента в список делается немного хитрее, здесь же мы воспользовались тем, что этот элемент там только что был и мы его просто возвращаем на место.

За счёт связных списков мы смогли избежать циклов в процедурах \(insert\) и \(delete\), что должно сильно (порядка в \(N\) раз) ускорить программу. Но, как уже говорилось, это не имеет отношения к перебору, а только к тому, что, если вы хотите вставлять/удалять элементы в произвольное место, то лучше использовать список, а не массив.

Кроме того, обратите внимание на переменную \(j\). Ею мы просто считаем элементы списка, чтобы знать, что записать в массив \(a\).

Задача 7.17: Собственно, все просто.

Если поддерживать сумму чисел:

var s:...
procedure find(i:integer);
var j:integer;
    ocur:...
    ob:..
begin
if nn=2 then begin
   check;
   exit;
end;
if cur+2*s>=best then exit;
ocur:=cur;
ob:=b;
for j:=2 to nn-1 do begin
    a[i]:=j;
    cur:=cur+b[j]*(b[j-1]+b[j+1]);
    s:=s-b[j];
    delete(j);
    find(i+1);
    b:=ob;
    cur:=ocur;
    s:=s+b[j];{Не забываем ее восстанавливать}
end;
end;

Если вычислять каждый раз заново:

procedure find(i:integer);
var j:integer;
    ocur:...
    ob:..
    s:...
begin
if nn=2 then begin
   check;
   exit;
end;
s:=0;
for j:=2 to nn-1 do
    s:=s+b[j];
if cur+2*s>=best then exit;
ocur:=cur;
ob:=b;
for j:=2 to nn-1 do begin
    a[i]:=j;
    cur:=cur+b[j]*(b[j-1]+b[j+1]);
    s:=s-b[j];
    delete(j);
    find(i+1);
    b:=ob;
    cur:=ocur;
    s:=s+b[j];{Не забываем ее восстанавливать,
       т.к. она нам понадобится при следующем j}
end;
end;

Задача 7.18: Я думаю, напишите, ничего тут сложного нет.

Задача 7.19: Например, следующий тест:

2 1 100 1

Наш жадный алгоритм сначала удалит единицу со штрафом \(1\cdot (2+100)=102\), а потом будет вынужден удалять сотню со штрафом \(100\cdot (2+1)=300\). На самом же деле ясно, что сотню надо удалять, пока с ней соседствуют единицы, т.е. можно сначала удалить сотню со штрафом \(100\cdot (1+1)=200\), а потом единицу со штрафом \(1\cdot (2+1)=3\), получив намного меньший суммарный штраф.

Кстати, этот пример указывает на то, что наш алгоритм очень тупой. Ниже в основном тексте я говорю о других идеях «а-ля жадных» алгоритмов.

Задача 7.20: Ответ писать не буду, надо просто сделать то, что сказано в основном тексте: взять код перебора, который был раньше, и запустить жадность перед перебором.

Задача 7.21: Ответа тоже не будет.

Задача 7.22: Элементарно аналогично приведённому в тексте коду :)

procedure find(i:integer);
var j,k:integer;
    x:integer;
    was:array...
    minj:integer;
    min:integer;
begin
if nn=2 then begin
   check;
   exit;
end;
fillchar(was,sizeof(was),0);
for k:=2 to nn-1 do begin
    min:=inf;  {бесконечность}
    for j:=2 to nn-1 do
        if (was[j]=0)and(b[j]*(b[j-1]+b[j+1])<min) then begin
           min:=b[j]*(b[j-1]+b[j+1]);
           minj:=j;
        end;
    was[minj]:=1;
    a[i]:=minj;
    cur:=cur+b[minj]*(b[minj-1]+b[minj+1]);
    x:=delete(minj);
    find(i+1);
    insert(minj,x);
    cur:=cur-b[minj]*(b[minj-1]+b[minj+1]);
end;
end;

Задача 7.23: Программу писать не буду, пишите сами.