Всем привет!
Несколько месяцев назад я решил написать все алгоритмы, которые знаю (и не знаю) в одном проекте Visual Studio, чтобы было легче использовать, запоминать, подготавливаться к интервью и было легче учить новые алгоритмы.
Я частично реализовал эту библиотеку, но перед тем как я углублюсь в детали, я хочу показать некоторые примеры использования библиотеки։
Пример
Для примера, вы можете посчитать n-ый элемент последовательности Фибоначчи используя матричные преобразования написал следующий код:
#include <iostream>
#include <Math/Math.h>
using namespace std;
int main()
{
algo::Matrix<int> mat{ {1, 1}, { 1, 0 } };
algo::Matrix<int> neutral{ {1, 0}, { 0, 1 } };
algo::Matrix<int> fib { {1, 1} };
mat = algo::bin_pow(mat, 7, neutral, algo::matrix_mul<int>);
fib = algo::matrix_mul(fib, mat);
cout << fib[0][0]; // prints 34
}
После компиляции данного кода так же сгенерируется файл, который не содержит каких либо заголовков этой библиотеки и этот файл уже можно отправлять на проверку:
Сгенерированный файл
#include <iostream>
#pragma once
#include<iostream>
#pragma once
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<cassert>
#include<queue>
#include<set>
#include<map>
namespace algo
{
const int Inf = INT_MAX;
const long long LInf = LLONG_MAX;
template<typename T, typename... Others>
T max(T first, Others... others);
template<typename T>
T max(T first);
template<typename T, typename... Others>
T min(T first, Others... others);
template<typename T>
T min(T first);
template<typename Container>
void input_container(std::istream& in,
int& n,
Container& container);
template<typename Container>
void output_container(std::ostream& out,
const Container& container,
const std::string& delimiter = " ");
template<typename Container, typename T>
void sum_container(const Container& container, T& sum);
template <typename T>
using Matrix = std::vector<std::vector<T>>;
template <typename T>
Matrix<T> CreateMatrix(size_t n, T etalon = T());
template <typename T>
Matrix<T> CreateMatrix(size_t n, size_t m, T etalon = T());
template <typename T>
void CreateMatrix(Matrix<T>& matrix, size_t n, T etalon = T());
template <typename T>
void CreateMatrix(Matrix<T>& matrix, size_t n, size_t m, T etalon = T());
double random(double min, double max);
}
#pragma once
#include<algorithm>
#include<random>
namespace algo
{
template<typename T, typename... Others>
inline T max(T first, Others... others)
{
return std::max(first, max<T>(others...));
}
template<typename T>
inline T max(T first)
{
return first;
}
template<typename T, typename... Others>
inline T min(T first, Others... others)
{
return std::min(first, min(others...));
}
template<typename T>
inline T min(T first)
{
return first;
}
template<typename Container, typename T>
inline void sum_container(const Container& container, T& sum)
{
for (auto& elem : container)
{
sum += elem;
}
}
template<typename T>
inline Matrix<T> CreateMatrix(size_t n, T etalon)
{
return Matrix<T>(n, std::vector<T>(n, etalon));
}
template<typename T>
inline Matrix<T> CreateMatrix(size_t n, size_t m, T etalon)
{
return Matrix<T>(n, std::vector<T>(m, etalon));
}
template<typename T>
inline void CreateMatrix(Matrix<T>& matrix, size_t n, T etalon)
{
matrix = Matrix<T>(n, std::vector<T>(n, etalon));
}
template<typename T>
inline void CreateMatrix(Matrix<T>& matrix, size_t n, size_t m, T etalon)
{
matrix = Matrix<T>(n, std::vector<T>(m, etalon));
}
inline double random(double min, double max)
{
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_real_distribution<double> dist(min, max);
return dist(mt);
}
template<typename Container>
inline void input_container(std::istream& in,
int& n,
Container& container)
{
in >> n;
container.resize(n);
for (auto& elem : container)
{
in >> elem;
}
}
template<typename Container>
inline void output_container(std::ostream& out,
const Container& container,
const std::string& delimiter)
{
for (auto& elem : container)
{
out << elem << delimiter;
}
}
}
#include<functional>
// TODO check math
namespace algo
{
template<typename T>
T gcd(T a, T b)
{
return b ? a : gcd(b, a % b);
}
template<typename T>
T lcm(T a, T b)
{
return a / gcd(a, b) * b;
}
int euler_function(int n)
{
int ans = 0;
for (int i = 1; i <= n; ++i)
{
ans += gcd(i, n) == 1;
}
return ans;
}
template<typename T, typename Func>
T bin_pow(T elem, int n, T neutral_element,
Func mul = std::multiplies<T>())
{
T ans = neutral_element;
while (n)
{
if (n & 1)
{
ans = mul(ans, elem);
}
elem = mul(elem, elem);
n >>= 1;
}
return ans;
}
template<typename T, typename Func>
T bin_pow(T elem, int n, int mod, T neutral_element,
Func mul = std::multiplies<T>(),
Func modulus = std::modulus<T>())
{
T ans = neutral_element;
while (n)
{
if (n & 1)
{
ans = mul(ans, elem);
ans = modulus(ans, mod);
}
elem = mul(elem, elem);
elem = modulus(elem, mod);
n >>= 1;
}
return ans;
}
template<typename T>
algo::Matrix<T> matrix_mul(const algo::Matrix<T>& l,
const algo::Matrix<T>& r)
{
if (l[0].size() != r.size())
{
throw std::runtime_error("Matrix dimensions must be equal");
}
algo::Matrix<T> matrix = CreateMatrix(l.size(), r[0].size(), 0);
for (int i = 0; i < l.size(); ++i)
for (int j = 0; j < r.size(); ++j)
for (int k = 0; k < l[i].size(); ++k)
matrix[i][j] += l[i][k] * r[k][j];
return matrix;
}
template<typename T>
algo::Matrix<T> matrix_mod(algo::Matrix<T> matrix, int mod)
{
for (int i = 0; i < matrix.size(); ++i)
for (int j = 0; j < matrix[i].size(); ++j)
matrix[i][j] %= mod;
return matrix;
}
std::vector<int> sieve_of_eratosthenes(int n)
{
std::vector<int> primes(1, 2);
std::vector<char> used(n, false);
for (int i = 2; i < used.size(); i += 2)
used[i] = true;
for (int i = 3; i < used.size(); i += 2)
{
if (!used[i])
{
primes.push_back(i);
for (int j = i * i; j < used.size(); j += i)
{
used[j] = true;
}
}
}
return primes;
}
int extended_euclidean(int a, int b, int& x, int& y)
{
if (a == 0)
{
x = 0, y = 1;
return b;
}
int x1, y1;
int gcd = extended_euclidean(b % a, a, x1, y1);
x = y1 - b / a * x1;
y = x1;
return gcd;
}
}
namespace algo
{
int euler_function(int n)
{
int ans = 0;
for (int i = 1; i <= n; ++i)
{
ans += gcd(i, n) == 1;
}
return ans;
}
}
using namespace std;
int main()
{
algo::Matrix<int> mat{ {1, 1}, { 1, 0 } };
algo::Matrix<int> neutral{ {1, 0}, { 0, 1 } };
algo::Matrix<int> fib { {1, 1} };
mat = algo::bin_pow(mat, 7, neutral, algo::matrix_mul<int>);
fib = algo::matrix_mul(fib, mat);
cout << fib[0][0]; // prints 34
}
Другой пример
Для другого примера я протестировал мою библиотеку на этой задаче. Вот код, который я написал в Визуале:
#include <iostream>
#include <DataStructures/SegmentTree.h>
using namespace std;
int main()
{
int n;
cin >> n;
algo::SegmentTree<int> tree(std::vector<int>(40000, 0), // initial array
std::plus<int>(), // operation (function or lambda or functor)
0, // neutral element of operation above
algo::SegmentTree<int>::UpdateType::Sum); // update type (assigning, product or sum for now)
vector<int> ans(n);
for (int i = 0; i < n; i++)
{
int x, y;
cin >> x >> y;
ans[tree.query(0, x)]++;
tree.update(x, 1);
}
for (int i = 0; i < n; i++)
{
cout << ans[i] << endl;
}
}
А вот этот код был сгенерирован после компиляции, и уже его вы можете спокойно сабмитить в тимус и получать свой АС :) (Тут мои сабмиты):
Код на проверку
#include <iostream>
#pragma once
#include<vector>
#include<functional>
#include<algorithm>
namespace algo
{
template<typename T>
class SegmentTree
{
public:
static T min(T a, T b)
{
return a < b ? a : b;
}
static T max(T a, T b)
{
return a > b ? a : b;
}
enum class UpdateType
{
Assign,
Sum,
Product
};
private:
std::vector<T> m_vec;
std::vector<T> m_tree;
std::vector<T> m_lazy_prop;
std::function<T(T, T)> m_tree_logic;
int m_neutral_element;
UpdateType m_upd_type;
void build_tree(int v, int l, int r);
void update(int pos, T elem, int v, int l, int r);
// void update(int pos_l, int pos_r, T elem, int v, int l, int r);
T query(int from, int to, int v, int l, int r) const;
static int left(int v);
static int right(int v);
static int mid(int l, int r);
void update_one(int& a, int b);
public:
SegmentTree(const std::vector<T>& vec,
const std::function<T(T, T)>& tree_logic,
int neutral_element,
UpdateType upd_type = UpdateType::Assign);
void build_tree();
void update(int pos, T elem);
// void update(int pos_l, int pos_r, T elem);
T query(int from, int to) const;
int size() const;
};
}
namespace algo
{
template<typename T>
inline void SegmentTree<T>::build_tree(int v, int l, int r)
{
if (l == r)
{
m_tree[v] = m_vec[l];
}
else
{
int m = mid(l, r);
build_tree(left(v), l, m);
build_tree(right(v), m + 1, r);
m_tree[v] = m_tree_logic(m_tree[left(v)], m_tree[right(v)]);
}
}
template<typename T>
inline void SegmentTree<T>::update(int pos, T elem, int v, int l, int r)
{
if (l == r)
{
update_one(m_tree[v], elem);
update_one(m_vec[pos], elem);
}
else
{
int m = mid(l, r);
if (pos <= m)
{
update(pos, elem, left(v), l, m);
}
else
{
update(pos, elem, right(v), m + 1, r);
}
m_tree[v] = m_tree_logic(m_tree[left(v)], m_tree[right(v)]);
}
}
/*template<typename T>
inline void SegmentTree<T>::update(int pos_l,
int pos_r,
T elem,
int v,
int l,
int r)
{
if (pos_l == l && pos_r == r)
{
m_lazy_prop = elem;
}
}*/
template<typename T>
inline T SegmentTree<T>::query(int from, int to, int v, int l, int r) const
{
if (from > to)
{
return m_neutral_element;
}
if (from == l && to == r)
{
return m_tree[v];
}
else
{
int m = mid(l, r);
int left_ans = query(from, std::min(m, to), left(v), l, m);
int right_ans = query(std::max(from, m+1), to, right(v), m + 1, r);
return m_tree_logic(left_ans, right_ans);
}
}
template<typename T>
inline int SegmentTree<T>::left(int v)
{
return v << 1;
}
template<typename T>
inline int SegmentTree<T>::right(int v)
{
return (v << 1) + 1;
}
template<typename T>
inline int SegmentTree<T>::mid(int l, int r)
{
return (l + r) >> 1;
}
template<typename T>
inline void SegmentTree<T>::update_one(int& a, int b)
{
switch (m_upd_type)
{
case UpdateType::Assign:
a = b;
break;
case UpdateType::Sum:
a += b;
break;
case UpdateType::Product:
a *= b;
break;
default:
break;
}
}
template<typename T>
SegmentTree<T>::SegmentTree(const std::vector<T>& vec,
const std::function<T(T, T)>& tree_logic,
int neutral_element,
UpdateType upd_type)
: m_vec(vec)
, m_tree_logic(tree_logic)
, m_neutral_element(neutral_element)
, m_upd_type(upd_type)
{
m_tree.resize(m_vec.size() << 2);
}
template<typename T>
inline void SegmentTree<T>::build_tree()
{
build_tree(1, 0, m_vec.size() - 1);
}
template<typename T>
inline void SegmentTree<T>::update(int pos, T elem)
{
update(pos, elem, 1, 0, m_vec.size() - 1);
}
/*template<typename T>
inline void SegmentTree<T>::update(int pos_l, int pos_r, T elem)
{
if (m_lazy_prop.empty())
{
m_lazy_prop.resize(m_tree.size());
}
update(pos_l, pos_r, elem, 1, 0, m_vec.size() - 1);
}*/
template<typename T>
inline T SegmentTree<T>::query(int from, int to) const
{
return query(from, to, 1, 0, m_vec.size() - 1);
}
template<typename T>
inline int SegmentTree<T>::size() const
{
return m_vec.size();
}
}
using namespace std;
int main()
{
int n;
cin >> n;
algo::SegmentTree<int> tree(std::vector<int>(40000, 0),
std::plus<int>(),
0,
algo::SegmentTree<int>::UpdateType::Sum);
vector<int> ans(n);
for (int i = 0; i < n; i++)
{
int x, y;
cin >> x >> y;
ans[tree.query(0, x)]++;
tree.update(x, 1);
}
for (int i = 0; i < n; i++)
{
cout << ans[i] << endl;
}
}
Это очень удобно и я планирую добавлять много алгоритмов сюда.
Репозитория этой библиотеки на ГитХабе и вот ссылка. Во вкладке "Projects" вы найдете темы (к примеру Graphs, Strings, Cryptography и т.д.) которые я планирую покрывать, а так же все алгоритмы, которые я уже реализовал и протестировал. Я использую конечно же Windows, С++14/17 и репозитория это сам по себе проект Visual Studio 2019. Все алгоритмы реализованы в пространстве имен "algo" и для каждого алгоритма я создал класс, которые разделил на его хедер и его реализацию.
Так же, как уже, наверное, понятно, я реализовал "препроцессор", который парсит только файлы моей библиотеки. Он нужен для того, что сгеренировать файл, который можно отправить на проверку и его работа вшита в процесс компиляции, так что вручную ничего не надо делать.
Любой программист здесь, конечно же, может использовать мою библиотеку для решения задачек. Я буду очень рад, если уто нибудь будет её использовать, и почему нет, развивать её, добавляя новые алгоритмы, исправляя старые ошибки и тому подобное!
Спасибо, что дочитали, всем добра :)
