Алгоритмы решения задач

КонтрольнаяПомощь в написанииУзнать стоимостьмоей работы

Функция алгоритм энтропия интегрирование Метод прямоугольников заключается в замене подынтегральной функции на многочлен нулевой степени на каждом элементарном отрезке. Если рассмотреть график подынтегральной функции, то метод будет заключаться в приближённом вычислении площади под графиком суммирования площадей конечного числа прямоугольников, ширина которых будет определяться расстоянием между… Читать ещё >

Алгоритмы решения задач (реферат, курсовая, диплом, контрольная)

МИНОБРНАУКИ РОССИИ Федеральное государственное бюджетное образовательное учреждение Высшего профессионального образования

«Пензенский государственный технологический университет»

(ПензГТУ) Факультет «Информационных и образовательных технологий»

Кафедра «Информационные технологии и системы»

Дисциплина «Языки программирования»

КОНТРОЛЬНАЯ РАБОТА № 2

на тему «Алгоритмы решения задач»

Выполнил: студент группы 13ИС2Б Чинков М.Ю.

Проверил: ст. преподаватель каф. ИТС Володин К.И.

Пенза 2014

СОДЕРЖАНИЕ ВВЕДЕНИЕ

1. МЕТОДЫ ИНТЕГРИРОВАНИЯ

2. СРАВНЕНИЕ МЕТОДОВ ИНТЕГРИРОВАНИЯ

3. МЕТОДЫ РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ

4. ЭНТРОПИЯ

5. МЕТОД МОНТЕ-КАРЛО ЗАКЛЮЧЕНИЕ СПИСОК ЛИТЕРАТУРЫ

Цель данной контрольной работы — актуализация знаний в области языков программирования. Основное задание — реализовать алгоритмы решения задач на языках программирования высокого уровня.

В рамках контрольной работы было выполнено 5 заданий:

1. Реализация интегрирования функции вида f (x) методами прямоугольников, трапеций, Симпсона.

2. Построение графика сравнения точности решения методов интегрирования в зависимости от количества разбиений.

3. Реализация методов решения системы линейных уравнений (GaussJordan, Cramer). Построение графика увеличения времени решения системы и объема занимаемой памяти с ростом размерности системы.

4. Реализация алгоритма расчета энтропии файлов с заданным расширением. Построение графика зависимости времени расчета от размера входного файла.

5. Реализация алгоритма определения значения числа Пи методом Монте-Карло (методом статистических испытаний). Построение графика зависимости точности расчета значения интеграла в зависимости от числа испытаний.

Задания № 1, 2, 3 были реализованы на языке программирования C. Задание № 4 было реализовано на языке программирования Java. Задание № 5 было реализовано на языке программирования Pascal.

1. МЕТОДЫ ИНТЕГРИРОВАНИЯ

Численное интегрирование — вычисление значения определённого интеграла, как правило, приближённое. Под численным интегрированием понимают набор численных методов для нахождения значения определённого интеграла.

Численное интегрирование применяется, когда:

1. Сама подынтегральная функция не задана аналитически. Например, она представлена в виде таблицы (массива) значений в узлах некоторой расчётной сетки.

2. Аналитическое представление подынтегральной функции известно, но её первообразная не выражается через аналитические функции.

Задачи, которые стоят в данном разделе — реализации интегрирования функции вида f (x) методами прямоугольников, трапеций, Симпсона (метод парабол). Подынтегральная функция была взята из лабораторной работы № 1 по дисциплине «Языки программирования».

функция алгоритм энтропия интегрирование Метод прямоугольников заключается в замене подынтегральной функции на многочлен нулевой степени на каждом элементарном отрезке. Если рассмотреть график подынтегральной функции, то метод будет заключаться в приближённом вычислении площади под графиком суммирования площадей конечного числа прямоугольников, ширина которых будет определяться расстоянием между соответствующими соседними узлами интегрирования, а высота — значением подынтегральной функции в этих узлах.

Метод трапеций заключается в замене на каждом элементарном отрезке подынтегральной функции на многочлен первой степени, то есть линейную функцию. Площадь под графиком функции аппроксимируется прямоугольными трапециями. Алгебраический порядок точности равен 1.

Метод Симпсона заключается в приближении подынтегральной функции на отрезке [a, b] интерполяционным многочленом второй степени, то есть приближение графика функции на отрезке параболой. Метод Симпсона имеет порядок погрешности 4 и алгебраический порядок точности 3.

Программа была реализована на языке C. Среда разработки — Visual Studio 2012.

В реализации были добавлены подынтегральная функция, все три метода интегрирования и функция main, которая принимает входные данные от пользователя и выводит результаты интегрирования.

Текст программы:

#include

double InFunction (double x, double a)

{

return acos (-30*a*a+19*a*x+5*x*x+1);

}

double CalcIntegralRectangleMethod (double a, double b, int n, double number_a)

{

double result, h;

int i;

h = (b-a)/n; //Шаг сетки

result = 0;

for (i=1; i <= n; i++)

{

result += InFunction (a + h * i — h/2,number_a); //Вычисляем в средней точке и добавляем в сумму

}

result *= h;

return result;

}

double CalcIntegralMethodTrapeze (double a, double b, int n, double number_a)

{

double result, h;

int i;

result = 0;

h=(b-a)/n;

for (i = 1; i < n; i++)

{

result += InFunction (a + i*h, number_a);

}

result *= h;

return result;

}

double CalcIntegralSimpsonMethod (double a, double b, int n, double number_a)

{

int i;

double S1=0, result=0, h;

h =(b — a) / (2*n);

for (i = 1; i <= 2*n-1; i++)

{

if (i % 2 == 0)

S1 += 2 * InFunction (a + i * h, number_a);

else S1+= 4 * InFunction (a + i * h, number_a);

}

result=((InFunction (a, number_a)+InFunction (b, number_a)+S1))*h/3;

return result;

}

int main (void)

{

double integral, number_a, a, b;

int n;

printf («enter a, b, accuracy of calculations and number an»);

scanf («%lf%lf%d%lf», &a,&b,&n,&number_a);

integral = CalcIntegralRectangleMethod (a, b, n, number_a);

printf («The value of the integral Rectangle method is: %lf n», integral);

integral = CalcIntegralMethodTrapeze (a, b, n, number_a);

printf («The value of the integral Method Trapeze is: %lf n», integral);

integral = CalcIntegralSimpsonMethod (a, b, n, number_a);

printf («The value of the integral Simpson’s method is: %lf n», integral);

scanf («%lf» ,&number_a);

return 0;

}

Результат работы программы:

2. СРАВНЕНИЕ МЕТОДОВ ИНТЕГРИРОВАНИЯ

Задачи, решенные в данном разделе — построение графика сравнения точности решения методов интегрирования (метод прямоугольников, метод трапеций, метод Симпсона, реализованные в разделе № 1) в зависимости от количества разбиений и построение графиков по каждому из методов.

Программа была реализована на языке C. Среда разработки — Visual Studio 2012.

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

Текст программы:

#include

double InFunction (double x, double a)

{ //Подынтегральная функция

return acos (-30*a*a+19*a*x+5*x*x+1);

}

double CalcIntegralRectangleMethod (double a, double b, int n, double number_a)

{

double result, h;

int i;

h = (b-a)/n; //Шаг сетки

result = 0;

for (i=1; i <= n; i++)

{

result += InFunction (a + h * i — h/2,number_a); //Вычисляем в средней точке и добавляем в сумму

}

result *= h;

return result;

}

double CalcIntegralMethodTrapeze (double a, double b, int n, double number_a)

{

double result, h;

int i;

result = 0;

h=(b-a)/n;

for (i = 1; i < n; i++)

{

result += InFunction (a + i*h, number_a);

}

result *= h;

return result;

}

double CalcIntegralSimpsonMethod (double a, double b, int n, double number_a)

{

int i;

double S1=0, result=0, h;

h =(b — a) / (2*n);

for (i = 1; i <= 2*n-1; i++)

{

if (i % 2 == 0)

S1 += 2 * InFunction (a + i * h, number_a);

else S1+= 4 * InFunction (a + i * h, number_a);

}

result=((InFunction (a, number_a)+InFunction (b, number_a)+S1))*h/3;

return result;

}

int main (void)

{

int p;

double integral1, integral2,integral3,number_a, a, b;

int n;

FILE *file;

printf («enter a, b, accuracy of calculations and namber an»);

scanf («%lf%lf%lf», &a,&b,&number_a);

file = (FILE *)fopen («resultat.txt», «w+»);

fprintf (file, «ntRectangletTrapezetSimpsonn»);

for (n=500;n<2500;n=n+50)

{

integral1 = CalcIntegralRectangleMethod (a, b, n, number_a);

integral2 = CalcIntegralMethodTrapeze (a, b, n, number_a);

integral3 = CalcIntegralSimpsonMethod (a, b, n, number_a);

fprintf (file, «%dt%lft%lft%lfn», n, integral1, integral2,integral3);

}

fclose (file);

scanf («%d», &p);

return 0;

}

Результаты работы программы.

Текстовый файл:

График:

3. МЕТОДЫ решения системы линейных уравнений

Система линейных алгебраических уравнений — это система уравнений вида

(1)

Здесь m — количество уравнений, а — количество неизвестных; x1, x2, …, xn — неизвестные, которые надо определить, a11, a12,…, amn — коэффициенты системы, b1, b2, … bm — свободные члены — предполагаются известными. Индексы коэффициентов системы обозначают номера уравнения и неизвестного, при котором стоит этот коэффициент.

Задачи, реализованные в данном разделе — реализация двух методов решения системы линейных уравнений (метод Гаусса-Жордана, метод Крамера), сравнение и построение графика увеличения времени решения системы и объема занимаемой памяти с ростом размерности системы.

Метод Гаусса-Жордана заключается в том, что с помощью элементарных преобразований система уравнений приводится к равносильной системе треугольного вида, из которой последовательно, начиная с последних (по номеру), находятся все переменные системы.

Метод Крамера — способ решения с числом уравнений равным числу неизвестных с ненулевым главным определителем матрицы коэффициентов системы.

Программа была реализована на языке C. Среда разработки — Visual Studio 2012.

Текст программы:

#include

double time_on_gaus, time_off_gaus, time_on_cramer, time_off_cramer;

void print_matrix (int str, int stb, float **mass)//вывод матрицы в консоль

{

for (int i=0;i

{

for (int j=0;j

printf («a[%d][%d]=%.2f t», i, j, mass[i][j]);

printf («n»);

}

printf («n»);

}

// Решение

int gaus (int str, float **mass, float *x)

{

int i, j, k;

//прямой ход

for (i=0;i

{

double a=mass[i][i];

for (j=i+1;j

{

float b=mass[j][i];

for (k=i;k

mass[j][k]=mass[i][k]*b-mass[j][k]*a;

}

//обратный ход

for (i=str-1;i>=0;i—)

{

double summ=0.;

for (j=i+1;j

summ+=mass[i][j]*x[j];

summ=mass[i][str]-summ;

if (mass[i][i]==0)

return 0;

x[i]=summ/mass[i][i];

}

return 1;

}

int gaus_det (int str, float **mass, float *det)

{

int i, j, k;

*det=1.0f;

//создаём копию матрицы, так как элементы матрицы мы будем использовать повторно

float **copy_mass=(float**)malloc (str*sizeof (float));

for (i=0;i

{

copy_mass[i]=(float*)malloc (str*sizeof (float));

for (j=0;j

copy_mass[i][j]=mass[i][j];

}

//прямой ход метод Гаусса

for (i=0;i

{

for (j=i+1;j

{

if (copy_mass[i][i]==0)

{

for (int i=0; i

free (copy_mass[i]);

free (copy_mass);

return 0;

}

float b=copy_mass[j][i]/copy_mass[i][i];

for (k=i;k

copy_mass[j][k]=copy_mass[j][k]-copy_mass[i][k]*b;

}

*det *= copy_mass[i][i]; //вычисление определителя

}

for (int i=0; i

free (copy_mass[i]);

free (copy_mass);

return 1;

}

int main ()

{

int str, stb;

str=stb=0;

float **mass;

float *x;

FILE *in;

FILE* logfile;

char *file_name = «text.txt» ;

char *file_name1 = «text1.txt» ;

char *file_name2 = «text2.txt» ;

for (int chet=0;chet<3;chet++)

{

if (chet==0) in = fopen (file_name," rt");

if (chet==1) in = fopen (file_name1," rt");

if (chet==2) in = fopen (file_name2," rt");

if (in == NULL)

{

if (chet==0) printf («Error 1: open file %sn», file_name);

if (chet==1) printf («Error 1: open file %sn», file_name1);

if (chet==2) printf («Error 1: open file %sn», file_name2);

getch ();

return 1;

}

// чтение размеров матрицы

fscanf (in, «%d %d», &str, &stb);

mass=(float**)malloc (str*sizeof (float)); // память под массив указателей на строки

for (int i=0; i

mass[i] = (float*)malloc (stb*sizeof (float)); // память под каждую строку

for (int i=0; i

for (int j=0; j

fscanf (in," %f" ,&mass[i][j]);

fclose (in);

setlocale (LC_ALL," Russian");

printf («_______________Матрица_______________n»);

print_matrix (str, stb, mass); // печать матрицы

printf («n_______________Решение методом Гауса_______________n»);

x = (float *)malloc (sizeof (float)*str);

time_on_gaus = omp_get_wtime ();

if (gaus (str, mass, x)==1)//решение системы линейных уравнений методом Гаусса и

//печать результата при удачном выполнение

{

time_off_gaus = omp_get_wtime ();

for (int i=0;i

printf («x[%d]=%.2f t», i+1,x[i]);

printf («n»);//вывод результата

}

else

{

printf («Ошибкаn»);

}

printf («n_______________Решение методом Крамера_______________n»);

float *det=(float *)malloc (sizeof (float)*(stb+1));//массив определителей

float *t=(float *)malloc (sizeof (float)*str);//временная переменная для хранения столбца матрицы

time_on_cramer = omp_get_wtime ();

for (int i=0;i

{

if (gaus_det (str, mass,&det[i])≠1)//вычисление определителя используя метод Гаусса

{

printf («Ошибкаn»);

// освобождение памяти

for (int i=0; i

free (mass[i]);

free (mass);

free (det);

free (t);

getch ();

return 0;

}

for (int j=0;j

{

if (i>0)

mass[j][i-1]=t[j]; //восстанавливаем значение столбца

t[j]=mass[j][i]; //сохраняем значения i — столбца матрицы в переменной t

mass[j][i]=mass[j][stb-1]; //в i — столбец матрицы записываем столбец свободных членов

}

time_off_cramer = omp_get_wtime ();

for (int i=1;i

printf («x[%d]=%.2f t», i, det[i]/det[0]);//вывод результата

printf («nn»);

logfile = (FILE *)fopen («logfile.txt», «a»);

fprintf (logfile," %lft%lfn", time_off_gaus-time_on_gaus, time_off_cramer-time_on_cramer);

fclose (logfile);

// освобождение памяти

for (int i=0; i

free (mass[i]);

free (mass);

free (x);

free (det);

free (t);

}

getch ();

return 0;

}

Результаты работы программы:

График:

4. ЭНТРОПИЯ ФАЙЛОВ

Информационная энтропия — мера неопределённости или непредсказуемости информации, неопределённость появления какого-либо символа первичного алфавита. При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения. Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной частотой, поэтому неопределённость появления для некоторых букв меньше, чем для других. Если же учесть, что некоторые сочетания букв встречаются очень редко, то неопределённость уменьшается еще сильнее.

Задачи, которые стоят в данном разделе — реализация алгоритма расчета энтропии файлов с заданным расширением и построение графика зависимости времени расчета от размера входного файла.

Программа была реализована на языке C++. Среда разработки — Visual Studio 2012.

В начале функции были введены переменные некого файлового потока, количества символов в тексте, массив частот символов и саму энтропию (entr). Затем был реализован ввод имени файла для его анализа. Открываем файл в режиме чтения и вводим логический оператор if для того случая, если файл не откроется. Затем читаем файл посимвольно, подсчитывая при этом частоту символов. Если символ не является последним в файле, то переходим к следующему символу, если является — закрываем файл. Затем был реализован сам расчет энтропии с замером времени. В конце функции процесс вывода на экран результатов энтропии, а также времени расчета.

Текст программы:

#include

using namespace std;

int main ()

{

fstream f;

string file_name;

long total=0;

int code[256] = {0};

float entr=0,

prob;

double t1, t2;

cout << «Input file name: » ;

cin >> file_name;

f.open (file_name.c_str (), ios: in | ios: binary);

if (!f)

{

cout << «Error 1: open input file «<< file_name << endl;

return 1;

}

t1 = omp_get_wtime ();

char ch;

f.unsetf (ios:skipws);

while (!f.eof ())

{

f >> ch;

if (!f.eof ())

{

code[(int)ch]++;

total++;

}

f.close ();

for (int i=0; i < 256; i++)

{

if (code[i] == 0)

continue;

prob=code[i]/(float)total;

entr-=prob*log (prob)/log (2.0f);

}

t2 = omp_get_wtime ();

cout << «Bytes: «<< total << endl;

cout.setf (ios:fixed);

cout.precision (3);

cout << «Entropy: «<< entr << endl;

cout.precision (10);

cout << «Time: «<< t2-t1 << endl;

_getch ();

return 0;

}

Результаты работы программы.

Окно вывода программы:

График зависимости времени расчета от размера входного файла:

5. определениЕ числа Пи МЕТОДОМ МОНТЕ-КАРЛО

Задачи, реализованные в данном разделе — реализация алгоритма определения значения числа Пи методом Монте-Карло (методом статистических испытаний) и построение графика зависимости точности расчета значения интеграла в зависимости от числа испытаний.

При определении значения числа Пи метод Монте-Карло — самый простой и легкий в реализации метод.

Рассмотрим произвольный квадрат с центром в начале координат и вписанный в него круг. Будем рассматривать только первую координатную четверть. В ней будет находиться четверть круга и четверть квадрата. Обозначим радиус круга r, тогда четверть квадрата тоже будет квадратом (очевидно) со стороной r.

Будем случайным образом выбирать точки в этом квадрате и считать количество точек, попавших в четверть круга с помощью функции randomize. Благодаря теории вероятности мы знаем, что отношение попаданий в четверть круга к попаданиям 'в молоко' равно отношению площадей — Пи/4. Чем больше взятых наугад точек мы проверим, тем точнее будет отношение площадей.

Данный метод был реализован на языке Pascal. Среда разработки — PascalABC.NET.

Текст программы:

uses Crt;

const

n=10 000 000;

r=46 340;

r2=46 340*46340;

var

i, pass: LongInt;

x, y: real;

{$F+}

begin

Randomize;

pass:=0;

for i:=1 to n do

begin

x:=Random (r+1);

y:=Random (r+1);

if (x*x+y*y < r2) then INC (pass);

end;

TextColor (GREEN);

WriteLn ('Число ПИ равно: ',(pass/i*4):0:5);

ReadLn;

end.

Результат работы программы:

График:

заключение

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

Было выполнено 5 заданий:

1. Реализация интегрирования функции вида f (x) методами прямоугольников, трапеций, Симпсона.

1. Нахождение интеграла с заданной точностью на C. Метод Симпсона. — SourcePrograms.Ru © 2011;2014 —. — Режим доступа: http://sourceprograms.ru/industries_programming/calculable_mathematics/15-nahozhdenie-integrala-s-zadannoy-tochnostyu-na-c-metod-simpsona.html.? Загл. с экрана.

2. МЕТОД ЖОРДАНА-ГАУССА —. — Режим доступа: http://ios.sseu.ru/public/eresmat/metod/met5/parmet5₃.htm.? Загл. с экрана.

4. Вычисление с нужной точностью числа Пи — Kantor Ilia —. — Режим доступа: http://algolist.manual.ru/maths/count_fast/pi.php.? Загл. с экрана

Показать весь текст

Заполнить форму текущей работой