Случайным образом выбираются два боба. Если они одного цвета, они выкидываются, а вместо них из кучи берется черный и кладется в банку. Если они разных цветов, белый боб возвращается в банку, а черный выбрасывается.
Докажите, что процесс сходится. Что вы можете сказать о цвете последнего оставшегося боба в зависимости от начального количества белых и черных бобов?
1. Мой коллега столкнулся со следующей задачей при написании программы, рисовавшей липни на растровом экране. Массив из п пар вещественных чисел (atbt) определял п линий вида у - atx + br Эти строки были упорядочены па интервале [ОД] в том смысле, что у[i] < у[i] + 1 для всех i между 0 и п-2 и всех значений х из отрезка [ОД] (рис. 4.2).
Рис. 4.2. Линии не имели общих точек на вертикальных прямых
Другими словами, линии не имели общих точек на вертикальных прямых (х = 0 и х = 1). Ему нужно было найти две линии, между которыми находилась произвольная точка с координатами (х, у), где х принадлежала отрезку [ОД]. Как можно быстро решить эту задачу?
8. Двоичный поиск работает принципиально быстрее последовательного. Для поиска в массиве из п элементов в двоичном поиске выполняется примерно log2 п сравнений, а для последовательного — в среднем п! 2. Хотя часто этого вполне достаточно, иногда приходится добиваться еще более высокого быстродействия. Если нельзя улучшить логарифмическую зависимость числа сравнений, можно ли переписать код так, чтобы он стал работать быстрее? Для определенности предположите, что вам нужно найти число в отсортированном массиве из п=1000 целых чисел.
9. В качестве упражнения в проверке программ попробуйте точно описать поведение на входе и выходе следующих программных блоков и покажите, что код соответствует требованиям. Первая программа реализует векторное сложение а = b + с.
0 - О
wh"lie i < п
a[i ] = b[1] + с[1]
1 =1 + 1
Этот и следующие два фрагмента используют цикл while вместо for i = [0, п). В следующем фрагменте вычисляется максимальное значение в массиве х.
max = х [ 0 ]
1 = 1
wh 11е 1<n do
if x[i] > max max = x[i]
i = i+l
Л эта программа последовательного поиска возвращает первое вхождение t в массив х[0..п-1].
i = О
wh11е 1<n && х[1] 1= t
i - i+l if i >= п р = -1
else
Р = i
Эта программа вычисляет n-ю степень числа х за время, пропорциональное логарифму п. Такую рекурсивную программу легко закодировать п проверить; итеративная версия достаточно сложна и предоставляется читателю в качестве дополнительного задания.
function ехр(х, п) рге п >= О post result = хЛп
i f n = О
return 1 else if even(n)
return square(exp(x . n/2))
else
return x*exp(x. n-1)
10. Добавьте ошибки в функцию двоичного поиска и посмотрите, сможете ли вы их обнаружить с помощью метода проверки и в чем они будут проявляться.
11. Напишите и докажите правильность рекурсивной функции двоичного поиска на языке С или C + + , причем функция должна соответствовать следующей декларации:
int biпаrysearch(DataTyре х[]. int п)
Используйте только одну эту функцию и не вызывайте никаких других.
Опубликовал vovan666
April 16 2013 23:58:21 ·
0 Комментариев ·
2994 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
