Курсова робота
З ДИСЦИПЛІНИ
ТЕХНОЛОГІЯ ПРОГРАМУВАННЯ
Отримання псевдовипадкових чисел
Зміст
Введення
1. Генератор псевдовипадкових чисел
2. Методи отримання псевдовипадкових чисел
Лінійний конгруентний метод
Метод Фібоначчі
Вихор Мерсенна
3. Тестування псевдовипадкових послідовностей
4. Генератор випадкових чисел в Borland C ++
Висновок
5. Список використаних джерел
Додаток
Введення
Програма призначена для формування та перегляду команди для олімпіади з програмування.
а) Введення інформації.
За запитом з клавіатури почергово вводяться прізвище, ім'я студента, а також мова програмування, на якому він воліє писати програми (Pascal, C, C ++).
б) Перегляд введеного списку.
Якщо список не порожній, то при виборі цього пункту меню на екран по черзі виводиться повна інформація про кожного студента.
в) Відбір команди.
При виборі цього пункту меню користувач повинен вказати мову програмування, на підставі цього зі списку студентів вибирається не більше трьох осіб (їх може бути менше), володіють цією мовою.
г) Перевірка, чи може бути укомплектована команда.
Передбачається, що команда складається з трьох чоловік. Користувач вводить мову програмування, а програма повідомляє йому, чи можна або не можна укомплектувати команду (можна, якщо студентів, які володіють даними мовою, не менше трьох)
Реалізувати програму на базі зв'язного списку.
генератор псевдовипадкове число послідовність
1. Генератор псевдовипадкових чисел
Фізичне моделювання випадковості за допомогою таких фізичних явищ як, наприклад, радіоактивне випромінювання або дробовий шум в електронній лампі є досить складним і дорогим, а використання натиснення клавіш і рух миші вимагає зусиль користувача і до того ж не дають повністю справжніх випадкових процесів. Тому замість фізичного моделювання використовують методи математичного моделювання випадковості і генерації випадкових послідовностей у вигляді програм для ЕОМ або спеціалізованих пристроїв.
Ці програми та пристрої хоча і називаються генераторами випадкових чисел, насправді генерують детерміновані послідовності, які тільки здаються випадковими за своїми властивостями і тому називаються псевдовипадковими послідовностями.
Генератор псевдовипадкових чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG) - алгоритм, що генерує послідовність чисел, елементи якої майже незалежні один від одного і підкоряються заданому розподілу (зазвичай рівномірному).
Найважливіша характеристика генератора псевдовипадкових чисел - це інформаційна довжина його періоду, після якого числа будуть або просто повторюватися, або їх можна буде передбачити.
Будь програмні ГПСЧ, які не використовують зовнішніх джерел ентропії і формують чергове число тільки алгебраїчними перетвореннями, не дають чисто випадкових чисел. Послідовність на виході такого генератора виглядає як випадкова, але насправді підпорядковується деякому закону і, як правило, рано чи пізно зациклюється. Такі числа називаються псевдовипадковими. Розглянемо тепер деякі практичні методи отримання псевдовипадкових чисел.
2. Методи отримання псевдовипадкових чисел
Одним з перших таких методів був метод, запропонований в 1946 році Д. фон Нейманом. Цей метод базувався на тому, що кожне наступне число в псевдовипадкової послідовності формувалося зведенням попереднього числа в квадрат і відкиданням цифр з обох кінців. Однак цей метод виявився ненадійним, і від нього швидко відмовилися. Іншим методом є так званий конгруентний спосіб.
Лінійний конгруентний метод
Лінійний конгруентний метод - один з алгоритмів генерації псевдовипадкових чисел. Входить до стандартні бібліотеки різних компіляторів.
Цей алгоритм полягає в итеративном застосуванні наступної формули:
,
де a gt; 0, c gt; 0, m gt; 0 - деякі цілочисельні константи. Отримана послідовність залежить від вибору ...
