89069

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

Контрольная

Информатика, кибернетика и программирование

Цель данной контрольной работы – актуализация знаний в области языков программирования. Основное задание – реализовать алгоритмы решения задач на языках программирования высокого уровня. В рамках контрольной работы было выполнено 5 заданий: Реализация интегрирования функции вида f(x) методами прямоугольников, трапеций, Симпсона.

Русский

2015-05-09

501 KB

3 чел.

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

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

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

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

(ПензГТУ)

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

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

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

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

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

Выполнил: студент группы 13ИС2Б

Чинков М.Ю.

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

Володин К.И.

Пенза 2014

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 3

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

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

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

4. ЭНТРОПИЯ 15

5. МЕТОД МОНТЕ-КАРЛО 18

заключение 20

список литературы 21


ВВЕДЕНИЕ

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

В рамках контрольной работы было выполнено 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 <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;

}

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


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

Задачи, решенные в данном разделе – построение графика сравнения точности решения методов интегрирования (метод прямоугольников, метод трапеций, метод Симпсона, реализованные в разделе №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;

}

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

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

График:

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

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

(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;

}

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

График:


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

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

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

Программа была реализована на языке 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;

}

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

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

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


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

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

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

Рассмотрим произвольный квадрат с центром в начале координат и вписанный в него круг. Будем рассматривать только первую координатную четверть. В ней будет находиться четверть круга и четверть квадрата. Обозначим радиус круга 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. − Загл. с экрана


 

А также другие работы, которые могут Вас заинтересовать

79356. Сценарий школьного праздника «Последний звонок» 81.5 KB
  Звучит музыка выходят одиннадцатиклассники. Так пусть начнет сегодня торжество Своим свободным голосом держава Звучит Гимн Украины Вед: Сегодня наш праздник мы назвали не совсем традиционно Школьная моя семья. Звучит музыка выходят выпускники читают слова о первом учителе.
79363. Ну-мо, хлопці! 289.5 KB
  Представлення журі. Представлення учасників змагань. Оголошення програми змагань. Проведення змагань: конкурс вітальних листівок; воєнізована естафета; музична пауза; одягання протигазу у складі взводу; бліц – опитування...