SHARE
TWEET

Untitled

vadimk772336 Oct 21st, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <math.h>
  3. #include <vector>
  4. #include <Windows.h>
  5. #include <stdlib.h>
  6. #include <fstream>
  7. #include <string.h>
  8.  
  9. using namespace std;
  10.  
  11. const double PI = 3.1415926535897932384626433832795;
  12.  
  13. typedef double(*functiontype)(double x);
  14.  
  15.  
  16. typedef struct Node
  17. {
  18.     double x, y;
  19. } Node;
  20.  
  21.  
  22. typedef double(*method)(double x, Node *Array, int Count);
  23.  
  24. typedef struct Interval
  25. {
  26.     double InitialNode, EndNode;
  27. } Interval;
  28.  
  29. int Factorial(int n)
  30. { // Факториал
  31.     int x = 1;
  32.     for (int i = 1; i <= n; i++)
  33.     {
  34.         x *= i;
  35.     }
  36.     return x;
  37. }
  38.  
  39. double Myfunc(double x)
  40. {
  41.     return (x*x);
  42. }
  43.  
  44. double exponenta(double x)
  45. { // Экспонента
  46.     return exp(x);
  47. }
  48.  
  49. void ValueUniformTable(functiontype* f, Node* Array, double Initial, double End, int Count) // Передаем массив в который все будет записано
  50. { // Создание равномерной таблицы значений
  51.     double step = abs(Initial - End) / (Count - 1);
  52.     Array[0].x = Initial;
  53.     Array[0].y = (*f)(Array[0].x);
  54.    
  55.     for (int i = 1; i < Count; i++)
  56.     {
  57.         Array[i].x = Array[i - 1].x + step;
  58.         Array[i].y = (*f)(Array[i].x);
  59.        
  60.     }
  61. }
  62. double DividedDifference(int i, Node* Array) //Не понимаем алгоритм
  63. { // Разделенная разность
  64.     double DD = 0;
  65.     for (int j = 0; j <= i; j++)
  66.     {
  67.         double tmp = 1;
  68.         for (int k = 0; k <= i; k++)
  69.         {
  70.             if (k != j)
  71.                 tmp *= Array[j].x - Array[k].x;
  72.         }
  73.         DD += Array[j].y / tmp;
  74.     }
  75.  
  76.     return DD;
  77. }
  78.  
  79. void ValueChebyshevTable(functiontype* f, Node* Array, double Initial, double End, int Count)
  80. { // Создание таблицы Чебышевских значений
  81.     for (int i = 0; i < Count; i++)
  82.     {
  83.         Array[i].x = ((End + Initial) / 2)
  84.             + ((End - Initial) / 2) * cos(((2 * i + 1) * PI) / (2 * (Count + 1)));
  85.         Array[i].y = (*f)(Array[i].x);
  86.     }
  87. }
  88.  
  89. void get_koef_polynom(double* mas, double* res, int n, int k) // k - кол во скобок для раскрытия (сколько надо, напр в ньютоне нужно не все), n - максимальное кол-во скобок
  90. {
  91.     int i;
  92.     double* anx = new double[k+1];
  93.     double* ann = new double[k+1];
  94.     res[0] = mas[0];
  95.     res[1] = 1;
  96.     int j;
  97.     for (j = 0; j <= k; j++)
  98.     {
  99.         anx[j] = 0.0;
  100.     }
  101.  
  102.     for (j = 0; j < k; j++)
  103.     {
  104.         ann[j] = 0.0;
  105.     }
  106.     for (i = 1; i < k; i++)
  107.         for (j = 0; j <= i + 1; j++)        //Спросить у Антона работу алгоритма
  108.         {
  109.             anx[j + 1] = res[j];
  110.             ann[j] = res[j] * mas[i];
  111.             res[j] = anx[j] + ann[j];
  112.         }
  113. }
  114.  
  115. //Возвращает число, возведенное в cтепень i
  116. double get_degree(double x, int degree) {
  117.     int i;
  118.     double y = x;
  119.     if (degree == 0)
  120.         return 1;
  121.  
  122.     for (i = 0; i < degree - 1; i++)
  123.         y *= x;
  124.     return y;
  125. }
  126.  
  127. double round(double x) {
  128.     if (x < 0.0000000001)
  129.         x = 0.0;
  130.     return x;
  131. }
  132.  
  133. // Полином Лагранжа в точке
  134. double PolynomLG_dot(double x, Node *Array, int Count)
  135. {
  136.     double Polynom = 0;
  137.     for (int i = 0; i < Count; i++)
  138.     { // Счетчик по функциям l_i
  139.         double Li = 1;
  140.         for (int j = 0; j < Count; j++)
  141.         { // Счетчик по x_j
  142.             if (i != j) Li *= (x - Array[j].x) / (Array[i].x - Array[j].x);
  143.         }
  144.         Polynom += Array[i].y * Li;
  145.     }
  146.     return Polynom;
  147. }
  148.  
  149. //Полином Ньютона в точке
  150. double PolynomN_dot(double x, Node *Array, int Count)
  151. {
  152.     double Result = Array[0].y, dd;
  153.     for (int i = 1; i < Count; i++)
  154.     {
  155.         dd = 0.0;
  156.         dd = DividedDifference(i, Array);
  157.         for (int k = 0; k < i; k++) dd = dd * (x - Array[k].x);
  158.         Result += dd; // Домножаем разделенную разность на скобки (x-x[0])...(x-x[i-1])
  159.     }
  160.  
  161.     return Result;
  162. }
  163.  
  164.  
  165.  
  166. //То же самое но значение считает сразу вточке
  167. void table_in_file2(Node* MyArray, Node* Array, int MyCount, int Count, string file_name, string file_name_error, string method_name) {
  168.     int k, j;
  169.     double y_value, x_value;
  170.  
  171.     ofstream fout(file_name); //Лежит таблица от интерполяции (по заданным точкам) по выбранному методу для графика (точки сами выбрали)
  172.     ofstream pogr(file_name_error);
  173.  
  174.     method Func = PolynomN_dot;
  175.     if (method_name == "Lagrange")
  176.         method Func = PolynomLG_dot;
  177.    
  178.     for (k = 0; k < MyCount; k++) {
  179.         x_value = MyArray[k].x;
  180.         fout << x_value << " ";
  181.         pogr << x_value << " ";
  182.         y_value = Func(x_value, Array, Count);
  183.        
  184.  
  185.         fout << y_value << endl;
  186.  
  187.         pogr << abs(y_value - MyArray[k].y) << endl;
  188.  
  189.     }
  190.  
  191.     fout.close();
  192. }
  193.  
  194. void orig_table_in_file(Node* Array, int Count) { // Функция берет таблицу иксов и игриков, количество точек в которых считаем знач полинома (мб убрать) и коэфф полинома,
  195.                                                                        // По итоге имеем файл с 2 столбацами: х и у, по которому гну пло
  196.     int k;
  197.     double y_value, x_value;
  198.  
  199.     ofstream fout("D:/Original_graphic.txt");
  200.  
  201.     for (k = 0; k < Count; k++) { //n иксов подставляев в полином степени n-1
  202.         x_value = Array[k].x;
  203.         fout << x_value << " ";
  204.         y_value = Array[k].y;
  205.         fout << y_value << endl;
  206.     }
  207.  
  208.     fout.close();
  209. }
  210.  
  211.  
  212.  
  213. double W(double x, int n, Node* Array)
  214. { // Полином вида: (x - x1) * (x - x2) * ... * (x - xn)
  215.     double w = 1;
  216.     for (int i = 1; i <= n; i++)
  217.     {
  218.         w *= x - Array[i].x;
  219.     }
  220.     return w;
  221. }
  222.  
  223.  
  224.  
  225. void ApproximateError(functiontype *Function, double Initial, double End, Node *Array, int Count)
  226. { // Приближенная погрешность
  227.  
  228.     for (double x = Initial; x <= End; x += 0.01f)
  229.     {
  230.         abs(MaxВerivative  * W(x, Count, Array) / Factorial(Count + 1));
  231.     }
  232. }
  233.  
  234. void PolynomLG(Node* Array, int Count, double* &mas_coeff_polynom) //Заполняет массив коэффициентами интерполяционного полинома
  235. {
  236.     int i, j, l, p, z, c;
  237.     double* tmp_massiv_coeff = new double[Count]; // Хранит коэффиценты Li                          
  238.     double* brackets_massiv = new double[Count - 1]; //Для раскрытия (x-x0)...(x-xn), умноженных на коэффициент
  239.    
  240.     double k;
  241.  
  242.     for (j = 0; j < Count; j++)
  243.     {
  244.         mas_coeff_polynom[j] = 0.0;
  245.     }
  246.  
  247.     for (i = 0; i < Count; i++)
  248.     {
  249.         c = 0; //Счетчик для числителя, т.к. иначе при счете по P будет дырка в массиве и get_koef_polynom не сможет посчитать (т.е. с делает сдвиг на  1 ячейку)
  250.         for (j = 0; j < Count - 1; j++)
  251.         {
  252.             brackets_massiv[j] = 0.0;
  253.             tmp_massiv_coeff[j] = 0.0;
  254.         }
  255.         tmp_massiv_coeff[Count - 1] = 0.0;
  256.         k = Array[i].y;
  257.         for (p = 0; p < Count; p++)
  258.         {
  259.             if (p != i)
  260.             {
  261.                 k *= 1.0 / (Array[i].x - Array[p].x);
  262.                 brackets_massiv[c] = 0.0 - Array[p].x;
  263.                 c++;
  264.             }
  265.         }
  266.  
  267.         get_koef_polynom(brackets_massiv, tmp_massiv_coeff, Count - 1, Count - 1); //Раскрываем все скобки из возможных (по Лагранжу так)
  268.         for (i = 0; j < Count; j++)
  269.         {
  270.             mas_coeff_polynom[j] += tmp_massiv_coeff[j] * k;
  271.         }
  272.  
  273.     }
  274.  
  275.  
  276. }
  277.  
  278.  
  279. void PolynomN(Node* Array, int Count, double* &mas_coeff_polynom)
  280. {
  281.     int j;
  282.     double dd;
  283.     double* tmp_massiv_coeff = new double[Count]; // массив А0...An конечных коэфф для одного шага цикла сколько точек, столько и коэфф
  284.     double* brackets_massiv = new double[Count - 1]; //массив X0,,,Хn
  285.  
  286.     int i;
  287.  
  288.     for (int j = 0; j < Count - 1; j++)
  289.     {
  290.         mas_coeff_polynom[j] = 0.0;
  291.         brackets_massiv[j] = 0.0;
  292.     }
  293.  
  294.     mas_coeff_polynom[Count - 1] = 0.0;
  295.  
  296.     for (int j = 0; j < Count - 1; j++)
  297.     { //Кладем все иксы
  298.         brackets_massiv[j] = 0.0 - Array[j].x;
  299.     }
  300.  
  301.     mas_coeff_polynom[0] = Array[0].y; // 0 индекс хранит свободный член итого многочлена
  302.  
  303.     for (i = 1; i < Count; i++)
  304.     {
  305.         for (j = 0; j < Count; j++)
  306.         {
  307.             tmp_massiv_coeff[j] = 0.0;
  308.         }
  309.  
  310.         dd = DividedDifference(i, Array); //Ищем итую РР
  311.  
  312.         get_koef_polynom(brackets_massiv, tmp_massiv_coeff, Count - 1, i); //Возвращает кф при перемножении (х-Х0)...(х-Хi+1)
  313.  
  314.         for (j = 0; j < Count; j++)
  315.         {
  316.             mas_coeff_polynom[j] += tmp_massiv_coeff[j] * dd;
  317.  
  318.         }
  319.  
  320.     }
  321.  
  322. }
  323.  
  324. double DFunc(functiontype* func, double x,
  325.     int n) //возварщает проивзодную нго порядка как константу типа дабл
  326. { // Производная функции
  327.     double h = 0.00001;
  328.     if (n == 1)
  329.     {
  330.         return ((*func)(x + h) - (*func)(x)) / h;
  331.     }
  332.     else
  333.     {
  334.         return (DFunc(func, x + h, n - 1) - DFunc(func, x, n - 1)) / h;
  335.     }
  336. }
  337.  
  338. double test(functiontype* func, double x, int n, long double h)
  339. { // Производная функции
  340.     h = 0.0001;
  341.     while (n > 1)
  342.     {
  343.         return (test(func, x + h, n - 1, h / pow(10, -2))
  344.             - test(func, x - h, n - 1, h / pow(10, -2)))
  345.             / 2 * h;
  346.     }
  347.     if (n == 1)
  348.     {
  349.         return ((*func)(x + h) - (*func)(x - h)) / 2 * h;
  350.     }
  351. }
  352.  
  353.  
  354.  
  355. int main()
  356. {
  357.  
  358.     setlocale(LC_ALL, "RUS");
  359.  
  360.     //ПОСТРОЕНИЕ ДАННЫХ
  361.     Interval Interval;
  362.     int CountNodes, MyNodes = 100;
  363.     functiontype Func = &Myfunc;
  364.  
  365.     cout << "Enter the interval: " << endl;
  366.     cin >> Interval.InitialNode >> Interval.EndNode;
  367.     cout << "Enter the number of nodes: " << endl;
  368.     cin >> CountNodes;
  369.  
  370.  
  371.     double* mas_coeff_polynomNew = new double[CountNodes];
  372.     double* mas_coeff_polynomLag = new double[CountNodes];
  373.     Node *ArrayUniformNodes = new Node[CountNodes];// Массив с равномерными // узлами
  374.     Node *Graph_ArrayUniformNodes = new Node[MyNodes];
  375.     Node* ArrayChebyshevNodes = new Node[CountNodes]; // Массив с Чебышевскими узлами
  376.     Node *Graph_ArrayformNodes = new Node[100]; //Массив где будет много точек для построение ориг графика
  377.  
  378.     ValueUniformTable(&Func, ArrayUniformNodes, Interval.InitialNode, Interval.EndNode, CountNodes); // Заполнение таблицы равномерных значений
  379.     ValueUniformTable(&Func, Graph_ArrayUniformNodes, Interval.InitialNode, Interval.EndNode, MyNodes);
  380.     ValueChebyshevTable(&Func, ArrayChebyshevNodes, Interval.InitialNode, Interval.EndNode, CountNodes); // Заполнение таблицы Чебышевских значений
  381.  
  382.  
  383.  
  384.     cout << endl;
  385.     //PolynomLG(ArrayUniformNodes, CountNodes, mas_coeff_polynom);
  386.     cout << endl;
  387.     //PolynomN(ArrayUniformNodes, CountNodes,mas_coeff_polynom);
  388.  
  389.     //Запись точек в файл для построения
  390.     table_in_file2(Graph_ArrayUniformNodes, ArrayUniformNodes, MyNodes, CountNodes, "D:/Lagrange.txt", "D:/Pogr_Lagrange.txt", "Lagrange");
  391.     table_in_file2(Graph_ArrayUniformNodes, ArrayUniformNodes, MyNodes, CountNodes, "D:/Newton.txt", "D:/Pogr_Newton.txt", "Newton");
  392.     orig_table_in_file(Graph_ArrayUniformNodes, MyNodes);
  393.  
  394.  
  395.  
  396.     // Приближенная погрешность
  397.     //ApproximateError(&Func, Interval.InitialNode, Interval.EndNode, ArrayUniformNodes, CountNodes);
  398.  
  399.     //system("pause");
  400.     return 0;
  401. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top