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

Размещено на http://www.allbest.ru/

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение

Высшего профессионального образования

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

(ПензГТУ)

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

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

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

КОНТРОЛЬНАЯ РАБОТА №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.

6. 

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

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

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

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

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

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

функция алгоритм энтропия интегрирование

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

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

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

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

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

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

#include <stdio.h>

#include <math.h>

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 a\n");

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 <stdio.h>

#include <math.h>

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 a\n");

scanf("%lf%lf%lf", &a,&b,&number_a);

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

fprintf(file, "n\tRectangle\tTrapeze\tSimpson\n");

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, "%d\t%lf\t%lf\t%lf\n",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 <stdio.h>

#include <conio.h>

#include <malloc.h>

#include <omp.h>

#include <locale.h>

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<str;i++)

{

for(int j=0;j<stb;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<str;i++)

{

double a=mass[i][i];

for(j=i+1;j<str;j++)

{

float b=mass[j][i];

for(k=i;k<str+1;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<str;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<str;i++)

{

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

for(j=0;j<str;j++)

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

}

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

for(i=0;i<str;i++)

{

for(j=i+1;j<str;j++)

{

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

{

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

free(copy_mass[i]);

free(copy_mass);

return 0;

}

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

for(k=i;k<str;k++)

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

}

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

}

for( int i=0; i<str; 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 %s\n", file_name);

if (chet==1) printf( "Error 1: open file %s\n", file_name1);

if (chet==2) printf( "Error 1: open file %s\n", file_name2);

getch();

return 1;

}

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

fscanf(in, "%d %d", &str, &stb);

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

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

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

for( int i=0; i<str; i++) // чтение матрицы

for(int j=0; j<stb;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<str;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<stb;i++)

{

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

{

printf("Ошибка\n");

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

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

free(mass[i]);

free(mass);

free(det);

free(t);

getch();

return 0;

}

for(int j=0;j<str;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<stb;i++)

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

printf("\n\n");

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

fprintf(logfile,"%lf\t%lf\n",time_off_gaus-time_on_gaus,time_off_cramer-time_on_cramer);

fclose(logfile);

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

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

free(mass[i]);

free(mass);

free(x);

free(det);

free(t);

}

getch();

return 0;

}

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



График:

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

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

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

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

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

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

#include <iostream>

#include <fstream>

#include <string>

#include <math.h>

#include <omp.h>

#include <conio.h>

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=10000000;

r=46340;

r2=46340*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) методами прямоугольников, трапеций, Симпсона.

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

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

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

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

Задания №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. ? Загл. с экрана.

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

3. Энтропия и WinRAR - TM © 2006-2014 - . - Режим доступа : http://habrahabr.ru/post/180803. ? Загл. с экрана.

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

Размещено на Allbest.ru