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: Программу писать не буду, пишите сами.