Чтобы найти номер разработчика системы М. Леска (Mike Lesk), нужно было набрать номер LESK*M* (то есть 5375*6*), и система озвучивала его номер. Сейчас подобные службы распространены повсеместно. Проблема может возникнуть, если несколько имен имеют один и тот же код; когда такое случалось в системе Леска, его программа запрашивала у пользователя дополнительную информацию. Если дан большой список имен наподобие обычного телефонного справочника, как бы вы выделили подобные совпадения? Леек провел подобный эксперимент и выяснил, что количество совпадений составляло всего лишь 0,2%. Как бы вы реализовали функцию, возвращающую список имен, задаваемых кодом, подаваемым на ее вход?
1. В начале 60-х Вик Высоцкий (Vic Vissotski) работал с программистом, которому нужно было транспонировать матрицу 4000 на 4000 элементов, хранившуюся на магнитной ленте. Все записи имели один и тот же формат и были длиной порядка нескольких десятков байт. Первому варианту программы, который был предложен этим программистом, потребовалось бы около 50 часов на выполнение задачи. Как удалось Высоцкому уменьшить это время до получаса?
2. [J. Ullmam] Дан набор из п вещественных чисел, вещественное число t, целое k. Как можно быстро определить существование ^-элементного подна- бора, сумма элементов которого не превышает t?
3. Последовательный поиск выполняется медленно, но не требует предварительной обработки, тогда как двоичный поиск работает очень быстро, но требует наличия отсортированного набора. Сколько нужно выполнить двоичных поисков на поэлементном массиве, чтобы окупить время, затраченное на его предварительную сортировку?
Когда к Томасу Эдисону обратился очередной претендент на должность помощника, Эдисон предложил ему вычислить объем пустой колбы от лампочки. Через несколько часов вычислений с кронциркулем в руках претендент вернулся с результатом — 150 см\ После нескольких секунд вычислений Эдисон ответил «ближе к 155». Как он это сделал?
Опубликовал vovan666
April 16 2013 23:34:56 ·
0 Комментариев ·
3517 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
