4-2 Недостающее число

Массив А[1. .га] содержит все целые числа от 0 до га, кроме одного. Чтобы найти пропущенное число, можно отмечать во вспомогательном массиве В [О . .га] все числа, встречающиеся в А, и затем посмотреть, какое число не отмечено (всё вместе требует времени О (га)). При этом использование элемента массива А в качестве индекса считается элементарной операцией.

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

Покажите, что и при таких ограничениях мы можем найти пропущенное число за время О (га).

4-3 Время передачи параметров

В этой книге мы предполагаем, что передача параметров занимает постоянное время, даже если передаваемый параметр - массив. В большинстве языков программирования это так и есть, поскольку передаётся не сам массив, а указатель на него. Но возможны и другие варианты. Сравним три способа передачи массивов в качестве параметров:

1.Массив передается как указатель за время 0(1).

2.Массив копируется за время Q(N), где N - размер массива.

3.В процедуру передаётся только та часть массива, которая будет в ней использоваться. При этом требуется время 0(g - р + 1), если передаётся участок А\р. .q].

а.Рассмотрим рекурсивный алгоритм двоичного поиска числа в упорядоченном массиве (упр. 1.3-5). Каково будет время его работы при каждом из указанных способов передачи параметра? (Аргументами рекурсивной процедуры являются искомый элемент и массив, в котором осуществляется поиск.)

б.Проведите такой анализ для алгоритма Merge-Sort из раздела 1.3.1.

4-4 Ещё несколько рекуррентных соотношений

Укажите возможно более точные асимптотические верхние и нижние оценки для Т(п) в каждом из указанных ниже примеров. Предполагается, что Т(п) - константа при га 8.

а. Т(п) = ЗГ(га/2) + га lgra.

Задачи к главе 4

73

б.Т(п) = ЗТ(га/3 + 5) + га/2.

в.ТЫ) = 2Г(та/2) + га/lgra.

г.Г(га) = Г(га - 1) + 1/га.

д.Г(га) = Г(га - 1) + lg га.

е.Г(га) = у/гаГ(у/га) + га.

4-5 Переход от степеней к произвольным аргументам

Пусть мы получили оценку для ТЫ) ПРИ всех га, являющихся степенями некоторого целого Ь. Как распространить её на произвольные га?

а.Пусть ТЫ) и h(n) - монотонно возрастающие функции, определённые для произвольных положительных аргументов (не обязательно целых), причём ТЫ) h(n) Для всех га, являющихся степенями целого числа Ь > 1. Пусть известно, кроме того, что h «растёт достаточно медленно»: h(n) = 0(h(n/b)) Докажите, что ТЫ) = 0(h(n)).

б.Пусть для функции Г выполнено соотношение ТЫ) = аТ(п/Ь) + f(n) ПРИ п > гао! пусть а 1, 6 > 1 и /(га) монотонно возрастает. Пусть ТЫ) монотонно возрастает при га гао, и при этом Г(гао) аТ(по/Ь) +/Ыо) Докажите, что ТЫ) монотонно возрастает.

в.Упростите доказательство теоремы 4.1 для случая монотонной и «достаточно медленно растущей» функции /(га). Воспользуйтесь леммой 4.4.

4-6 Числа Фибоначчи

Числа Фибоначчи определяются соотношением (2.13). Здесь мы рассмотрим некоторые их свойства. Для этого определим производящую функцию (generating function), определяемую как формальный степенной ряд (formal power series)

оо

Т = £ Ftzl = 0 + z + z2 + 2z3 + 3z4 + 5z5 + 8z6 + 13/ + ...

8 = 0

а.Покажите, что T(z) = z ~\~ zT(z) + z2T(z).

б.Покажите, что

Tlz)

1/1

1 - z - г2 (1 - <z) (1 - (pz) д/5 \ 1 - <£z 1 - (/5,2

где

1 + V5 ¥> == 1,61803...

и

£= 1 ~ = -0,61803...

Глава 4 Гекуррентные соотношения в. Покажите, что

оо

n*) = i-rW-?)z%

8 = 0

V5V

г.Докажите, что Fi при i > 0 равно ближайшему к <р>1 /\/Ъ целому числу. (Указание: \ф\ < 1.)

д.Докажите, что -F8+2 <~рг для всех г 0.

4-7 Тестирование микросхем

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

Ответ АОтвет ВРезультат

В исправнаА исправнаобе хорошие или обе плохие

В исправнаА неисправнахотя бы одна неисправна

В неисправнаА исправнахотя бы одна неисправна

В неисправнаА неисправнахотя бы одна неисправна

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

б.Пусть нужно найти хотя бы одну хорошую микросхему из га штук, из которых больше половины исправных. Покажите, что достаточно [га/2] попарных тестов, чтобы свести задачу к аналогичной задаче половинного размера.

в.Пусть исправно больше половины микросхем. Покажите, что можно найти все хорошие микросхемы за О (га) попарных тестов. (Воспользуйтесь рекуррентным соотношением.)

[Эту задачу можно переформулировать в иных терминах: имеется га одинаковых на вид предметов, но на самом деле они относятся к нескольким категориям. Есть прибор, который по двум предметам проверяет, одинаковы ли они. Известно, что предметы некоторой категории составляют большинство. Надо найти представитель этого большинства за О (га) сравнений. Помимо рекуррентного решения, эта задача имеет простое итеративное решение. Заведём коробку, в которой будем накапливать одинаковые предметы, а также урну, куда можно выкидывать предметы. Перекладываем непросмотренные элементы в коробку или урну, поддерживая такое свойство: среди невыкинутых искомые составляют большинство.]