Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

ТЕОРИЯ АЛГОРИТМОВ. Цель работы: экспериментально исследовать теоретическую оценку трудоемкости алгоритма поиска минимума





Цель работы: экспериментально исследовать теоретическую оценку трудоемкости алгоритма поиска минимума, ознакомиться с принципами использования ГСЧ.

Вариант задания №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.

ТЕОРИЯ АЛГОРИТМОВ

(Вариант № 18)

Выполнил:

Студент группы И-21з

Емельянов К.Ю.

Проверил:

Шишкевич В.Е.

 


Поможем в написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой





Дата добавления: 2015-10-12; просмотров: 758. Нарушение авторских прав; Мы поможем в написании вашей работы!

Studopedia.info - Студопедия - 2014-2022 год . (0.052 сек.) русская версия | украинская версия
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7