Короткие примеры C++ кода-1 Кувшинов Д

return string(pos, pos + len);

}
/// Проверка результата для тестовых строк.

int test_longest_palindrome()

{

if (longest_palindrome("this isn't a text with no palindromic substrings") != "t a t")

return 1;

if (longest_palindrome("there is no word redivider in English") != " redivider ")

return 2;

if (longest_palindrome("who knows what \"detartrated\" means?") != " \"detartrated\" ")

return 3;

if (longest_palindrome("saippuakalasalakauppias is longer than"

"saippuakivikauppias but what about"

"kuulilennuteetunneliluuk?") != "kuulilennuteetunneliluuk")

return 4;

if (longest_palindrome("blast") != "")

return 5;

return 0;

}
int main()

{

auto test = test_longest_palindrome();

cout << test << endl;

assert(test == 0);

return EXIT_SUCCESS;

}

0590-longest_palindromic_substring_c.cpp

// longest_palindromic_substring_c.cpp

// Задача: в заданной строке найти самую длинную подстроку-палиндром.

// Алгоритм решения

// Палиндромы нечётной длины: перебирать символы строки, определять наибольший палиндром, центром которого они являются.

// Палиндромы чётной длины: перебирать пары совпадающих символов, определять наибольший палиндром, центром которого они являются.

#include

#include
/// Определить максимальную длину совпадающих суффикса массива [begin, left) и префикса массива [right, end)

std::size_t max_common_prefix_suffix

(

const char *begin, const char *left,

const char *right, const char *end

)

{

std::size_t steps = 0;

while (begin != left && right != end && *--left == *right++)

++steps;

return steps;

}
/// Определить радиус палиндрома нечётной длины с центром center.

inline std::size_t longest_odd_palindrome_radius_from

(

const char *begin, const char *end,

const char *center

)

{

assert(begin <= center && center < end);

return max_common_prefix_suffix(begin, center, center + 1, end);

}
/// Определить радиус палиндрома чётной длины с центром (левым символом пары) в center.

inline std::size_t longest_even_palindrome_radius_from

(

const char *begin, const char *end,

const char *center

)

{

assert(begin <= center && center + 1 < end);

return max_common_prefix_suffix(begin, center, center + 2, end);

}

/// Найти самую длинную подстроку-палиндром в диапазоне строки.

/// Возвращает длину найденной подстроки, по указателю found записывает указатель на начало найденной подстроки.

std::size_t longest_palindrome(const char *begin, const char *end, const char **found)

{

std::size_t cur_max = 0;

for (auto pos = begin + 1; pos + 1 < end; ++pos)

{

const auto odd_len = 2 * longest_odd_palindrome_radius_from(begin, end, pos) + 1;

if (cur_max < odd_len)

{

cur_max = odd_len;

*found = pos - odd_len / 2;

}
if (*pos == *(pos + 1))

{

const auto even_len = 2 * longest_even_palindrome_radius_from(begin, end, pos) + 2;

if (cur_max < even_len)

{

cur_max = even_len;

*found = (pos + 1) - even_len / 2;

}

}

}
return cur_max > 1 ? cur_max : 0;

}

///////////////////////////////////////////////////////////////////////////////

// Тестирование

#include

#include

using namespace std;
/// В заданном объекте std::string найти самую длинную подстроку-палиндром

/// и вернуть её в виде нового объекта std::string.

string longest_palindrome(const string &text)

{

const char *pos = nullptr;

const auto len = longest_palindrome(text.data(), text.data() + text.size(), &pos);

return string(pos, pos + len);

}
/// Проверка результата для тестовых строк.

int test_longest_palindrome()

{

if (longest_palindrome("this isn't a text with no palindromic substrings") != "t a t")

return 1;

if (longest_palindrome("there is no word redivider in English") != " redivider ")

return 2;

if (longest_palindrome("who knows what \"detartrated\" means?") != " \"detartrated\" ")

return 3;

if (longest_palindrome("saippuakalasalakauppias is longer than"

"saippuakivikauppias but what about"

"kuulilennuteetunneliluuk?") != "kuulilennuteetunneliluuk")

return 4;

if (longest_palindrome("blast") != "")

return 5;

return 0;

}
int main()

{

auto test = test_longest_palindrome();

cout << test << endl;

assert(test == 0);

return EXIT_SUCCESS;

}

0600-function_ptr_solve.cpp

// function_ptr_solve.cpp

// Приближённое решение произвольного уравнения f(x) = 0

// методом деления отрезка пополам.

// f передаётся указателем на функцию.

#include

#include
/// Тип "правая часть уравнения" -- функция одного действительного параметра.

typedef double (*Unary_real_function)(double);
/// Точность приближённого решения, используемая по умолчанию.

const double TOLERANCE = 1e-8;
/// Алгоритм численного решения уравнения f(x) = 0 на отрезке [a, b] делением отрезка пополам.

/// Данный алгоритм является вариантом двоичного поиска.

double nsolve(Unary_real_function f, double a, double b, double tol = TOLERANCE)

{

using namespace std;

assert(f != nullptr);

assert(a < b);

assert(0. <= tol);

for (auto fa = f(a), fb = f(b);;)

{

// Проверим значения функции на концах отрезка.

if (fa == 0.)

return a;

if (fb == 0.)

return b;
// Делим отрезок пополам.

const auto mid = 0.5 * (a + b); // середина отрезка

if (mid <= a || b <= mid)

return abs(fa) < abs(fb)? a: b;

if (b - a <= tol)

return mid;
// Выберем одну из половин в качестве уточнённого отрезка.

const auto fmid = f(mid);

if (signbit(fa) != signbit(fmid))

{

// Корень на левой половине.

b = mid;

fb = fmid;

}

else

{

assert(signbit(fb) != signbit(fmid));

// Корень на правой половине.

a = mid;

fa = fmid;

}

}

}

// Тестирование.

#include

#include

using namespace std;
/// Модельная функция 1.

double poly5(double x)

{

return (x - 1.)*(x - 2.)*(x - 3.)*(x - 4.)*(x - 5.);

}
/// Модельная функция 2.

double loge(double x)

{

return log(x) - 1.;

}
/// Модельная функция 3.

double ipl(double x)

{

return x*x*x - pow(3., x);

}

/// Вывести результат для заданной функции.

void print_root(Unary_real_function f, double a, double b)

{

const auto root = nsolve(f, a, b);

cout << "on [" << a << ", " << b << "] root is " << root << endl;

}
int main()

{

struct { const char *msg; Unary_real_function f; double a, b; }

tasks[] =

{

{ "poly: ", poly5, 0.5, 100. },

{ "poly (1): ", poly5, 0.5, 1.5 },

{ "e: ", loge, 0.01, 1000. },

{ "ipl: ", ipl, 0.0, 2.7 },

{ "ipl (3): ", ipl, 2.7, 10. }

};
cout.precision(16);

for (auto &task : tasks)

{

cout << task.msg;

print_root(task.f, task.a, task.b);

}
return EXIT_SUCCESS;

}

0605-nsolve_callback.cpp

// nsolve_callback.cpp

// Приближённое решение произвольного уравнения f(x) = 0 с поиском нескольких корней.

// Метод деления пополам на равномерной сетке, разбивающей заданный отрезок (участок поиска).

#include

#include
/// Тип "правая часть уравнения" -- функция одного действительного параметра.

typedef double (*Unary_real_function)(double);
/// Точность приближённого решения, используемая по умолчанию.

const double TOLERANCE = 1e-8;
/// Алгоритм численного решения уравнения f(x) = 0 на отрезке [a, b] делением отрезка пополам.

/// Данный алгоритм является вариантом двоичного поиска.

double nsolve(Unary_real_function f, double a, double b, double tol = TOLERANCE)

{

using namespace std;

assert(f != nullptr);

assert(a < b);

assert(0. <= tol);

for (auto fa = f(a), fb = f(b);;)

{

// Проверим значения функции на концах отрезка.

if (fa == 0.)

return a;

if (fb == 0.)

return b;
// Делим отрезок пополам.

const auto mid = 0.5 * (a + b); // середина отрезка

if (mid <= a || b <= mid)

return abs(fa) < abs(fb)? a: b;

if (b - a <= tol)

return mid;
// Выберем одну из половин в качестве уточнённого отрезка.

const auto fmid = f(mid);

if (signbit(fa) != signbit(fmid))

{

// Корень на левой половине.

b = mid;

fb = fmid;

}

else

{

assert(signbit(fb) != signbit(fmid));

// Корень на правой половине.

a = mid;

fa = fmid;

}

}

}

/// Тип "решатель уравнения на отрезке" -- функция вроде nsolve, определённой выше.

typedef double (*Equation_solver)(Unary_real_function, double a, double b, double tol);

/// Тип функции, вызываемой для каждого корня.

/// Процесс поиска останавливается, если эта функция возвращает ложь.

typedef bool (*Root_reporter)(double);
/// Применяет заданный алгоритм поиска корня на отрезке,

/// разбивая заданный отрезок [a, b] на отрезки одинаковой длины step (кроме, возможно, последнего).

/// Для каждого найденного корня вызывает функцию report (callback-функция).

/// Возвращает правую границу пройденного участка (идёт слева направо по заданному отрезку).

double repeated_nsolve

(

Unary_real_function f, double a, double b,

double step, // шаг на отрезке

Root_reporter report,

double x_tol = TOLERANCE, // чувствительность по аргументу

double f_tol = TOLERANCE, // чувствительность по значению функции

Equation_solver solver = nsolve

)

{

assert(x_tol >= 0. && f_tol >= 0.);

assert(a <= b);

assert(step > 0.);

assert(f && report && solver);