1. Хотя наше доказательство правильности двоичного поиска было достаточно трудоемким, оно все еще не вполне закопчено. Как вы докажете, что программа не содержит ошибок времени выполнения (деление на ноль, переполнение, выход за границы диапазона или массива)? Если вы знакомы с дискретной математикой, можете ли вы формализовать доказательство в некоторой логической системе?
2. Если этот вариант двоичного поиска был для вас слишком прост, попробуйте возвращать в переменной р позицию первого вхождения t в массив х (если вхождений несколько, наш алгоритм возвращал произвольное вхождение). Ваш код должен быть логарифмическим по числу сравнений; задачу можно решить за log2п сравнений.
3. Напишите и проверьте рекурсивную программу двоичного поиска. Какие части кода и доказательства остаются неизменными по сравнению с итерационной версией, а какие меняются?
4. Добавьте вспомогательные переменные для определения количества сравнений и используйте методы проверки программ для доказательства того, что это количество действительно пропорционально логарифму размера массива.
5. Докажите, что программа завершает работу, если х — положительное целое число:
while х != 1 do if even(х) x = х/2
else
x = 3*x + 1
6. [С. Sholten] Дэвид Грис в своей книге «Наука программирования» (David Gries, Science of Programming) назвал эту задачу «Задачей о кофейной банке». Дается кофейная банка, в которой есть несколько черных бобов и несколько белых, и, кроме того, дается большая куча черных бобов. Затем следующий процесс выполняется до тех пор, пока в банке не останется один боб.
Опубликовал vovan666
April 16 2013 23:58:19 ·
0 Комментариев ·
3516 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
