Задание

Исходные данные

По заданной последовательности значений функции y(x), представленной в виде массива, необходимо найти количество ее экстремумов.

Ход работы

1. Пусть функция представлена дискретной последовательностью значений . Тогда для любых трех последовательных значений функции с номерами справедливо

Для дискретного ряда значений функцию удобно ее производную представить в виде [1]

,        (1)

или

       (2)

Это так называемые формулы левых и правых разностей. В точках экстремума производная меняет знак, а значит, если i-я точка является точкой экстремума, то знаки выражений (1) и (2) будут различаться. Так как шаг постоянен, то из (1) и (2) получим

.        (3)

Выражение (3) и будет основой алгоритма решения поставленной задачи.

2. Следующим этапом является выбор подходящей структуры данных. Можно было бы выбрать контейнер std::vector [3 – 4]из стандартной библиотеки. Однако необходимую функциональность можно без труда реализовать самостоятельно, добавив при этом несколько полезных функций.

Пользовательская структура данных, инкапсулирующая массив должна [3]

динамически распределять память под массив и очищать ее за ненадобностью; обеспечивать стандартный доступ к элементам массива в С-стиле; обеспечивать стандартный вывод в поток вывода в С++-стиле.

Такой класс удобно реализовать как шаблонный [3 – 4]. Его листинг приведен ниже

//simple_vector. h

#ifndef _SIMPLE_VECTOR_H

#define _SIMPLE_VECTOR_H

#include <iostream>

#include <fstream>

#include <exception>

//Исключение при попытки обратится к пустому массиву

struct xInvalidAccess : public std::exception

{};

//Исключение при неправильном индексе элемента

struct xIndexOutOfRange : public std::exception

{};

//Тип данных для индексов и размеров

typedef unsigned int szint;

/**Шаблонный класс массив

*  Повторяет некоторую функциональность стандартного класса std::vector

*  Содержит ряд дополнительных возможностей, как то ввод элемента из консоли

*  и прочее

**/

template <class T>

class simple_vector

{

private:

       szint size;//размер

       szint capacity;//емкость

       T* data;//указатель на область памяти, где хранятся объекты массива

       /*

       * Метод для копирования данных из внешнего источника в данный объект

       */

       void copy_from(T* src, szint sz)

       {

               clear();

               resize(sz);

               if (src && sz > 0)

               {

                       for (szint i = 0; i < size; ++i)

                       {

                               data[i] = src[i];

                       }

               }

       }

       /*

       * Метод для увеличения емкости массива

       */

       void inc_capacity()

       {

               capacity += kIncrementSize;

               T* buff = new T[capacity];

               if (data)

               {

                       for (szint i = 0; i < size; ++i)

                               buff[i] = data[i];

                       delete[] data;

               }

               data = buff;

       }

public:

/*

       * Постоянная величина, на которую увеличивается емкость массива при заполнении

       */

       static szint kIncrementSize;

/*

       * Конструкторы

       */

       simple_vector()

               : size(0), capacity(0), data(NULL)

       {}

       

       simple_vector(T* src, szint sz)

       { copy_from(src, sz); }

       simple_vector(const simple_vector<T>& src)

       { copy_from(src. data, src. size); }

/*

       * Деструктор

       */

       ~simple_vector()

       { clear(); }

       simple_vector<T>& operator = (const simple_vector<T>& rhs)

       {

               if (&rhs!= this)

                       copy_from(rhs. data, rhs. size);

               

               return *this;

       }

       /*

       * Изменение размеров массива. Емкость и размер при этом совпадают

       */

       void resize(szint new_size)

       {

               if (size == new_size && new_size > 0)

                       return;

               T* buff = new T[new_size];

               

               if (data)

               {

                       for (szint i = 0; i < size && i < new_size; ++i)

                       {

                               buff[i] = data[i];

                       }

                       delete[] data;

               }

               data = buff;

               size = new_size;

               capacity = size;

       }

       /*

       * Очистка массива и освобождение занятой памяти

       */

       void clear()

       {

               if (data)

                       delete[] data;

               size = 0;

               capacity = 0;

       }

       /*

       * Перегруженные операторы доступа к элементам массива по индексу

       */

       T& operator [](szint index)

       {

               if (!data)

                       throw xInvalidAccess();

               

               if (index >= size)

                       throw xIndexOutOfRange();

               

               return data[index];

       }

       

       const T& operator [](szint index) const

       {

               if (!data)

                       throw xInvalidAccess();

               

               if (index >= size)

                       throw xIndexOutOfRange();

               return data[index];

       }

       /*

       * Оператор приведения к типу bool

       */

       operator bool () const

       {

               return data!= NULL;

       }

       /*

       * Метод, возвращающий текущий размер массива

       */

       szint get_size() const

       { return size; }

       /*

       * Метод, возвращающий емкость массива

       */

       szint get_capacity() const

       { return capacity; }

       /*

       * Метод для добавления элемента в массив

       * Возвращает индекс добавленного элемента

       */

       szint add(T item)

       {

               if (!size || size == capacity)

                       inc_capacity();

               data[size++] = item;

               return size - 1;

       }

       /*

       * Метод для поиска элемента в массиве

       * Возвращает индекс элемента или -1

       */

       int find(T item)

       {

               if (!data)

                       return -1;

               for (szint i = 0; i < size; ++i)

               {

                       if (data[i] == item)

                               return i;

               }

               

               return -1;

       }

       /*

       * Метод для удаления элемента с заданным индексом из массива

       */

       bool remove(szint index)

       {

               if (!data || !size)

                       return false;

               for (szint i = index; i < size - 1; ++i)

               {

                       data[i] = data[i + 1];

               }

               --size;

               return false;

       }

       /*

       * Метод, возвращающий признак пустоты массива

       */

       bool empty() const

       { return size == 0; }

       /*

       * Функция для вывода массива в поток вывода

       */

       template<class U>

       friend std::ostream& operator << (std::ostream& os, const simple_vector<U>& vector);

       /*

       * Метод для добавления элемента в массив

       */

       simple_vector<T>& operator << (const T& item)

       {

               add(item);

               return *this;

       }

};

template <class T>

szint simple_vector<T>::kIncrementSize = 16;

template<class T>

std::ostream& operator << (std::ostream& os, const simple_vector<T>& vector)

{

       for (szint i = 0; i < vector. get_size(); ++i)

       {

               if (i > 0)

                       os << " ";

               os << vector[i];

       }

       

       return os;

}

#endif

Листинг 1. Код класса, инкапсулирующего массив

В листинге 2 приведен код программы

#include <iostream>

#include <fstream>

#include <sstream>

#include <string>

#include <exception>

#include "simple_vector. h"

//функция для подсчета числа экстремумов

int count_extremums(const simple_vector<double>&);

//функция для преобразования строкового представления числа: 1.45*10^(-3) -> 1.45E-3

void transform_str_num(std::string&);

int main(int argc, char** argv)

{

       simple_vector<double> v;

       std::string file_name;

       //получаем имя файла данных из командной строки

       if (argc > 1)

               file_name = argv[0];

       else//или из консоли

       {

               std::cout << "Enter file name: ";

               std::cin >> file_name;

       }

       //открываем файл

       std::ifstream ifs(file_name. c_str());

       if (!ifs)

       {

               std::cout << "Error opening of file: " << file_name << std::endl;

               return -1;

       }

       

       std::string line;

       //считываем строки из файла

       while (std::getline(ifs, line))

       {

               std::stringstream sin;

               sin << line;//каждую строку как пару чисел передаем строковому потоку

               std::string y_str;

               sin >> y_str;//пропускаем Х

               sin >> y_str;//извлекаем Y

               //корректируем Y

               transform_str_num(y_str);

               double item;

               //передаем строку в строковый поток

               sin << y_str;

               //пытаемся извлечь Y в виде числа

               if (sin >> item)

               {

                       v << item;//если ОК, добавляем в массив

               }

       }

       ifs. close();

       std::cout << "Count of extremums: " << count_extremums(v) << std::endl;

       return 0;

}

void transform_str_num(std::string& str)

{

       const std::string subs = "*10^";

       std::size_t ipos = str. find(subs);

       if (ipos!= std::string::npos)

       {

               str. replace(ipos, subs. length(),"E");

       }

       ipos = str. find("(");

       if (ipos!= std::string::npos)

       {

               str. replace(ipos,1,"");

       }

       ipos = str. find(")");

       if (ipos!= std::string::npos)

       {

               str. replace(ipos,1,"");

       }

}

//шаблонная функция для вычисления знака числа

template <class T>

int sgn_number(const T& a)

{

       return (a < 0) ? -1 : (a > 0) ? 1 : 0;

}

int count_extremums(const simple_vector<double>& src)

{

       //Если массив не задан или задан неправильный его размер - выходим с кодом ошибки

       if (!src)

               return -1;

       int cn_extrems = 0;

       for (int i = 1; i < src. get_size() - 1; ++i)

       {

               //вычисляем знаки наклона касательной

               int sgn1 = sgn_number(src[i] - src[i - 1]);

               int sgn2 = sgn_number(src[i + 1] - src[i]);

               //если они разные - экстремум

               if (sgn1 != sgn2)

               {

                       std::cout << i + 1 << ": " << src[i] << std::endl;

                       ++cn_extrems;

               }

       }

       return cn_extrems;

}

Листинг 2. Код программы для поиска экстремумов.

В программе (см. листинг 2) сначала создается объект массива.

simple_vector<double> v;

Ввод исходных данных в него осуществляется из файла, имя которого задается из командой строки или из консоли

       std::string file_name;

       //получаем имя файла данных из командной строки

       if (argc > 1)

               file_name = argv[0];

       else//или из консоли

       {

               std::cout << "Enter file name: ";

               std::cin >> file_name;

       }

Затем пытаемся открыть файл. Если файл не существует, или произошла ошибка, то выходим из программы

       //открываем файл

       std::ifstream ifs(file_name. c_str());

       if (!ifs)

       {

               std::cout << "Error opening of file: " << file_name << std::endl;

               return -1;

       }

Далее идет процедура чтения файла. Поскольку тестовый файл имеет структуру

f(x)=x*x*sin(x)-x*cos(x)

x  f(x) 

…………………………………………………………….,

то его чтение в цикле осуществляется по такому алгоритму:

считываем строку из файла в объект типа std::string

while (std::getline(ifs, line))

передаем эту строку объекту типа std::stringstream

std::stringstream sin;

sin << line;//каждую строку как пару чисел передаем строковому потоку

из объекта типа std::stringstream считываем сначала первый элемент данных (X) и не используем его

std::string y_str;

sin >> y_str;//пропускаем Х

затем точно также считываем второй элемент данных (Y)

sin >> y_str;//извлекаем Y

поскольку строковое представление вещественного числа может содержать числа в формате 3.9801*10^(-5) и т. п, то предварительно корректируем такие числа, приводя их к виду 3.9801E-5

//корректируем Y

transform_str_num(y_str);

затем опять передаем преобразованную строку в объект типа std::stringstream и пытаемся считывать уже оттуда число

double item;

//передаем строку в строковый поток

sin << y_str;

//пытаемся извлечь Y в виде числа

if (sin >> item)

{

v << item;//если ОК, добавляем в массив

}

.

По завершению ввода данных закрываем файл с данными

       ifs. close();

и вызываем функцию для подсчета количества экстремумов

       std::cout << "Count of extremums: " << count_extremums(v) << std::endl;

Программа завершается корректно, так как не требуется ручной очистки памяти. Объект класса simple_vector удаляется при выходе из функции main, перед этим вызывается его деструктор, который и очищает всю занятую память.

Ниже приведен скриншот проекта Visual Studio 2012 (рис. 1).

Рисунок 1.

В качестве теста была рассмотрена функция

,

на отрезке . Шаг дискретизации был выбран 0,01. Протабулированную функцию было записано в файл test. txt.

На рисунке 2 представлены результаты работы программы

Рисунок 2.

На рис. 3 представлен график этой функции.

Рисунок 3.

Выводы

Разработано программу для поиска количества экстремумов дискретно заданной функции.

Получены навыки работы в среде Visual Studio 2012.

Получены навыки работы с шаблонными классами C++.

Литература

Вержбицкий методы (математический анализ и обыкновенные дифференциальные уравнения): Учебн. пособие для вузов. – М.: Высш. шк., 2001 Пратта, Стивен Язык программирования C++. Лекции и упражнения, 6 изд.: Пер. с англ. – М.: , 2012. Солтер, и др. C++ для профессионалов: Пер. с англ. – М.: , 2006. Шилдт, Герберт Искусство программирования на C++. – СпБ.: БХВ-Петербург, 2005.