7.5. Все задачи

Контрольный вопрос 7.1: Видите, почему?

Задача 7.2: Напишите эту программу (собственно, я надеюсь, что и предыдущие программы вы написали). Потестите её (обратите внимание, что тут время работы от \(n\) не зависит, только от \(k\), потому имеет смысл брать и большие \(n\)). Кроме того, заметьте, что одно и то же решение выводится несколько раз, отличаясь перестановкой слагаемых. Придумайте, как это исправить (может быть, вам поможет сначала почитать следующий пример, но лучше подумайте сначала, не читая примера дальше).

Задача 7.3: Можно, конечно, это проверять в процедуре \(check\). Т.е. процедура \(find\) будет фактически работать по предыдущему примеру, а процедура \(check\) будет отбирать то, что нужно. Напишите такую программу. Обратите внимание на то, чтобы не брать одно и то же сочетание несколько раз.

Задача 7.4: а) Напишите эту программу. Обратите внимание на подготовку вызова \(find(0)\); проверьте, что перебираются действительно все сочетания (например, выводя их в файл и проверяя при маленьких \(n\) и \(k\)).

б) Добавьте в программу код, который выводит (на экран или в файл) «лог» работы рекурсии (например, выводя при присвоении \(a[i]=j\) на экран строку a[i]=j (с конкретными значениями i и j, т.е. print("a[", i, "]=", j)), сдвинутую на \(i\) пробелов от левого края строки: вам этот вывод покажет, что на самом деле делает программа и пояснит предыдущий абзац); этот «лог» лучше выводить вперемешку с найденными решениями, чтобы видеть, какая ветка рекурсии чем закончилась. (Вообще, такой «лог» — очень полезная вещь при отладке программ с перебором.) Подумайте над тем, как исправить то, что описано в предыдущем абзаце, т.е. как сделать так, чтобы каждая ветка рекурсии заканчивалась нахождением решения.

Задача 7.5: Напишите программу перебора всех \(A_n^k\) — всех размещений из \(n\) по \(k\) (в них, в отличии от \(C_n^k\), порядок важен).

Задача 7.6: (Сложное) Напишите эту программу полностью и доведите ее до такого состояния, чтобы можно было играть с компьютером в крестики-нолики.

Задача 7.7: (Задача «резисторы») Радиолюбитель Петя решил собрать детекторный приемник. Для этого ему понадобился конденсатор емкостью \(C\) мкФ. В распоряжении Пети есть набор из \(n\) конденсаторов, емкости которых равны \(c_1\), \(c_2\), …, \(c_n\), соответственно. Петя помнит, как вычисляется емкость параллельного соединения двух конденсаторов (\(C_{new} = C_1 + C_2\)) и последовательного соединения двух конденсаторов (\(C_{new} = C1\cdot C2/(C1+C2)\)). Петя хочет спаять некоторую последовательно-параллельную схему из имеющегося набора конденсаторов, такую, что ее емкость ближе всего к искомой (то есть абсолютная величина разности значений минимальна). Разумеется, Петя не обязан использовать для изготовления схемы все конденсаторы.

Напомним определение последовательно-параллельной схемы. Схема, составленная из одного конденсатора, – последовательно-параллельная схема. Любая схема, полученная последовательным соединением двух последовательно-параллельных схем, – последовательно-параллельная, а также любая схема, полученная параллельным соединением двух последовательно-параллельных схем, – последовательно-параллельная. Обратите внимание, что это определение не допускает произвольные схемы, а только полученные именно последовательностью параллельных или последовательных соединений.

Задача 7.8: Напишите программу перебора всех последовательностей длины \(n\), состоящих из нулей и единиц, в которых не встречается \(k\) нулей подряд. (Например, при \(k=2\) и \(n=3\) это будут последовательности 010, 011, 101, 110 и 111). Основной задачей программы будет посчитать, сколько таких последовательностей всего, но имеет смысл выводить их на экран (или в файл) для проверки.

а) Напишите эту программу, модифицировав пример 1, т.е перебирая все последовательности из 0 и 1 длины \(n\), и проверяя, что последовательность «правильная», только в процедуре \(check\).

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

в) (дополнительный пункт, не имеющий отношения к перебору) Если вы раньше не сталкивались с такой задачей, то попробуйте найти несложную закономерность ответов при фиксированном \(k\) (т.е. сначала посмотрите на ответы на задачу при \(k=2\) и найдите в них закономерность, потом поищите закономерность при \(k=3\), потом при \(k=4\) и т.д.) Кстати, не забудьте, что тестить имеет смысл и очевидный случай \(k=1\) :)

Задача 7.9: Паросочетание в произвольном графе. Рассмотрим граф с \(2N\) (т.е. чётным) количеством вершин. Паросочетанием в нем назовём набор из \(N\) рёбер, у которых все концы различны (т.е. каждая вершина соединена ровно с одной другой: разбиение вершин на пары). [В олимпиадном программировании обычно рассматривается только паросочетание в двудольном графе, т.к. там есть простой эффективный алгоритм. Но у нас граф будет произвольным и мы будем решать задачу перебором]. [Т.е. смысл этой задачи на самом деле — чтобы вы умели перебирать все разбиения на пары]

а) Напишите программу, которая будет перебирать все разбиения вершин на пары и проверять, является ли такое разбиение паросочетанием (т.е. все ли нужные ребра присутствуют в нашем графе).

б) Считая, что граф полный и взвешенный, напишите программу, которая найдёт паросочетание наименьшего веса.

Задача 7.10: Напишите программу перебора всех разложений числа \(N\) на натуральные слагаемые.

Вариант 1: ровно на \(k\) слагаемых

а) считая, что слагаемые могут повторяться и что порядок слагаемых важен (т.е. что \(2+1\) и \(1+2\) — это разные решения);

б) считая, что порядок слагаемых не важен, т.е. выводя только одно разложение из разложений \(2+1\) и \(1+2\), при этом допуская одинаковые слагаемые;

в) считая, что все слагаемые должны быть различны, при этом порядок слагаемых не важен.

Вариант 2: на сколько угодно слагаемых в тех же трёх подвариантах (а, б и в)

Написав программы, прежде чем тестировать их, ответьте в уме на такой вопрос: ваша (уже написанная!) программа в варианте «а» будет при \(n=3\) выводить решения \(1+2\) и \(2+1\). А при \(n=2\) она будет выводить \(1+1\) один раз или два раза (во второй раз как будто переставив единички)?

Задача 7.11: Задача «Числа». Дана последовательность из \(N\) чисел. За одно действие разрешается удалить любое число (кроме крайних), заплатив за это штраф, равный произведению этого числа на сумму двух его соседей. Требуется удалить все числа (кроме двух крайних) с минимальным суммарным штрафом.

У этой задачи есть (не самое тривиальное) динамическое решение, но напишите переборное решение. Тут надо перебрать все варианты удаления чисел и выбирать из них тот, который даст минимальный штраф.

Задача 7.12: (Какая-то довольно искусственная задача, но хорошо подходит для иллюстрации одной из идей далее). Посчитать количество последовательностей из \(m\) нулей и \(n\) единиц, удовлетворяющих следующих условиям. Первое условие: никакие две единицы не должны стоять рядом. Таким образом единицы делят последовательность на несколько групп из подряд идущих нулей. Второе условие: количество нулей в последовательных группах должно неубывать, и при этом в соседних группах должно отличаться не более чем на 1. Эта задача имеет динамическое решение, но напишите перебор.

Задача 7.13: Переделайте эту программу, чтобы не хранить глобальную переменную \(s\), а передавать \(s\) (или \(n-s\), т.е. оставшееся число) через параметр процедуры.

Задача 7.14: (Творческое) Попробуйте придумать, как бы написать программу, чтобы не нужно было выделять \(i=1\) в особый случай. Это не очень тривиально, и есть несколько вариантов, как это сделать.

Задача 7.15: Напишите программу без массива \(a\) и переменной \(i\). Попробуйте её осознать «с нуля».

Задача 7.16: Напишите эту программу, работая со связными списками.

Задача 7.17: Напишите оба этих варианта программы: с хранением суммы в отдельной переменной или с вычислением каждый раз заново.

Задача 7.18: Придумайте отсечения к задаче о паросочетании в произвольном графе, в обоих вариантах: а и б). Напишите полную программу.

Задача 7.19: Приведите пример, когда этот алгоритм находит неоптимальное решение.

Задача 7.20: Напишите эту программу полностью. Сравните её эффективность с программой без предварительного жадного поиска решения.

Задача 7.21: Напишите задачу про удаление чисел со всеми четырьмя обсуждавшимися тут эвристиками. Может быть, вы придумаете ещё эвристики к ней?

Задача 7.22: Напишите такую программу.

Задача 7.23: Придумайте эвристики до перебора и во время перебора к задаче о паросочетании в произвольном графе (в обоих вариантах: а и б). Напишите полную программу.