- •Предназначено студентам очной формы обучения.
- •Введение
- •1. Оценки сложности алгоритмов
- •1.1. Определение понятия алгоритм
- •1.2. Оценка сложности алгоритмов
- •2. Линейные структуры данных
- •2.1. Методы организации и хранения линейных списков
- •2.2. Операции со списками при последовательном хранении
- •2.3. Операции со списками при связном хранении
- •2.4. Организация двусвязных списков
- •Задания для самоконтроля
- •2.5. Стеки и очереди
- •2.6. Сжатое и индексное хранение линейных списков
- •3. Сортировка и слияние
- •3.1. Пузырьковая сортировка
- •3.2. Сортировка вставкой
- •3.3. Сортировка посредством выбора
- •3.4. Сортировка квадратичной выборкой
- •3.5. Слияние списков
- •3.6. Сортировка списков путем слияния
- •3.7. Быстрая и распределяющая сортировки
- •4. Поиск
- •4.1. Последовательный поиск
- •4.2. Бинарный поиск
- •4.4. Методы вычисления адреса
- •4.5. Выбор в линейных списках
- •5. Рекурсия
- •6. Алгоритмы на графах и сетях
- •6.1. Исходные понятия
- •6.2. Матричные представления графов
- •6.3. Другие представления графов
- •6.4. Поиск в глубину как система исследования графа
- •6.5. Перебор цепей поиском в глубину
- •6.6. Взвешенные графы. Ориентированные графы
- •6.7. Нахождение фундаментального множества циклов
- •6.8. Выявление мостов и точек сочленений
- •6.9. Поиск в ширину как система исследования графа
- •6.10. Кратчайшие пути, ведущие от заданного узла X ко всем прочим
- •6.11. Алгоритм Дейкстры нахождения кратчайших путей во взвешенном графе
- •6.12. Улучшения алгоритма Дейкстры
- •6.13. Построение кратчайшего каркаса
- •6.14. Нахождение всевозможных кратчайших путей в графе
- •6.15. Потоковые задачи
- •6.16. Пример практической задачи на графах
- •7. Генераторы случайных и псевдослучайных последовательностей
- •7.1. Общая постановка задачи
- •7.3. Генератор случайных чисел, поставляемый с системой
- •7.4. Генератор с малым кодом
- •7.5. Генератор Парка-Миллера
- •7.6. Улучшенная версия генератора Парка-Миллера
- •7.7. Быстрый генератор для 32-битового представления целых и действительных чисел
- •7.8. Алгоритм л'Экюера, комбинирующий две последовательности
- •Оглавление
- •7. Генераторы случайных и псевдослучайных последовательностей 144
- •394026 Воронеж, Московский просп., 14
7.5. Генератор Парка-Миллера
Самая простая последовательность, которую можно предложить для реализации генератора равномерного распределения:
I(j+1)=a*I(j)(modm)
при соответствующем выборе констант. Константы были предложены Park и Miller:
a=75=16807, m=231-1=2147483647
и протестированы в исследованиях Lewis, Goodman, Miller (1969).
Прямое приложение этого метода возможно на языках ассемблера, но языки высокого уровня могут при этом зафиксировать переполнение. Для обхода этого Scharge предложил метод частичной факторизации модуля. Модуль разлагается в выражение:
m=a*q+r
Если r<q и 0<z<m-1, то при этом величины a*(z mod q) и r*[z/q] всегда лежат в интервале 0,...,m-1. Для умножения (a*z)(mod m) при этом используется алгоритм:
t = a(z mod q)-r[z/q]
если t<0, то t += m.
(a*z)(mod m)=t.
В случае констант Парка-Миллера можно использовать q=12773 и r=2836.
/* Minimal portable random generator by Park and Miller */
/* Lewis-Goodman-Miller constants */
#define IA 16807
#define IM 2147483647
#define AM (1./IM)
/* Scharge constants */
#define IQ 12773
#define IR 2836
/* Special mask to be explained below */
#define MASK 123456789
static long dummy;
/* initial seed, for all the generators here */
void Seed(long dum) {dummy=dum;}
/* returns random uniformly distributed between 0 and 1 */
float unirand0(void) {
long k;
float ans;
dummy^=MASK; /* avoid dummy==0 */
k=dummy/IQ;
if((dummy=IA*(dummy-k*IQ)-IR*k)<0) dummy+=IM;
ans=AM*dummy;
dummy^=MASK; /* restore unmasked dummy */
return(ans);
}
Использование маски связано с тем, что специфика алгоритма не позволяет устанавливать счетчик в нуль. Но, как показывает опыт, большинство пользователей счетчиков делают именно так. Маска гарантирует, что установленный счетчик не будет нулем. Если вы очень уверены в том, что человек не допустит подобной ошибки после вашего предупреждения, то можете убрать из программы все инструкции, связанные с маской.
7.6. Улучшенная версия генератора Парка-Миллера
В дополнение к предыдущему алгоритму, производит перетасовку по методу Bays и Durham, что позволяет уничтожить нежелательные корреляции между сериями сгенерированных случайных чисел.
/* Minimal random generator with Bays-Durham shuffle */
/* previous functions, variables and constants are described above.
Only additional follow */
#define NTAB 32
#define NWUP 8
#define NDIV (1+(IM-1)/NTAB)
#define EPS 1.2e-7
#define RNMX (1.0-EPS)
float unirand1(void) {
int j;
long k;
static long iy=0,iv[NTAB];
float temp;
/* initialize */
if(dummy<=0 || !iy) {
/* avoid negative or zero seed */
if(dummy<0) dummy=-dummy;
else if(dummy==0) dummy=1;
/* after NWUP warmups, initialize shuffle table */
for(j=NTAB+NWUP-1;j>=0;j--) {
k=dummy/IQ;
if((dummy=IA*(dummy-k*IQ)-IR*k)<0) dummy+=IM;
if(j<NTAB) iv[j]=dummy;
}
/* first specimen from the table */
iy=iv[0];
}
/* regular work: generate new number */
k=dummy/IQ;
if((dummy=IA*(dummy-k*IQ)-IR*k)<0) dummy+=IM;
/* shuffle output */
iy=iv[j=iy/NDIV];iv[j]=dummy;
/* return */
if((temp=AM*iy)>RNMX) return(RNMX);
elsereturn(temp);
}
Заметим, что маска здесь не применяется, поскольку метод инициализации алгоритма отсекает ошибочные значения текущего счетчика.
Алгоритм Парка-Миллера с перетасовкой проходит все известные тесты, включая и те, где без перетасовки этот алгоритм дает сбой. Хорошее поведение наблюдается до значений числа вызовов счетчика порядка 108, где он начинает повторяться.