Кодирование алгоритма.
Характеристика псевдослучайных чисел
Рассмотрим процедуру Rand. В ней всего 4 шага, одно сравнение. Для процедуры G (n) рабочая функция имеет вид. Функцию f (n) определяют как О и говорят, что она порядка g (n) для больших n, если. Определили новое целое случайное число IX из и случайную величину из}. О, в противном случае алгоритм является экспоненциальным. Z:=Ix; x:=z {*1.e-6}; {обнулим 7 и далее разряды числа Х.}. Алгоритм G (n… Читать ещё >
Кодирование алгоритма. Характеристика псевдослучайных чисел (реферат, курсовая, диплом, контрольная)
Program seredina {метод середины квадрата}.
Uses crt;
Var.
Urand: Single;
Dm, Dd: Double;
n, i, j, k, l, ll: LongInt;
F: Text;
Procedure Rand (var Ix, k: LongInt; Urand: Single);
Var.
x, z: Single;
y, z1: Double; i: LongInt;
Begin.
z:=Ix; x:=z {*1.e-6}; {обнулим 7 и далее разряды числа Х.}.
z1:=x+1.e-6; y:=z1*z1*1.e-12; {вычислим квадрат Х.}.
z1:=y*1.e+3; y:=z1-Trunc (z1); {выберем 4…9 разряды числа Y.}.
if y<1.e-6 then.
Begin.
z1:=y*1.e+6;
y:=z1-Trunc (z1);
End;
z1:=y*1.e+6;
y:=Trunc (z1);
Ix:=Trunc (y); y:=y*1.e-6; Urand:=y;
{определили новое целое случайное число IX из [0.999 999] и случайную величину из [0.1]}.
k:=Round ((k+1)*y); {вычисляем число К из [0, К+1]}.
End; {Rand}.
Begin.
Clrscr;
Assign (F, 'd:/F/Rand.dat');
Rewrite (F);
n:=3−23; Dm:=0; Dd:=0; ll:=50 000;
for l:=1 to ll do.
begin.
k:=100;
Rand (n, k, Urand);
Dm:=Dm+Urand/ll;
Dd:=Dd+(Urand-0.5)*(Urand-0.5)/ll;
End;
Writeln (F, 'M=', Dm, 'Sig2=', Dd);
Close (F);
End.
В результате работы алгоритма, после создания текстового файла по указанному адресу, получаем файл Rand, содержащий результат — математическое ожидание и дисперсию.
Анализ сложности алгоритма Для этого воспользуемся способом, заключающимся в подсчете арифметических операций, необходимых для выполнения алгоритма (в этом случае определяется рабочая функция).
Пусть G (n) — алгоритм для решения некоторого класса задач, а n — размерность отдельной задачи из этого класса. Определим (n) как рабочую функцию, дающую верхнюю границу для максимального числа основных операций, которые должен выполнить алгоритм G (n) для решения любой задачи размерности n.
Алгоритм G (n) полиномиальный, если (n) растет не быстрее, чем полином от n, в противном случае алгоритм экспоненциальный.
Функцию f(n) определяют как О и говорят, что она порядка g (n) для больших n, если.
Функция h(n) является О для больших n, если.
Если f(n) есть О, то эти две функции возрастают с одинаковой скоростью при n>?. Если f(n) есть О, то g (n) возрастает гораздо быстрее, чем f(n).
Алгоритм G (n) называется полиномиальным, если.
(n)= О, в противном случае алгоритм является экспоненциальным.
Рассмотрим процедуру Rand. В ней всего 4 шага, одно сравнение. Для процедуры G (n) рабочая функция имеет вид.
(n)= О (n).
и она является полиномиальной [6].