Продолжим решать задачу из предыдущей главы: нам нужно было получить упорядоченную последовательность m случайных чисел из диапазона [0, макс.), причем выбор осуществляется без возврата (одинаковых чисел быть не может). Итак, задача состоит в том, чтобы реализовать следующий псевдокод:
Листинг 13.1. Псевдокод программы-генератора случайной выборки
initialize set S to empty
/* инициализация набора S пустым множеством */
size = О
whi1е size < m do
t = bigrand() % maxva1
if t is not in S /* элемента t еще нет в S */
insert t into S /* добавить элемент t в набор S */ size++
вывод элементов S в порядке возрастания
Назовем нашу структуру данных IntSet (набор целых чисел). Объявим ее как класс C++ со следующими экспортируемыми членами:
Листинг 13.2. Определение структуры для хранения набора целых чисел
class IntSet Imp { public
IntSetImp(int maxelements, int maxval), void i nsert(lnt t) ; int size() , void report(int *v ) ,
} :
Конструктор IntSetlmp инициализирует структуру пустым множеством. У функции имеется два аргумента, задающих максимальное количество элементов в наборе и максимальное значение элемента. В зависимости от реализации эти параметры могут игнорироваться. Функция insert добавляет новое целое число в набор, если оно там отсутствовало. Функция size возвращает текущее количество элементов в наборе, а функция report выводит эти элементы в порядке возрастания в массив V.
Этот короткий интерфейс подходит исключительно для обучения программированию. Ему недостает множества компонентов, необходимых для реального использования этого интерфейса, например обработки ошибок и деструктора. Опытный программист на C++ воспользовался бы абстрактным классом с виртуальными функциями, а потом бы наследовал его в своих реализациях. Мы пойдем более простым (а иногда и более эффективным путем) и будем использовать имена типа IntSetArr для реализации массива, IntSetList для реализации списка и так далее. Для произвольной реализации будет использоваться имя IntSetlmp.
Приведенный в листинге 13.3 код использует описанную в листинге 13.2 структуру для формирования упорядоченного набора случайных целых чисел.
Опубликовал vovan666
April 17 2013 00:03:13 ·
0 Комментариев ·
3000 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
