|
|
|
|
|
|
|
|
|
|
|
|
|
Д. Макилроем предложена иллюстрация циклического сдвига 10-эле-ментного массива на пять позиций с помощью переворотов ладоней. Начните, расположив ладони перед собой, левую над правой.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Программа реверсирования эффективна по времени, по памяти и настолько коротка и проста, что в ней довольно тяжело допустить ошибки. Это в точности та программа,которую использовали в своей книге Кер-ниган и Плоджер для редактора текста, которая стала работать правильно при первом же прогоне, в то время как их предыдущая программа для решения подобной задачи, в основе которой лежали списки со ссылками, содержала несколько ошибок. Эта программа использовалась в нескольких редакторах текста, в том числе в редакторе ED для операционной системы UNIX, с помощью которого я ввел с клавиатуры эту главу. К. Томпсон написал этот редактор и программу реверсирования в 1971 г. и утверждает, что она стала легендой,
|
|
|
|
|
|
|
|
2.4. СОБЕРЕМ ВСЕ ВМЕСТЕ (СОРТИРОВКА)
Обратимся теперь к задаче В. Дан словарь английских слов (по одному слову, набранному строчными буквами, на каждой строке входных данных), =1 мы должны найти все группы анаграмм. Для изучения этой задачи еаь ряд серьезных причин. Первая - техническая: ее решение является удачной комбинацией выработки правильного взгляда на задачу и выбора подходящих средств. Вторая причина существеннее: вам же не хочется оказаться единственным человеком на вечеринке, который не знает, что deposit, dopiest, posited и topside - анаграммы? А если этих причин недостаточно, то в задаче 6 будет описан подобный пример как следствие из прикладной задачи.
Есть несколько удивительно неэффективных и сложных способов решения данной задачи. Любой метод, в котором рассматриваются все перестановки букв в слове, обречен на неудачу. Для слова microphoto-graphic (анаграмма слова photomicrographic) существует 17! перестановок, а 17! * 3 х Ю . Даже допустив адскую скорость - 1 мкс на переста-
26
|
|
|
|
|
|
|
|
|
|
|
|
|
