ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем Подготовка входных данных Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем ОСНОВЫ ПРОГРАММИРОВАНИЯ

Псевдослучайные числа в языке СИ © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 2 В стандартной библиотеке языка Си предусмотрены две функции генерации случайных чисел: rand() и random(). Обе функции объявлены в файле stdlib.h: int rand(void); long int random(void); Случайные числа генерируются в диапазоне от 0 до RAND_MAX, где RAND_MAX – константа, определенная в заголовочном файле stdlib.h. Для определения значения константы RAND_MAX можно выполнить ее печать на экран: printf("RAND_MAX = %d\n", RAND_MAX); В общем случае функция random() генерирует более качественные случайные числа. Младшие биты случайных чисел, генерируемых функцией rand() будут в меньшей степени случайными по сравнению со старшими. Для функции random() гарантируется, что как старшие, так и младшие биты формируемых чисел в одинаковой степени будут случайными. В GNU LibC обе функции реализованы идентично.

Задание 1. Генерация случайных чисел © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 3 #include int main() { int rval, i, n; printf("Input number of random values: "); printf("sizeof(int)=%ld, RAND_MAX=%d\n", sizeof(int),RAND_MAX); scanf("%d",&n); for(i=0;i

Случайное зерно © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 4 Вычислительная техника является детерминированной, т.е. не обладает никакими элементами случайности. Числа, формируемые генераторами псевдослучайных чисел будут "случайными" относительно друг друга, но будут всегда одинаковыми относительно запусков программы. [Данное свойство эффективно используется при отладке программ]. Такое поведение связано с тем, что генераторы псевдослучайных чисел вычисляют следующее число, используя предыдущее. Для того, чтобы при каждом запуске программы случайные числа были различными необходимо по-разному инициализировать генератор. Для инициализации генератора в стандартной библиотеке предусмотрены функции : void srand(unsigned int seed); // для rand() void srandom(unsigned int seed); // для random() Параметр seed (англ. зерно) инициализирует генератора случайных чисел. В качестве него обычно используют текущее время. которое можно получить при помощи функции time(NULL).

Задание 2. Генерация различных наборов случайных чисел © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 5 1. На основе prog1 выполните реализацию prog1_s. В новой программе перед генерацией случайных чисел должен выполняться вызов функции srand(), при этом необходимо обеспечить возможность ввода значения seed с клавиатуры (аналогично параметру n). 2. Выполните 3 запуска модифицированной программы со значениями seed=1, 1024, Сравните результаты prog1 и prog1_s. 3. На основе программы prog1_s разработайте программу prog1_st, в которой для инициализации генератора случайных чисел будет использоваться текущее время, которое можно получить с использованием функции time() следующим образом: srand(time(NULL)); Сравните результаты prog1, prog1_s и prog1_st.

Алгоритм поиска с барьером в упорядоченной последовательности (средний случай) (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 6 a1a1 a2a2 anan... R R / (n+1) a1a1 anan... a2a2 a1a1 a2a2 anan 3. Точки сосредоточены в конце диапазона R 2. Точки равномерно распределены по диапазону R 1. Точки сосредоточены в начале диапазона R Рассмотрим 3 частных случая распределения элементов последовательности a по диапазону допустимых значений R В рамках практического занятия "Алгоритмы сортировки" был рассмотрен только случай 2, R / (n+1) = 100

Задание 3. Формирование входных данных класса 1. © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 7 Разработать программу beginrange_gen, генерирующую возрастающую последовательность a длины n. Элементы последовательности располагаются в начале диапазона R = 100n. Расстояние между элементами последовательности 10. Например, при n = 4, R = 100n = 400 может быть сформирована следующая последовательность: Расстояние между соседними точками формируется случайным образом с использованием функции random(). Для того, чтобы изменить диапазон значений генерируемых случайных чисел с [0, RAND_MAX] на [1, 10] использовать выражение "(r mod 10) + 1", где r – псевдослучайное, сгенерированное функцией random(). Выходные данные: файл, следующего формата: n R\n a 1 a 2 a 3 a 4 … a n \n

Задание 4. Формирование входных данных класса 3. © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 8 Разработать программу endrange_gen, генерирующую возрастающую последовательность длины n. Элементы последовательности располагаются в конце диапазона R = 100n. Расстояние между элементами последовательности 10. Например, при n = 4, R = 100n = 400 может быть сформирована следующая последовательность: Расстояние между соседними точками формируется случайным образом с использованием функции random(). Для того, чтобы изменить диапазон значений генерируемых случайных чисел с [0, RAND_MAX] на [1, 10] использовать выражение "(r mod 10) + 1", где r – псевдослучайное, сгенерированное функцией random(). Выходные данные аналогично заданию 3.

Задание 5. Формирование входных данных класса 2. © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 9 В рамках практической работы "Алгоритмы сортировки" рассматривались только последовательности, в которых числа шли с одинаковым шагом R / (n+1) = 100, следовательно, R = 100n. На практике входные данные, соответствующие классу 2 не будут так равномерно распределены. Разработать программу unirange_gen генерации входных данных, соответствующие классу 2. На вход программы поступает количество чисел n и среднее расстояние d между точками. Значение R принимается равным nd. Расстояние между соседними точками формируется случайным образом с использованием функции random(). Для того, чтобы изменить диапазон значений генерируемых случайных чисел с [0, RAND_MAX] на [1, 10] использовать выражение "(r mod 10) + 1", где r – псевдослучайное, сгенерированное функцией random(). Выходные данные аналогично заданию 3. R / (n+1) a1a1 anan... a2a2

Генерация случайных последовательностей © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 10 В рассмотренных ранее задачах последовательности формировались с использованием случайных чисел, однако обладали заранее известнывми свойствами: были упорядочены. Генерация случайных последовательностей, в которых числа не повторяются и располагаются в произвольном порядке является более сложной. При использовании функции random() расстояние между случайными числами с одинаковым значением заранее неизвестно. Поэтому требование уникальности (отсутствия повторений) не позволяет использовать генерируемую последовательность случайных в чистом виде. В рамках данной практической работы будет рассмотрен один из возможных подходов к решению данной проблемы, который предусматривает перемешивание упорядоченной последовательности с целью нарушения порядка следования ее элементов.

Перемешивание последовательности © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 11 Пусть мы располагаем упорядоченной последовательностью a размера n и генератором случайных чисел RND() в диапазоне [0, M]: Используя генератор RND() случайным образом сформируем два допустимых индекса в данной последовательности: i = (RND() mod 10) + 1, j = (RND() mod 10) + 1 Пусть i = 6, а j = 11. Обменяем местами a[i] и a[j] Процедура повторяется не менее n / 2 раз. После упорядоченность последовательности a будет нарушена и последовательность можно рассматривать как случайную, однако состоящую из заданного набора чисел.

Задание 6. Формирование неупорядоченных входных данных. © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 12 Разработать программу random_gen формирования неупорядоченных входных данных для алгоритмов сортировки. За основу взять программу, разработанную в задании 5. Сначала, используя алгоритм исходной программы, генерируется набор случайных значений последовательности. Однако эта последовательность не выводится в файл, а размещается во вспомогательном массиве размера n. Для создания данного массива желательно использовать динамическое выделение памяти (см. демонстрационную программу последовательного поиска из практического занятия "Алгоритмы сортировки", функция malloc и free). Далее полученный массив перемешивается согласно алгоритму, рассмотренному на предыдущем слайде. После этого результат выводится в файл согласно принятому формату.

Дополнительные исследования к занятию "Алгоритмы сортировки" © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Проверить теоретические оценки вычислительной сложности всех рассмотренных алгоритмов сортировки для класса 1 и 3 входных данных. Данные подготовить с помощью разработанных программ beginrange_gen и endrange_gen. 2. С помощью программы unirange_gen проверить, сохраняются ли полученные ранее соотношения в том случае, когда элементы последовательности распределены не с равным шагом 100, а случайным образом. При этом считать, что расстояние между элементами не превышает Используя программу random_gen подготовить входные данные размером 2 5, 2 6, 2 7, 2 8, 2 9, 2 10, 2 11, 2 12, 2 13, 2 14, 2 15, 2 16, 2 17, 2 18, 2 19, Построить график, показывающий зависимость среднего времени внутреннего поиска от размера входной последовательности. По полученной информации подготовить приложение к отчету по практике "Алгоритмы поиска", в котором описать только полученные результаты.