Часть работы программиста состоит в том, чтобы решать сегодняшние задачи. Другая, возможно, более важная, состоит в подготовке к решению завтрашних задач. Иногда подготовка заключается в прохождении курсов или чтении книг вроде трудов Кнута. Но чаще программисты учатся самостоятельно. Попробуем сделать это сейчас — исследуем пространство возможных решений этой задачи.
Рассказав о задаче на семинаре в Вестпойнтском училище, я попросил предложить лучший подход (по сравнению с исходным — вводить 200 названий вручную). Один из курсантов предложил скопировать исходный список, разрезать его с помощью машинки для нарезки бумаги, перемешать кусочки в коробке и вытащить наугад требуемое их количество. Этот кадет продемонстрировал пример «концептуального прорыва», описанного в книге Адамса, цитируемой в разделе 1.7
Теперь мы займемся исключительно программой, позволяющей получить m упорядоченных случайных целых чисел из диапазона О..п-l. Начнем мы с исследования программы 12.1. Идея алгоритма прямолинейна, программа короткая, памяти используется совсем мало, а время выполнения отлично подходит для данного приложения. Однако это время выполнения пропорционально п, что может быть недопустимо для каких-либо других приложений. Имеет смысл потратить несколько минут на поиск другого решения той же задачи. Прежде чем продолжить свое ознакомление с данной главой, набросайте как можно больше схем алгоритмов высокого уровня, не заботясь о деталях реализации.
Одно из возможных решений состоит в помещении случайных целых чисел в изначально пустой набор до тех пор, пока в нем есть место. На псевдокоде он может быть записан так:
инициализация набора S пустым множеством
size = О
whi1е size < m do t = bigrand() % n
if t is not in S /* t не принадлежит S */
insert t into S /* вставка элемента в набор */ si ze++
вывод элементов S в порядке возрастания
В этом алгоритме нет выделенных элементов, поэтому результат его работы оказывается вполне случайным. Однако остается проблема реализации набора S. Подумайте о том, какая структура данных могла бы для этого использоваться.
Раньше мне пришлось бы поразмыслить о сравнительных характеристиках отсортированных связных списков, двоичных деревьях и других возможных структурах данных. Сегодня у меня есть возможность воспользоваться чужим трудом, вложенным в стандартную библиотеку шаблонов C++, и назвать набор набором (set).
Опубликовал vovan666
April 17 2013 00:02:57 ·
0 Комментариев ·
3670 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
