Рисунок 1. блок-схем программы

Нет

4

Да

4

Рисунок 2. блок-схема процедуры Rand

Кодирование алгоритма

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.999999] и случайную величину из [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:=50000;

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, 'Sig^2=', 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 7 8 9 10 11 12 14

4

22 21 20 19 18 17 15

Рисунок 4. Схема Мартынюка

На приведенной выше схеме Мартынюка путь является простым, так как он не содержит ни одной вершины или дуги более одного раза. Схема правильная, так как выполняется условие, что каждая вершина принадлежит хотя бы одному пути по графу.

Таблица 2. Матрица Путей

Матрица путей С - путей длины 1.

Рис. 6

Таблица 3. Матрица Путей

Матрица Р - матрица всех путей

Все элементы 1 столбца равны 1, значит в 1 вершину управление не передается ни из какой другой. Все элементы 1 строки равны 1, значит из 1 вершины управление не передается ни в какую другую, отсюда следует, что схема программы является правильной.

Проверка диапазона значений переменных

Dm - математическое ожидание, Dm: Dm+Urand/ll;

Dd - дисперсия, Dd: Dd+Urand;

k: Round((k+1)*y);

L: array [1..50 000];

ll: 50 000;

Ix: Trunc(y);

Urand: y;

X: z;

Z: Ix;

Y: z1*z1z*1.e-12, z1-Trunc(z1), Trunc(z1);

Z1: x+1.e-6, y*1.e+3, y*1.e+6.

Тестирование программы

Проверка входных данных. N:=3-23, Dm:=0, Dd:=0, ll:=50000, l:=[1..ll], k:=10. все входные данные обрабатываются верно.

Список литературы

1. Основы алгоритмизации, учебное пособие. А.В. Налимов. Барнаул 2000 г.

2. Анализ и разработка алгоритмов, методические рекомендации. А.В. Налимов. Барнаул 2001 г.

3. Алгоритмы построение и анализ, Т. Кормен, Ч. Лейзерсон, Р. Ривест. Москва 2007 г.

4. Алгоритмы дискретной математики, Л.Е. Захарова. Москва 2007 г.

5. Искусство программирования, Д.Э. Кнут. Том 2.

Страницы: 1, 2