Цель работы: экспериментально исследовать теоретическую оценку трудоемкости алгоритма поиска минимума, ознакомиться с принципами использования ГСЧ.
Вариант задания №18
| Вариант
| Наибольшее случайное число в последовательности
| Количество элементов в массиве случайных чисел
|
|
|
| 250, 300, 400
|
Ход выполнения работы
В ходе выполнения работы были разработаны 2 процедуры: harmonic – для расчета гармонического числа, create_array – для генерации матрицы псевдослучайных чисел и записи ее в файл. Реализация процедуры create_array представлена на рис. 1, блок-схема – на рис.2.
| void create_array(int Nmax,int *vector)
{
// Cоздание массива из Nmax псевдослучайных целых чисел величиной от 0 до 550
// массив записывается в файл Example_TA2.TXT, на экран выводим максимальное // целое
int i;//переменная цикла
FILE *stream;//файл данных
//Nmax соответствует размерности массива
stream = fopen("Example_TA2.TXT", "w+");//открываем файл для записи
std::cout << std::endl <<"Maximal integer " << RAND_MAX << std::endl;//вывод максимально возможного числа
printf("\n%d%s\n", Nmax, " random numbers from 0 to 550");//вывод справочного сообщения
for(i=0; i<Nmax; i++)//цикл вывода в файл и на экран элементов массива
{
vector[i]= rand() % 550;//генерация очередного случайного числа в диапазоне от 0 до 550
if ((i+1)%20!=0)//вывод по 20 чисел в ряд
{
printf("%d ", vector[i]);
fprintf(stream,"%d ", vector[i]);
}
else
{
printf("%d\n", vector[i]);
fprintf(stream,"%d\n", vector[i]);
}
}
fclose(stream);
}
|
| Рис.1. Реализация процедуры create_array
|
|
| Рис. 2. Блок-схема процедуры create_array
|
Реализация процедуры harmonic представлена на рис. 3, блок-схема – на рис.4.
| double harmonic(int n)
{
//Функция вычисления гармонического числа
double sum = 0;
for (int i=1; i<=n; i++) sum+=1/(double)i;
return sum;
}
|
| Рис. 3. Реализация процедуры harmonic
|
|
| Рис. 4. Блок-схема процедуры harmonic
|
На рис.5 представлен листинг основной части программы.
| #include <conio.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <time.h>
#include "Lab2_TA_func.h"
using namespace std;
int vector[10];
// Cоздание массива из 10 псевдослучайных целых чисел величиной от 0 до 100
// массив записывается в файл Example_TA2.TXT, на экран выводим максимальное // целое
int main(int argc, char* argv[])
{
int i,
N, //кол-во чисел
min, // значение минимума
cnt; //счетчик операций переприсваивания
double result;
cout << "Input amount of numbers: "; cin >> N;
result = Lab2_TA::harmonic(N); //расчет гармонического числа
// harmonic(N) – функция подсчета n-го гармонического числа
cout << "Harmonic(" << N << ")=" << result;
Lab2_TA::create_array(N,vector);
//генерация массива псевдослучайных чисел
min = vector[0];//берем в качестве первого минимального элемента первый элемент массива
cnt = 1;
for (i=0;i<N;i++)
{
if(vector[i]<min)
{
min = vector[i]; cnt++;
}
}
printf("\n%s%d%s%d\n", "Minimal ", min, " Num oper ", cnt);//Вывод минимального числа и кол-ва операций переприсваивания
_getch();
return 0;
}
|
| Рис. 5. Листинг основной части программы
|
Для нашего варианта заданий были получены следующие результаты рис. 6-8.
|
| Рис.6. Результаты расчета для массива из 250 элементов
|
|
| Рис.7. Результаты расчета для массива из 300 элементов
|
|
| Рис.8. Результаты расчета для массива из 400 элементов
|
Выводы.
В результате выполнения лабораторной работы:
· была исследована теоретическая оценка трудоемкости алгоритма поиска минимума;
· были получены навыки работы с генератором псевдослучайных чисел;
· были создана программа для исследования трудоемкости алгоритма и блок-схемы основных функций;
· было установлено, что практическая оценка трудоемкости алгоритма значительно меньше теоретической. Это связано с тем, что использовались массивы небольшого размера. Если увеличивать кол-во элементов массива до бесконечности, то разница между теоретической и практической оценкой будет стремится к 0.
