Все примеры, представленные в данном наборе доступны в виде отдельных .cpp-файлов в папке cpp1.
int main()
{
}
// Это однострочный комментарий.
/* Это многострочный комментарий.
Наша программа ничего не делает.
*/
int main()
{
}
/*
* Это многострочный комментарий.
* Наша программа ничего не делает.
*/
int main()
{
return 0; // Возвратим ОС "код результата работы".
}
// hello.cpp
// Подключить стандартные потоки текстового ввода-вывода.
#include <iostream>
int main()
{
std::cout << "Hello, user!";
return 0; // Возвратим ОС "код результата работы".
}
// exit_success.cpp
#include <iostream>
#include <cstdlib>
int main()
{
std::cout << "Hello, user!";
return EXIT_SUCCESS; // Возвратим ОС "код успеха".
}
// string_variable.cpp
#include <iostream>
#include <cstdlib>
// Строки C++.
#include <string>
int main()
{
std::string user_name = "user"; // Определить переменную.
std::cout << "Hello, " << user_name << "!";
return EXIT_SUCCESS; // Возвратим ОС "код успеха".
}
// endl_string_variable.cpp
#include <iostream>
#include <cstdlib>
// Строки C++.
#include <string>
int main()
{
std::string user_name = "user"; // Определить переменную.
std::cout << "Hello, " << user_name << "!" << std::endl;
user_name = "The Great Whale"; // Изменить значение переменной.
std::cout << "I am " << user_name;
return EXIT_SUCCESS; // Возвратим ОС "код успеха".
}
// using_namespace.cpp
#include <iostream>
#include <cstdlib>
// Строки C++.
#include <string>
int main()
{
using namespace std; // Искать имена в std.
string user_name = "user"; // Определить переменную.
cout << "Hello, " << user_name << "!" << endl;
user_name = "The Great Whale"; // Изменить значение переменной.
cout << "I am " << user_name;
return EXIT_SUCCESS; // Возвратим ОС "код успеха".
}
// russian_win32.cpp
#include <iostream>
#include <clocale>
int main()
{
using namespace std;
setlocale(LC_ALL, "Russian");
cout << "Текст" << endl;
return EXIT_SUCCESS;
}
// russian_win32_cpp.cpp
#include <iostream>
#include <locale>
int main()
{
using namespace std;
locale::global(locale("Russian"));
cout << "Текст" << endl;
return EXIT_SUCCESS;
}
// cin.cpp
#include <iostream>
#include <cstdlib>
#include <string>
int main()
{
using namespace std; // Искать имена в std.
string user_name = "user"; // Определить переменную.
cout << "Login: ";
cin >> user_name; // Считать слово из потока ввода.
cout << "Hello, " << user_name << "!" << endl;
return EXIT_SUCCESS; // Возвратим ОС "код успеха".
}
// getline.cpp
#include <iostream>
#include <cstdlib>
#include <string>
int main()
{
using namespace std; // Искать имена в std.
string user_name = "user"; // Определить переменную.
cout << "Login: ";
getline(cin, user_name); // Считать строку из потока ввода.
cout << "Hello, " << user_name << "!" << endl;
return EXIT_SUCCESS; // Возвратим ОС "код успеха".
}
// string_concat.cpp
#include <iostream>
#include <cstdlib>
#include <string>
int main()
{
using namespace std;
string line1, line2; // Сразу две переменные, пустые строки.
getline(cin, line1);
getline(cin, line2);
cout << (line1 + line2) << endl; // + "склеивает" строки.
return EXIT_SUCCESS;
}
// var_assign_expr.cpp
#include <iostream>
#include <cstdlib>
#include <string>
int main()
{
using namespace std;
string line1, line2; // Сразу две переменные, пустые строки.
getline(cin, line1);
getline(cin, line2);
line1 = line1 + line2; // Заменить первую строку на результат "склеивания".
cout << line1 << endl;
return EXIT_SUCCESS;
}
// combined_assignment.cpp
#include <iostream>
#include <cstdlib>
#include <string>
int main()
{
using namespace std;
string line1, line2; // Сразу две переменные, пустые строки.
getline(cin, line1);
getline(cin, line2);
// То же, что line1 = line1 + line2, но без создания временного объекта.
line1 += line2; // Заменить первую строку на результат "склеивания".
cout << line1 << endl;
return EXIT_SUCCESS;
}
// basic_arith.cpp
#include <iostream>
#include <cstdlib>
int main()
{
using namespace std;
int a = 0, b = 0; // Целые числа.
cout << "a = ";
cin >> a;
cout << "b = ";
cin >> b;
cout << "(a + 2b) (a - 2b) = ";
cout << (a + 2*b) * (a - 2*b) << endl;
return EXIT_SUCCESS;
}
// quot_rem.cpp
#include <iostream>
#include <cstdlib>
int main()
{
using namespace std;
int a = 0, b = 0; // Целые числа.
cout << "a = ";
cin >> a;
cout << "b = ";
cin >> b;
cout << "quotient a:b = " << a / b << endl;
cout << "remainder a:b = " << a % b << endl;
return EXIT_SUCCESS;
}
// double.cpp
#include <iostream>
#include <cstdlib>
int main()
{
using namespace std;
double a = 0, b = 0; // Числа с плавающей запятой.
cout << "a = ";
cin >> a;
cout << "b = ";
cin >> b;
cout << "quotient a:b = " << a / b << endl;
//cout << "remainder a:b = " << a % b << endl;
// Операция взятия остатка не определена.
return EXIT_SUCCESS;
}
// cout_precision.cpp
#include <iostream>
#include <cstdlib>
int main()
{
using namespace std;
double a = 0, b = 0; // Числа с плавающей запятой.
cout << "a = ";
cin >> a;
cout << "b = ";
cin >> b;
cout.precision(16); // 16 значащих знаков.
cout << "quotient a:b = " << a / b << endl;
//cout << "remainder a:b = " << a % b << endl;
// Операция взятия остатка не определена.
return EXIT_SUCCESS;
}
// cmath.cpp
#include <iostream>
#include <cstdlib>
// "Математические функции".
#include <cmath>
int main()
{
using namespace std;
double a = 0, b = 0; // Числа с плавающей запятой.
cout << "a = ";
cin >> a;
cout << "b = ";
cin >> b;
cout.precision(16); // 16 значащих знаков.
cout << "a to b power = " << pow(a, b) << endl;
//cout << "remainder a:b = " << a % b << endl;
// Операция взятия остатка не определена.
return EXIT_SUCCESS;
}
// function_log.cpp
#include <iostream>
#include <cstdlib>
// "Математические функции".
#include <cmath>
// Определение своей функции.
double log(double base, double arg)
{
// Через стандартный натуральный логарифм.
return std::log(arg) / std::log(base);
}
int main()
{
using namespace std;
double a = 0, b = 0; // Числа с плавающей запятой.
cout << "a = ";
cin >> a;
cout << "b = ";
cin >> b;
cout.precision(16); // 16 значащих знаков.
cout << "log(b, a) = " << log(b, a) << endl;
return EXIT_SUCCESS;
}
// file_scope_using_namespace.cpp
#include <iostream>
#include <cstdlib>
// "Математические функции".
#include <cmath>
using namespace std;
// Определение своей функции.
double log(double base, double arg)
{
// Через стандартный натуральный логарифм.
return log(arg) / log(base);
}
int main()
{
double a = 0, b = 0; // Числа с плавающей запятой.
cout << "a = ";
cin >> a;
cout << "b = ";
cin >> b;
cout.precision(16); // 16 значащих знаков.
cout << "log(b, a) = " << log(b, a) << endl;
return EXIT_SUCCESS;
}
// units_conversion.cpp
#include <iostream>
#include <cstdlib>
// Дюймы in в метры.
double in2m(double in) { return 0.0254 * in; }
// Футы ft в метры.
double ft2m(double ft) { return 0.304 * ft; }
// Метры m в дюймы.
double m2in(double m) { return m / 0.0254; }
// Метры m в футы.
double m2ft(double m) { return m / 0.304; }
int main()
{
using namespace std;
cout << "Enter length: ";
double len = 0.0;
cin >> len;
cout << "in to m = " << in2m(len) << endl;
cout << "ft to m = " << ft2m(len) << endl;
cout << "m to in = " << m2in(len) << endl;
cout << "m to ft = " << m2ft(len) << endl;
cout << "in to ft = " << m2ft(in2m(len)) << endl;
cout << "ft to in = " << m2in(ft2m(len)) << endl;
return EXIT_SUCCESS;
}
// if.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
int main()
{
double x = 0;
cout << "x = ";
cin >> x;
cout << "x*x ";
if (x*x < 2) // Условие.
cout << " < ";
else // Альтернатива.
cout << " > ";
cout << "2" << endl;
return EXIT_SUCCESS;
}
// bool_expr.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
int main()
{
double x = 0;
cout << "x = ";
cin >> x;
// Логическое выражение.
cout << "x*x < 2 == " << (x*x < 2) << endl;
return EXIT_SUCCESS;
}
// bool_pred.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
// Определение своей функции-предиката.
// Проверяет условие: x в квадрате меньше 2.
bool sqr_lt_2(double x)
{
return x*x < 2;
}
int main()
{
double x = 0;
cout << "x = ";
cin >> x;
cout << "x*x < 2 == " << sqr_lt_2(x) << endl;
return EXIT_SUCCESS;
}
// while_true.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
// Определение своей функции-предиката.
// Проверяет условие: x в квадрате меньше 2.
bool sqr_lt_2(double x)
{
return x*x < 2;
}
int main()
{
double x = 0;
while (true)
{
cout << "x = ";
cin >> x;
cout << "x*x < 2 == " << sqr_lt_2(x) << endl;
}
return EXIT_SUCCESS;
}
// while_cin.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
// Определение своей функции-предиката.
// Проверяет условие: x в квадрате меньше 2.
bool sqr_lt_2(double x)
{
return x*x < 2;
}
int main()
{
double x = 0;
cout << "Enter a sequence of numbers x: ";
while (cin >> x) // Условие продолжения выполнения цикла.
{
cout << "x*x < 2 == " << sqr_lt_2(x) << endl;
}
return EXIT_SUCCESS;
}
// for_cin.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
// Определение своей функции-предиката.
// Проверяет условие: x в квадрате меньше 2.
bool sqr_lt_2(double x)
{
return x*x < 2;
}
int main()
{
cout << "Enter a sequence of numbers x: ";
// Определение переменных; условие продолжения; последнее действие на каждом повторении.
for (double x = 0; cin >> x;)
{
cout << "x*x < 2 == " << sqr_lt_2(x) << endl;
}
return EXIT_SUCCESS;
}
// cin_delay.cpp
// Задержка экрана средствами ISO C++.
#include <iostream>
using namespace std;
/// Сбросить флаги ошибок и содержимое буфера потока.
void ignore_all(istream &is)
{
is.clear(); // Сброс ошибок.
is.sync(); // Синхронизация объекта потока с внешним устройством.
is.ignore(is.rdbuf()->in_avail()); // Сброс символов уже считанных в буфер потока.
}
/// Задержка экрана = сброс стандартного потока ввода и ожидание следующего символа.
void console_delay()
{
ignore_all(cin);
cin.ignore();
}
// Демонстрация.
int main()
{
while (true)
{
cout << "Enter a sequence of integers:\n";
for (int i; cin >> i;)
cout << i << ' ';
cout << "\nPress Enter to repeat\n";
console_delay();
}
}
// cin_delay_eof_exit.cpp
// Задержка экрана средствами ISO C++.
#include <cstddef>
#include <iostream>
using namespace std;
/// Сбросить флаги ошибок и содержимое буфера потока.
void ignore_all(istream &is)
{
is.clear();
is.sync();
is.ignore(is.rdbuf()->in_avail());
}
/// Задержка экрана = сброс стандартного потока ввода и ожидание следующего символа.
void console_delay()
{
ignore_all(cin);
cin.ignore();
}
// Демонстрация.
int main()
{
while (true)
{
cout << "Enter a sequence of integers:\n";
for (int i; cin >> i;)
cout << i << ' ';
// Выйти, если введён признак конца файла.
if (cin.eof())
return EXIT_SUCCESS;
cout << "\nPress Enter to repeat\n";
console_delay();
}
}
// circle_const.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
// Определение своей функции-предиката.
// проверить попадание в круг
bool in_circle(float x, float y,
float cx, float cy, float r)
// координаты центра круга и его радиус
{
// Константы -- после инициализации значения не изменяются.
const float dx = x - cx,
dy = y - cy;
return dx * dx + dy * dy <= r * r;
}
int main()
{
cout << "Enter a sequence of coordinates x, y: ";
// Определение переменных; условие продолжения; последнее действие на каждом повторении.
for (float x, y; cin >> x >> y;)
{
const bool within_the_circle = in_circle(x, y, 1, -1, 3);
cout << "(x, y) within the circle == " << within_the_circle << endl;
}
return EXIT_SUCCESS;
}
// complex_bool_expr.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
// Проверить попадание в круг.
bool in_circle(float x, float y,
float cx, float cy, float r)
// координаты центра круга и его радиус
{
// Константы -- после инициализации значения не изменяются.
const float dx = x - cx,
dy = y - cy;
return dx * dx + dy * dy <= r * r;
}
// Проверить попадание в прямоугольник.
bool in_rectangle(float x, float y,
float left, float right, float bottom, float top)
// координаты левой, правой, нижней и верхней граней
{
return left <= x && x <= right // && -- "и"
&& bottom <= y && y <= top;
}
// Проверить попадание в заданную фигуру.
bool in_figure(float x, float y)
{
// фигура может быть представлена как пересечение полуплоскости и
// объединения трёх фигур: двух прямоугольников и сегмента круга
return (in_rectangle(x, y, 2.0, 4.0, -5.0, 5.0)
|| in_rectangle(x, y, -4.0, -2.0, -5.0, 5.0) // || -- "или"
|| in_circle(x, y, -2.0, 0.0, 5.0)) && x >= -4.0;
}
int main()
{
cout << "Enter a sequence of coordinates x, y: ";
// Определение переменных; условие продолжения; последнее действие на каждом повторении.
for (double x = 0, y = 0; cin >> x >> y;)
{
cout << "(x, y) within the figure == " << in_figure(x, y) << endl;
}
return EXIT_SUCCESS;
}
// ternary_operator.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
// Проверить попадание в круг.
bool in_circle(float x, float y,
float cx, float cy, float r)
// координаты центра круга и его радиус
{
// Константы -- после инициализации значения не изменяются.
const float dx = x - cx,
dy = y - cy;
return dx * dx + dy * dy <= r * r;
}
// Проверить попадание в прямоугольник.
bool in_rectangle(float x, float y,
float left, float right, float bottom, float top)
// координаты левой, правой, нижней и верхней граней
{
return left <= x && x <= right // && -- "и"
&& bottom <= y && y <= top;
}
// Проверить попадание в заданную фигуру.
bool in_figure(float x, float y)
{
// фигура может быть представлена как пересечение полуплоскости и
// объединения трёх фигур: двух прямоугольников и сегмента круга
return (in_rectangle(x, y, 2.0, 4.0, -5.0, 5.0)
|| in_rectangle(x, y, -4.0, -2.0, -5.0, 5.0) // || -- "или"
|| in_circle(x, y, -2.0, 0.0, 5.0)) && x >= -4.0;
}
int main()
{
cout << "Enter a sequence of coordinates x, y: ";
// Определение переменных; условие продолжения; последнее действие на каждом повторении.
for (double x = 0, y = 0; cin >> x >> y;)
{
cout << "(" << x << ", " << y << ") " <<
(in_figure(x, y)? "is": "is not") // "тернарный оператор": условие в выражении
<< " inside the figure" << endl;
}
return EXIT_SUCCESS;
}
// for.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
int main()
{
// Определение переменных; условие продолжения; последнее действие на каждом повторении.
for (int i = 1; i <= 10; ++i) // ++i --> i = i + 1
{
cout << "i == " << i << "\ti squared == " << i * i << endl;
}
return EXIT_SUCCESS;
}
// for_for.cpp
// Двойной цикл for.
#include <iostream>
#include <cstdlib>
using namespace std;
// Таблица умножения.
int main()
{
// Определение переменных; условие продолжения; последнее действие на каждом повторении.
for (int i = 1; i <= 10; ++i) // ++i --> i = i + 1
{
for (int j = 1; j <= 10; ++j)
{
cout << i << "*" << j << "\t== " << i * j << endl;
}
}
return EXIT_SUCCESS;
}
// products_table.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
// Таблица умножения.
int main()
{
// Строчка.
for (int i = 1; i <= 10; ++i)
{
// Столбец.
for (int j = 1; j <= 10; ++j)
{
cout << i * j << " ";
}
cout << endl;
}
return EXIT_SUCCESS;
}
// iomanip_setw.cpp
#include <iostream>
#include <cstdlib>
#include <iomanip> // "Манипуляторы потока".
using namespace std;
// Таблица умножения.
int main()
{
// Строчка.
for (int i = 1; i <= 10; ++i)
{
// Столбец.
for (int j = 1; j <= 10; ++j)
{
// Манипулятор setw вставляет пробелы (до четырёх), если выведено менее 4 символов.
cout << setw(4) << i * j;
}
cout << endl;
}
return EXIT_SUCCESS;
}
// cat.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
// Читаем из потока ввода символы и пишем их в поток вывода.
int main()
{
for (char ch; cin.get(ch);)
cout.put(ch);
return EXIT_SUCCESS;
}
// cat_2.cpp
// Вариант на основе вывода в поток буфера другого потока.
#include <iostream>
#include <cstdlib>
using namespace std;
// Читаем из потока ввода символы и пишем их в поток вывода.
int main()
{
cout << cin.rdbuf();
return EXIT_SUCCESS;
}
// char_subst.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
// Читаем из потока ввода символы и пишем их в поток вывода,
// подменяя некоторые на другие (e -> i, o -> u, a -> o).
int main()
{
for (char ch; cin.get(ch);)
{
char output = ch;
if (ch == 'e')
output = 'i';
else if (ch == 'o')
output = 'u';
else if (ch == 'a')
output = 'o';
cout.put(output);
}
return EXIT_SUCCESS;
}
// count_lines.cpp
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;
// Читаем из потока ввода строки, выводим их в поток вывода,
// а в конце выводим их количество в отдельной строке.
int main()
{
int amount = 0;
for (string line; getline(cin, line); ++amount)
cout << line << endl;
cout << amount << endl;
return EXIT_SUCCESS;
}
// size_t.cpp
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;
// Читаем из потока ввода строки, выводим их в поток вывода,
// а в конце выводим их количество в отдельной строке.
int main()
{
size_t amount = 0; // Тип "количество", не может быть отрицательным.
for (string line; getline(cin, line); ++amount)
cout << line << endl;
cout << amount << endl;
return EXIT_SUCCESS;
}
// line_unique_0.cpp
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;
// Читаем из потока ввода строки, выводим их в поток вывода,
// пропуская подряд идущие повторяющиеся строки.
int main()
{
// Нет ли здесь ошибок?
for (string last, next; getline(cin, next);)
{
if (last != next)
{
cout << next << endl;
last = next;
}
}
return EXIT_SUCCESS;
}
// line_unique.cpp
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;
// Читаем из потока ввода строки, выводим их в поток вывода,
// пропуская подряд идущие повторяющиеся строки.
int main()
{
// Первая строка -- особый случай.
string last;
if (!getline(cin, last))
return EXIT_FAILURE; // Не смогли прочитать и одной строки.
cout << last << endl; // Вывести первую строку.
// Продолжить работу с остатком файла.
for (string next; getline(cin, next);)
{
if (last != next)
{
cout << next << endl;
last = next;
}
}
return EXIT_SUCCESS;
}
// spinning_pipe.cpp
#include <iostream>
int main()
{
while (true) std::cout
.put('|').flush().put('\b')
.put('/').flush().put('\b')
.put('-').flush().put('\b')
.put('\\').flush().put('\b');
}
// spinning_pipe_waiting.cpp
#include <iostream>
#include <cstdlib>
#include <thread> // sleep
#include <chrono> // суффикс ms (C++14)
// Выполнить "следующий фрагмент работы".
// Для примера мы просто ждём 200мс.
bool do_next_job()
{
using namespace std::chrono_literals;
std::this_thread::sleep_for(200ms);
// C++11-вариант:
// std::this_thread::sleep_for(std::chrono::milliseconds(200));
return true;
}
int main()
{
static char sprite[] = "|/-\\";
for (unsigned s = 0;; s = (s + 1) % 4)
{
std::cout.put(sprite[s]).flush();
if (!do_next_job())
break;
std::cout.put('\b');
}
return EXIT_SUCCESS;
}
// reverse_lines.cpp
#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;
struct Line
{
Line *prev;
string line;
};
int main()
{
Line *last = nullptr;
// Чтение строк.
for (string line; getline(cin, line);)
{
Line *new_line = new Line;
new_line->prev = last;
new_line->line = line;
last = new_line;
}
// Вывод строк в обратном порядке.
while (last)
{
cout << last->line << '\n';
Line *old_line = last;
last = last->prev;
delete old_line;
}
return EXIT_SUCCESS;
}
// void_list.cpp
#include <cstdlib>
using namespace std;
///////////////////////////////////////////////////////////////////////////////
// Следующие 4 функции ничего не знают о содержимом списка.
/// Возвращает ссылку на указатель на следующее звено звена link.
void*& next(void *link)
{
return *(void**)link;
}
/// Вставляет link перед head и возвращает link (теперь это -- новая голова списка).
void* insert_head(void *head, void *link)
{
next(link) = head;
return link;
}
/// Вычисляет длину списка.
size_t size(void *head)
{
size_t sz = 0;
for (; head; head = next(head))
++sz;
return sz;
}
/// Указатель на функцию, выполняющую удаление звена.
using Link_delete = void(*)(void*);
/// Удаляет список, используя пользовательскую функцию удаления.
void delete_list(void *head, Link_delete link_delete)
{
while (head)
{
auto next_head = next(head);
link_delete(head);
head = next_head;
}
}
///////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
/// Звено списка -- одна строка.
struct Line
{
void *prev;
string line;
};
/// Вывести строку и удалить объект Line.
void print_and_delete(void *ptr)
{
auto line = (Line*)ptr;
cout << line->line << '\n';
delete line;
}
int main()
{
Line *head = nullptr;
// Чтение строк.
for (string line; getline(cin, line);)
{
Line *new_line = new Line;
new_line->line = line;
head = (Line*)insert_head(head, new_line);
}
// Вывод количества строк -- элементов списка.
cout << "\nLines: " << size(head) << "\n\n";
// Вывод строк в обратном порядке.
delete_list(head, print_and_delete);
cin.clear();
cin.ignore();
return EXIT_SUCCESS;
}
// solve_linear_0.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
// Решаем уравнение ax + b = 0.
double solve_linear(double a, double b)
{
// Неужели так просто?
return -b / a;
}
int main()
{
cout << "Solving ax + b = 0, enter a, b:\n";
cout.precision(16);
for (double a, b; cin >> a >> b;)
cout << "x == " << solve_linear(a, b) << endl;
return EXIT_SUCCESS;
}
// solve_linear_ref.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
// Особое значение "бесконечное количество корней".
const int INFINITE_ROOTS = -1;
// Решаем уравнение ax + b = 0.
// Функция возвращает "количество корней".
// Корень записывает по ссылке root.
int solve_linear(double a, double b, double &root)
{
if (a == 0)
return b == 0? INFINITE_ROOTS: 0;
root = -b / a;
return 1;
}
int main()
{
cout << "Solving ax + b = 0, enter a, b:\n";
cout.precision(16);
for (double a, b, x; cin >> a >> b;)
{
const int roots = solve_linear(a, b, x);
if (roots == 0)
cout << "no roots\n";
else if (roots == INFINITE_ROOTS)
cout << "any number is a root\n";
else // один корень, записан в x
cout << "x == " << x << endl;
}
return EXIT_SUCCESS;
}
// switch_case_0.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
// Особое значение "бесконечное количество корней".
const int INFINITE_ROOTS = -1;
// Решаем уравнение ax + b = 0.
// Функция возвращает "количество корней".
// Корень записывает по ссылке root.
int solve_linear(double a, double b, double &root)
{
if (a == 0)
return b == 0? INFINITE_ROOTS: 0;
root = -b / a;
return 1;
}
int main()
{
cout << "Solving ax + b = 0, enter a, b:\n";
cout.precision(16);
for (double a, b, x; cin >> a >> b;)
{
const int roots = solve_linear(a, b, x);
switch (roots)
{
case 0:
cout << "no roots\n";
break;
case INFINITE_ROOTS:
cout << "any number is a root\n";
break;
default: // один корень, записан в x
cout << "x == " << x << endl;
}
}
return EXIT_SUCCESS;
}
// switch_case.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
// Особое значение "бесконечное количество корней".
const int INFINITE_ROOTS = -1;
// Решаем уравнение ax + b = 0.
// Функция возвращает "количество корней".
// Корень записывает по ссылке root.
int solve_linear(double a, double b, double &root)
{
if (a == 0)
return b == 0? INFINITE_ROOTS: 0;
root = -b / a;
return 1;
}
int main()
{
cout << "Solving ax + b = 0, enter a, b:\n";
cout.precision(16);
for (double a, b, x; cin >> a >> b;)
{
switch (solve_linear(a, b, x))
{
case 0:
cout << "no roots\n";
break;
case INFINITE_ROOTS:
cout << "any number is a root\n";
break;
default: // один корень, записан в x
cout << "x == " << x << endl;
}
}
return EXIT_SUCCESS;
}
// solve_quadratic.cpp
#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;
// Особое значение "бесконечное количество корней".
const int INFINITE_ROOTS = -1;
// Решаем уравнение ax + b = 0.
// Функция возвращает "количество корней".
// Корень записывает по ссылке root.
int solve_linear(double a, double b, double &root)
{
if (a == 0)
return b == 0? INFINITE_ROOTS: 0;
root = -b / a;
return 1;
}
// Решаем уравнение ax2 + bx + c = 0.
// Функция возвращает "количество корней",
// до двух корней записывает по ссылкам.
int solve_quadratic(double a, double b, double c, double &root1, double &root2)
{
if (a == 0) // сводится к линейному
return solve_linear(b, c, root1);
// a != 0
const double d = b * b - 4.0 * a * c;
if (d < 0) // нет корней
return 0;
if (d == 0) // один корень
{
root1 = -b / (2.0 * a); // обратите внимание на скобки
return 1;
}
// два корня
const double ds = sqrt(d);
root1 = (-b - ds) / (2.0 * a);
root2 = (-b + ds) / (2.0 * a);
return 2;
}
// Вычислить значение квадратного трёхчлена в точке.
double quadratic(double a, double b, double c, double x)
{
return (a * x + b) * x + c;
}
int main()
{
cout << "Solving ax2 + bx + c = 0, enter a, b, c:\n";
cout.precision(16);
for (double a, b, c, x1, x2; cin >> a >> b >> c;)
{
switch (solve_quadratic(a, b, c, x1, x2))
{
case 0:
cout << "no roots\n";
break;
case INFINITE_ROOTS:
cout << "any number is a root\n";
break;
case 1: // один корень, записан в x1
cout << "x == " << x1 << ", error is " << quadratic(a, b, c, x1) << endl;
break;
case 2: // два корня, записаны в x1 и x2
cout << "x1 == " << x1 << ", error is " << quadratic(a, b, c, x1) << endl;
cout << "x2 == " << x2 << ", error is " << quadratic(a, b, c, x2) << endl;
break;
default:
cout << "???\n"; // невозможный случай
}
}
return EXIT_SUCCESS;
}
// assert_0.cpp
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cassert> // assert
using namespace std;
// Особое значение "бесконечное количество корней".
const int INFINITE_ROOTS = -1;
// Решаем уравнение ax + b = 0.
// Функция возвращает "количество корней".
// Корень записывает по ссылке root.
int solve_linear(double a, double b, double &root)
{
if (a == 0)
return b == 0? INFINITE_ROOTS: 0;
root = -b / a;
return 1;
}
// Решаем уравнение ax2 + bx + c = 0.
// Функция возвращает "количество корней",
// до двух корней записывает по ссылкам.
int solve_quadratic(double a, double b, double c, double &root1, double &root2)
{
if (a == 0) // сводится к линейному
return solve_linear(b, c, root1);
// a != 0
const double d = b * b - 4.0 * a * c;
if (d < 0) // нет корней
return 0;
if (d == 0) // один корень
{
root1 = -b / (2.0 * a); // обратите внимание на скобки
return 1;
}
// два корня
const double ds = sqrt(d);
root1 = (-b - ds) / (2.0 * a);
root2 = (-b + ds) / (2.0 * a);
return 2;
}
// Вычислить значение квадратного трёхчлена в точке.
double quadratic(double a, double b, double c, double x)
{
return (a * x + b) * x + c;
}
int main()
{
cout << "Solving ax2 + bx + c = 0, enter a, b, c:\n";
cout.precision(16);
for (double a, b, c, x1, x2; cin >> a >> b >> c;)
{
switch (solve_quadratic(a, b, c, x1, x2))
{
case 0:
cout << "no roots\n";
break;
case INFINITE_ROOTS:
cout << "any number is a root\n";
break;
case 1: // один корень, записан в x1
cout << "x == " << x1 << ", error is " << quadratic(a, b, c, x1) << endl;
break;
case 2: // два корня, записаны в x1 и x2
cout << "x1 == " << x1 << ", error is " << quadratic(a, b, c, x1) << endl;
cout << "x2 == " << x2 << ", error is " << quadratic(a, b, c, x2) << endl;
break;
default:
assert(!"impossible case: 3 or more roots"); // невозможный случай
cout << "unknown error\n";
return EXIT_FAILURE;
}
}
return EXIT_SUCCESS;
}
// solve_transcend_0.cpp
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cassert> // assert
using namespace std;
// Особое значение "бесконечное количество корней".
const int INFINITE_ROOTS = -1;
const double // Вспомогательные числовые константы
HALF_PI = 1.570796326795, // половина пи
TOLERANCE = 1e-10; // граница между "нулём" и "ненулём"
// Логарифм по произвольному основанию.
double log(double base, double arg)
{
return log(arg) / log(base);
}
// Проверка значения на близость нулю.
bool is_almost_zero(double x, double tolerance = TOLERANCE)
{
return abs(x) <= tolerance;
}
// Левая часть уравнения.
double f(double a, double b, double c, double x)
{
return 1.0 + sin(pow(a, x) + abs(log(b, c)));
}
// Решаем уравнение f(a, b, c, root) = 0 относительно root.
// Функция возвращает "количество корней",
// один корень записывает по ссылке.
int solve_f(double a, double b, double c, double &root)
{
if (a < 0.0 || b <= 0.0 || b == 1.0 || c <= 0.0)
return 0; // нет корней
if (a == 0.0 || a == 1.0) // потенциально почти все возможные x -- корни
return is_almost_zero(f(a, b, c, 1.0))? INFINITE_ROOTS: 0;
// Счётное число корней, вернём один из них (он может не существовать).
root = log(a, 3.0 * HALF_PI - abs(log(b, c)));
return 1;
}
int main()
{
cout << "Solving f(a, b, c, x) = 0, enter a, b, c:\n";
cout.precision(16);
for (double a, b, c, x; cin >> a >> b >> c;)
{
switch (solve_f(a, b, c, x))
{
case 0:
cout << "no roots\n";
break;
case INFINITE_ROOTS:
cout << "any number is a root\n";
break;
case 1: // один корень, записан в x
cout << "x == " << x << ", error is " << f(a, b, c, x) << endl;
break;
default:
assert(!"impossible case: invalid roots quantity"); // невозможный случай
cout << "unknown error\n";
return EXIT_FAILURE;
}
}
return EXIT_SUCCESS;
}
// solve_transcend.cpp
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cassert> // assert
using namespace std;
// Особое значение "бесконечное количество корней".
const int INFINITE_ROOTS = -1;
const double // Вспомогательные числовые константы
HALF_PI = 1.5707963267949, // половина пи
PI = 3.14159265358979, // число пи
DOUBLE_PI = 6.2831853071796, // два пи
TOLERANCE = 1e-10; // граница между "нулём" и "ненулём"
// Логарифм по произвольному основанию.
double log(double base, double arg)
{
return log(arg) / log(base);
}
// Проверка значения на близость нулю.
bool is_almost_zero(double x, double tolerance = TOLERANCE)
{
return abs(x) <= tolerance;
}
// Левая часть уравнения.
double f(double a, double b, double c, double x)
{
return 1.0 + sin(pow(a, x) + abs(log(b, c)));
}
// Решаем уравнение f(a, b, c, root) = 0 относительно root.
// Функция возвращает "количество корней",
// один корень записывает по ссылке.
int solve_f(double a, double b, double c, double &root)
{
if (a < 0.0 || b <= 0.0 || b == 1.0 || c <= 0.0)
return 0; // нет корней
if (a == 0.0 || a == 1.0) // потенциально почти все возможные x -- корни
return is_almost_zero(f(a, b, c, 1.0))? INFINITE_ROOTS: 0;
// Счётное число корней, получим один из них.
const double
expr_part = abs(log(b, c)) + HALF_PI, // часть выражения
n = 1.0 + ceil(expr_part / DOUBLE_PI), // номер корня
log_arg = DOUBLE_PI * n - expr_part; // аргумент логарифма в формуле корня
assert(log_arg > 0.0); // всегда должен быть положительным по построению
root = log(a, log_arg);
return 1;
}
int main()
{
cout << "Solving f(a, b, c, x) = 0, enter a, b, c:\n";
cout.precision(16);
for (double a, b, c, x; cin >> a >> b >> c;)
{
switch (solve_f(a, b, c, x))
{
case 0:
cout << "no roots\n";
break;
case INFINITE_ROOTS:
cout << "any number is a root\n";
break;
case 1: // один корень, записан в x
cout << "x == " << x << ", error is " << f(a, b, c, x) << endl;
break;
default:
assert(!"impossible case: invalid roots quantity"); // невозможный случай
cout << "unknown error\n";
return EXIT_FAILURE;
}
}
return EXIT_SUCCESS;
}
// array_initialization.cpp
// Примеры инициализации одномерных статических массивов.
#include <iostream>
using namespace std;
// Макрос для "распечатки" статического массива.
#define PRINTA(a) \
for (auto item: a) \
cout << item << ' '; \
cout << endl
int main()
{
// Указан и размер и значения всех элементов.
int xyz[3] = { 1, 2, 3 };
PRINTA(xyz);
// Последние три элемента будут нули.
int zero_tail[6] = { 7, 7, 7 };
PRINTA(zero_tail);
// Типичная инициализация локального массива нулями.
float zeroes[10] = {};
PRINTA(zeroes);
// Размер не указан, определяется количеством значений в инициализаторе.
char word[] = { 'w', 'o', 'r', 'd' };
PRINTA(word);
// В качестве инициализатора можно использовать строковый литерал.
// В конце добавляется нулевой символ, поэтому размер greets 11, а не 10.
char greets[] = "greetings!";
PRINTA(greets) << sizeof(greets) << '\n';
greets[3] = 'a';
cout << greets << endl;
}
// positives_negatives.cpp
// Отношение количества положительных к количеству отрицательных элементов.
// Пример: { 4, 1, 100, 0, 20, 0, -1, -2, 3, -6 } -> 5/3 = 1.6666667.
#include <cstddef>
#include <iostream>
using namespace std;
// П.1: обработка произвольного массива, переданного как адрес + размер,
// size_t -- стандартный тип (определён в Стандартной библиотеке C),
// предназначенный для хранения размеров массивов.
double pn_ratio(const double numbers[], size_t n)
{
// Счётчики положительных и отрицательных чисел.
size_t positives = 0, negatives = 0;
for (size_t i = 0; i < n; ++i)
{
// Ключевое слово auto предписывает компилятору вывести тип переменной
// автоматически по типу инициализирующего выражения.
const auto x = numbers[i]; // следующий элемент последовательности
if (x < 0.0)
++negatives;
else if (x > 0.0)
++positives;
}
// Без приведения к double будет деление в целых числах.
return double(positives) / negatives;
}
// П.2: тестирование функции из п.1 на заранее заданных массивах.
bool test_pn_ratio()
{
const double test1[] = { 4, 1, 100, 0, 20, 0, -1, -2, 3, -6 };
// sizeof возвращает размер статического массива в байтах
// (!) при этом массив должен быть виден в данном контексте непосредственно,
// (!) иначе программист рискует получить вместо размера массива размер указателя на него
if (pn_ratio(test1, sizeof(test1) / sizeof(double)) != 5.0 / 3.0)
return false;
const double test2[] = { -40, -2, -111, 42, 0, 0, 2, -1000, -4 };
if (pn_ratio(test2, sizeof(test2) / sizeof(double)) != 2.0 / 5.0)
return false;
// Все проверки прошли успешно.
return true;
}
// П.3: считывание чисел с потока ввода.
double pn_ratio(istream &in)
{
// Счётчики положительных и отрицательных чисел.
size_t positives = 0, negatives = 0;
for (double x; in >> x;)
{
if (x < 0.0)
++negatives;
else if (x > 0.0)
++positives;
}
// Без приведения к double будет деление в целых числах.
return double(positives) / negatives;
}
int main()
{
// Тестирование варианта обработки данных для массива.
cout << test_pn_ratio() << endl;
// Вариант для обработки данных с потока ввода.
const auto result = pn_ratio(cin);
cout << "\nResult: " << result << endl;
return EXIT_SUCCESS;
}
// positives_negatives_2.cpp
// Отношение количества положительных к количеству отрицательных элементов.
// Пример: { 4, 1, 100, 0, 20, 0, -1, -2, 3, -6 } -> 5/3 = 1.6666667.
#include <cstddef>
#include <iostream>
using namespace std;
// П.1: обработка произвольного массива, переданного как адрес + размер,
// size_t -- стандартный тип (определён в Стандартной библиотеке C),
// предназначенный для хранения размеров массивов.
double pn_ratio(const double numbers[], size_t n)
{
// Счётчики положительных и отрицательных чисел.
size_t positives = 0, negatives = 0;
for (size_t i = 0; i < n; ++i)
{
// Ключевое слово auto предписывает компилятору вывести тип переменной
// автоматически по типу инициализирующего выражения.
const auto x = numbers[i]; // следующий элемент последовательности
// Воспользуемся тем фактом, что логические операции возвращают 0 или 1.
negatives += x < 0.0;
positives += x > 0.0;
}
// Без приведения к double будет деление в целых числах.
return double(positives) / negatives;
}
// П.2: тестирование функции из п.1 на заранее заданных массивах.
bool test_pn_ratio()
{
const double test1[] = { 4, 1, 100, 0, 20, 0, -1, -2, 3, -6 };
// sizeof возвращает размер статического массива в байтах
// (!) при этом массив должен быть виден в данном контексте непосредственно,
// (!) иначе программист рискует получить вместо размера массива размер указателя на него
if (pn_ratio(test1, sizeof(test1) / sizeof(double)) != 5.0 / 3.0)
return false;
const double test2[] = { -40, -2, -111, 42, 0, 0, 2, -1000, -4 };
if (pn_ratio(test2, sizeof(test2) / sizeof(double)) != 2.0 / 5.0)
return false;
// Все проверки прошли успешно.
return true;
}
// П.3: считывание чисел с потока ввода.
double pn_ratio(istream &in)
{
// Счётчики положительных и отрицательных чисел.
size_t positives = 0, negatives = 0;
for (double x; in >> x;)
{
if (x < 0.0)
++negatives;
else if (x > 0.0)
++positives;
}
// Без приведения к double будет деление в целых числах.
return double(positives) / negatives;
}
int main()
{
// Тестирование варианта обработки данных для массива.
cout << test_pn_ratio() << endl;
// Вариант для обработки данных с потока ввода.
const auto result = pn_ratio(cin);
cout << "\nResult: " << result << endl;
return EXIT_SUCCESS;
}
// static_array_begin_end.cpp
// Использование std::begin и std::end для получения границ диапазона статического массива.
#include <iostream>
#include <iterator> // begin, end
using namespace std;
// Заполняет [begin, end) квадратами индексов.
void fill_with_squares(float* begin, float* end)
{
// Количество элементов равно разности указателей.
for (size_t i = 0; i != end - begin; ++i)
begin[i] = i * i;
}
// Выводим array в консоль.
void print_array(float* begin, float* end)
{
while (begin != end)
cout << *begin++ << '\n';
}
int main()
{
// Локальный статический массив. Его размер виден только внутри main.
float squares[100];
// begin(squares) возвращает указатель на первый элемент массива, а
// end(squares) возвращает указатель на фиктивный элемент, следующий за последним элементом массива.
fill_with_squares(begin(squares), end(squares));
// Вывести в консоль.
print_array(begin(squares), end(squares));
}
// euclid_norm.cpp
// Евклидова норма последовательности как многомерного вектора.
// Пример: { 1, -5, 2, 20, -13 } -> (1+25+4+400+169)1/2 = 24.4744765.
#include <cstddef>
#include <cmath>
#include <iostream>
using namespace std;
/// Чувствительность к погрешности при проверке нормы.
const double TOLERANCE = 1e-6;
// Сравнение двух значений на примерное равенство
// с заданным уровнем относительной разности tolerance.
// В данном примере используется при тестировании.
bool almost_equal(double x1, double x2, double tolerance = TOLERANCE)
{
return abs(x1 - x2) <= tolerance * fmax(abs(x1), abs(x2));
}
// П.1: обработка произвольного массива, переданного как адрес + размер,
// size_t -- стандартный тип (определён в Стандартной библиотеке C),
// предназначенный для хранения размеров массивов.
double euclid_norm(const double a[], size_t n)
{
double s = 0.0;
for (size_t i = 0; i < n; ++i)
s += a[i] * a[i];
return sqrt(s);
}
// П.2: тестирование функции из п.2 на заранее заданных массивах.
bool test_euclid_norm()
{
const double test1[] = { 4, 1, 0, 3, 0, -1, -2, -6 };
// sizeof возвращает размер статического массива в байтах
// (!) при этом массив должен быть виден в данном контексте непосредственно,
// (!) иначе программист рискует получить вместо размера массива размер указателя на него
if (!almost_equal(
euclid_norm(test1, sizeof(test1) / sizeof(double)),
8.18535277))
return false;
const double test2[] = { -40, -2, -111, 42, 2, -1000, -4 };
if (!almost_equal(
euclid_norm(test2, sizeof(test2) / sizeof(double)),
1007.823893))
return false;
// Все тесты прошли успешно.
return true;
}
// П.3: считывание чисел с потока ввода.
double euclid_norm(istream &in)
{
double s = 0.0;
for (double x; in >> x;)
s += x * x;
return sqrt(s);
}
int main()
{
// Запуск тестов из п.2.
cout << test_euclid_norm() << endl;
// Запуск функции из п.3.
const auto result = euclid_norm(cin);
cout << "\nResult: " << result << endl;
return EXIT_SUCCESS;
}
// euclid_norm_2.cpp
// Евклидова норма последовательности как многомерного вектора.
// Пример: { 1, -5, 2, 20, -13 } -> (1+25+4+400+169)1/2 = 24.4744765.
#include <cstddef>
#include <cmath>
#include <iostream>
#include <sstream> // строковые потоки ввода-вывода
using namespace std;
/// Чувствительность к погрешности при проверке нормы.
const double TOLERANCE = 1e-6;
// Сравнение двух значений на примерное равенство
// с заданным уровнем относительной разности tolerance.
// В данном примере используется при тестировании.
bool almost_equal(double x1, double x2, double tolerance = TOLERANCE)
{
return abs(x1 - x2) <= tolerance * fmax(abs(x1), abs(x2));
}
// П.1: обработка произвольного массива, переданного как адрес + размер,
// size_t -- стандартный тип (определён в Стандартной библиотеке C),
// предназначенный для хранения размеров массивов.
double euclid_norm(const double a[], size_t n)
{
double s = 0.0;
for (size_t i = 0; i < n; ++i)
s += a[i] * a[i];
return sqrt(s);
}
// П.2: тестирование функции из п.2 на заранее заданных массивах.
bool test_euclid_norm_array()
{
const double test1[] = { 4, 1, 0, 3, 0, -1, -2, -6 };
// sizeof возвращает размер статического массива в байтах
// (!) при этом массив должен быть виден в данном контексте непосредственно,
// (!) иначе программист рискует получить вместо размера массива размер указателя на него
if (!almost_equal(
euclid_norm(test1, sizeof(test1) / sizeof(double)),
8.18535277))
return false;
const double test2[] = { -40, -2, -111, 42, 2, -1000, -4 };
if (!almost_equal(
euclid_norm(test2, sizeof(test2) / sizeof(double)),
1007.823893))
return false;
// Все тесты прошли успешно.
return true;
}
// П.3: считывание чисел с потока ввода.
double euclid_norm(istream &in)
{
double s = 0.0;
for (double x; in >> x;)
s += x * x;
return sqrt(s);
}
// Дополнение: тестирование функции из п.3 на заранее заданных последовательностях.
bool test_euclid_norm_stream()
{
stringstream ts;
ts << 4 << ' ' << 1 << ' ' << 0 << ' ' << 3 << ' ';
ts << 0 << ' ' << -1 << ' ' << -2 << ' ' << -6;
if (!almost_equal(euclid_norm(ts), 8.18535277))
return false;
ts.clear(); // сбросить флаг конца файла
ts.seekp(0); // сбросить позицию записи в поток на начало
ts.seekg(0); // сбросить позицию чтения из потока на начало
ts << -40 << ' ' << -2 << ' ' << -111 << ' ' << 42 << ' ';
ts << 2 << ' ' << -1000 << ' ' << -4;
if (!almost_equal(euclid_norm(ts), 1007.823893))
return false;
// Все тесты прошли успешно.
return true;
}
int main()
{
// Запуск тестов из п.2.
cout << test_euclid_norm_array() << endl;
// Запуск тестов для функции из п.3.
cout << test_euclid_norm_stream() << endl;
return EXIT_SUCCESS;
}
// max_duplicates_sequence.cpp
// Определить длину максимальной подпоследовательности, состоящей из идущих подряд равных элементов.
// Пример: { 1, 2, 3, 3, 0, 0, 0, 1, 2 } -> 3 (три нуля подряд).
#include <cstddef>
#include <iostream>
#include <sstream> // строковые потоки для тестирования п.4
using namespace std;
// Вычислить максимум двух целых чисел.
inline size_t max(size_t a, size_t b)
{
return a < b? b: a;
}
// П.1: обработка произвольного массива, переданного как адрес + размер
size_t max_duprun(const double a[], size_t n)
{
if (n == 0)
return 0;
// По крайней мере, один элемент в массиве есть.
size_t max_run = 1; // максимальная длина на данный момент
size_t cur_run = 1; // текущая длина
for (size_t i = 1; i < n; ++i)
{
if (a[i] != a[i - 1]) // соседние элементы не равны
cur_run = 1;
else // продолжается подпоследовательность равных
++cur_run;
max_run = max(max_run, cur_run);
}
return max_run;
}
// П.2: тестирование функции из п.1 на заданном массиве с заданным результатом.
bool test_max_duprun_array(const double a[], size_t n, size_t result)
{
return result == max_duprun(a, n);
}
// П.3: считывание чисел с потока ввода.
size_t max_duprun(istream &in)
{
size_t max_run = 0; // максимальная длина на данный момент
double x, prev_x; // последнее и предпоследнее прочитанные числа
if (in >> prev_x)
{
// Последовательность содержит не менее одного элемента.
size_t cur_run = 1; // текущая длина
max_run = 1; // по крайней мере, есть один элемент
while (in >> x)
{
if (x != prev_x) // соседние элементы не равны
{
cur_run = 1;
prev_x = x;
}
else // продолжается подпоследовательность равных
{
++cur_run;
}
max_run = max(max_run, cur_run);
}
}
return max_run;
}
// П.4: тестирование функции из п.3 на заданном массиве с заданным результатом.
bool test_max_duprun_stream(const double a[], size_t n, size_t result)
{
stringstream test;
for (size_t i = 0; i < n; ++i)
test << a[i] << ' ';
return result == max_duprun(test);
}
// Тип функции-"тестера".
using Max_duprun_tester = bool (*)(const double a[], size_t n, size_t result);
// П.2 и п.4: тестирование функции из п.1 или п.3 (выбирается через tester).
int test_max_duprun(Max_duprun_tester tester)
{
const double test1[] = { 1, 1, 2, 2, 2, 2, 0, 4, 2, 2 };
if (!tester(test1, 0, 0)) return 1;
if (!tester(test1, 1, 1)) return 2;
if (!tester(test1, 2, 2)) return 3;
if (!tester(test1, 5, 3)) return 4;
// sizeof возвращает размер статического массива в байтах
// (!) при этом массив должен быть виден в данном контексте непосредственно,
// (!) иначе программист рискует получить вместо размера массива размер указателя на него
if (!tester(test1, sizeof(test1) / sizeof(double), 4))
return 5;
const double test2[] = { -4, -3, -2, -1 };
if (!tester(test2, sizeof(test2) / sizeof(double), 1))
return 6;
const double test3[] = { 1, 2, 3, 3, 0, 0, 0, 1, 2 };
if (!tester(test3, sizeof(test3) / sizeof(double), 3))
return 7;
// Все тесты пройдены успешно.
return 0;
}
int main()
{
cout << test_max_duprun(test_max_duprun_array)
<< test_max_duprun(test_max_duprun_stream)
<< endl;
return EXIT_SUCCESS;
}
// digit_freqs.cpp
// Частоты цифр (относительно всех, только графических, друг друга).
// Выводит только ненулевые частоты.
#include <cstddef>
#include <cctype>
#include <climits> // CHAR_BIT
#include <cassert>
#include <iostream>
using namespace std;
// Количество разных байт. Байт и char -- синонимы в C и C++.
const size_t BYTES = 1u << CHAR_BIT;
// Целочисленный тип для представления счётчиков.
// Тип streamoff -- целочисленный тип, достаточный для того, чтобы описать смещение в потоке
// или размер любого файла в данной системе, т.е. "достаточно большое целое".
using Counter = streamoff;
// Тип "гистограмма" -- массив счётчиков.
using Histogram = Counter[BYTES];
// Строит гистограмму байт потока. Добавляет количества к счётчикам h.
// Возвращает общее количество.
Counter byte_histogram(istream &in, Histogram h)
{
Counter bytes_read = 0;
// Читать по символу из потока, увеличивая на каждой итерации соответствующий счётчик в h.
for (char ch; in.get(ch); ++bytes_read)
h[(unsigned char)ch]++; /* Приведение к unsigned char необходимо так как
по стандарту char может быть "знаковым" и "верхняя половина" диапазона
в таком случае попадает в отрицательные индексы, что (при прямом использовании char)
повлекло бы выход за пределы массива h. */
return bytes_read;
}
// Строит гистограмму массива. Добавляет количества к счётчикам h.
// Возвращает переданный размер.
size_t byte_histogram(const char a[], size_t sz, Histogram h)
{
for (size_t i = 0; i < sz; ++i)
h[(unsigned char)(a[i])]++; /* Приведение к unsigned char необходимо так как
по стандарту char может быть "знаковым" и "верхняя половина" диапазона
в таком случае попадает в отрицательные индексы, что (при прямом использовании char)
повлекло бы выход за пределы массива h. */
return sz;
}
// Тип: указатель на функцию, принимающую и возвращающую целое число.
using Char_predicate = int (*)(int);
// Возвращает сумму элементов гистограммы, для индексов которых предикат filter возвращает истину.
Counter histogram_filter_sum(const Histogram h, Char_predicate filter)
{
Counter s = 0;
for (size_t i = 0; i < BYTES; ++i)
s += filter((int)i)? h[i]: 0; /* i приводится к int,
т.к. стандартные функции --- символьные предикаты принимают int, а не size_t */
return s;
}
// Преобразование номер десятичной цифры -> символ цифры.
inline unsigned char dec_digit(int n)
{
assert(0 <= n && n < 10);
return '0' + n;
}
// Для заданной гистограммы и заданного общего количества символов total получить частоты цифр.
// Возвращает суммарную частоту.
// Данную функцию удобно использовать для тестирования.
double digits_freqs(const Histogram h, Counter total, double freqs[10])
{
Counter h_digit_sum = 0;
const auto divisor = double(total);
for (int digit = 0; digit < 10; ++digit)
{
const auto h_digit = h[dec_digit(digit)];
h_digit_sum += h_digit;
freqs[digit] = h_digit / divisor;
}
return h_digit_sum / divisor;
}
// Вывести частоты в стандартный поток вывода.
// total_freq -- значение, возвращаемое функцией digits_freqs.
void print_digit_freqs(const double freqs[10], double total_freq)
{
for (int digit = 0; digit < 10; ++digit)
{
const auto digit_freq = freqs[digit];
if (digit_freq != 0.0)
cout << dec_digit(digit) << ": " << digit_freq << '\n';
}
cout << "Total: " << total_freq << endl;
}
// "Комплекс мероприятий": по гистограмме получить и вывести частоты для всех трёх случаев из задания.
// total -- количество всех символов (сумма гистограммы).
void print_relative_digit_freqs(const Histogram h, Counter total)
{
double freqs[10];
// 1. Для всех символов.
cout << "Digits among all characters\n";
print_digit_freqs(freqs,
digits_freqs(h, total, freqs));
// 2. Для графических.
cout << "\nDigits among graphical characters\n";
print_digit_freqs(freqs,
digits_freqs(h, histogram_filter_sum(h, isgraph), freqs));
// 3. Для цифр.
cout << "\nDigits among digits\n";
print_digit_freqs(freqs,
digits_freqs(h, histogram_filter_sum(h, isdigit), freqs));
}
///////////////////////////////////////////////////////////////////////////////
// Тестирование
// Сравнение на равенство пары массивов из 10 double.
bool are_freqs_equal(const double ft[10], const double fr[10])
{
for (int i = 0; i < 10; ++i)
if (ft[i] != fr[i])
return false;
return true;
}
// Собственно автоматический тест.
int test_digits_freqs()
{
const auto text = "This is a text with some 013 digits in it 01456...";
// 50 символов, из них графических 40, цифр 8, 0 и 1 встречаются дважды, 3456 -- однажды.
const double
f0[10] = { 0.04, 0.04, 0.0, 0.02, 0.02, 0.02, 0.02 },
f1[10] = { 0.05, 0.05, 0.0, 0.025, 0.025, 0.025, 0.025 },
f2[10] = { 0.25, 0.25, 0.0, 0.125, 0.125, 0.125, 0.125 };
Histogram h = {};
double freqs[10];
const auto total = byte_histogram(text, 50, h);
if (digits_freqs(h, total, freqs) != 0.16)
return 1;
if (!are_freqs_equal(freqs, f0))
return 2;
if (digits_freqs(h, histogram_filter_sum(h, isgraph), freqs) != 0.2)
return 3;
if (!are_freqs_equal(freqs, f1))
return 4;
if (digits_freqs(h, histogram_filter_sum(h, isdigit), freqs) != 1.0)
return 5;
if (!are_freqs_equal(freqs, f2))
return 6;
return 0;
}
int main()
{
cout << "Testing: " << test_digits_freqs() << endl;
Histogram h = {};
auto total = byte_histogram(cin, h);
cin.clear();
cout.precision(16);
print_relative_digit_freqs(h, total);
return EXIT_SUCCESS;
}
// cstring_array.cpp
// Ввод-вывод средствами стандартной библиотеки C (не C++),
// управление динамической памятью также средствами C (malloc, calloc, realloc, free).
#include <cstdlib> // malloc, realloc, free
#include <cstdio> // puts, fgets
#include <cstring> // strlen, memcpy
using namespace std;
/// Максимальная длина строки (не включая '\0'), возвращаемой нашим вариантом gets.
const size_t MAX_GETS_LENGTH = 1023;
/// Вместо std::gets (которая объявлена устаревшей), мы реализуем
/// собственную функцию gets, создающую строку в динамической памяти.
/// Если строка на вводе слишком длинная, отрезаем на MAX_GETS_LENGTH символах.
/// Возвращает нулевой указатель, если не удалось прочитать ни одного символа.
char* gets()
{
char buffer[MAX_GETS_LENGTH + 1];
if (!fgets(buffer, MAX_GETS_LENGTH + 1, stdin))
return nullptr;
// Узнать длину считанной строки.
auto alloc_len = strlen(buffer) + 1;
// В отличие от gets, fgets записывает в буфер и перевод строки (если хватает места).
// Уберём этот перевод строки.
if (alloc_len > 1 && buffer[alloc_len - 2] == '\n')
{
buffer[alloc_len - 2] = '\0';
--alloc_len;
}
// Выделить в динамической памяти место на копию.
const auto new_str = (char*)malloc(alloc_len);
if (!new_str) // не хватило памяти?
return nullptr;
// Скопировать содержимое буфера в выделенную память.
memcpy(new_str, buffer, alloc_len);
return new_str;
}
/// Читаем построчно и складываем в динамический массив указатели.
/// Последний указатель в массиве обязательно нулевой.
/// Возвращает нулевой указатель в случае невозможности выделить память хотя бы на два указателя.
/// Увеличиваем массив "на ходу" по мере необходимости.
char** getlines()
{
auto lines = (char**)calloc(2, sizeof(char*));
if (!lines) // не хватило памяти?
return nullptr;
// Цикл по строкам.
for (size_t item = 0, capacity = 2; lines[item++] = gets();)
{
if (capacity == item + 1) // все элементы массива задействованы -- увеличим его
{
// Попытка 1: попробуем увеличить capacity в 1.5 раза.
capacity += capacity / 2 + 1;
// Для больших capacity возможно переполнение capacity * sizeof(char*).
assert((capacity * sizeof(char*)) / sizeof(char*) == capacity);
if (auto new_lines = (char**)realloc(lines, capacity * sizeof(char*)))
{
lines = new_lines;
}
else // Попытка 2: попробуем увеличить capacity на 1 элемент.
if (auto new_lines = (char**)realloc(lines, (item + 2) * sizeof(char*)))
{
capacity = item + 2;
lines = new_lines;
}
else // Не получается выделить память.
{
lines[item] = nullptr; // закрывающий нулевой указатель
break;
}
}
}
return lines;
}
/// Вывести в стандартный поток вывода массив строк.
void putlines(const char* const* lines)
{
if (!lines)
return;
while (*lines)
puts(*lines++);
}
/// Освободить память, занимаемую массивом строк.
void freelines(char** lines)
{
if (!lines)
return;
for (auto p = lines; *p != nullptr; ++p)
free(*p);
free(lines);
}
///////////////////////////////////////////////////////////////////////////////
// Тестирование: ввести и вывести текст через консоль.
int main()
{
while (true)
{
// Ввод текста.
puts("\nEnter a text:\n");
auto lines = getlines();
clearerr(stdin);
// Вывод текста.
puts("\nThe text entered is:\n");
putlines(lines);
freelines(lines);
}
}
// remove_comments_simple.cpp
/// Найти в си-строке str символ ch (аналог стандартной функции strchr).
/// Возвращает указатель на найденный символ или нулевой указатель, если символа в строке нет.
char* find_char(char *str, char ch)
{
for (; *str != '\0'; ++str)
{
if (*str == ch)
return str;
}
return nullptr;
}
/// Затереть нулём первый символ, открывающий комментарий, закончив таким образом на нём си-строку.
void remove_comment(char *line, char comment_mark)
{
if (auto pos = find_char(line, comment_mark))
*pos = '\0';
}
/// Удалить однострочные комментарии из текста.
void remove_comments(char *text[], char comment_mark)
{
for (; *text != nullptr; ++text)
remove_comment(*text, comment_mark);
}
///////////////////////////////////////////////////////////////////////////////
// Тестирование.
#include <cstring> // strcmp, strlen, memcpy
// Вспомогательные функции.
/// Сравнение текстов на равенство.
bool are_equal(const char * const text1[], const char * const text2[])
{
for (; *text1 && *text2; ++text1, ++text2)
{
// Сравнение си-строк на равенство с помощью стандартной функции.
if (std::strcmp(*text1, *text2) != 0)
return false;
}
// Оба указателя должны быть нулевыми, если тексты совпадают.
return *text1 == *text2;
}
/// Определить количество строк в тексте.
std::size_t lines_in_text(const char * const source[])
{
std::size_t source_size = 0;
for (auto p = source; *p != nullptr; ++p)
++source_size;
return source_size;
}
/// Вспомогательная функция для создания копии текста.
/// Она нужна для того, чтобы не изменять значения, заданные строковыми литералами (что чревато неопределённым поведением).
char** copy_text(const char * const source[])
{
// Создать массив строк.
const auto source_size = lines_in_text(source);
auto copy = new char*[source_size + 1];
// Скопировать массив построчно.
for (size_t i = 0; i < source_size; ++i)
{
// Выделить память для новой строки.
const auto line_len = std::strlen(source[i]) + 1;
copy[i] = new char[line_len];
// Скопировать строку (вместе с завершающим нулём).
std::memcpy(copy[i], source[i], line_len);
}
// Записать завершающий нуль.
copy[source_size] = nullptr;
// Вернуть результат.
return copy;
}
/// Освобождение памяти, занятой текстом, созданным с помощью функции copy_text.
void free_text(char *text[])
{
for (auto p = text; *p != nullptr; ++p)
delete[] *p;
delete[] text;
}
// Собственно тестирование.
/// Тест функции remove_comments.
bool test_remove_comments()
{
// Исходный текст.
const char *input[] =
{
"",
"# comment",
"something; # comment",
"'hello, world!'",
"'# not a comment but it's OK to cut here too'... # a real comment",
nullptr
};
// Текст результата, который должен получиться.
const char *reference[] =
{
"",
"",
"something; ",
"'hello, world!'",
"'",
nullptr
};
auto text = copy_text(input);
remove_comments(text, '#');
const auto result = are_equal(text, reference);
free_text(text);
return result;
}
#include <iostream>
int main()
{
std::cout << test_remove_comments();
return EXIT_SUCCESS;
}
// simple_tokenize.cpp
//
// Задача.
//
// Вычленить в строке слова, заполнив массив си-строк указателями на первые буквы слов,
// а пробельные символы заменив нулями.
// Память под массив выделяется извне (пользователем).
// Функция принимает указатель на целевой массив и его размер,
// возвращает указатель на последний необработанный символ (нулевой указатель, если вся строка обработана).
// Элемент, следующий за последним записанным в массив указателем должен быть нулём.
//
// Алгоритм.
//
// Пока исходная строка не кончилась, циклически повторяем два действия:
//
// 1. Проходим по исходной строке, затирая нулями пробельные символы.
// Если встретился непробельный символ, то записываем указатель на него на следующую позицию в массиве.
// 2. Двигаемся по строке до первого пробельного символа.
//
#include <cassert>
#include <cstddef> // size_t
#include <cctype> // isspace
/// Затереть последовательность пробельных символов нулевым символом.
char* zero_spaces(char *text)
{
while (std::isspace(*text))
*text++ = '\0';
return text;
}
/// Пропустить все непробельные символы (кроме завершающего нуля).
char* skip_non_spaces(char *line)
{
while (*line != '\0' && !std::isspace(*line))
++line;
return line;
}
/// Выполнить вычленение "слов" в строке text, указатели на слова записать в массив words.
/// Массив words создаётся кодом, вызывающим эту функцию.
/// Параметром words_size передаётся размер массива words.
char* split(char *text, char *words[], std::size_t words_size)
{
assert(words_size > 1);
const auto max_words = words_size - 1;
for (std::size_t word = 0; word < max_words; ++word)
{
text = zero_spaces(text);
if (*text == '\0')
{
words[word] = nullptr;
return nullptr;
}
words[word] = text;
text = skip_non_spaces(text);
}
words[max_words] = nullptr;
// Перейти к началу следующего слова.
text = zero_spaces(text);
// Возможно, строка кончилась (т.е. был "хвост" из пробельных символов), тогда вернуть nullptr.
return *text != '\0' ? text : nullptr;
}
///////////////////////////////////////////////////////////////////////////////
// Тестирование.
#include <cstring> // strcmp, strlen, memcpy
/// Сравнение текстов на равенство.
bool are_equal(const char * const text1[], const char * const text2[])
{
for (; *text1 && *text2; ++text1, ++text2)
{
// Сравнение си-строк на равенство с помощью стандартной функции.
if (std::strcmp(*text1, *text2) != 0)
return false;
}
// Оба указателя должны быть нулевыми, если тексты совпадают.
return *text1 == *text2;
}
/// Тест split.
int test_split()
{
char text[] = "Just a simple sentence.";
const char *reference[] =
{
"Just",
"a",
"simple",
"sentence.",
nullptr
};
// Проверка случая, когда передан массив достаточного размера.
char *words[10];
if (split(text, words, 10))
return 1; // split должна вернуть нулевой указатель
if (!are_equal(words, reference))
return 2;
// Проверка случая, когда передан массив недостаточного размера.
char long_text[] =
"This program is free software; you can redistribute it and/or modify\n"
"it under the terms of the GNU General Public License as published by\n"
"the Free Software Foundation; either version 3 of the License, or (at\n"
"your option) any later version.";
const auto last_pos = split(long_text, words, 10);
if (!last_pos || sizeof(long_text) < last_pos - long_text)
return 3;
if (*last_pos != 'a') // следующее слово было бы "and/or"
return 4;
const char *long_reference[] =
{
"This",
"program",
"is",
"free",
"software;",
"you",
"can",
"redistribute",
"it",
nullptr
};
if (!are_equal(words, long_reference))
return 5;
return 0; // ошибки не обнаружены.
}
#include <iostream>
int main()
{
const auto test = test_split();
std::cout << test << std::endl;
assert(test == 0);
return EXIT_SUCCESS;
}
// login.c
// Пример уязвимости gets и printf.
// Имел параллели в реальном коде.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
// Сгенерировать псевдослучайную строку.
void generate_random_str(char *str, size_t n)
{
memset(str, 0, n + 1);
while (n--)
str[n] = 'a' + rand() % 26;
}
// Сгенерировать псевдослучайные логин и пароль.
void load_credentials(char **login, char **pwd)
{
static char login_buf[9];
static char pwd_buf[9];
generate_random_str(login_buf, 8);
generate_random_str(pwd_buf, 8);
*login = login_buf;
*pwd = pwd_buf;
}
int main(void)
{
#define BUFSIZE 80
char login_buf[BUFSIZE];
char pwd_buf[BUFSIZE];
char *root_login;
char *root_pwd;
// Сгенерировать случайные логин и пароль.
srand(time(NULL));
load_credentials(&root_login, &root_pwd);
// Допускается бесконечное число попыток входа.
for (;;)
{
// Считать логин.
memset(login_buf, 0, BUFSIZE);
memset(pwd_buf, 0, BUFSIZE);
printf("Login:");
gets(login_buf);
// Считать пароль.
printf("Pwd:");
gets(pwd_buf);
// Сравнить логин и пароль со сгенерированными.
if (strcmp(login_buf, root_login) || strcmp(pwd_buf, root_pwd))
{
printf(login_buf);
printf(" failed to login\n");
}
else // access granted
{
printf("Congratulations! Access granted!\n");
break;
}
}
getchar(); // задержка экрана
}
// longest_palindromic_substring_a.cpp
// Задача: в заданной строке найти самую длинную подстроку-палиндром.
// Алгоритм решения: начиная с длины строки (и уменьшая её до 2) перебирать все подстроки заданной длины,
// проверяя, являются ли они палиндромами.
#include <cstddef>
/// Функция проверяет, является ли содержимое диапазона строки палиндромом.
bool is_palindrome(const char *begin, const char *end)
{
while (begin < end)
if (*begin++ != *--end)
return false;
return true;
}
/// Найти самую длинную подстроку-палиндром в диапазоне строки.
/// Возвращает длину найденной подстроки, по указателю found записывает указатель на начало найденной подстроки.
std::size_t longest_palindrome(const char *begin, const char *end, const char **found)
{
for (auto n = end - begin; n > 1; --n) // длина палиндрома
{
for (auto pos = begin; end - pos >= n; ++pos) // начало подстроки
{
if (is_palindrome(pos, pos + n)) // палиндром?
{
*found = pos;
return n;
}
}
}
return 0;
}
///////////////////////////////////////////////////////////////////////////////
// Тестирование
#include <string>
#include <iostream>
#include <cassert>
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;
}
// longest_palindromic_substring_b.cpp
// Задача: в заданной строке найти самую длинную подстроку-палиндром.
// Алгоритм решения
// Искать набольшую общую подстроку двух строк: исходной и исходной в обратном порядке.
#include <cstddef>
/// Найти совпадающие символы при движении по диапазону 1 в прямом направлении, а по диапазону 2 -- в обратном.
/// Возвращает истину, если удалось найти.
bool find_factor
(
const char *begin1, const char *end1, // диапазон 1
const char *begin2, const char *end2, // диапазон 2
const char **found1, // позиция найденного символа в диапазоне 1
const char **found2 // позиция найденного символа в диапазоне 2
)
{
while (begin1 != end1 && begin2 != end2)
{
if (*begin1++ == *--end2)
{
*found1 = begin1 - 1;
*found2 = end2;
return true;
}
}
return false;
}
/// Посчитать длину максимальной совпадающей последовательности с начала диапазона 1 и конца диапазона 2.
std::size_t longest_common_prefix_suffix
(
const char *begin1, const char *end1, // диапазон 1
const char *begin2, const char *end2 // диапазон 2
)
{
std::size_t cnt = 0;
while (begin1 != end1 && begin2 != end2)
{
if (*begin1++ != *--end2)
break;
++cnt;
}
return cnt;
}
/// Идти по диапазону 1 с начала, а по диапазону 2 -- с конца.
/// В случае совпадающей последовательности символов считать их и вернуть самую длинную последовательность (указатель в диапазоне 1).
std::size_t longest_common_factor_0
(
const char *begin1, const char *end1, // диапазон 1
const char *begin2, const char *end2, // диапазон 2
const char **found1 // позиция найденной подстроки в диапазоне 1
)
{
std::size_t cur_max = 0;
while (find_factor(begin1, end1, begin2, end2, &begin1, &end2))
{
if (end1 <= begin1 + cur_max || ++end2 <= begin2 + cur_max)
break;
// Первый символ уже проверен find_factor, отсюда отступы на единицы.
const auto factor_len = 1 + longest_common_prefix_suffix(begin1 + 1, end1, begin2, end2 - 1);
if (cur_max < factor_len)
{
*found1 = begin1;
cur_max = factor_len;
}
begin1 += factor_len;
end2 -= factor_len;
}
return cur_max;
}
/// Перебирать все подстроки диапазона 1, сохраняя максимум результата longest_common_factor.
std::size_t longest_common_factor_1
(
const char *begin1, const char *end1, // диапазон 1
const char *begin2, const char *end2, // диапазон 2
const char **found1 // позиция найденной подстроки в диапазоне 1
)
{
std::size_t cur_max = 0;
for (; begin1 + cur_max < end1; ++begin1)
{
const char *factor_pos;
const auto factor_len = longest_common_factor_0(begin1, end1, begin2, end2, &factor_pos);
if (cur_max < factor_len)
{
cur_max = factor_len;
*found1 = factor_pos;
}
}
return cur_max;
}
/// Перебирать все подстроки диапазона 2, сохраняя максимум результата longest_common_factor.
std::size_t longest_common_factor_2
(
const char *begin1, const char *end1, // диапазон 1
const char *begin2, const char *end2, // диапазон 2
const char **found1 // позиция найденной подстроки в диапазоне 1
)
{
std::size_t cur_max = 0;
for (; begin2 + cur_max < end2; --end2)
{
const char *factor_pos;
const auto factor_len = longest_common_factor_0(begin1, end1, begin2, end2, &factor_pos);
if (cur_max < factor_len)
{
cur_max = factor_len;
*found1 = factor_pos;
}
}
return cur_max;
}
/// Найти самую длинную подстроку-палиндром в диапазоне строки.
/// Возвращает длину найденной подстроки, по указателю found записывает указатель на начало найденной подстроки.
std::size_t longest_palindrome(const char *begin, const char *end, const char **found)
{
const char *f1, *f2;
const auto
l1 = longest_common_factor_1(begin, end, begin, end, &f1),
l2 = longest_common_factor_2(begin, end, begin, end, &f2);
if (l1 == 1 && l2 == 1)
return 0;
if (l2 < l1)
{
*found = f1;
return l1;
}
else
{
*found = f2;
return l2;
}
}
///////////////////////////////////////////////////////////////////////////////
// Тестирование
#include <string>
#include <iostream>
#include <cassert>
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;
}
// longest_palindromic_substring_c.cpp
// Задача: в заданной строке найти самую длинную подстроку-палиндром.
// Алгоритм решения
// Палиндромы нечётной длины: перебирать символы строки, определять наибольший палиндром, центром которого они являются.
// Палиндромы чётной длины: перебирать пары совпадающих символов, определять наибольший палиндром, центром которого они являются.
#include <cstddef>
#include <cassert>
/// Определить максимальную длину совпадающих суффикса массива [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 <string>
#include <iostream>
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;
}
// function_ptr_solve.cpp
// Приближённое решение произвольного уравнения f(x) = 0
// методом деления отрезка пополам.
// f передаётся указателем на функцию.
#include <cassert>
#include <cmath>
/// Тип "правая часть уравнения" -- функция одного действительного параметра.
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 <cstdlib>
#include <iostream>
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;
}
// nsolve_callback.cpp
// Приближённое решение произвольного уравнения f(x) = 0 с поиском нескольких корней.
// Метод деления пополам на равномерной сетке, разбивающей заданный отрезок (участок поиска).
#include <cassert>
#include <cmath>
/// Тип "правая часть уравнения" -- функция одного действительного параметра.
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);
using namespace std;
double left = a, f_left = f(left);
bool f_left_zero = abs(f_left) <= f_tol;
// Корень на левой границе исходного отрезка?
if (f_left_zero && !report(left))
return left;
while (left != b)
{
// Правая граница очередного участка.
const double right = fmin(b, left + step), f_right = f(right);
const bool f_right_zero = abs(f_right) <= f_tol;
// Корень на правой границе участка?
if (f_right_zero && !report(right))
return right;
// Есть корень внутри участка?
if (!(f_left_zero || f_right_zero) && signbit(f_left) != signbit(f_right))
{
const double root = solver(f, left, right, x_tol);
if (!report(root))
return root;
}
// Передвинуть левую границу.
left = right;
f_left = f_right;
f_left_zero = f_right_zero;
}
return b;
}
///////////////////////////////////////////////////////////////////////////////
// Тестирование.
#include <cstdlib>
#include <iostream>
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);
}
/// Вывести очередной корень.
bool print_root(double root)
{
cout << root << endl;
return true;
}
int main()
{
struct { const char *msg; Unary_real_function f; double a, b, step; }
tasks[] =
{
{ "poly: ", poly5, -10.0, 10.0, 0.5 },
{ "poly (1): ", poly5, -10.5, 10.5, 0.3 },
{ "e: ", loge, 0.01, 100., 0.1 },
{ "ipl: ", ipl, -100., 100., 0.5 },
{ "sin: ", sin, 0., 30., 0.2 }
};
cout.precision(16);
for (auto &task : tasks)
{
cout << task.msg << endl;
repeated_nsolve(task.f, task.a, task.b, task.step, print_root);
cout << "---------------\n" << endl;
}
return EXIT_SUCCESS;
}
// global_solve.cpp
#include <cfloat>
#include <cassert>
#include <cmath>
/// Точность приближённого решения, используемая по умолчанию.
const double TOLERANCE = 1e-9;
/// Найти диапазон [left, right] такой, что x0 >= left и существует left <= x <= right, что f(x) = 0.
/// Предполагается, что f(x) -- непрерывная функция.
/// Минимальная ширина шага по x задаётся параметром tol.
typedef double (*Function)(double);
bool catch_root_to_the_right
(
Function f,
double &left,
double &right,
double x0 = 0.,
double tol = TOLERANCE,
double max_j = DBL_MAX
)
{
using namespace std;
max_j = fmin(max_j, 1. / DBL_EPSILON);
double f_left = f(x0), f_right;
// Найти левую границу отрезка.
if (isnan(f_left))
for (double j = 1.; j < max_j; j += 2.)
for (double i = tol * j; isfinite(i); i *= 2.)
if (isfinite(f_left = f(x0 + i)))
{
x0 += i;
goto left_found;
}
left_found:
// Уже нашли ноль?
if (f_left == 0.)
{
left = right = x0;
return true;
}
// Найти правую границу отрезка.
for (double j = 1.; j < max_j; j += 2.)
for (double i = tol * j; isfinite(i); i *= 2.)
if (isfinite(f_right = f(x0 + i)))
{
// Нашли ноль?
if (f_right == 0.)
{
left = right = x0 + i;
return true;
}
// Разные знаки на концах отрезка?
if (f_left * f_right < 0.)
{
left = x0;
right = x0 + i;
return true;
}
}
// Найти не удалось.
return false;
}
/// Алгоритм численного решения уравнения f(x) = 0 на отрезке [a, b] делением отрезка пополам.
/// Данный алгоритм является вариантом двоичного поиска.
double nsolve(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 <cstdlib>
#include <iostream>
struct Test_result
{
bool root_found; // корень был найден?
double a, b, root, f_root; // диапазон, корень, значение функции в корне
};
// Для заданной функции f найти диапазон, содержащий корень f(x) = 0.
// Затем найти на этом диапазоне сам корень (приближённо) и вычислить значение функции в нём.
void test(Function f, Test_result &result)
{
result.root_found = false;
if (catch_root_to_the_right(f, result.a, result.b))
{
result.root_found = true;
result.root = nsolve(f, result.a, result.b);
result.f_root = f(result.root);
}
}
int main()
{
using namespace std;
cout.precision(9);
// Набор заданий: функции и текстовые обозначения.
struct Task {
Function f;
const char *name;
Test_result result;
} task[] =
{
{ sin, "sin" },
{ cos, "cos" },
#define F(expr, name) \
{ [](double x) { return expr; }, name }
F(tan(x - 1.), "tan1"),
F(exp(x) - 1000., "expm"),
F(20. / (x*x) - 0.1, "rep"),
F(pow(3., x) - x*x*x, "W3"),
F(exp(sin(0.1*x)) - exp(cos(sqrt(2.)*x)), "cexp"),
F(log((x + 100.) / x) - 1 / sqrt(x), "logr"),
F(log(sin(x) / x) / tan(x - 2.5)*cos(x), "f1"),
F(10. / cbrt(x) - 1 / (1. + log(x + 1.)) + 100. / sqrt(x), "f2"),
F(atan(log(abs(tan(x) - exp(x)))) - 0.5, "f3"),
F(atan(log(abs(tan(x + 0.5)*tan(sqrt(2.)*x + 0.3)))) - 1.4, "f4"),
F(tanh(-sin(1. / cosh(x - 100.)*sin(sinh(x - 100.)))) + 0.15, "chirp"),
F(exp(-1. / pow(x - 100123., 8)) - 0.7, "b100k"),
F(log(x) / exp(1. / x) + 0.09726, "touch"),
F(0.1 + cbrt(x) - pow(x, 1./5.) - pow(x, 1./7.), "357"),
F((x < 1e+6? abs(sin(x+0.1)*sin(sqrt(30.)*x+0.1)) - 0.001: 1.), "s30")
#undef F
};
// Параллельное вычисление результатов (использует OpenMP).
static const int tasks = sizeof(task) / sizeof(Task);
#pragma omp parallel for
for (int i = 0; i < tasks; ++i)
test(task[i].f, task[i].result);
// Последовательный вывод результатов.
for (auto &t: task)
{
cout << t.name << ": ";
auto &r = t.result;
if (r.root_found)
{
cout << '[' << r.a << ", " << r.b << "], root = ";
cout << r.root << ", f(root) = " << r.f_root << '\n';
}
else
{
cout << "no roots found\n";
}
}
cout << "done" << endl;
cin.ignore();
return EXIT_SUCCESS;
}
// isqrt.cpp
// Квадратный корень целого числа, округлённый вниз.
#include <cstdint>
#include <cmath>
// Через стандартную функцию для вычисления квадратного корня в плавающей точке.
// Должно работать быстро на современных процессорах.
// "Внутри" обычно реализовано на основе метода Ньютона.
inline uint32_t isqrt_fpu(uint32_t n)
{
return uint32_t(sqrt(double(n)));
}
// Метод деления отрезка пополам.
uint32_t isqrt_dt1(uint32_t n)
{
// Границы диапазона: [0, 65535]
// (65535 в квадрате представимо в 32-битным числом, 65536 -- уже нет).
uint32_t a = 0, b = 65536;
// Цикл выполняет 16 итераций.
for (int i = 0; i < 16; ++i)
{
// Середина отрезка [a, b], с округлением вниз.
const auto m = (a + b) >> 1;
if (m * m > n)
b = m;
else
a = m;
}
return a;
}
// Метод деления отрезка пополам: на одну переменную меньше.
uint32_t isqrt_dt2(uint32_t n)
{
register uint32_t a = 0, d = 32768;
do
{
// Середина отрезка [a, b], с округлением вниз.
const auto m = a + d;
if (m * m <= n)
a = m;
} while (d >>= 1);
return a;
}
/////////////////////////////////////////////////////////////////////
// Тестирование
#include <iostream>
#include <ctime>
using namespace std;
// Корректность
void test_isqrt()
{
for (uint32_t n = 0;; ++n)
{
const auto
fpu = isqrt_fpu(n),
dt1 = isqrt_dt1(n),
dt2 = isqrt_dt2(n);
if (dt1 != fpu)
cout << "dt1 " << n << endl;
if (dt2 != fpu)
cout << "dt2 " << n << endl;
if (n == UINT32_MAX)
return;
}
}
// Время
#define TIME_TEST(func)\
double time_##func(unsigned dummy)\
{\
const auto t0 = clock();\
for (uint32_t n = 0; func(n) != dummy && n != UINT32_MAX; ++n) {}\
return double(clock() - t0) / CLOCKS_PER_SEC;\
}
TIME_TEST(isqrt_fpu)
TIME_TEST(isqrt_dt1)
TIME_TEST(isqrt_dt2)
void time_all(const char *msg, int dummy)
{
cout << msg;
cout << "\nfpu: " << time_isqrt_fpu(dummy) << "s\n";
cout << "dt1: " << time_isqrt_dt1(dummy) << "s\n";
cout << "dt2: " << time_isqrt_dt2(dummy) << "s\n\n";
}
int main()
{
test_isqrt();
cout << "Correctness testing done." << endl;
time_all("Full uint32_t range:", 65536);
time_all("First 1/64 of uint32_t range:", 8192);
time_all("First 1/256 of uint32_t range:", 4096);
time_all("First 1/4096 of uint32_t range:", 1024);
cout << "Time testing done." << endl;
//cin.ignore();
return EXIT_SUCCESS;
}
// polynomials_estrin2.cpp
// Вычисление многочленов.
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cassert>
using namespace std;
/// близость значений по абсолютной разности
bool abs_close(double a, double b, double tol = 1e-10)
{
return abs(a - b) <= tol;
}
// многочлены
// sum(ai*x^i, i=0:(n-1)) = (...((a(n-1)*x + a(n-2))*x + ...)*x + a0
double poly_horner(double x, double a[], size_t n)
{
assert(n != 0);
auto s = a[--n];
while (n != 0)
s = s * x + a[--n];
return s;
}
// fma(a, b, c) --> (a * b + c) с одним округлением (C99, C++11)
double poly_horner_fma(double x, double a[], size_t n)
{
assert(n != 0);
auto s = a[--n];
while (n != 0)
s = fma(s, x, a[--n]);
return s;
}
// a3*x^3 + a2*x^2 + a1*x + a0 = (a3*x + a2)*x^2 + (a1*x + a0)
// sum(ai*x^i, i=0:(n-1)) =
// (...((a(n-1)*x + a(n-2))*x^2 + (a(n-3)*x + a(n-4)))*x^2 + ...)*x^2 + (a1*x + a0)
// -- метод Горнера по x^2
double poly_estrin2_fma(double x, double a[], size_t n)
{
assert(n != 0);
if (n == 1)
return a[0];
// один шаг схемы Эстрина + метод Горнера + fma
const auto x2 = x * x;
auto s = fma(a[n-1], x, a[n-2]);
for (--n; n > 2; n -= 2)
{
const auto p = fma(a[n-2], x, a[n-3]);
s = fma(s, x2, p);
}
// если был нечётный размер массива, то n == 2, иначе 1
return n != 2? s: fma(s, x, a[0]);
}
///////////////////////////////////////////////////////////////////////////////
// Тестирование
typedef double (*poly_eval_fun)(double, double*, size_t);
bool test_poly_eval(poly_eval_fun poly)
{
double test[] = { 20., -1., 4., 9., -8., 4. };
const size_t size = sizeof(test) / sizeof(double);
return poly(100., test, 1) == 20.
&& poly(0., test, size) == 20.
&& poly(0., test, size - 1) == 20.
&& abs_close(poly(1., test, size - 1), 24.)
&& abs_close(poly(-1., test, size - 1), 8.)
&& abs_close(poly(2.5, test, size - 1), -129.375)
&& abs_close(poly(1., test, size), 28.)
&& abs_close(poly(-1., test, size), 4.)
&& abs_close(poly(2.5, test, size), 261.25);
}
int main()
{
using namespace std;
poly_eval_fun poly[] =
{
poly_horner,
poly_horner_fma,
poly_estrin2_fma
};
for (auto pf: poly)
cout << test_poly_eval(pf);
cout << endl;
return EXIT_SUCCESS;
}
// amatrix.hpp
// Общие задачи обслуживания динамических массивов, которые можно интерпретировать как матрицы.
// Работа на C++ в стиле C.
#ifndef AMATRIX_HPP_INCLUDED_AMA700
#define AMATRIX_HPP_INCLUDED_AMA700
// Используются упакованные двумерные массивы.
// Под "упакованным" понимается массив, все элементы которого расположены в памяти без разрывов.
// Таким образом, фактически двумерный массив является одномерным с особым режимом индексирования.
// Элемент с двумерным индексом (i, j) имеет одномерный индекс (i * cols + j),
// где cols -- количество столбцов (т.е. строки идут друг за другом в памяти).
#include <cstddef> // size_t
#include <cstdlib> // calloc, realloc, free
/// Описание матрицы.
struct Matrix_info
{
double *data; ///< Указатель на массив элементов.
size_t rows, ///< Количество строк.
cols; ///< Размер строки (количество столбцов).
};
// Ключевое слово inline позволяет размещать определения функций
// непосредственно в заголовочном файле, что часто удобно, так как не требуется отдельный .cpp файл.
/// Определить количество элементов матрицы mtx.
inline size_t matrix_size(const Matrix_info *mtx)
{
return mtx->rows * mtx->cols;
}
/// Создать динамический массив нужного размера, заполнить поля mtx.
/// Возвращает true в случае успеха и false в случае ошибки.
/// В случае ошибки выделения памяти обнуляет поля *mtx.
inline bool alloc_matrix(Matrix_info *mtx, size_t rows, size_t cols)
{
// Проверить, представимо ли произведение rows на cols в виде значения size_t.
const auto elements = rows * cols;
if (elements / rows == cols &&
(mtx->data = (double*)std::calloc(elements, sizeof(double))))
{
mtx->rows = rows;
mtx->cols = cols;
return true;
}
else
{
mtx->data = nullptr;
mtx->rows = 0;
mtx->cols = 0;
return false;
}
}
/// Освободить динамический массив, привязанный к матрице.
/// Обнуляет поля *mtx.
inline void free_matrix(Matrix_info *mtx)
{
std::free(mtx->data);
mtx->data = nullptr;
mtx->rows = 0;
mtx->cols = 0;
}
/// Переформатировать существующую матрицу под новый размер.
/// Возвращает true в случае успеха и false в случае ошибки.
/// В случае ошибки выделения памяти оставляет поля *mtx неизменными.
inline bool realloc_matrix(Matrix_info *mtx, size_t rows, size_t cols)
{
const auto elements = rows * cols;
// Проверить, представимо ли произведение rows на cols в виде значения size_t.
if (elements / rows != cols)
return false;
if (matrix_size(mtx) < elements)
{
const auto bytes = elements * sizeof(double);
if (bytes / sizeof(double) != elements)
return false; // Столько байт нельзя выделить.
// Попытаться расширить блок.
const auto data = (double*)std::realloc(mtx->data, bytes);
if (!data)
return false;
// Удалось расширить блок.
mtx->data = data;
mtx->rows = rows;
mtx->cols = cols;
return true;
}
else
{
mtx->rows = rows;
mtx->cols = cols;
return true;
}
}
/// Присвоить всем элементам матрицы заданное значение.
inline void fill_matrix(Matrix_info *mtx, double value)
{
const auto elements = matrix_size(mtx);
const auto data = mtx->data;
for (size_t i = 0; i < elements; ++i)
data[i] = value;
}
/// Заполнить матрицу значениями из статического массива (если требуется, выделяет память).
/// Значения полей *mtx должны быть инициализированы (хотя бы нулями).
inline void matrix_from_array(Matrix_info *mtx, size_t rows, size_t cols, const double *arr2)
{
// Подготовить место.
realloc_matrix(mtx, rows, cols);
// Скопировать поэлементно подряд.
const auto sz = matrix_size(mtx);
const auto data = mtx->data;
for (size_t i = 0; i < sz; ++i)
data[i] = arr2[i]; // вместо цикла можно использовать memcpy из cstring
}
/// Создать единичную матрицу размера n x n.
/// Значения полей *mtx должны быть инициализированы (хотя бы нулями).
inline void identity(Matrix_info *mtx, size_t n)
{
// Подготовить место.
realloc_matrix(mtx, n, n);
// Большинство элементов единичной матрицы -- нули.
fill_matrix(mtx, 0.0);
// Но по диагонали идут единицы.
auto write_pos = mtx->data;
for (size_t i = 0; i < n; ++i)
{
*write_pos = 1.0;
write_pos += (n + 1);
}
}
/// Скопировать содержимое одной матрицы в другую.
/// Значения полей *dst должны быть инициализированы (хотя бы нулями).
inline void copy_matrix(const Matrix_info *src, Matrix_info *dst)
{
// Подготовить место под копию.
realloc_matrix(dst, src->rows, src->cols);
// Скопировать всё содержимое массива подряд.
const auto elements = matrix_size(src);
const auto sd = src->data;
const auto dd = dst->data;
for (size_t i = 0; i < elements; ++i)
dd[i] = sd[i];
}
/// Сравнить матрицы на равенство.
inline bool matrices_are_equal(const Matrix_info *a, const Matrix_info *b)
{
// Если размеры матриц не равны, то и матрицы не равны.
if (a->rows != b->rows || a->cols != b->cols)
return false;
// Размеры совпали, сравним поэлементно.
const auto elements = matrix_size(a);
auto ad = a->data, bd = b->data;
for (size_t i = 0; i < elements; ++i)
if (ad[i] != bd[i])
return false;
// Равны поэлементно => равны.
return true;
}
/// Получить указатель на строку с заданным номером (только для чтения).
inline const double* get_row(const Matrix_info *m, size_t i)
{
return m->data + i * m->cols;
}
/// Получить указатель на строку с заданным номером.
inline double* get_row(Matrix_info *m, size_t i)
{
return m->data + i * m->cols;
}
/// Извлечь элемент по номерам строки и столбца.
inline double get_element(const Matrix_info *m, size_t i, size_t j)
{
return m->data[i * m->cols + j];
}
/// Установить элемент с заданными номерами строки и столбца.
inline void set_element(Matrix_info *m, size_t i, size_t j, double value)
{
m->data[i * m->cols + j] = value;
}
#endif//AMATRIX_HPP_INCLUDED_AMA700
// transpose_naive.cpp
// Транспонирование матрицы
#include "amatrix.hpp"
/// Создать новую матрицу mt как результат транспонирования m.
void make_transpose_naive(const Matrix_info *m, Matrix_info *mt)
{
// размеры
const auto
rows = m->rows,
cols = m->cols;
// подготовить место
realloc_matrix(mt, cols, rows);
auto m_row = m->data; // начало текущей строки в m
auto mt_col = mt->data; // начало текущего столбца в mt
for (size_t i = 0; i < rows; ++i)
{
auto mt_pos = mt_col; // позиция записи
for (size_t j = 0; j < cols; ++j)
{
// соседние элементы строки идут в массиве друг за другом непосредственно (шаг = 1)
*mt_pos = m_row[j];
// соседние элементы столбца идут в массиве с шагом в одну строку
// (шаг = rows -- количество столбцов в mt)
mt_pos += rows;
}
++mt_col; // перейти на следующий столбец в mt
m_row += cols; // перейти к следующей строке в m
}
// простой вариант:
//for (size_t i = 0; i < rows; ++i)
// for (size_t j = 0; j < cols; ++j)
// mt->data[j * mt->cols + i] = m->data[i * m->cols + j];
// код выше избавлен от умножений
}
///////////////////////////////////////////////////////////////////////////////
#include <cstdlib>
#include <iostream>
/// Тестирование функции, выполняющей транспозицию.
int test_transpose()
{
int result = 0;
Matrix_info m = {}, mt = {}, mt2 = {}; // = {} заполняет поля нулями
// Квадратная матрица, заполненная константой после транспонирования совпдает сама с собой.
alloc_matrix(&m, 100, 100);
fill_matrix(&m, 1.0);
make_transpose_naive(&m, &mt);
// Серия проверок.
if (!matrices_are_equal(&m, &mt))
result = 1;
// Единичная матрица при транспонировании тоже не изменяется.
identity(&m, 90);
make_transpose_naive(&m, &mt);
if (!matrices_are_equal(&m, &mt))
result = 2;
// Теперь сделаем так, чтобы транспонированная матрица не была равна исходной,
// повторное транспонирование должно вернуть исходную матрицу.
set_element(&m, 1, 25, 100.);
make_transpose_naive(&m, &mt);
make_transpose_naive(&mt, &mt2);
if (get_element(&mt, 1, 25) != 0.) result = 3;
if (get_element(&mt, 25, 1) != 100.) result = 4;
if (matrices_are_equal(&m, &mt)) result = 5;
if (!matrices_are_equal(&m, &mt2)) result = 6;
// Освободим память.
free_matrix(&m);
free_matrix(&mt);
return result;
}
int main()
{
using namespace std;
cout << test_transpose() << endl;
return EXIT_SUCCESS;
}
// matrix_zero_block.cpp
// Требуется определить, являются ли строки или столбцы за пределами максимальной квадратной
// угловой подматрицы нулевыми. В случае, когда исходная матрица квадратная, возвращать истину.
// Формально записать это условие можно следующим образом.
// Пусть A = (a_ij) -- матрица размера n x m.
// Пусть k = min(n, m), проверить, равны ли нулю все элементы a_ij при k<i<=n или k<j<=m.
#include "amatrix.hpp"
/// Определить, являются ли внешние по отношению к квадратной подматрице строки или столбцы нулевыми.
bool are_outer_lines_zeroes(const Matrix_info *mtx)
{
const auto data = mtx->data;
const auto rows = mtx->rows, cols = mtx->cols;
if (rows < cols)
{
// Строк меньше, чем столбцов -- проверим "хвосты" строк на равенство нулю.
// Длина "хвоста".
const auto diff = cols - rows;
for (size_t i = 0; i < rows; ++i)
{
// Вычислим указатель на первый элемент "хвоста" i-й строки.
const auto tail = data + i * cols + rows;
// Проверим элементы "хвоста" на равенство нулю.
for (size_t j = 0; j < diff; ++j)
if (tail[j] != 0)
return false;
}
}
else if (cols < rows)
{
// Столбцов меньше, чем строк -- проверим "лишние" строки на равенство нулю.
// Вычислим указатель на первую "лишнюю" строку,
// все последующие элементы массива принадлежат "лишним" строкам, проверим их на равенство нулю.
const auto excess = data + cols * cols;
const auto size = (rows - cols) * cols; // сколько оставшихся элементов
for (size_t i = 0; i < size; ++i)
if (excess[i] != 0)
return false;
}
// Либо матрица является квадратной, либо проверка в ветках if прошла успешно.
return true;
}
///////////////////////////////////////////////////////////////////////////////
// Тестирование
#include <cstdlib>
#include <iostream>
int test_are_outer_lines_zeroes()
{
int result = 0;
Matrix_info m = {};
alloc_matrix(&m, 10, 20);
fill_matrix(&m, 0.);
if (!are_outer_lines_zeroes(&m))
result = 1;
set_element(&m, 5, 15, 42.);
if (are_outer_lines_zeroes(&m))
result = 2;
realloc_matrix(&m, 20, 10);
fill_matrix(&m, 0.);
if (!are_outer_lines_zeroes(&m))
result = 3;
set_element(&m, 15, 5, 42.);
if (are_outer_lines_zeroes(&m))
result = 4;
realloc_matrix(&m, 15, 15);
fill_matrix(&m, 123.);
if (!are_outer_lines_zeroes(&m))
result = 5;
free_matrix(&m);
return result;
}
int main()
{
using namespace std;
cout << test_are_outer_lines_zeroes() << endl;
return EXIT_SUCCESS;
}
// matrix_multiply.cpp
// Тестирование различных вариантов реализации алгоритма умножения матриц "по определению".
#include "amatrix.hpp"
// Закомментировать при отсутствии ассемблерных вариантов:
#define USE_ASSEMBLY_VARIANTS
// Вариант 1 "в лоб".
bool multiply_v1(const Matrix_info *a, const Matrix_info *b, Matrix_info *c)
{
const auto n = a->rows, s = a->cols, m = b->cols;
if (n == 0 || s == 0 || m == 0 || s != b->rows)
return false;
realloc_matrix(c, n, m);
for (size_t i = 0; i < n; ++i)
{
for (size_t k = 0; k < m; ++k)
{
double sum = 0.;
for (size_t j = 0; j < s; ++j)
sum += get_element(a, i, j) * get_element(b, j, k);
set_element(c, i, k, sum);
}
}
return true;
}
// Вариант 2: прямое манипулирование указателями.
bool multiply_v2(const Matrix_info *a, const Matrix_info *b, Matrix_info *c)
{
const auto n = a->rows, s = a->cols, m = b->cols;
const auto b_data = b->data; // Указатель на массив элементов матрицы b.
if (n == 0 || s == 0 || m == 0 || s != b->rows)
return false;
realloc_matrix(c, n, m);
auto a_row = a->data, // Указатель на текущую строку матрицы a.
c_item = c->data; // Указатель на текущий элемент матрицы c.
for (size_t i = 0; i < n; ++i, a_row += s)
{
for (size_t k = 0; k < m; ++k)
{
double sum = 0.;
auto b_item = b_data + k; // k-й столбец в j-й строке матрицы b.
for (size_t j = 0; j < s; ++j, b_item += m)
sum += a_row[j] * (*b_item);
*c_item++ = sum;
}
}
return true;
}
// Вариант 3: последовательный порядок доступа к памяти.
bool multiply_v3(const Matrix_info *a, const Matrix_info *b, Matrix_info *c)
{
const auto n = a->rows, s = a->cols, m = b->cols;
if (n == 0 || s == 0 || m == 0 || s != b->rows)
return false;
realloc_matrix(c, n, m);
fill_matrix(c, 0.);
auto a_row = a->data, // Указатель на текущую строку матрицы a.
c_row = c->data; // Указатель на текущую строку матрицы c.
for (size_t i = 0; i < n; ++i, a_row += s, c_row += m)
{
auto b_row = b->data; // Указатель на текущую строку матрицы b.
for (size_t j = 0; j < s; ++j, b_row += m)
{
const auto aij = a_row[j];
for (size_t k = 0; k < m; ++k)
c_row[k] += aij * b_row[k];
}
}
return true;
}
#ifdef USE_ASSEMBLY_VARIANTS
// Ссылка на процедуру в ассемблерном коде.
extern "C" void addmtxmul(double*, double*, double*, size_t, size_t, size_t);
// Вариант 4: обёртка ассемблерного кода.
bool multiply_v4(const Matrix_info *a, const Matrix_info *b, Matrix_info *c)
{
const auto n = a->rows, s = a->cols, m = b->cols;
if (n == 0 || s == 0 || m == 0 || s != b->rows)
return false;
realloc_matrix(c, n, m);
fill_matrix(c, 0.);
addmtxmul(a->data, b->data, c->data, n, s, m);
return true;
}
#endif//USE_ASSEMBLY_VARIANTS
///////////////////////////////////////////////////////////////////////////////
// Тестирование
#include <cstdlib>
#include <iostream>
#include <iterator> // begin, end
#include <chrono> // высокоточный таймер
#include <random> // генераторы (псевдо)случайных чисел
//////////////////////////////
// Тестирование корректности
// Заполнить матрицу случайными целыми числами из диапазона [-100, 100].
void random100_matrix(size_t seed, Matrix_info *m)
{
using namespace std;
// Генератор псевдослучайной последовательности -- "вихрь Мерсенна".
std::mt19937_64 rng(seed);
// Случайное распределение -- равномерное на [-1, 1].
std::uniform_int_distribution<> dist(-100, 100);
// Заполнить матрицу.
const auto sz = matrix_size(m);
const auto data = m->data;
for (size_t i = 0; i < sz; ++i)
data[i] = dist(rng);
}
typedef bool (*Mtx_multiply)(const Matrix_info*, const Matrix_info*, Matrix_info*);
int test_multiply(Mtx_multiply mtx_mul)
{
Matrix_info a = {}, b = {}, c = {}, t = {};
// Тестирование на заранее заданных матрицах
const double a_items[5][6] =
{
{ -10, -5, -1, 2, 6, 12 },
{ -8, -4, 0, 1, 5, 10 },
{ -4, -2, -1, 3, 5, 15 },
{ 24, 12, 10, 8, 4, 2 },
{ 16, -10, 30, -20, 18, -6 }
};
matrix_from_array(&a, 5, 6, &a_items[0][0]);
const double b_items[6][4] =
{
{ 1, 2, 3, 4 },
{ 40, 20, 30, 10 },
{ 0, -5, -6, -7 },
{ 3, 5, 7, 11 },
{ 13, 17, 19, 23 },
{ -4, -3, -2, -1 }
};
matrix_from_array(&b, 6, 4, &b_items[0][0]);
const double t_items[5][4] =
{
{ -174, -39, -70, 65 },
{ -140, -36, -62, 44 },
{ -70, 12, 20, 104 },
{ 572, 340, 500, 324 },
{ -186, -94, -218, -46 }
};
matrix_from_array(&t, 5, 4, &t_items[0][0]);
int result = 0;
if (!mtx_mul(&a, &b, &c))
{
result = 1;
}
else if (!matrices_are_equal(&c, &t))
{
double cd[5][4] = {};
memcpy(&cd[0][0], c.data, 20); // для того, чтобы в отладчике можно было увидеть полученную матрицу
result = 2;
}
// Тестирование на случайных матрицах
const size_t Ns[] = { 3, 4, 5, 6, 7, 10, 20, 25, 113 };
const size_t Ss[] = { 5, 7, 8, 9, 3, 11, 23, 25, 37 };
for (size_t i = 0, i_bnd = std::end(Ns) - std::begin(Ns); i < i_bnd; ++i)
{
realloc_matrix(&a, Ns[i], Ss[i]);
random100_matrix(i * 1234, &a);
realloc_matrix(&b, Ss[i], Ns[i]);
random100_matrix(i * 4321, &b);
if (multiply_v1(&a, &b, &t) != mtx_mul(&a, &b, &c))
{
result = 3;
break;
}
if (!matrices_are_equal(&c, &t))
{
result = 4;
break;
}
}
free_matrix(&a);
free_matrix(&b);
free_matrix(&c);
free_matrix(&t);
return result;
}
//////////////////////////
// Тестирование скорости
// Заполнить матрицу случайными числами из диапазона [-1, 1].
void random_matrix(Matrix_info *m)
{
using namespace std;
// Используем системный генератор случайных чисел для генерации зерна псевдослучайной последовательности.
random_device seed_gen;
// Генератор псевдослучайной последовательности -- "вихрь Мерсенна".
std::mt19937_64 rng(seed_gen());
// Случайное распределение -- равномерное на [-1, 1].
std::uniform_real_distribution<> dist(-1., 1.);
// Заполнить матрицу.
const auto sz = matrix_size(m);
const auto data = m->data;
for (size_t i = 0; i < sz; ++i)
data[i] = dist(rng);
}
// Замерить время, потраченное на перемножение.
double test_speed(Mtx_multiply mtx_mul, size_t m, size_t s, size_t n, size_t rounds = 1)
{
using namespace std::chrono;
volatile auto
a = new Matrix_info[rounds],
b = new Matrix_info[rounds],
c = new Matrix_info[rounds];
for (size_t i = 0; i < rounds; ++i)
{
alloc_matrix(a + i, m, s);
alloc_matrix(b + i, s, n);
alloc_matrix(c + i, m, n);
random_matrix(a + i);
random_matrix(b + i);
}
// Стартовый момент времени.
const auto t0 = high_resolution_clock::now();
// rounds раз выполнить перемножение.
for (size_t i = 0; i < rounds; ++i)
mtx_mul(a + i, b + i, c + i);
// Получить продолжительность в секундах (на MSVC 2013 низкая точность).
const auto t1 = high_resolution_clock::now();
for (size_t i = 0; i < rounds; ++i)
{
free_matrix(a + i);
free_matrix(b + i);
free_matrix(c + i);
}
return duration<double>(t1 - t0).count() / rounds;
}
int main()
{
using namespace std;
int v = 1;
Mtx_multiply variants[] =
{
multiply_v1, multiply_v2,
multiply_v3,
#ifdef USE_ASSEMBLY_VARIANTS
multiply_v4
#endif
};
for (auto variant : variants)
cout << v++ << ") " << test_multiply(variant)
#if defined(DEBUG) || defined(_DEBUG)
<< "\n104 x 104 " << test_speed(variant, 104, 104, 104)
#else
<< "\n36 x 36 " << test_speed(variant, 36, 36, 36, 200000) // 32kb in L1
<< "\n104 x 104 " << test_speed(variant, 104, 104, 104, 1000) // 256kb in L2
<< "\n208 x 208 " << test_speed(variant, 208, 208, 208, 200) // 1Mb in L3
<< "\n416 x 416 " << test_speed(variant, 416, 416, 416, 40) // 4Mb in L3
<< "\n590 x 590 " << test_speed(variant, 590, 590, 590, 20) // 8Mb in L3
<< "\n3k x 1k " << test_speed(variant, 3000, 1000, 3000, 5)
<< "\n1k x 3k " << test_speed(variant, 1000, 3000, 1000, 5)
<< "\n2k x 2k " << test_speed(variant, 2000, 2000, 2000, 5)
#endif
<< endl;
return EXIT_SUCCESS;
}
// cvarargs.cpp
#include <cmath>
#include <cstdarg>
/// Длина вектора с количеством компонент comps.
/// Компоненты вектора передаются параметрами функции.
double vec_len(int comps, ...)
{
std::va_list args;
va_start(args, comps);
double s = 0.0;
while (comps-- > 0)
{
const double arg = va_arg(args, double);
s += arg * arg;
}
va_end(args);
return std::sqrt(s);
}
#include <iostream>
#include <cstdlib>
int main()
{
using namespace std;
cout << vec_len(1, 2.0) << endl
<< vec_len(2, 1.f, 2.f) << endl
<< vec_len(4, 0., 0., -1., 0.) << endl;
return EXIT_SUCCESS;
}
// recursion.cpp
// Демонстрация перехода "рекурсия -> рекурсия через "хвостовой" вызов -> итеративное решение (цикл)".
// Примеры: факториал, числа Фибоначчи, линейный поиск, двоичный поиск.
// При запуске выполняет автоматическое тестирование всех вариантов (кроме линейного поиска).
// rec == "recursive"
// tcr == "tail-call recursion"
// itr == "iterative"
///////////////////////////////////////////////////////////////////////////////
// factorial
double rec_fact(unsigned n)
{
return n == 0 ? 1.0 : n * rec_fact(n - 1);
}
double tcr_fact(unsigned n, double fact = 1.0)
{
return n == 0 ? fact : tcr_fact(n - 1, n * fact);
}
double tcr_fact_caller(unsigned n)
{
return tcr_fact(n);
}
double itr_fact_0(unsigned n)
{
double fact = 1.0;
while (true)
{
if (n == 0)
return fact;
const auto old_n = n;
const auto old_fact = fact;
n = old_n - 1;
fact = old_n * old_fact;
}
}
double itr_fact(unsigned n)
{
double fact = 1.0;
for (; n != 0; --n)
fact *= n;
return fact;
}
typedef double (*fact_variant)(unsigned);
int test_fact(fact_variant fact)
{
const unsigned ns[] = { 0, 1, 2, 5, 7, 10 };
const double fs[] = { 1., 1., 2., 120., 5040., 3628800. };
for (unsigned i = 0; i < sizeof(fs) / sizeof(double); ++i)
if (fact(ns[i]) != fs[i])
return i + 1;
return 0;
}
///////////////////////////////////////////////////////////////////////////////
// Fibonacci
double rec_fib(unsigned n)
{
return n < 2 ? n : rec_fib(n - 1) + rec_fib(n - 2);
}
double tcr_fib(unsigned n, double a = 0.0, double b = 1.0)
{
return n == 0 ? a : tcr_fib(n - 1, b, a + b);
}
double tcr_fib_caller(unsigned n)
{
return tcr_fib(n);
}
double itr_fib_0(unsigned n)
{
double a = 0.0, b = 1.0;
while (true)
{
if (n == 0)
return a;
const auto old_n = n;
const auto old_a = a, old_b = b;
a = old_b;
b = old_a + old_b;
n = old_n - 1;
}
}
double itr_fib(unsigned n)
{
double a = 0.0, b = 1.0;
while (n-- > 0)
{
const auto sum = a + b;
a = b;
b = sum;
}
return a;
}
typedef double(*fib_variant)(unsigned);
int test_fib(fib_variant fact)
{
const unsigned ns[] = { 0, 1, 2, 4, 6, 10 };
const double fs[] = { 0., 1., 1., 3., 8., 55. };
for (unsigned i = 0; i < sizeof(fs) / sizeof(double); ++i)
if (fact(ns[i]) != fs[i])
return i + 1;
return 0;
}
///////////////////////////////////////////////////////////////////////////////
// lsr == "linear search right"
const int* rec_lsr(const int *begin, const int *end, int x)
{
if (begin == end)
return end;
return *begin == x ? begin : rec_lsr(begin + 1, end, x);
}
const int* itr_lsr(const int *begin, const int *end, int x)
{
for (; begin != end; ++begin)
if (*begin == x)
break;
return begin;
}
///////////////////////////////////////////////////////////////////////////////
// bsl == "binary search left"
const int* rec_bsl(const int *begin, const int *end, int x)
{
const auto mid = begin + (end - begin) / 2;
if (mid == begin)
return begin == end || *begin < x ? end : begin;
return *mid < x ?
rec_bsl(mid + 1, end, x)
: rec_bsl(begin, mid, x);
}
const int* itr_bsl(const int *begin, const int *end, int x)
{
while (true)
{
const auto mid = begin + (end - begin) / 2;
if (mid == begin)
return begin == end || *begin < x ? end : begin;
if (*mid < x)
begin = mid + 1;
else
end = mid;
}
}
typedef const int* (*bsl_variant)(const int*, const int*, int);
int test_bsl(bsl_variant bsl)
{
const int data[] = { 0, 0, 0, 1, 1, 1, 1, 2, 3, 5, 10, 11, 11, 11, 20 };
const struct {
int b, e, x, r;
} ts[] =
{
{ 0, 15, 0, 0 }, //1
{ 0, 15, 1, 3 }, //2
{ 0, 15, 2, 7 }, //3
{ 0, 15, 3, 8 }, //4
{ 0, 15, 5, 9 }, //5
{ 0, 15, 4, 9 }, //6
{ 0, 15, 7, 10 }, //7
{ 0, 15, 10, 10 }, //8
{ 0, 15, 11, 11 }, //9
{ 0, 15, 20, 14 }, //10
{ 0, 15, 25, 15 }, //11
{ 0, 0, 10, 0 }, //12
{ 0, 1, 0, 0 }, //13
{ 0, 1, 10, 1 }, //14
{ 0, 2, 2, 2 }, //15
{ 0, 2, 0, 0 }, //16
{ 0, 3, 2, 3 }, //17
{ 0, 3, 0, 0 }, //18
{ 0, 4, 2, 4 }, //19
{ 0, 4, 1, 3 }, //20
{ 0, 4, 0, 0 }, //21
{ 1, 5, 2, 5 }, //22
{ 1, 5, 1, 3 }, //23
{ 1, 5, 0, 1 }, //24
{ 2, 6, 2, 6 }, //25
{ 2, 6, 1, 3 }, //26
{ 2, 6, 0, 2 }, //27
{ 13, 15, 15, 14 } //28
};
int test = 0;
for (auto &t : ts)
{
++test;
if (bsl(data + t.b, data + t.e, t.x) - data != t.r)
return test;
}
return 0;
}
///////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <cstdlib>
void report(int test_result, const char* msg)
{
if (test_result)
std::cout << msg << ": " << test_result << std::endl;
}
int main()
{
using namespace std;
cout << "Testing factorial variants:\n";
{
const struct {
fact_variant fact;
const char *name;
} vs[] =
{
{ rec_fact, "rec" },
{ tcr_fact_caller, "tcr" },
{ itr_fact_0, "itr0" },
{ itr_fact, "itr" }
};
for (auto &v : vs)
report(test_fact(v.fact), v.name);
}
cout << "done.\nTesting fib variants:\n";
{
const struct {
fib_variant fib;
const char *name;
} vs[] =
{
{ rec_fib, "rec" },
{ tcr_fib_caller, "tcr" },
{ itr_fib_0, "itr0" },
{ itr_fib, "itr" }
};
for (auto &v : vs)
report(test_fib(v.fib), v.name);
}
cout << "done.\nTesting binary search variants:\n";
{
const struct {
bsl_variant bsl;
const char *name;
} vs[] =
{
{ rec_bsl, "rec" },
{ itr_bsl, "itr" }
};
for (auto &v : vs)
report(test_bsl(v.bsl), v.name);
}
cout << "done." << endl;
return EXIT_SUCCESS;
}
// memoized_fib.cpp
// Результат применения техники мемоизации к рекурсивной функции,
// вычисляющей числа Фибоначчи "по определению".
// Мемоизация заключается в запоминании вычисленных значений функции
// и извлечении их при повторном вызове функции с теми же параметрами.
// В данном случае мемоизация позволяет "линеаризовать" вычисление --
// вместо экспоненциального по номеру числа времени требуется линейное
// (или постоянное при повторных вызовах).
#include <cmath> // HUGE_VAL
double fib(unsigned n)
{
// Хранилище вычисленных значений -- достаточно 1500 элементов,
// так как в диапазон IEEE-754 double precision не вписываются числа Фибоначчи за номером 1500 и более.
// В общем случае мемоизации могут понадобиться сложные структуры данных,
// оперирующие динамической памятью.
static const unsigned N = 1500;
static double value[N] = { 0., 1. };
// Признак того, что значение уже вычисленно и надо извлечь его из таблицы value.
static bool stored[N] = { true, true };
if (N <= n)
return HUGE_VAL;
if (stored[n]) // уже посчитано?
return value[n]; // да -- вернуть сохранённое
// ещё не посчитано -- посчитать по определению, сохранить и вернуть:
stored[n] = true;
return value[n] = fib(n - 1) + fib(n - 2);
}
#include <iostream>
int main()
{
for (unsigned n; std::cin >> n;)
std::cout << fib(n) << std::endl;
return EXIT_SUCCESS;
}
// memoized_fib_thread_local.cpp
// Пример использования хранилища потока (ключевого слова thread_local) для
// реализации потокобезопасной (thread-safe) версии memoized_fib.
// Т.е. fib из этого примера можно без проблем выполнять одновременно из разных нитей (threads) исполнения.
#include <cmath> // HUGE_VAL
double fib(unsigned n)
{
static const unsigned N = 1500;
thread_local static double value[N] = { 0., 1. };
thread_local static bool stored[N] = { true, true };
if (N <= n)
return HUGE_VAL;
if (stored[n])
return value[n];
stored[n] = true;
return value[n] = fib(n - 1) + fib(n - 2);
}
///////////////////////////////////////////////////////////////////////////////
// Проверочный код.
// Вариант fib, не использующий глобальную память.
// Используется для тестирования варианта fib, приведённого выше.
double reference_fib(unsigned n)
{
double a = 0., b = 1.;
while (n--)
{
const auto sum = a + b;
a = b;
b = sum;
}
return a;
}
#include <iostream>
#include <thread>
#include <random>
using namespace std;
int main()
{
void thread_body(unsigned);
// Создать три нити исполнения, которые будут вычислять разные значения fib
// и сравнивать с результатом reference_fib.
thread a(thread_body, 1), b(thread_body, 2), c(thread_body, 3);
// Дождаться завершения вычислений.
a.join();
b.join();
c.join();
// Задержка экрана.
cin.ignore();
return EXIT_SUCCESS;
}
// Код, выполняемый параллельно.
void thread_body(unsigned tid)
{
random_device seed_gen; // генератор случайного зерна
mt19937_64 rng(seed_gen() + tid); // генератор псевдослучайных целых чисел
uniform_int_distribution<> ud(0, 1501); // генератор равномерно распределённых в [0, 1501] целых чисел
for (int rounds = 1000; rounds--;)
{
const auto n = ud(rng); // следующий псевдослучайный аргумент fib
if (fib(n) != reference_fib(n)) // проверить корректность вычисления
return (void)cout.put('0'); // ошибка
}
cout.put('1'); // все раунды успешны
}
// prefix_calc.cpp
// Рекурсивная реализация калькулятора с поддержкой четырёх арифметических действий,
// принимающего выражения в префиксной записи (она же "польская нотация").
// Грамматика выражения: операция операнд операнд, где операнд может быть числом или опять выражением
// Например, + * 2 3 4 ==> (2 * 3) + 4 == 10
#include <iostream>
#include <cstring> // strchr
using namespace std;
// Читает выражение с cin, возвращает вычисленное значение выражения.
double prefix()
{
// Выражение?
char op;
if (cin >> op)
{
// Считали знак операции?
if (strchr("+-*/", op))
{
// Вычислить операнды.
double x = prefix(), y = prefix();
// Вычислить результат выполнения операции.
switch (op)
{
case '+': return x + y;
case '-': return x - y;
case '*': return x * y;
case '/': return x / y;
}
}
else // не знак операции -- вернуть считанный символ
cin.unget();
}
// Число?
double value;
if (cin >> value)
return value;
// Ошибка ввода.
cerr << "input error\n";
return 0.;
}
int main()
{
while (true)
{
double answer = prefix();
// Сброс потока ввода.
cin.clear();
cin.ignore(cin.rdbuf()->in_avail());
cin.sync();
// Вывод ответа.
cout << "answer = " << answer << endl;
}
return EXIT_SUCCESS;
}
// postfix_calc.cpp
// Рекурсивная реализация калькулятора с поддержкой четырёх арифметических действий,
// принимающего выражения в постфиксной записи (она же "обратная польская нотация").
// Грамматика выражения: операнд операнд операция, где операнд может быть числом или опять выражением
// Например, 4 3 2 * + ==> 4 + (3 * 2) == 10
#include <iostream>
using namespace std;
// Читает выражение из потока cin, возвращает вычисленное значение.
// Для того, чтобы суметь выполнить прочитанную операцию, надо получить уже ранее прочитанные операнды.
// Эти операнды передадим через параметры x (первый операнд), y (второй операнд).
double postfix(double x = 0., double y = 0.)
{
// Операция?
char op;
if (cin >> op)
{
switch (op)
{
// Вычислить значение выражения (операнды уже известны -- x, y) и вернуть результат.
case '+': return x + y;
case '-': return x - y;
case '*': return x * y;
case '/': return x / y;
// Не операция? вернуть считанный символ в поток.
default: cin.unget();
}
}
// Число?
double z;
if (cin >> z)
return postfix(x, postfix(y, z));
// Новые операнды -- y и считанное z.
// Но x тоже никуда не делся. После того, как будет вычислено значение над ним,
// может быть считана операция, которая задействует x. Отсюда второй рекурсивный вызов.
// Этот последний вызов является хвостовым и может быть раскрыт в цикл.
// Иначе конец ввода или ошибка, вернём последнее вычисленное значение (операнд y).
return y;
}
int main()
{
while (true)
{
double answer = postfix();
// Сброс потока.
cin.clear();
cin.ignore(cin.rdbuf()->in_avail());
cin.sync();
// Вывод ответа.
cout << "answer = " << answer << endl;
}
return EXIT_SUCCESS;
}
// postfix_calc_tc.cpp
// Рекурсивная реализация калькулятора с поддержкой четырёх арифметических действий,
// принимающего выражения в постфиксной записи (она же "обратная польская нотация").
// Грамматика выражения: операнд операнд операция, где операнд может быть числом или опять выражением
// Например, 4 3 2 * + ==> 4 + (3 * 2) == 10
// От postfix_calc.cpp отличается тем, что один из рекурсивных вызовов раскрыт в цикл.
#include <iostream>
using namespace std;
// Читает выражение из потока cin, возвращает вычисленное значение.
// Для того, чтобы суметь выполнить прочитанную операцию, надо получить уже ранее прочитанные операнды.
// Эти операнды передадим через параметры x (первый операнд), y (второй операнд).
double postfix(double x = 0., double y = 0.)
{
while (true)
{
// Операция?
char op;
if (cin >> op)
{
switch (op)
{
// Вычислить значение выражения (операнды уже известны -- x, y) и вернуть результат.
case '+': return x + y;
case '-': return x - y;
case '*': return x * y;
case '/': return x / y;
// Не операция? вернуть считанный символ в поток.
default: cin.unget();
}
}
// Число?
double z;
if (cin >> z)
y = postfix(y, z);
else
return y;
}
}
int main()
{
while (true)
{
double answer = postfix();
// Сброс потока.
cin.clear();
cin.ignore(cin.rdbuf()->in_avail());
cin.sync();
// Вывод ответа.
cout << "answer = " << answer << endl;
}
return EXIT_SUCCESS;
}
// postfix_calc_stack.cpp
// Реализация калькулятора с поддержкой четырёх арифметических действий,
// принимающего выражения в постфиксной записи (она же "обратная польская нотация").
// Грамматика выражения: операнд операнд операция, где операнд может быть числом или опять выражением
// Например, 4 3 2 * + ==> 4 + (3 * 2) == 10
// От postfix_calc.cpp отличается тем, что вместо рекурсии и неявного использования стека вызовов
// для хранения промежуточных результатов (операндов) используется явный стек чисел в виде
// статического массива (размер зафиксирован в момент компиляции).
#include <iostream>
#include <cstring> // strchr
using namespace std;
// Читает выражение из потока cin, возвращает вычисленное значение.
double postfix()
{
static const unsigned STACK_SIZE = 1024; // Размер стека.
double operand[STACK_SIZE]; // Стек (на основе массива).
unsigned operand_top = 0; /* Индекс элемента массива,
который станет вершиной стека при добавлении элемента. */
while (true)
{
// Операция?
char op;
if (cin >> op)
{
double z;
if (strchr("+-*/", op))
{
// Убедиться, что в стеке есть хотя бы два числа.
if (operand_top < 2)
{
cerr << "stack underflow: at least 2 items are needed\n";
break;
}
// Извлечь операнды (для сокращения записи).
const double
x = operand[operand_top - 2],
y = operand[operand_top - 1];
operand_top -= 2;
// Вычислить значение выражения (операнды уже известны -- x, y).
switch (op)
{
case '+': z = x + y; break;
case '-': z = x - y; break;
case '*': z = x * y; break;
case '/': z = x / y; break;
}
// Записать новое значение в стек.
operand[operand_top++] = z;
// Проверить переполнение стека.
if (operand_top == STACK_SIZE)
{
cerr << "stack overflow\n";
break;
}
}
else // Не операция? вернуть считанный символ в поток.
{
cin.unget();
// Число?
if (cin >> z)
{
// Записать новое значение в стек.
operand[operand_top++] = z;
// Проверить переполнение стека.
if (operand_top == STACK_SIZE)
{
cerr << "stack overflow\n";
break;
}
}
else // Ошибка ввода.
break;
}
}
else // Ошибка ввода.
break;
}
// Вернуть текущую вершину стека.
if (operand_top == 0) // Стек пуст.
{
cerr << "stack underflow: at least 1 item is needed\n";
return 0.;
}
return operand[operand_top - 1];
}
int main()
{
while (true)
{
double answer = postfix();
// Сброс потока.
cin.clear();
cin.ignore(cin.rdbuf()->in_avail());
cin.sync();
// Вывод ответа.
cout << "answer = " << answer << endl;
}
return EXIT_SUCCESS;
}
// postfix_calc_stack_std.cpp
// Реализация калькулятора с поддержкой четырёх арифметических действий,
// принимающего выражения в постфиксной записи (она же "обратная польская нотация").
// Грамматика выражения: операнд операнд операция, где операнд может быть числом или опять выражением
// Например, 4 3 2 * + ==> 4 + (3 * 2) == 10
// От postfix_calc_stack.cpp отличается тем, что вместо статического массива (размер зафиксирован в момент компиляции)
// для хранения промежуточных результатов (операндов) используется стек чисел на основе стандартного класса stack,
// автоматически увеличивающийся по мере надобности (располагает данные в динамической памяти).
#include <iostream>
#include <cstring> // strchr
#include <stack>
using namespace std;
// Читает выражение из потока cin, возвращает вычисленное значение.
double postfix()
{
stack<double> operands; // Стек операндов.
while (true)
{
// Операция?
char op;
if (cin >> op)
{
double x, y, z;
if (strchr("+-*/", op))
{
// Извлечь операнды, проверяя их наличие.
if (operands.empty())
goto Stack_underflow_error;
y = operands.top();
operands.pop();
if (operands.empty())
goto Stack_underflow_error;
x = operands.top();
operands.pop();
// Вычислить значение выражения (операнды уже известны -- x, y).
switch (op)
{
case '+': z = x + y; break;
case '-': z = x - y; break;
case '*': z = x * y; break;
case '/': z = x / y; break;
}
// Записать новое значение в стек.
operands.push(z);
}
else // Не операция? вернуть считанный символ в поток.
{
cin.unget();
// Число?
if (cin >> z)
operands.push(z);
else // Ошибка ввода.
break;
}
}
else // Ошибка ввода.
break;
}
// Вернуть текущую вершину стека.
if (operands.empty()) // Стек пуст.
{
Stack_underflow_error:
cerr << "stack underflow\n";
return 0.;
}
return operands.top();
}
int main()
{
while (true)
{
double answer = postfix();
// Сброс потока.
cin.clear();
cin.ignore(cin.rdbuf()->in_avail());
cin.sync();
// Вывод ответа.
cout << "answer = " << answer << endl;
}
return EXIT_SUCCESS;
}
// prefix_calc_stack_std.cpp
// Реализация калькулятора с поддержкой четырёх арифметических действий,
// принимающего выражения в префиксной записи (она же "польская нотация").
// Грамматика выражения: операция операнд операнд, где операнд может быть числом или опять выражением
// Например, + * 2 3 4 ==> (2 * 3) + 4 == 10
// Для хранения промежуточных данных используются стеки на основе стандартного класса stack.
#include <iostream>
#include <cstring> // strchr
#include <stack>
using namespace std;
// Читает выражение с cin, возвращает вычисленное значение выражения.
double prefix()
{
stack<char> ops; // Стек отложенных значений op.
stack<double> xs; // Стек отложенных значений x.
stack<bool> has_x; // Стек признака "операция уже имеет первый операнд в стеке xs".
double y = 0.; // Второй операнд.
do
{
char op;
if (cin >> op)
{
if (strchr("+-*/", op)) // Считали знак операции.
{
ops.push(op);
has_x.push(false); // Новая операция -- ещё нет ни одного операнда.
}
else // не знак операции -- вернуть считанный символ и прочитать число
{
cin.unget();
if (cin >> y) // Считали число.
{
// Можно выполнить "свёртку" операций, для которых есть первый операнд.
while (!ops.empty() && has_x.top())
{
// Извлечь из стека первый аргумент операции.
const auto x = xs.top();
xs.pop();
switch (ops.top())
{
case '+': y = x + y; break;
case '-': y = x - y; break;
case '*': y = x * y; break;
case '/': y = x / y; break;
}
// Убрать вычисленную операцию.
ops.pop();
has_x.pop();
}
// Получили первый операнд некоторой операции?
if (!ops.empty())
{
has_x.top() = true;
xs.push(y);
}
}
}
}
else
{
// Ошибка ввода.
cerr << "input error\n";
break;
}
} while (!ops.empty()); // Продолжать, пока есть ещё операции.
return y;
}
int main()
{
while (true)
{
double answer = prefix();
// Сброс потока ввода.
cin.clear();
cin.ignore(cin.rdbuf()->in_avail());
cin.sync();
// Вывод ответа.
cout << "answer = " << answer << endl;
}
return EXIT_SUCCESS;
}
// infix_calc.cpp
// Инфиксный калькулятор без учёта приоритетов операций и без поддержки скобок.
// Пример: 2+2*2 ==> 8 (выполняет операции подряд).
// Рекурсивная реализация.
#include <iostream>
using namespace std;
// Читает из потока cin, возвращает значение выражения.
double infix(double x)
{
char op;
if (cin >> op)
{
double y;
if (cin >> y)
{
switch (op)
{
case '+': return infix(x + y);
case '-': return infix(x - y);
case '*': return infix(x * y);
case '/': return infix(x / y);
default:
cerr << "unknown operation '" << op << "'\n";
return x;
}
}
else
cerr << "number expected\n";
}
return x;
}
double infix()
{
double x;
if (cin >> x)
return infix(x);
cerr << "number expected\n";
return 0.;
}
int main()
{
while (true)
{
double answer = infix();
cin.clear();
cin.ignore(cin.rdbuf()->in_avail());
cin.sync();
cout << "answer = " << answer << endl;
}
return EXIT_SUCCESS;
}
// infix_calc_tc.cpp
// Инфиксный калькулятор без учёта приоритетов операций и без поддержки скобок.
// Пример: 2+2*2 ==> 8 (выполняет операции подряд).
// Получен из infix_calc.cpp путём замены рекурсии на итерацию
// (нетрудно заметить, что в рекурсивном варианте только хвостовые вызовы).
#include <iostream>
using namespace std;
// Читает из потока cin, возвращает значение выражения.
double infix(double x)
{
char op;
while (cin >> op)
{
double y;
if (cin >> y)
{
switch (op)
{
case '+': x = x + y; break;
case '-': x = x - y; break;
case '*': x = x * y; break;
case '/': x = x / y; break;
default:
cerr << "unknown operation '" << op << "'\n";
return x;
}
}
else
cerr << "number expected\n";
}
return x;
}
double infix()
{
double x;
if (cin >> x)
return infix(x);
cerr << "number expected\n";
return 0.;
}
int main()
{
while (true)
{
double answer = infix();
cin.clear();
cin.ignore(cin.rdbuf()->in_avail());
cin.sync();
cout << "answer = " << answer << endl;
}
return EXIT_SUCCESS;
}
// infix_calc_tc_2.cpp
// Инфиксный калькулятор без учёта приоритетов операций и без поддержки скобок.
// Пример: 2+2*2 ==> 8 (выполняет операции подряд).
// Получен из infix_calc_tc.cpp слиянием двух функций infix в одну
// (без рекурсии два варианта уже не нужны).
#include <iostream>
using namespace std;
// Читает из потока cin, возвращает значение выражения.
double infix()
{
double x;
if (!(cin >> x))
{
cerr << "number expected\n";
return 0.;
}
for (char op; cin >> op;)
{
double y;
if (cin >> y)
{
switch (op)
{
case '+': x = x + y; break;
case '-': x = x - y; break;
case '*': x = x * y; break;
case '/': x = x / y; break;
default:
cerr << "unknown operation '" << op << "'\n";
return x;
}
}
else
cerr << "number expected\n";
}
return x;
}
int main()
{
while (true)
{
double answer = infix();
cin.clear();
cin.ignore(cin.rdbuf()->in_avail());
cin.sync();
cout << "answer = " << answer << endl;
}
return EXIT_SUCCESS;
}
// infix_calc_p.cpp
// Инфиксный калькулятор без учёта приоритетов операций, но с поддержкой скобок.
// Пример: 2+(2*2) ==> 6.
// Грамматика:
// Терм --> Число | '(' Выражение ')' // term
// Выражение --> Терм { Операция Терм } // infix
// Рекурсивная реализация на основе грамматики.
#include <iostream>
using namespace std;
// Вспомогательная функция:
// посмотреть следующий непробельный символ в потоке cin, не извлекая его.
// (Пробельные символы пропускаются. Возвращает EOF если поток закончился.)
char peek()
{
char ch = EOF;
if (cin >> ch)
cin.unget();
return ch;
}
// Вспомогательная функция для установки ошибки.
void error(const char *message)
{
cerr << message;
cin.setstate(ios::failbit);
}
double infix();
// Терм --> Число | '(' Выражение ')'
double term()
{
double result = 0.;
switch (peek()) // Ожидается число или открывающая скобка.
{
case '-': case '+': case '.':
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
if (!(cin >> result))
error("number expected\n");
return result;
case '(':
cin.ignore(); // Пропустить '('.
result = infix();
if (peek() != ')')
error("unmatched '(' found\n");
else
cin.ignore(); // Пропустить ')'.
return result;
case ')':
error("unmatched ')' found\n");
return 0.;
default:
error("term expected, '");
cerr << peek() << "' found\n";
return 0.;
}
}
// Выражение --> Терм { Операция Терм }
double infix()
{
double x = term(), y = 0.;
while (true)
{
switch (char op = peek()) // Ожидается операция.
{
case '+': case '-': case '*': case '/':
cin.ignore();
y = term(); // Получить второй операнд.
if (!cin)
{
error("no second argument for operation '");
cerr << op << "'\n";
return x;
}
switch (op) // Вычислить результат операции.
{
case '+': x = x + y; break;
case '-': x = x - y; break;
case '*': x = x * y; break;
case '/': x = x / y; break;
}
break;
case ')': case EOF:
return x;
default:
error("unknown operation: '");
cerr << op << "'\n";
return x;
}
}
}
int main()
{
while (true)
{
double answer = infix();
cin.clear();
cin.ignore(cin.rdbuf()->in_avail());
cin.sync();
cout << "answer = " << answer << endl;
}
return EXIT_SUCCESS;
}
// infix_calc_p_stack.cpp
// Инфиксный калькулятор без учёта приоритетов операций, но с поддержкой скобок.
// Пример: 2+(2*2) ==> 6.
// Грамматика:
// Терм --> Число | '(' Выражение ')' // term
// Выражение --> Терм { Операция Терм } // infix
// Конверсия рекурсивного варианта infix_calc_p.cpp в вариант с использованием стека.
// Добавлены операции взятия остатка (реализована через std::fmod) и
// возведения в степень (реализована через std::pow) -- символы '%' и '^'.
#include <iostream>
#include <cmath>
#include <stack>
using namespace std;
// Вспомогательная функция:
// посмотреть следующий непробельный символ в потоке cin, не извлекая его.
// (Пробельные символы пропускаются. Возвращает EOF если поток закончился.)
char peek()
{
char ch = EOF;
if (cin >> ch)
cin.unget();
return ch;
}
// Вспомогательная функция для установки ошибки.
void error(const char *message)
{
cerr << message;
cin.setstate(ios::failbit);
}
double infix()
{
stack<char> ops; // Стек операций.
stack<double> xs; // Стек операндов.
// Вложенная функция, выполняющая операцию на вершине стека ops.
// Возвращает "успех" (false если произошла ошибка, true если выполнено успешно).
auto do_next_op = [&]() -> bool
{
double x, y;
if (xs.empty())
{
error("not enough operands\n");
return false;
}
y = xs.top();
xs.pop();
if (xs.empty())
{
xs.push(y);
error("not enough operands\n");
return false;
}
x = xs.top();
switch (ops.top())
{
case '+': x = x + y; break;
case '-': x = x - y; break;
case '*': x = x * y; break;
case '/': x = x / y; break;
case '%': x = fmod(x, y); break;
case '^': x = pow(x, y); break;
default:
error("internal error\n");
return false;
}
// Сохранить результат операции вместо операндов на стеке xs.
xs.top() = x;
// Убрать со стека операций выполненную операцию.
ops.pop();
return true;
};
bool awaiting_term = true; // Ожидает терм (true) или операцию (false)?
while (true)
{
if (awaiting_term)
{
double x;
switch (peek())
{
case '-': case '+': case '.':
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
if (!(cin >> x))
{
error("number expected\n");
goto Finish;
}
xs.push(x);
awaiting_term = false;
break;
case '(':
cin.ignore(); // Убрать открывающую скобку из потока.
ops.push('(');
break;
case ')':
error("unmatched ')' found\n");
goto Finish;
default:
error("term expected, '");
cerr << peek() << "' found\n";
goto Finish;
}
}
else
{
switch (char op = peek())
{
case '+': case '-': case '*': case '/': case '%': case '^':
cin.ignore(); // Убрать знак операции с потока.
// Выполнить предыдущую операцию, положить на стек следующую.
if (!ops.empty() && ops.top() != '(' && !do_next_op())
goto Finish;
// Положить на стек операций следующую операцию.
ops.push(op);
// Теперь ожидаем терм.
awaiting_term = true;
break;
case ')':
// Убрать скобку с потока cin.
cin.ignore();
// Выполнять операции, пока не встретится открывающая скобка.
while (true)
{
if (ops.empty())
{
error("unmatched ')' found\n");
goto Finish;
}
if (ops.top() == '(')
{
ops.pop();
break;
}
if (!do_next_op())
goto Finish;
}
break;
case EOF:
// Выполнить все оставшиеся операции.
while (!ops.empty())
{
if (ops.top() == '(')
{
error("unmatched '(' found\n");
break;
}
if (!do_next_op())
break;
}
goto Finish;
default:
error("operation expected: '");
cerr << op << "'\n";
goto Finish;
}
}
}
Finish:
if (xs.empty())
{
error("not enough operands\n");
return 0.;
}
return xs.top();
}
int main()
{
while (true)
{
double answer = infix();
cin.clear();
cin.ignore(cin.rdbuf()->in_avail());
cin.sync();
cout << "answer = " << answer << endl;
}
return EXIT_SUCCESS;
}
// infix_calc_shunting_yard.cpp
// Инфиксный калькулятор с учётом приоритетов и ассоциативности операций и поддержкой скобок.
// Пример: 2+(2*2) ==> 6.
// Упрощённая грамматика:
// Терм --> Число | '(' Выражение ')' // term
// Выражение --> Терм { Операция Терм } // infix
// Реализован алгоритм сортировочной станции Э.Дейкстры на основе примера infix_calc_p_stack_std.cpp.
#include <iostream>
#include <cmath>
#include <stack>
using namespace std;
// Вспомогательная функция:
// посмотреть следующий непробельный символ в потоке cin, не извлекая его.
// (Пробельные символы пропускаются. Возвращает EOF если поток закончился.)
char peek()
{
char ch = EOF;
if (cin >> ch)
cin.unget();
return ch;
}
// Вспомогательная функция для установки ошибки.
void error(const char *message)
{
cerr << message;
cin.setstate(ios::failbit);
}
// Числовой приоритет операции.
int precedence(char op)
{
switch (op)
{
case '+': case '-': return 100;
case '*': case '/': case '%': return 200;
case '^': return 300;
default: return 0;
}
}
// Операция op связывает операнды слева направо?
bool is_left_associative(char op)
{
return op != '^';
}
double infix()
{
stack<char> ops; // Стек операций.
stack<double> xs; // Стек операндов.
// Вложенная функция, выполняющая операцию на вершине стека ops.
// Возвращает "успех" (false если произошла ошибка, true если выполнено успешно).
auto do_next_op = [&]() -> bool
{
double x, y;
if (xs.empty())
{
error("not enough operands\n");
return false;
}
y = xs.top();
xs.pop();
if (xs.empty())
{
xs.push(y);
error("not enough operands\n");
return false;
}
x = xs.top();
switch (ops.top())
{
case '+': x = x + y; break;
case '-': x = x - y; break;
case '*': x = x * y; break;
case '/': x = x / y; break;
case '%': x = fmod(x, y); break;
case '^': x = pow(x, y); break;
default:
error("internal error\n");
return false;
}
// Сохранить результат операции вместо операндов на стеке xs.
xs.top() = x;
// Убрать со стека операций выполненную операцию.
ops.pop();
return true;
};
bool awaiting_term = true; // Ожидает терм (true) или операцию (false)?
while (true)
{
if (awaiting_term) // Ожидается терм.
{
double x;
switch (char ch = peek())
{
// - и + могут стоять перед скобкой (, а не перед числом,
// поэтому обрабатываем этот случай особо.
case '-': case '+':
if (cin.ignore() && cin.peek() == '(')
{
// Имитируем отрицание вычитанием из нуля.
if (ch == '-')
{
xs.push(0);
ops.push('-');
}
cin.ignore(); // Убрать открывающую скобку из потока.
ops.push('(');
break;
}
cin.unget(); // Не скобка -- возвращаем - или + обратно.
// "Полноценный калькулятор" должен поддерживать унарные операции непосредственно.
// Данный пример упрощён: поддерживаются только бинарные инфиксные операции.
case '.':
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
if (!(cin >> x))
{
error("number expected\n");
goto Finish;
}
xs.push(x);
awaiting_term = false;
break;
case '(':
cin.ignore(); // Убрать открывающую скобку из потока.
ops.push('(');
break;
case ')':
error("unmatched ')' found\n");
goto Finish;
default:
error("term expected, '");
cerr << peek() << "' found\n";
goto Finish;
}
}
else // Ожидается операция.
{
switch (char op = peek())
{
case '+': case '-': case '*': case '/': case '%': case '^':
// Основное отличие от предыдущего варианта калькулятора,
// позволяющее учитывать приоритеты операций, находится здесь.
{
cin.ignore(); // Убрать знак операции с потока.
const auto op_prec = precedence(op); // Приоритет считанной операции.
const auto op_ltr = is_left_associative(op); // Левоассоциирующая операция?
// Выполнить все предыдущие операции, имеющие приоритет выше op,
// либо равный приоритет при условии, что op -- левоассоциирующая.
while (!ops.empty() && ops.top() != '(')
{
const auto left_op_prec = precedence(ops.top());
// Отрицание условия, записанного в комментарии выше (условие выхода из цикла).
if ((op_ltr && left_op_prec < op_prec)
|| (!op_ltr && left_op_prec <= op_prec))
break;
if (!do_next_op())
goto Finish;
}
// Положить на стек операций следующую операцию.
ops.push(op);
// Теперь ожидаем терм.
awaiting_term = true;
}
break;
case ')':
// Убрать скобку с потока cin.
cin.ignore();
// Выполнять операции, пока не встретится открывающая скобка.
while (true)
{
if (ops.empty())
{
error("unmatched ')' found\n");
goto Finish;
}
if (ops.top() == '(')
{
ops.pop();
break;
}
if (!do_next_op())
goto Finish;
}
break;
case EOF:
// Выполнить все оставшиеся операции.
while (!ops.empty())
{
if (ops.top() == '(')
{
error("unmatched '(' found\n");
break;
}
if (!do_next_op())
break;
}
goto Finish;
default:
error("operation expected: '");
cerr << op << "'\n";
goto Finish;
}
}
}
Finish:
if (xs.empty())
{
error("not enough operands\n");
return 0.;
}
return xs.top();
}
int main()
{
cout.precision(16);
while (true)
{
double answer = infix();
cin.clear();
cin.ignore(cin.rdbuf()->in_avail());
cin.sync();
cout << "answer = " << answer << endl;
}
return EXIT_SUCCESS;
}
// merge_sort.cpp
// Сортировка слияниями (рекурсивный вариант и вариант с явным стеком).
// Сортирует массивы целых.
#include <cstddef>
#include <cassert>
using namespace std;
// Операция слияния двух упорядоченных массивов (a и b)
// в третий упорядоченный массив c.
// Предполагается, что c имеет размер не менее, чем an + bn.
// Функция возвращает индекс следующего элемента за последним записанным в c.
size_t merge(const int a[], size_t an, const int b[], size_t bn, int c[])
{
assert(an != 0 && bn != 0);
for (size_t i = 0, j = 0, k = 0;; ++k)
{
if (b[j] < a[i])
{
c[k] = b[j];
if (++j == bn)
{
while (i != an)
c[++k] = a[i++];
return k + 1;
}
}
else
{
c[k] = a[i];
if (++i == an)
{
while (j != bn)
c[++k] = b[j++];
return k + 1;
}
}
}
}
// Сортировка слияниями с внешнем буфером.
// Сортирует массив a на месте, используя buf для хранения промежуточных результатов.
// Размер buf должен быть не меньше an.
void merge_sort(int a[], size_t an, int buf[])
{
if (1 < an)
{
// Размеры сортируемых "половин": p1 -- левая, p2 -- правая.
const auto p1 = an / 2, p2 = an - p1;
// Отсортировать левую половину.
merge_sort(a, p1, buf);
// Отсортировать правую половину.
merge_sort(a + p1, p2, buf);
// Выполнить слияние отсортированных половин в буфер.
merge(a, p1, a + p1, p2, buf);
// Скопировать содержимое буфера в исходный массив.
for (size_t i = 0; i < an; ++i)
a[i] = buf[i];
}
}
// Сортировка слияниями, создающая свой буфер.
// Использует предыдущий алгоритм.
void merge_sort(int a[], size_t an)
{
int *buf = new int[an];
merge_sort(a, an, buf);
delete[] buf;
}
// Сортировка слияниями на основе цикла и стека.
// Представляет собой модификацию рекурсивного варианта.
// Использует буфер того же размера, что и исходный массив (создаёт и удаляет буфер динамически).
void merge_sort_s(int a[], size_t an)
{
// Стек отложенных задач реализован в виде статического массива размера 64.
// Предполагается, что адреса не более, чем 64-битные.
struct {
int *a; // Указатель на начало сортируемого диапазона.
size_t an; // Размер сортируемого диапазона.
int stage; // Стадия сортировки диапазона (0, 1, 2, 3).
} ds[64];
size_t sp = 0; // Индекс текущей вершины стека.
int *buf = new int[an];
// Положить в стек первоначальную задачу -- весь исходный массив.
ds[0].a = a;
ds[0].an = an;
ds[0].stage = 0;
while (true)
{
// На каждой стадии выполняется своё действие.
switch (ds[sp].stage++)
{
case 0: // Создать задачу для сортировки левой половины.
if (1 < an)
{
an /= 2;
auto &t = ds[++sp];
t.a = a;
t.an = an;
t.stage = 0;
}
break;
case 1: // Создать задачу для сортировки правой половины.
if (1 < an)
{
const auto p = an / 2;
a += p;
an -= p;
auto &t = ds[++sp];
t.a = a;
t.an = an;
t.stage = 0;
}
break;
case 2: // Выполнить слияние отсортированных половин.
if (1 < an)
{
const auto p = an / 2;
merge(a, p, a + p, an - p, buf);
for (size_t i = 0; i < an; ++i)
a[i] = buf[i];
}
break;
default: // Убрать задачу из стека.
if (sp-- == 0)
{
// Все задачи выполнены, завершить работу.
delete[] buf;
return;
}
else
{
auto &t = ds[sp];
a = t.a;
an = t.an;
}
}
}
}
// sll_merge.cpp
// Односвязный список (singly-linked list, SLL) и сортировка слияниями.
#include <cassert>
#include <cstddef>
///////////////////////////////////////////////////////////////////////////////
// Односвязный список
// Тип значений, хранимый в списке.
typedef long Value;
// Звено односвязного списка.
struct Link
{
Link *next; // указатель на следующее звено
Value value; // значение, хранящееся в звене
// Элементарные конструкторы
Link(): next(nullptr) {}
explicit Link(Value value, Link *next = nullptr)
: next(next), value(value) {}
};
// Добавить значение в начало списка.
Link* push_front(Link *list, Value value)
{
return new Link(value, list);
}
// Создать список из массива.
Link* list_from_array(const Value a[], std::size_t n)
{
Link *head = nullptr;
while (n != 0)
head = push_front(head, a[--n]);
return head;
}
// Удалить начальное звено списка.
// Если removed_value != nullptr, то по этому адресу будет записано значение удалённого узла.
Link* pop_front(Link *list, Value *removed_value = nullptr)
{
assert(list);
const auto next = list->next;
if (removed_value)
*removed_value = list->value;
delete list;
return next;
}
// Удалить список целиком.
void delete_list(Link *list)
{
while (list)
list = pop_front(list);
}
// Проверить, является ли список закольцованным.
// Данная функция приводится как пример, далее она не используется (только тестируется).
bool has_loop(Link *list)
{
auto slow = list;
while (true)
{
// Два шага по list.
if (!list)
return false;
list = list->next;
if (!list)
return false;
if (list == slow)
return true;
list = list->next;
if (list == slow)
return true;
// Один шаг по slow.
slow = slow->next;
}
}
// Тест работоспособности has_loop.
int test_has_loop()
{
// Незакольцованный список.
Link a, b, c, d, e;
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
if (has_loop(&a))
return 1;
// Закольцованный список.
e.next = &a;
if (!has_loop(&a))
return 2;
// "Лассо".
e.next = &c;
if (!has_loop(&a))
return 3;
return 0;
}
///////////////////////////////////////////////////////////////////////////////
// Сортировка списка слияниями
// Требует O(N log N) время и O(1) память.
// Вспомогательная функция: возвращает указатель на звено с минимальным значением.
// Продвигает переменную, указывающую на возвращённое звено на следующую позицию.
inline Link* merging_next(Link *&a, Link *&b)
{
assert(a && b);
auto result = a;
if (b->value < a->value)
{
result = b;
b = b->next;
}
else
a = a->next;
return result;
}
// Слияние двух упорядоченных списков в один упорядоченный список.
Link* merge(Link *a, Link *b)
{
// Если один из списков пуст...
if (!a)
return b;
if (!b)
return a;
// Оба непусты: головой нового списка будет голова с меньшим значением.
for (auto head = merging_next(a, b), tail = head;;)
{
if (!a)
{
tail->next = b;
return head;
}
if (!b)
{
tail->next = a;
return head;
}
tail = tail->next = merging_next(a, b);
}
}
// Найти элемент перед средним элементом списка.
Link* list_premiddle(Link *list)
{
// Два шага по list -- один шаг по mid.
for (auto premid = list, mid = premid;;)
{
if (!list)
return premid;
list = list->next;
if (!list)
return premid;
list = list->next;
premid = mid;
mid = mid->next;
}
}
// Собственно сортировка слияниями (рекурсивный нисходящий вариант).
// Возвращает новую голову исходного списка.
Link* merge_sort(Link *list)
{
// Менее двух элементов?
if (!list || !list->next)
return list;
// Разрезать на два списка посередине.
auto premid = list_premiddle(list);
auto tail = premid->next;
premid->next = nullptr;
// Отсортировать списки по отдельности.
list = merge_sort(list);
tail = merge_sort(tail);
// Слить в общий и вернуть.
return merge(list, tail);
}
///////////////////////////////////////////////////////////////////////////////
// Тестирование работоспособности сортировки
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
using namespace std;
// Генерирует случайные списки, сортирует и сравнивает с результатом стандартной сортировки на исходном массиве.
int test_merge_sort()
{
mt19937_64 rng(5151);
uniform_int_distribution<Value> vg;
static const auto MAX_LENGTH = 2049;
vector<Value> reference;
for (int i = 0; i < MAX_LENGTH; ++i)
{
// Заполнить референс-массив.
reference.resize(i);
for (auto &item : reference)
item = vg(rng);
// Скопировать массив в новый список.
auto list = list_from_array(reference.data(), reference.size());
// Отсортировать и то и другое.
sort(reference.begin(), reference.end());
list = merge_sort(list);
// Сравнить на равенство содержимое массива и списка.
bool error = false;
auto pos = list;
for (auto &item : reference)
{
if (item != pos->value)
{
error = true;
break;
}
pos = pos->next;
}
// Удалить список.
delete_list(list);
// Нашли ошибку?
if (error)
return i+1;
}
return 0;
}
int main()
{
cout << "test_has_loop: " << test_has_loop() << endl;
cout << "test_merge_sort: " << test_merge_sort() << endl;
return EXIT_SUCCESS;
}
// quick_sort.cpp
// Быстрая сортировка (рекурсивный вариант, вариант с одной веткой рекурсии и вариант с явным стеком).
// Сортирует массивы целых.
#include <cstddef>
#include <cassert>
using namespace std;
// Выполнить обмен значениями двух целочисленных ячеек памяти (переменных).
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
// Разделить элементы массива a (перемещая их внутри массива) на две части:
// Левая часть: все элементы a, меньшие key.
// Правая часть: все элементы a, не меньшие key.
// Возвращает размер левой части (т.е. индекс первого элемента правой части).
// Левая часть может быть пустой (массив не содержит элементов, меньших key),
// в этом случае функция возвращает 0.
// Предполагается, что массив не пуст (n != 0), и значение key содержится в массиве, поэтому
// правая часть пустой быть не может и результат функции обязательно меньше n.
size_t qpartition(int a[], size_t n, int key)
{
assert(n != 0);
// Движемся в массиве с левого конца (указатель l) вправо
// и с правого конца (указатель r) влево.
int *l = a, *r = a + n - 1;
// Говорим, что "произошло пересечение", если случается ситуация r <= l.
// В случае, когда произошло пересечение, разделение завершено, и можно закончить.
while (true)
{
// Установим l на следующую позицию, в которой находится элемент, не меньший key.
while (*l < key)
if (r < ++l) // Произошло пересечение?
return l - a;
// Установим r на следующую позицию, в которой находится элемент, меньший key.
while (!(*r < key))
if (--r < l) // Произошло пересечение?
return l - a;
// Все элементы слева от l меньше key.
// Элемент по адресу l не меньше key.
// Все элементы справа от r не меньше key.
// Элемент по адресу r меньше key.
// Обменять элементы на позициях l и r.
swap(*l, *r);
// Переместить l и r на следующие позиции и проверить наличие пересечения.
if (--r <= ++l)
{
// Может возникнуть ситуация, когда между l и r находился один элемент,
// меньший key. В этом случае, его надо отнести к левой половине.
if (*l < key) ++l;
return l - a;
}
}
}
// Быстрая сортировка, рекурсивный вариант.
// Сортирует массив a на месте.
void quick_sort(int a[], size_t n)
{
if (n > 1)
{
// Выберем в качестве ключа элемент посередине массива
// (можно выбирать любой элемент, средний -- произвольный выбор автора)
// и выполним разделение по нему.
size_t left_n = qpartition(a, n, a[n / 2]);
if (left_n == 0)
{
// Все элементы a не меньше, чем средний элемент,
// т.е. средний элемент равен минимуму из всех элементов массива.
// В этом случае qpartition не изменяет исходный массив.
// Обменяем средний элемент массива с начальным.
swap(a[0], a[n / 2]);
// Отсортируем рекурсивно оставшуюся часть из n - 1 элемента.
quick_sort(a + 1, n - 1);
}
else
{
// Удалось разделить массив на две части.
// Так как любой элемент из левой части меньше любого элемента из правой части,
// то теперь достаточно независимо отсортировать обе части,
// что мы и выполним рекурсивно.
quick_sort(a, left_n);
quick_sort(a + left_n, n - left_n);
}
}
}
// Быстрая сортировка, рекурсивный вариант с раскрытием одной ветки рекурсии в цикл.
// Засчёт того, что рекурсивный вызов выполняется для части минимального размера,
// позволяет избежать переполнения стека вызовов (полностью рекурсивный вариант,
// приведённый выше, может выполнять до n вложенных рекурсивных вызовов).
void quick_sort_tc(int a[], size_t n)
{
// Пока есть что сортировать.
while (n > 1)
{
// Выполним разделение диапазона по среднему элементу.
size_t left_n = qpartition(a, n, a[n / 2]);
if (left_n == 0)
{
// Разделить не удалось, т.к. средний элемент равен минимуму всех элементов.
// Обменяем его с начальным элементом,
swap(a[0], a[n / 2]);
// а на следующей итерации цикла начнём сортировать оставшуюся часть.
++a;
--n;
}
else if (left_n < n - left_n)
{
// Левая часть меньше правой, отсортируем её рекурсивно.
quick_sort_tc(a, left_n);
// Правую часть отсортируем в цикле.
a += left_n;
n -= left_n;
}
else
{
// Правая часть не больше левой, отсортируем её рекурсивно.
quick_sort(a + left_n, n - left_n);
// Левую часть отсортируем в цикле.
n = left_n;
}
}
}
// Быстрая сортировка, вариант с раскрытием одной ветки в цикле и явным стеком отложенных веток.
void quick_sort_s(int a[], size_t n)
{
// Предполагаем, что размер адреса не превосходит 64 бит.
// Благодаря тому, что откладываются только "меньшие" части,
// глубина стека не может превзойти 64.
struct {
int *a;
size_t n;
} ds[64];
size_t sp = 0; // Количество элементов, помещённых в стек.
while (true)
{
while (n > 1)
{
// Выполним разделение диапазона по среднему элементу.
size_t left_n = qpartition(a, n, a[n / 2]);
if (left_n == 0)
{
// Разделить не удалось, обменяем начальный элемент со средним
swap(a[0], a[n / 2]);
// и будем дальше сортировать оставшиеся.
++a;
--n;
}
else if (left_n < n - left_n)
{
// Вместо выполнения рекурсивного вызова для левой (меньшей) части
// отложим её в стек.
auto &t = ds[sp++];
t.a = a;
t.n = left_n;
// Дальше сортируем правую часть.
a += left_n;
n -= left_n;
}
else
{
// Вместо выполнения рекурсивного вызова для правой части
// отложим её в стек.
auto &t = ds[sp++];
t.a = a + left_n;
t.n = n - left_n;
// Дальше сортируем левую часть.
n = left_n;
}
}
// Нет отложенных задач? Завершить работу.
if (sp == 0)
return;
// Есть отложенные задачи. Извлечь самую верхнюю из них.
auto &t = ds[--sp];
a = t.a;
n = t.n;
}
}
// bitmap_works.cpp
// Поиск в глубину и поиск в ширину на картинке:
// заливка связной области картинки заданным цветом,
// обведение контуром заданной ширины (сглаживание не реализовано).
// Загружает и сохраняет 32-битные BMP без сжатия.
#include <cassert>
#include <cstddef> // size_t
#include <cstdlib>
#include <cstdint> // uint32_t etc
#include <cstring> // memcpy
#include <utility> // swap
#include <stack>
#include <queue>
#include <fstream>
/// Тип "цвет". Синоним 32-битного беззнакового целого.
using Color = std::uint32_t;
/// Тип "координата". Синоним 32-битного беззнакового целого.
using Coordinate = std::uint32_t;
/// Тип "точка". Имеет две координаты.
struct Point
{
Coordinate x, y;
/// Создать точку в начале координат.
Point()
: x(0), y(0) {}
/// Создать точку с заданными координатами.
Point(Coordinate x, Coordinate y)
: x(x), y(y) {}
};
/// Тип "размеры" (прямоугольной области). Два размера: ширина и высота.
struct Extents
{
Coordinate width, height;
/// Создать область нулевых размеров.
Extents()
: width(0), height(0) {}
/// Создать область с заданными шириной и высотой.
Extents(Coordinate width, Coordinate height)
: width(width), height(height) {}
/// Вычислить площадь области.
std::size_t area() const { return std::size_t(width) * height; }
/// Проверить, выходят ли координаты точки за пределы области.
bool contains(Point point) const
{
return point.x < width && point.y < height;
}
};
/// Тип "картинка". Управляет массивом пикселей.
class Picture
{
Color *pixels; // упакованный двумерный массив
Extents extents;
/// Выделить память и выполнить копирование данных из другой картинки.
void copy_other(const Picture &other)
{
const auto area = extents.area();
pixels = new Color[area];
std::memcpy(pixels, other.pixels, area);
}
/// Удостовериться, что координаты точки корректны.
void assert_point(Point point) const
{
assert(extents.contains(point));
}
public:
/// Освободить занимаемую память.
void clear()
{
delete[] pixels;
pixels = nullptr;
extents = Extents();
}
/// Обменять содержимое двух объектов.
void swap(Picture &other)
{
std::swap(pixels, other.pixels);
std::swap(extents, other.extents);
}
/// Завершить существование объекта картинки.
~Picture() { clear(); }
/// Создать пустую картинку.
Picture()
: pixels(nullptr) {}
/// Создать картинку заданных размеров с неопределённым содержимым.
explicit Picture(Extents extents)
: pixels(nullptr), extents(extents)
{
pixels = new Color[extents.area()];
}
/// Создать копию картинки.
Picture(const Picture &other)
: pixels(nullptr), extents(other.extents)
{
copy_other(other);
}
/// Скопировать картинку присваиванием.
Picture& operator=(const Picture &other)
{
return *this = Picture(other);
}
/// Переместить картинку, не копируя данные.
Picture(Picture &&other)
: pixels(other.pixels), extents(other.extents)
{
other.pixels = nullptr;
other.extents = Extents();
}
/// Переместить картинку при присваивании, не копируя данные.
Picture& operator=(Picture &&other)
{
assert(this != &other);
clear();
swap(other);
return *this;
}
/// Получить размеры картинки.
const Extents& size() const { return extents; }
/// Получить указатель на пиксели.
const Color* data() const { return pixels; }
Color* data() { return pixels; }
/// Обратиться к одному пикселю по его координатам.
const Color& operator()(Point point) const
{
assert_point(point);
return pixels[point.x + extents.width * point.y];
}
Color& operator()(Point point)
{
assert_point(point);
return pixels[point.x + extents.width * point.y];
}
};
/// Получить значение цвета в формате BGRX для заданных значений трёх каналов модели RGB.
inline Color bgrx(unsigned red, unsigned green, unsigned blue)
{
return (blue & 0xFF) | ((green & 0xFF) << 8) | ((red & 0xFF) << 16);
}
/// Закрасить картинку целиком одним цветом.
void fill(Picture &picture, Color color)
{
const auto pixels = picture.size().area();
const auto data = picture.data();
for (std::size_t i = 0; i < pixels; ++i)
data[i] = color;
}
/// Заливка связной области.
/// Рекурсия заменена на стек+цикл = поиск в глубину по соседним пикселям.
void flood_fill(Picture &picture, Point start, Color color)
{
const auto target_color = picture(start);
std::stack<Point> points;
points.push(start);
do
{
start = points.top();
points.pop();
if (picture.size().contains(start) && picture(start) == target_color)
{
picture(start) = color;
points.emplace(start.x - 1, start.y);
points.emplace(start.x + 1, start.y);
points.emplace(start.x, start.y - 1);
points.emplace(start.x, start.y + 1);
}
} while (!points.empty());
}
/// Обвести фрагменты заданного цвета (what) контуром заданной толщины (в пикселях).
/// Алгоритм основан на ограниченном поиске в ширину.
void make_outline(Picture &picture, Color what, Color outline, unsigned width)
{
struct Pos
{
Point pos;
Color* ptr;
unsigned distance;
Pos(Coordinate x, Coordinate y, Color *ptr, unsigned d)
: pos(x, y), ptr(ptr), distance(d) {}
};
std::queue<Pos> positions;
const auto data = picture.data();
const auto pw = picture.size().width,
ph = picture.size().height;
// Сканируем картинку в поисках пикселей цвета what и
// добавляем их координаты в очередь со значением distances == 0.
for (Coordinate row = 0, i = 0; row < ph; ++row)
for (Coordinate col = 0; col < pw; ++col, ++i)
if (data[i] == what)
positions.emplace(col, row, data + i, 0);
// Выполняем ограниченный по дальности поиск в ширину, используя накопленную очередь.
while (!positions.empty())
{
const auto &cur = positions.front();
const auto x = cur.pos.x, y = cur.pos.y;
const auto ptr = cur.ptr;
auto distance = cur.distance;
positions.pop();
if (*ptr != what)
*ptr = outline;
if (++distance < width)
{
if (x != 0)
positions.emplace(x - 1, y, ptr - 1, distance);
if (x != pw - 1)
positions.emplace(x + 1, y, ptr + 1, distance);
if (y != 0)
positions.emplace(x, y - 1, ptr - pw, distance);
if (y != ph - 1)
positions.emplace(x, y + 1, ptr + pw, distance);
}
}
}
// Загрузка и сохранение простого варианта BMP.
// По данным https://en.wikipedia.org/wiki/BMP_file_format
/// Follows minimalistic BITMAPINFOHEADER structure.
#if defined(_MSC_VER) // Компилируем MSVC?
#pragma pack(push) // Сохранить текущее значение упаковки структур.
#pragma pack(1) // Нестандартное расширение MSVC: упакованная структура.
struct
#else
struct __attribute__((packed)) // Нестандартное расширение GCC: упакованная структура.
#endif
Bmp_header
{
// BMP header
char b = 'B', m = 'M';
std::uint32_t file_size = 54; // == data_offset + pixels size in bytes
std::uint16_t reserved1 = 0, reserved2 = 0;
std::uint32_t data_offset = 54; // this header size in bytes
// DIB header (BITMAPINFOHEADER)
std::uint32_t header_size = 40;
std::int32_t bitmap_width = 0, bitmap_height = 0;
std::uint16_t color_planes = 1;
std::uint16_t bpp = 32; // bits per pixel
std::uint32_t compression_method = 0; // 0 = none (BGRX), 3 = XBGR
std::uint32_t image_size = 0;
std::uint32_t x_dpi = 96, y_dpi = 96; // actually ignored
std::uint32_t palette_size = 0;
std::uint32_t important_colors = 0;
/// Конструктор по умолчанию (пустая картинка).
Bmp_header() = default;
/// Конструктор на основе картинки.
explicit Bmp_header(const Picture &picture)
{
bitmap_width = picture.size().width;
bitmap_height = picture.size().height;
file_size = 54 + picture.size().area() * sizeof(Color); // возможно переполнение
}
/// Проверка заголовка на корректность (ограничено возможностями данной реализации).
bool is_valid() const
{
return b == 'B' && m == 'M' &&
data_offset >= 54 && header_size >= 40 &&
bitmap_width != 0 && bitmap_height != 0 && color_planes == 1 &&
bpp == 32 && (compression_method == 0 || compression_method == 3);
// other values ignored
}
};
#if defined(_MSC_VER)
#pragma pack(pop) // Восстановить предыдущее значение упаковки структур.
#endif
// Вспомогательные функции, выполняющие насилие над системой типов
// (конверсия произвольного указателя в указатель на char/const char).
inline char* to_byte_ptr(void *ptr) { return (char*)ptr; }
inline const char* to_byte_ptr(const void *ptr) { return (const char*)ptr; }
/// Преобразование формата пикселя.
inline Color xbgr_to_bgrx(Color color)
{
return (color << 24) | (color >> 8);
}
/// Прочитать BMP из потока (фиксированный формат: 32 бита на пиксель, нет сжатия).
/// Поток должен быть открыт в двоичном режиме.
std::istream& read_bmp_32bpp(std::istream &is, Picture &picture)
{
// Считать заголовок из файла.
Bmp_header header;
is.read(to_byte_ptr(&header), header.data_offset);
if (!is || !header.is_valid())
{
is.setstate(std::ios::failbit);
return is;
}
// Создать картинку нужных размеров.
picture = Picture(Extents(header.bitmap_width, header.bitmap_height));
// Пропустить заданное число байт после заголовка.
is.ignore(header.data_offset - sizeof(header));
// Считать пиксели.
is.read(to_byte_ptr(picture.data()), picture.size().area() * sizeof(Color));
// Если "метод компрессии" == 3 (RGBA, результат работы GIMP), обратить порядок байт.
if (header.compression_method == 3)
{
const auto data = picture.data();
const auto sz = picture.size().area();
for (std::size_t i = 0; i < sz; ++i)
data[i] = xbgr_to_bgrx(data[i]);
}
// Вернуть результирующую картинку.
return is;
}
/// Записать BMP в двоичный поток.
std::ostream& write_bmp_32bpp(std::ostream &os, const Picture &picture)
{
// Построить и записать в файл соответствующий картинке заголовок.
Bmp_header header(picture);
os.write(to_byte_ptr(&header), header.data_offset);
// Записать пиксели.
os.write(to_byte_ptr(picture.data()), picture.size().area() * sizeof(Color));
return os;
}
///////////////////////////////////////////////////////////////////////////////
// Тестирование
#include <iostream>
int main()
{
using namespace std;
// Test 1.
fstream bmp("100x50orange.bmp", ios::binary | ios::out | ios::trunc);
Picture picture(Extents(100, 50));
fill(picture, bgrx(255, 144, 0));
write_bmp_32bpp(bmp, picture);
bmp.close();
// Test 2.
picture.clear();
bmp.open("input.bmp", ios::binary | ios::in);
read_bmp_32bpp(bmp, picture);
bmp.close();
// Заливка белым из центра.
flood_fill(picture,
Point(picture.size().width / 2, picture.size().height / 2),
0xFFFFFFFF);
bmp.open("flood_fill.bmp", ios::binary | ios::out | ios::trunc);
write_bmp_32bpp(bmp, picture);
bmp.close();
// Test 3.
picture.clear();
bmp.open("input.bmp", ios::binary | ios::in);
read_bmp_32bpp(bmp, picture);
bmp.close();
// Белый контур вокруг чёрных пикселей.
make_outline(picture, bgrx(0, 0, 0), bgrx(255, 255, 255), 4);
bmp.open("outline.bmp", ios::binary | ios::out | ios::trunc);
write_bmp_32bpp(bmp, picture);
bmp.close();
return EXIT_SUCCESS;
}
// ageo2d.hpp
// Точки и вектора на плоскости, элементарные определения.
#ifndef AGEO2D_HPP_INCLUDED_
#define AGEO2D_HPP_INCLUDED_
///////////////////////////////////////////////////////////////////////////////
// Вектора
/// Двумерный вектор.
struct Vector_2
{
double x, y;
/// Конструктор по умолчанию -- нулевой вектор.
Vector_2()
: x(0.), y(0.) {}
/// Создать вектор с заданными координатами.
Vector_2(double x, double y)
: x(x), y(y) {}
/// Добавить другой вектор "на месте".
Vector_2& operator+=(const Vector_2 &other)
{
x += other.x;
y += other.y;
return *this;
}
/// Вычесть другой вектор "на месте".
Vector_2& operator-=(const Vector_2 &other)
{
x -= other.x;
y -= other.y;
return *this;
}
/// Домножить на скаляр "на месте".
Vector_2& operator*=(double factor)
{
x *= factor;
y *= factor;
return *this;
}
};
/// Проверка пары векторов на равенство.
inline bool operator==(const Vector_2 &a, const Vector_2 &b)
{
return a.x == b.x && a.y == b.y;
}
/// Проверка пары векторов на неравенство.
inline bool operator!=(const Vector_2 &a, const Vector_2 &b)
{
return !(a == b);
}
/// Сумма векторов: операция "+".
inline Vector_2 operator+(const Vector_2 &a, const Vector_2 &b)
{
return Vector_2(a.x + b.x, a.y + b.y);
}
/// Разность векторов: операция "-".
inline Vector_2 operator-(const Vector_2 &a, const Vector_2 &b)
{
return Vector_2(a.x - b.x, a.y - b.y);
}
/// Унарный минус.
inline Vector_2 operator-(const Vector_2 &a)
{
return Vector_2(-a.x, -a.y);
}
/// Умножение вектора на скаляр слева: операция "*".
inline Vector_2 operator*(double factor, const Vector_2 &vec)
{
return Vector_2(factor * vec.x, factor * vec.y);
}
/// Умножение вектора на скаляр справа: операция "*".
inline Vector_2 operator*(const Vector_2 &vec, double factor)
{
return factor * vec; // то же, что и слева
}
/// Скалярное произведение векторов.
inline double dotp(const Vector_2 &a, const Vector_2 &b)
{
return a.x * b.x + a.y * b.y;
}
/// Псевдоскалярное произведение векторов.
/// Равно произведению длин векторов на синус угла между ними.
inline double crossp(const Vector_2 &a, const Vector_2 &b)
{
return a.x * b.y - a.y * b.x;
}
///////////////////////////////////////////////////////////////////////////////
// Точки
/// Точка на плоскости.
struct Point_2
{
double x, y;
/// Конструктор по умолчанию -- начало координат.
Point_2()
: x(0.), y(0.) {}
/// Создать точку с заданными координатами.
Point_2(double x, double y)
: x(x), y(y) {}
/// Радиус-вектор точки.
Vector_2 radius() const
{
return Vector_2(x, y);
}
/// Сместить эту точку на заданный вектор.
Point_2& operator+=(const Vector_2 &delta)
{
x += delta.x;
y += delta.y;
return *this;
}
/// Сместить эту точку на -delta.
Point_2& operator-=(const Vector_2 &delta)
{
x -= delta.x;
y -= delta.y;
return *this;
}
};
/// Проверка пары точек на равенство.
inline bool operator==(const Point_2 &a, const Point_2 &b)
{
return a.x == b.x && a.y == b.y;
}
/// Проверка пары точек на неравенство.
inline bool operator!=(const Point_2 &a, const Point_2 &b)
{
return !(a == b);
}
/// Разность двух точек даёт вектор.
inline Vector_2 operator-(const Point_2 &a, const Point_2 &b)
{
return Vector_2(a.x - b.x, a.y - b.y);
}
/// К точке можно добавить вектор, чтобы получить смещённую точку.
inline Point_2 operator+(const Point_2 &a, const Vector_2 &delta)
{
return Point_2(a.x + delta.x, a.y + delta.y);
}
/// К точке можно добавить вектор, чтобы получить смещённую точку.
inline Point_2 operator+(const Vector_2 &delta, const Point_2 &a)
{
return a + delta;
}
/// Из точки можно вычесть вектор, чтобы получить смещённую точку.
inline Point_2 operator-(const Point_2 &a, const Vector_2 &delta)
{
return Point_2(a.x - delta.x, a.y - delta.y);
}
#endif//AGEO2D_HPP_INCLUDED_
// jarvis.cpp
// Алгоритм Джарвиса ("заворачивания подарка")
// построения выпуклой оболочки множества точек на плоскости.
#include <cassert>
#include <utility> // swap
#include <cmath> // abs
#include "ageo2d.hpp" // точки и вектора
/// В диапазоне точек найти самую верхнюю из самых правых.
Point_2* find_highest_rightmost(Point_2 *begin, Point_2 *end)
{
assert(begin < end);
double x_max = begin->x, y_max = begin->y;
auto cur_max = begin;
while (++begin != end)
{
if (x_max < begin->x
|| begin->x == x_max && y_max < begin->y)
{
x_max = begin->x;
y_max = begin->y;
cur_max = begin;
}
}
return cur_max;
}
/// В диапазоне точек найти самый дальний поворот по часовой стрелке от точки v.
Point_2* max_cw_turn(Point_2 *begin, Point_2 *end, Point_2 v)
{
assert(begin < end);
auto cur_max = begin;
auto vector = *begin - v; // воспользуемся оператором минус, определённым для точек выше
while (++begin != end)
{
const auto new_vector = *begin - v;
const auto cp = crossp(vector, new_vector);
if (cp < 0. // поворот от vector к new_vector по ЧС?
|| cp == 0. // коллинеарны, но сонаправленны и new_vector длиннее, чем vector?
&& dotp(vector, vector) < dotp(vector, new_vector))
{
cur_max = begin;
vector = new_vector;
}
}
return cur_max;
}
/// Алгоритм заворачивания подарка.
/// Переставляет элементы исходного диапазона точек так,
/// чтобы вершины выпуклой оболочки в порядке обхода против часовой стрелки
/// встали в начале диапазона, возвращает указатель на следующую за последней
/// вершиной построенной выпуклой оболочки вершину.
Point_2* convex_hull_jarvis(Point_2 *begin, Point_2 *end)
{
using std::swap;
if (begin == end)
return end;
// Найти позицию самой верхней из самых правых точек.
// Это -- последняя вершина выпуклой оболочки.
auto cur = find_highest_rightmost(begin, end);
// Потенциальная ошибка: если есть более одной точки, равной *cur,
// то алгоритм может выдать некорректный результат.
// Как можно исправить эту ситуацию?
// Поставить её в конец последовательности для того,
// чтобы корректно выйти из цикла, когда следующая вершина совпадёт с ней.
const auto last_pos = end - 1;
swap(*cur, *last_pos);
cur = last_pos;
// Цикл по вершинам выпуклой оболочки.
while (true)
{
const auto next = max_cw_turn(begin, end, *cur);
// Поставить следующую вершину.
swap(*begin, *next);
cur = begin++;
if (next == last_pos) // Выпуклая оболочка построена.
return begin;
}
}
///////////////////////////////////////////////////////////////////////////////
// Геометрические операции, применяемые при тестировании
/// Проверка многоугольника на строгую выпуклость.
bool is_strictly_convex(const Point_2 *begin, const Point_2 *end)
{
if (end - begin < 2)
return true; // одна точка
if (end - begin < 3)
return begin[0] != begin[1]; // отрезок
// Проходя по всем углам (парам смежных рёбер) многоугольника,
// проверять, что поворот происходит строго против ЧС.
auto a = *(end - 2), b = *(end - 1);
do
{
const auto c = *begin++;
const auto // рёбра
ba = b - a,
cb = c - b;
// Проверить поворот от ba к cb.
if (crossp(ba, cb) <= 0.)
return false;
a = b;
b = c;
} while (begin != end);
return true;
}
/// Положение точки относительно множества.
enum Point_location
{
point_location_inside, // внутри
point_location_boundary, // на границе
point_location_outside // снаружи
};
/// Определить положение точки p относительно многоугольника [begin, end),
/// в котором вершины перечислены в порядке обхода против часовой стрелки.
/// Осторожно: на результат может влиять погрешность вычислений.
/// Используется правило витков (== ненулевого индекса).
/// Алгоритм позаимствован с http://geomalgorithms.com/a03-_inclusion.html
Point_location locate_point
(
const Point_2 *begin, const Point_2 *end, // многоугольник
Point_2 p, // точка
double tolerance = 0. // условный допуск на границе
)
{
using std::abs;
if (begin == end)
return point_location_outside;
int wn = 0; // количество витков
// Проходя по всем рёбрам многоугольника, считать количество витков.
auto prev = *(end - 1);
do
{
const auto next = *begin++;
const auto
edge = next - prev,
prad = p - prev;
const auto cp = crossp(prad, edge);
// Ребро пересекает луч снизу-вверх справа от точки p.
if (prev.y <= p.y && p.y < next.y && 0. < cp)
++wn;
// Ребро пересекает луч сверху-вниз справа от точки p.
else if (next.y <= p.y && p.y < prev.y && cp < 0.)
--wn;
// Дополнительная проверка: точка лежит на ребре
else if (abs(cp) <= tolerance
&& dotp(prad, prad) <= dotp(prad, edge))
return point_location_boundary;
prev = next;
} while (begin != end);
return wn == 0 ? point_location_outside : point_location_inside;
}
///////////////////////////////////////////////////////////////////////////////
// Тестирование
#include <iostream>
#include <random>
/// Тест на основе заранее известной оболочки.
int test_chj_0()
{
Point_2 points[]
{
{ 0, 0 },
{ 10, 0 },
{ 0, 10 },
{ 10, 10 },
{ 0, 1 },
{ 0, 0 },
{ 5, 0 },
{ 5, 5 },
{ 2, 7 }
};
const auto points_sz = sizeof(points) / sizeof(Point_2);
const Point_2 ch[]
{
{ 0, 10 },
{ 0, 0 },
{ 10, 0 },
{ 10, 10 },
};
const auto ch_sz = sizeof(ch) / sizeof(Point_2);
if (convex_hull_jarvis(points, points + points_sz)
- points != ch_sz) // в оболочке должно быть ch_sz вершин
return 1;
for (int i = 0; i < ch_sz; ++i)
if (points[i] != ch[i])
return 2;
return 0;
}
/// Заполнить диапазон случайными точками с нормальным распределением по каждой координате.
/// Центр в нуле, среднеквадратичное отклонение единица.
void fill_random_normal(Point_2 *begin, Point_2 *end)
{
using namespace std;
random_device seed_gen; // генератор случайного зерна
mt19937_64 rng(seed_gen()); // генератор псевдослучайных последовательностей бит
normal_distribution<> distr; // нормальное распределение
while (begin != end)
*begin++ = Point_2(distr(rng), distr(rng));
}
/// Проверить алгоритм выпуклой оболочки на заданном наборе точек.
int test_cvj_on(Point_2 *begin, Point_2 *end)
{
const auto ch_end = convex_hull_jarvis(begin, end);
if (!is_strictly_convex(begin, ch_end))
return 1;
for (auto p = ch_end; p != end; ++p)
if (locate_point(begin, ch_end, *p) != point_location_inside)
return 2;
return 0;
}
/// Сгенерировать случайный набор точек и проверить на нём алгоритм выпуклой оболочки.
int test_cvj_1()
{
using namespace std;
random_device seed_gen; // генератор случайного зерна
mt19937_64 rng(seed_gen()); // генератор псевдослучайных последовательностей бит
uniform_int_distribution<> distr(3, 2000); // равномерное распределение на целых из [3, 2000]
// Случайное количество точек.
const auto sz = distr(rng);
cout << sz << '\t';
auto points = new Point_2[sz];
// Сгенерировать случайные точки.
fill_random_normal(points, points + sz);
// Проверить работу алгоритма на этом наборе точек.
const auto result = test_cvj_on(points, points + sz);
cout << result << endl;
delete[] points;
return result;
}
int main()
{
using namespace std;
cout << test_chj_0() << endl;
while (true)
assert(test_cvj_1() == 0);
return EXIT_SUCCESS;
}
Кувшинов Д.Р. © 2015