Алгоритмы решения задач
МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное
образовательное учреждение
Высшего профессионального образования
«Пензенский государственный
технологический университет»
(ПензГТУ)
Факультет «Информационных и
образовательных технологий»
Кафедра «Информационные технологии и
системы»
Дисциплина «Языки программирования»
КОНТРОЛЬНАЯ РАБОТА №2
на тему «Алгоритмы решения задач»
Выполнил:
студент группы 13ИС2Б
Чинков М.Ю.
Проверил: ст.
преподаватель каф. ИТС
Володин К.И.
Пенза 2014
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
. МЕТОДЫ ИНТЕГРИРОВАНИЯ
. СРАВНЕНИЕ МЕТОДОВ ИНТЕГРИРОВАНИЯ
. МЕТОДЫ РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ
. ЭНТРОПИЯ
. МЕТОД МОНТЕ-КАРЛО
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
ВВЕДЕНИЕ
Цель данной контрольной работы - актуализация знаний в области языков
программирования. Основное задание - реализовать алгоритмы решения задач на
языках программирования высокого уровня.
В рамках контрольной работы было выполнено 5 заданий:
. Реализация интегрирования функции вида f(x) методами
прямоугольников, трапеций, Симпсона.
. Построение графика сравнения точности решения методов
интегрирования в зависимости от количества разбиений.
. Реализация методов решения системы линейных уравнений
(GaussJordan, Cramer). Построение графика увеличения времени решения системы и
объема занимаемой памяти с ростом размерности системы.
. Реализация алгоритма расчета энтропии файлов с заданным
расширением. Построение графика зависимости времени расчета от размера входного
файла.
. Реализация алгоритма определения значения числа Пи методом
Монте-Карло (методом статистических испытаний). Построение графика зависимости
точности расчета значения интеграла в зависимости от числа испытаний.
Задания №1, 2, 3 были реализованы на языке программирования C. Задание №4 было реализовано на
языке программирования Java.
Задание №5 было реализовано на языке программирования Pascal.
.
1. МЕТОДЫ
ИНТЕГРИРОВАНИЯ
Численное интегрирование - вычисление значения определённого интеграла,
как правило, приближённое. Под численным интегрированием понимают набор численных
методов для нахождения значения определённого интеграла.
Численное интегрирование применяется, когда:
. Сама подынтегральная функция не задана аналитически. Например,
она представлена в виде таблицы (массива) значений в узлах некоторой расчётной сетки.
. Аналитическое представление подынтегральной функции известно, но
её первообразная не выражается через аналитические функции.
Задачи, которые стоят в данном разделе - реализации интегрирования
функции вида f(x) методами прямоугольников, трапеций, Симпсона (метод парабол).
Подынтегральная функция была взята из лабораторной работы №1 по дисциплине
«Языки программирования».
функция алгоритм энтропия интегрирование
Метод прямоугольников заключается в замене подынтегральной функции на
многочлен нулевой степени на каждом элементарном отрезке. Если рассмотреть
график подынтегральной функции, то метод будет заключаться в приближённом
вычислении площади под графиком суммирования площадей конечного числа
прямоугольников, ширина которых будет определяться расстоянием между
соответствующими соседними узлами интегрирования, а высота - значением
подынтегральной функции в этих узлах.
Метод трапеций заключается в замене на каждом элементарном отрезке
подынтегральной функции на многочлен первой степени, то есть линейную функцию.
Площадь под графиком функции аппроксимируется прямоугольными трапециями.
Алгебраический порядок точности равен 1.
Метод Симпсона заключается в приближении подынтегральной функции на
отрезке [a,b] интерполяционным многочленом второй степени, то есть приближение
графика функции на отрезке параболой. Метод Симпсона имеет порядок погрешности
4 и алгебраический порядок точности 3.
Программа была реализована на языке C. Среда разработки - Visual Studio 2012.
В реализации были добавлены подынтегральная функция, все три метода
интегрирования и функция main,
которая принимает входные данные от пользователя и выводит результаты
интегрирования.
Текст программы:
#include <stdio.h>
#include <math.h>InFunction(double
x,double a)
{acos(-30*a*a+19*a*x+5*x*x+1);
}CalcIntegralRectangleMethod(double a,
double b, int n,double number_a)
{result, h;i;= (b-a)/n; //Шаг сетки= 0;(i=1;
i <= n; i++)
{+= InFunction(a + h * i - h/2,number_a); //Вычисляем в
средней точке и добавляем в сумму
}*= h;result;
}CalcIntegralMethodTrapeze(double a, double
b, int n,double number_a)
{result, h;i;= 0;=(b-a)/n;(i = 1; i < n;
i++)
{+= InFunction(a + i*h,number_a);
}*= h;result;
}CalcIntegralSimpsonMethod(double a, double
b, int n,double number_a)
{i;S1=0, result=0, h;=(b - a) / (2*n);(i =
1; i <= 2*n-1; i++)
{(i % 2 == 0)+= 2 * InFunction(a + i *
h,number_a);S1+= 4 * InFunction(a + i * h,number_a);
}=((InFunction(a,number_a)+InFunction(b,number_a)+S1))*h/3;result;
}main(void)
{integral,number_a,a,b;n;("enter a, b,
accuracy of calculations and number a\n");("%lf%lf%d%lf",
&a,&b,&n,&number_a);=
CalcIntegralRectangleMethod(a,b,n,number_a);("The value of the integral
Rectangle method is: %lf \n", integral);= CalcIntegralMethodTrapeze(a,b,n,number_a);("The
value of the integral Method Trapeze is: %lf \n", integral);=
CalcIntegralSimpsonMethod(a,b,n,number_a);("The value of the integral
Simpson's method is: %lf \n", integral);("%lf",&number_a);0;
}
Результат работы программы:
2. СРАВНЕНИЕ
МЕТОДОВ ИНТЕГРИРОВАНИЯ
Задачи, решенные в данном разделе - построение графика сравнения точности
решения методов интегрирования (метод прямоугольников, метод трапеций, метод
Симпсона, реализованные в разделе №1) в зависимости от количества разбиений и
построение графиков по каждому из методов.
Программа была реализована на языке C. Среда разработки - Visual Studio 2012.
Все графики представлены на одном графике для сравнения. По сравнению с
заданием №1, в программу была добавлена реализация записи результатов
интегрирования в текстовый файл.
Текст программы:
#include <math.h>InFunction(double
x,double a)
{ //Подынтегральная функцияacos(-30*a*a+19*a*x+5*x*x+1);
}CalcIntegralRectangleMethod(double a,
double b, int n,double number_a)
{result, h;i;= (b-a)/n; //Шаг сетки= 0;(i=1;
i <= n; i++)
{+= InFunction(a + h * i - h/2,number_a); //Вычисляем в
средней точке и добавляем в сумму
}*= h;result;
}CalcIntegralMethodTrapeze(double a, double
b, int n,double number_a)
{result, h;i;= 0;=(b-a)/n;(i = 1; i < n;
i++)
{+= InFunction(a + i*h,number_a);
}*= h;result;
}CalcIntegralSimpsonMethod(double a, double
b, int n,double number_a)
{i;S1=0, result=0, h;=(b - a) / (2*n);(i =
1; i <= 2*n-1; i++)
{(i % 2 == 0)+= 2 * InFunction(a + i * h,number_a);S1+=
4 * InFunction(a + i * h,number_a);
}=((InFunction(a,number_a)+InFunction(b,number_a)+S1))*h/3;result;
}main(void)
{p;integral1,integral2,integral3,number_a,a,b;n;*file;("enter
a, b, accuracy of calculations and namber a\n");("%lf%lf%lf",
&a,&b,&number_a);= (FILE *)fopen("resultat.txt",
"w+");(file,
"n\tRectangle\tTrapeze\tSimpson\n");(n=500;n<2500;n=n+50)
{=
CalcIntegralRectangleMethod(a,b,n,number_a);=
CalcIntegralMethodTrapeze(a,b,n,number_a);=
CalcIntegralSimpsonMethod(a,b,n,number_a);(file,
"%d\t%lf\t%lf\t%lf\n",n,integral1,integral2,integral3);
}(file);("%d", &p);
return 0;
}
Результаты работы программы.
Текстовый файл:
График:
3. МЕТОДЫ решения системы линейных уравнений
Система
линейных алгебраических уравнений
<#"792043.files/image006.gif"> (1)
Здесь m - количество уравнений, а - количество неизвестных;
x1, x2, …, xn - неизвестные, которые надо определить, a11, a12,…, amn -
коэффициенты системы, b1, b2, … bm - свободные члены - предполагаются
известными. Индексы коэффициентов системы обозначают номера уравнения и
неизвестного, при котором стоит этот коэффициент.
Задачи, реализованные в данном разделе - реализация двух методов решения
системы линейных уравнений (метод Гаусса-Жордана, метод Крамера), сравнение и
построение графика увеличения времени решения системы и объема занимаемой
памяти с ростом размерности системы.
Метод Гаусса-Жордана заключается в том, что с помощью элементарных
преобразований система уравнений приводится к равносильной системе треугольного
вида, из которой последовательно, начиная с последних (по номеру), находятся
все переменные системы.
Метод Крамера - способ решения с числом уравнений равным числу
неизвестных с ненулевым главным определителем матрицы коэффициентов системы.
Программа была реализована на языке C. Среда разработки - Visual Studio 2012.
Текст программы:
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <omp.h>
#include
<locale.h>time_on_gaus,time_off_gaus,time_on_cramer,time_off_cramer;print_matrix(int
str,int stb,float **mass)//вывод матрицы в консоль
{(int i=0;i<str;i++)
{(int j=0;j<stb;j++)("a[%d][%d]=%.2f
\t",i,j,mass[i][j]);("\n");
}("\n");
}
// Решениеgaus(int str,float
**mass,float *x)
{i,j,k;
//прямой ход
for(i=0;i<str;i++)
{a=mass[i][i];(j=i+1;j<str;j++)
{b=mass[j][i];(k=i;k<str+1;k++)[j][k]=mass[i][k]*b-mass[j][k]*a;
}
}
//обратный ход(i=str-1;i>=0;i--)
{summ=0.;(j=i+1;j<str;j++)+=mass[i][j]*x[j];=mass[i][str]-summ;(mass[i][i]==0)0;[i]=summ/mass[i][i];
}1;
}gaus_det(int str,float **mass,float *det)
{i,j,k;
*det=1.0f;
//создаём копию матрицы, так как элементы матрицы мы
будем использовать повторно
float
**copy_mass=(float**)malloc(str*sizeof(float));(i=0;i<str;i++)
{_mass[i]=(float*)malloc(str*sizeof(float));(j=0;j<str;j++)_mass[i][j]=mass[i][j];
}
//прямой ход метод Гаусса(i=0;i<str;i++)
{(j=i+1;j<str;j++)
{(copy_mass[i][i]==0)
{( int i=0; i<str;
i++)(copy_mass[i]);(copy_mass);0;
}b=copy_mass[j][i]/copy_mass[i][i];(k=i;k<str;k++)_mass[j][k]=copy_mass[j][k]-copy_mass[i][k]*b;
}
*det *= copy_mass[i][i];//вычисление определителя
}( int i=0; i<str;
i++)(copy_mass[i]);(copy_mass);1;
}main()
{str,stb;=stb=0;**mass;*x;*in;*
logfile;*file_name = "text.txt";*file_name1 =
"text1.txt";*file_name2 = "text2.txt";(int
chet=0;chet<3;chet++)
{(chet==0) printf( "Error 1: open file
%s\n", file_name);(chet==1) printf( "Error 1: open file %s\n",
file_name1);(chet==2) printf( "Error 1: open file %s\n",
file_name2);();1;
}
// чтение размеров матрицы(in, "%d
%d", &str, &stb);=(float**)malloc(str*sizeof(float)); // память под массив указателей на строки( int
i=0; i<str; i++)[i] = (float*)malloc(stb*sizeof(float)); // память под каждую строку( int
i=0; i<str; i++) // чтение матрицы(int j=0;
j<stb;j++)(in,"%f",&mass[i][j]);(in);(LC_ALL,"Russian");("_______________Матрица_______________\n");_matrix(str,stb,mass);
// печать матрицы
printf("\n_______________Решение методом
Гауса_______________\n");
x = (float *)malloc( sizeof(float)*str
);_on_gaus = omp_get_wtime();
if(gaus(str,mass,x)==1)//решение системы линейных
уравнений методом Гаусса и
//печать результата при удачном выполнение
{
time_off_gaus = omp_get_wtime();(int
i=0;i<str;i++)("x[%d]=%.2f \t",i+1,x[i]);
printf("\n");//вывод результата
}
{("Ошибка\n");
}("\n_______________Решение методом
Крамера_______________\n");
float *det=(float *)malloc(
sizeof(float)*(stb+1) );//массив определителей
float *t=(float *)malloc( sizeof(float)*str
);//временная переменная для хранения столбца матрицы
time_on_cramer = omp_get_wtime();(int i=0;i<stb;i++)
{(gaus_det(str,mass,&det[i])!=1)//вычисление
определителя используя метод Гаусса
{("Ошибка\n");
// освобождение памяти( int i=0; i<str;
i++)(mass[i]);(mass);(det);(t);();
return 0;
}(int j=0;j<str;j++)//последовательная замена
столбцов матрицы
{(i>0)[j][i-1]=t[j];//восстанавливаем значение
столбца[j]=mass[j][i];//сохраняем значения i - столбца матрицы в переменной
t[j][i]=mass[j][stb-1];//в i - столбец матрицы записываем столбец свободных
членов
}
}_off_cramer = omp_get_wtime();(int
i=1;i<stb;i++)("x[%d]=%.2f \t",i,det[i]/det[0]);//вывод результата("\n\n");=
(FILE *)fopen("logfile.txt",
"a");(logfile,"%lf\t%lf\n",time_off_gaus-time_on_gaus,time_off_cramer-time_on_cramer);(logfile);
// освобождение памяти( int i=0; i<str;
i++)(mass[i]);(mass);(x);(det);(t);
}();0;
}
Результаты работы программы:
График:
4. ЭНТРОПИЯ
ФАЙЛОВ
Информационная энтропия - мера неопределённости или непредсказуемости
информации, неопределённость появления какого-либо символа первичного алфавита.
При отсутствии информационных потерь численно равна количеству информации на
символ передаваемого сообщения. Например, в последовательности букв,
составляющих какое-либо предложение на русском языке, разные буквы появляются с
разной частотой, поэтому неопределённость появления для некоторых букв меньше,
чем для других. Если же учесть, что некоторые сочетания букв встречаются очень
редко, то неопределённость уменьшается еще сильнее.
Задачи, которые стоят в данном разделе - реализация алгоритма расчета
энтропии файлов с заданным расширением и построение графика зависимости времени
расчета от размера входного файла.
Программа была реализована на языке C++. Среда разработки - Visual Studio 2012.
В начале функции были введены переменные некого файлового потока, количества
символов в тексте, массив частот символов и саму энтропию (entr). Затем был
реализован ввод имени файла для его анализа. Открываем файл в режиме чтения и
вводим логический оператор if для
того случая, если файл не откроется. Затем читаем файл посимвольно, подсчитывая
при этом частоту символов. Если символ не является последним в файле, то
переходим к следующему символу, если является - закрываем файл. Затем был
реализован сам расчет энтропии с замером времени. В конце функции процесс
вывода на экран результатов энтропии, а также времени расчета.
Текст программы:
#include <iostream>
#include <fstream>
#include <string>
#include <math.h>
#include <omp.h>
#include <conio.h>namespace std;main()
{f;file_name;total=0;code[256] =
{0};entr=0,;t1,t2;<< "Input file name: " ;>>
file_name;.open( file_name.c_str(), ios::in | ios::binary);( !f )
{<< "Error 1: open input file
" << file_name << endl;1;
}= omp_get_wtime();ch;.unsetf(ios::skipws);(
!f.eof() )
{>> ch;( !f.eof() )
{[(int)ch]++;++;
}
}.close();( int i=0; i < 256; i++ )
{( code[i] == 0
);=code[i]/(float)total;=prob*log(prob)/log(2.0f);
}= omp_get_wtime();<< "Bytes:
" << total << endl;.setf(ios::fixed);.precision(3);<<
"Entropy: " << entr << endl;.precision(10);<<
"Time: " << t2-t1 << endl;
_getch();0;
}
Результаты работы программы.
Окно вывода программы:
График зависимости времени расчета от размера входного файла:
5. определениЕ числа Пи МЕТОДОМ МОНТЕ-КАРЛО
Задачи, реализованные в данном разделе - реализация алгоритма определения
значения числа Пи методом Монте-Карло (методом статистических испытаний) и
построение графика зависимости точности расчета значения интеграла в
зависимости от числа испытаний.
При определении значения числа Пи метод Монте-Карло - самый простой и
легкий в реализации метод.
Рассмотрим произвольный квадрат с центром в начале координат и вписанный
в него круг. Будем рассматривать только первую координатную четверть. В ней
будет находиться четверть круга и четверть квадрата. Обозначим радиус круга r,
тогда четверть квадрата тоже будет квадратом(очевидно) со стороной r.
Будем случайным образом выбирать точки в этом квадрате и считать
количество точек, попавших в четверть круга с помощью функции randomize. Благодаря теории
вероятности мы знаем, что отношение попаданий в четверть круга к попаданиям 'в
молоко' равно отношению площадей - Пи/4. Чем больше взятых наугад точек мы
проверим, тем точнее будет отношение площадей.
Данный метод был реализован на языке Pascal. Среда разработки - PascalABC.NET.
Текст программы:
uses Crt;=10000000;=46340;=46340*46340;,pass : LongInt;,y :
real;
{$F+};:=0;i:=1 to n do:=Random(r+1);:=Random(r+1);( x*x+y*y
< r2 ) then INC(pass);;(GREEN);('Число ПИ равно: ',(pass/i*4):0:5);
ReadLn;.
Результат работы программы:
График:
заключение
В рамках контрольной работы были изучены различные алгоритмы решения
задач на языках программирования высокого уровня, а также принцип построения
графиков по итогам реализации алгоритмов.
Было выполнено 5 заданий:
. Реализация интегрирования функции вида f(x) методами
прямоугольников, трапеций, Симпсона.
. Построение графика сравнения точности решения методов
интегрирования в зависимости от количества разбиений.
. Реализация методов решения системы линейных уравнений
(GaussJordan, Cramer). Построение графика увеличения времени решения системы и
объема занимаемой памяти с ростом размерности системы.
. Реализация алгоритма расчета энтропии файлов с заданным
расширением. Построение графика зависимости времени расчета от размера входного
файла.
. Реализация алгоритма определения значения числа Пи методом
Монте-Карло (методом статистических испытаний). Построение графика зависимости
точности расчета значения интеграла в зависимости от числа испытаний.
Задания №1, 2, 3 были реализованы на языке программирования C. Задание №4
было реализовано на языке программирования Java. Задание №5 было реализовано на
языке программирования Pascal.
список
литературы
1. Нахождение
интеграла с заданной точностью на C. Метод Симпсона. - SourcePrograms.Ru ©
2011-2014 - . - Режим доступа :
http://sourceprograms.ru/industries_programming/calculable_mathematics/15-nahozhdenie-integrala-s-zadannoy-tochnostyu-na-c-metod-simpsona.html.
− Загл. с экрана.
. МЕТОД
ЖОРДАНА-ГАУССА - . - Режим доступа :
http://ios.sseu.ru/public/eresmat/metod/met5/parmet5_3.htm. − Загл. с
экрана.
. Энтропия
и WinRAR - TM © 2006-2014 - . - Режим доступа :
http://habrahabr.ru/post/180803. − Загл. с экрана.
. Вычисление
с нужной точностью числа Пи - Kantor Ilia - . - Режим доступа :
http://algolist.manual.ru/maths/count_fast/pi.php. − Загл. с экрана