Я верю, что моя реализация двоичного поиска па языке С верпа. Почему? Я аккуратно написал псевдокод на подходящем языке, затем воспользовался аналитическими методами для его верификации. Я перевел программу с псевдокода на С строку за строкой и проверил ее работу на различных вариантах входных данных и наблюдал выводимые результаты. Я добавил в ее текст утверждения, чтобы убедиться, что реальная ее работа совпадает с теоретически ожидаемой. Компьютер тоже внес свой вклад, проверив программу огромным количеством тестов. Наконец, простейшие эксперименты показали, что время ее выполнения растет именно так, как и должно.
Теперь я могу спокойно использовать написанную мной функцию двоичного поиска в заранее отсортированном массиве в большой программе. Я был бы сильно удивлен, если бы в логике программы нашелся какой-нибудь изъян. Правда, меня не удивило бы появление других ошибок. Не забыл ли вызвавший функцию отсортировать массив? Действительно ли должно возвращаться значение -1, если элемента в массиве пет? Если искомый объект содержится в массиве в нескольких экземплярах, какой именно нужен пользователю? И так далее, и тому подобное.
Можете ли вы доверять этой программе? Можете на меня положиться. Можете скачать коиию программы с сайта этой книги (http://netlib.bell-labs.com/cm/cs/ pearls/). В нее включены все функции, которые мы уже видели, и несколько вариантов двоичного поиска, рассматриваемых /далее в главе 9. Функция main этой программы выглядит следующим образом:
int та 1n(void)
{ /* probel () ; */
/* test(25), */ ti medn ver () , return 0,}
Закомментировав все вызовы, кроме одного, вы можете работать с конкретными вариантами входных данных, проверять программу тестовыми массивами и измерять время ее работы.
Опубликовал vovan666
April 16 2013 23:58:46 ·
0 Комментариев ·
3210 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.