Advertisement
Urbani

Untitled

Jun 28th, 2016
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.49 KB | None | 0 0
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <limits>
  7. #include <cstdlib>
  8.  
  9. using namespace std;
  10.  
  11. #include <cstdlib>
  12. #include <cmath>
  13. #include <limits>
  14.  
  15. class cubic_spline
  16. {
  17. private:
  18.     // Структура, описывающая сплайн на каждом сегменте сетки
  19.     struct spline_tuple
  20.     {
  21.         double a, b, c, d, x;
  22.     };
  23.  
  24.     spline_tuple *splines; // Сплайн
  25.     std::size_t n; // Количество узлов сетки
  26.  
  27.     void free_mem(); // Освобождение памяти
  28.  
  29. public:
  30.     cubic_spline(); //конструктор
  31.     ~cubic_spline(); //деструктор
  32.  
  33.     // Построение сплайна
  34.     // x - узлы сетки, должны быть упорядочены по возрастанию, кратные узлы запрещены
  35.     // y - значения функции в узлах сетки
  36.     // n - количество узлов сетки
  37.     void build_spline(const double *x, const double *y, std::size_t n);
  38.  
  39.     // Вычисление значения интерполированной функции в произвольной точке
  40.     double f(double x) const;
  41. };
  42.  
  43. cubic_spline::cubic_spline() : splines(NULL)
  44. {
  45.  
  46. }
  47.  
  48. cubic_spline::~cubic_spline()
  49. {
  50.     free_mem();
  51. }
  52.  
  53. void cubic_spline::build_spline(const double *x, const double *y, std::size_t n)
  54. {
  55.     free_mem();
  56.  
  57.     this->n = n;
  58.  
  59.     // Инициализация массива сплайнов
  60.     splines = new spline_tuple[n];
  61.     for (std::size_t i = 0; i < n; ++i)
  62.     {
  63.         splines[i].x = x[i];
  64.         splines[i].a = y[i];
  65.     }
  66.     splines[0].c = 0.;
  67.  
  68.     // Решение СЛАУ относительно коэффициентов сплайнов c[i] методом прогонки для трехдиагональных матриц
  69.     // Вычисление прогоночных коэффициентов - прямой ход метода прогонки
  70.     double *alpha = new double[n - 1];
  71.     double *beta = new double[n - 1];
  72.     double A, B, C, F, h_i, h_i1, z;
  73.     alpha[0] = beta[0] = 0.;
  74.     for (std::size_t i = 1; i < n - 1; ++i)
  75.     {
  76.         h_i = x[i] - x[i - 1], h_i1 = x[i + 1] - x[i];
  77.         A = h_i;
  78.         C = 2. * (h_i + h_i1);
  79.         B = h_i1;
  80.         F = 6. * ((y[i + 1] - y[i]) / h_i1 - (y[i] - y[i - 1]) / h_i);
  81.         z = (A * alpha[i - 1] + C);
  82.         alpha[i] = -B / z;
  83.         beta[i] = (F - A * beta[i - 1]) / z;
  84.     }
  85.  
  86.     splines[n - 1].c = (F - A * beta[n - 2]) / (C + A * alpha[n - 2]);
  87.  
  88.     // Нахождение решения - обратный ход метода прогонки
  89.     for (std::size_t i = n - 2; i > 0; --i)
  90.         splines[i].c = alpha[i] * splines[i + 1].c + beta[i];
  91.  
  92.     // Освобождение памяти, занимаемой прогоночными коэффициентами
  93.     delete[] beta;
  94.     delete[] alpha;
  95.  
  96.     // По известным коэффициентам c[i] находим значения b[i] и d[i]
  97.     for (std::size_t i = n - 1; i > 0; --i)
  98.     {
  99.         double h_i = x[i] - x[i - 1];
  100.         splines[i].d = (splines[i].c - splines[i - 1].c) / h_i;
  101.         splines[i].b = h_i * (2. * splines[i].c + splines[i - 1].c) / 6. + (y[i] - y[i - 1]) / h_i;
  102.     }
  103. }
  104.  
  105. double cubic_spline::f(double x) const
  106. {
  107.     if (!splines)
  108.         return std::numeric_limits<double>::quiet_NaN(); // Если сплайны ещё не построены - возвращаем NaN
  109.  
  110.     spline_tuple *s;
  111.     if (x <= splines[0].x) // Если x меньше точки сетки x[0] - пользуемся первым эл-том массива
  112.         s = splines + 1;
  113.     else if (x >= splines[n - 1].x) // Если x больше точки сетки x[n - 1] - пользуемся последним эл-том массива
  114.         s = splines + n - 1;
  115.     else // Иначе x лежит между граничными точками сетки - производим бинарный поиск нужного эл-та массива
  116.     {
  117.         std::size_t i = 0, j = n - 1;
  118.         while (i + 1 < j)
  119.         {
  120.             std::size_t k = i + (j - i) / 2;
  121.             if (x <= splines[k].x)
  122.                 j = k;
  123.             else
  124.                 i = k;
  125.         }
  126.         s = splines + j;
  127.     }
  128.  
  129.     double dx = (x - s->x);
  130.     return s->a + (s->b + (s->c / 2. + s->d * dx / 6.) * dx) * dx; // Вычисляем значение сплайна в заданной точке.
  131. }
  132.  
  133. void cubic_spline::free_mem()
  134. {
  135.     delete[] splines;
  136.     splines = NULL;
  137. }
  138.  
  139. int mounth_to_int(string mounth){
  140.     if(mounth == "January") return 1;
  141.     if(mounth == "February" ) return 2;
  142.     if(mounth == "March" ) return 3;
  143.     if(mounth == "April" ) return 4;
  144.     if(mounth == "May" ) return 5;
  145.     if(mounth == "June" ) return 6;
  146.     if(mounth == "July" ) return 7;
  147.     if(mounth == "August" ) return 8;
  148.     if(mounth == "September" ) return 9;
  149.     if(mounth == "October" ) return 10;
  150.     if(mounth == "November" ) return 11;
  151.     return 12;
  152. }
  153. int main() {
  154.     /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
  155.     int N;
  156.     cin >> N;
  157.     string line;
  158.     vector<vector<string>> splitline(N, vector<string>(4));
  159.     vector<double> mean;
  160.     vector<double> diff;
  161.     vector<int> dates;
  162.     vector<pair<int,int>> miss;
  163.     splitline.resize(N);
  164.     getline(cin, line);
  165.     getline(cin, line);
  166.     for(int i = 0; i < N; i++){
  167.         cin >> splitline[i][0] >> splitline[i][1] >> splitline[i][2] >> splitline[i][3];
  168.        
  169.     }
  170.     for(int i =0; i < N; i++){
  171.         if(splitline[i][2][0] == 'M' || splitline[i][3][0] == 'M'){
  172.             if(splitline[i][2][0] == 'M') miss.push_back(pair<int,int> (12 * atoi(splitline[i][0].c_str()) + mounth_to_int(splitline[i][1]),2));
  173.             else miss.push_back(pair<int,int> (12 * atoi(splitline[i][0].c_str()) + mounth_to_int(splitline[i][1]),3));
  174.         }
  175.         else {
  176.             mean.push_back((atof(splitline[i][2].c_str()) + atof(splitline[i][3].c_str()))/2);
  177.             diff.push_back(atof(splitline[i][2].c_str()) - atof(splitline[i][3].c_str() ) );
  178.             dates.push_back(12 * atoi(splitline[i][0].c_str()) + mounth_to_int(splitline[i][1]));
  179.         }
  180.     }
  181.     cubic_spline cubic_mean;
  182.     cubic_spline cubic_diff;;
  183.     cubic_mean.build_spline(static_cast<double*> (&dates[0]), static_cast<double*> (&mean[0]), dates.size());
  184.     cubic_mean.build_spline(static_cast<double*> (&dates[0]), static_cast<double*> (&diff[0]), dates.size());
  185.     for(int i = 0; i< miss.size(); i++){
  186.         if(miss[i]->second == 2) cout << mean.f(miss[i]->firsr) - diff(miss[i]->first)/2 << endl;
  187.         else  cout << mean.f(miss[i]->firsr) + diff(miss[i]->first)/2 << endl;
  188.     }
  189.     return 0;
  190. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement