Task (Контрольная работа 2)

Задача о вагонах.

Имеется поезд, состоящий из 2n вагонов – n черных, и n белых, причем порядок вагонов может быть любым. Изначально поезд стоит на пути в пункте 1, и первый вагон может либо проехать прямо в пункт 2, либо свернуть в тупик, из которого потом можно будет выехать к пункту 2:

Надо в пункте 2 сформировать состав, в котором цвета вагонов чередуются.

Предложенный алгоритм.

Первый вагон едет прямо. Далее, повторяем до тех пор, пока в пункте 1 не кончатся вагоны: если цвета вагонов в пунктах 1 и 2 различны, то перегоняем вагон из пункта 1 в пункт 2, иначе, если в тупике есть вагоны и если цвета вагонов в тупике и в пункте 2 различны, то перегоняем вагон из тупика в пункт 2, иначе перегоняем вагон из пункта 1 в тупик.

Утверждение 1. Максимальное количество перегонок вагонов в предложенном алгоритме равно 3n-1.

Доказательство:

Очевидно, первый и последний вагоны проедут прямо, на это будет затрачено 2 операции. Далее, для каждого вагона, загнанного в тупик, существует вагон другого цвета, который проедет прямо, и за которым в пункт 2 сразу же проедет этот вагон из тупика. Итого, на такую пару будет потрачено 3 операции. В худшем случае все оставшиеся 2n-2 вагонов будут разбиты на такие пары. То есть в худшем случае, потребуется (2n-2)/2*3+2=3n-1 операций.

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

Утверждение 2. Если представить состав последовательностью нулей и единиц длины 2n, то для последовательности, начинающейся с нуля, количество затраченных операций будет равно 3n-k, где k – количество непрерывных подпоследовательностей единиц. Доказательство:

Очевидно, нам необходимо как минимум 2n операций – по одной на каждый вагон. Теперь посчитаем количество дополнительных операций, связанных с перегонкой некоторых из вагонов в тупик. Очевидно, на каждый вагон, стоящий не первым в непрерывной подпоследовательности единиц, будет затрачена одна дополнительная операция – мы либо загоним этот вагон в тупик, либо сначала выгоним из тупика вагон другого цвета, т.к. прогнать этот вагон прямо мы не можем. Очевидно, при этом мы учли все дополнительные операции. Всего вагонов, стоящих не первыми в непрерывных подпоследовательностях единиц, ровно n-k. Итого получаем 3n-k операций.

Утверждение 3. Количество последовательностей нулей и единиц длины 2n, начинающихся с нуля, в которых одинаковое количество нулей и единиц, и ровно k непрерывных подпоследовательностей единиц, равно .

Доказательство:

Рассмотрим все возможные перестановки из n-k нулей и k объектов вида 01*. Всего их . Здесь 1* – это некоторая последовательность единиц, длина которой больше нуля. Такие перестановки задают последовательности нулей и единиц, начинающиеся с нуля (т.к. в начале перестановки будет стоять либо 0, либо объект вида 01*, который также начинается с 0). Теперь нам осталось распределить оставшиеся n-k не занятых единиц по k последовательностям 1*. Это можно сделать способами. Итого получаем последовательностей нужного нам вида.

Из утверждения 3 и из того, что последовательностей из нулей и единиц длины 2n с одинаковым количеством нулей и единиц существует ровно , можно получить выражение для средней сложности нашего алгоритма:

Здесь 2n – базовая сложность; константа 2 перед частным появляется из того соображения, что до сих пор мы рассматривали только последовательности, начинающиеся с нуля, а все остальные необходимые нам последовательности можно получить их побитовым отрицанием.

Для упрощения этого выражения нам необходимо доказать еще одно утверждение:

Утверждение 4.

Доказательство:

Разобьем последовательность длины 2n-2 пополам. Тогда, если нам надо выбрать из нее n элементов, мы можем выбрать n-k элементов из первой половины способами, и k из второй половины .способами. Суммируя по всем k, получаем искомое выражение.

Тогда: