Часть работы программиста состоит в том, чтобы решать сегодняшние задачи. Другая, возможно, более важная, состоит в подготовке к решению завтрашних задач. Иногда подготовка заключается в прохождении курсов или чтении книг вроде трудов Кнута. Но чаще программисты учатся самостоятельно. Попробуем сделать это сейчас — исследуем пространство возможных решений этой задачи.
Рассказав о задаче на семинаре в Вестпойнтском училище, я попросил предложить лучший подход (по сравнению с исходным — вводить 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 Комментариев ·
3627 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.