Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save bejaneps/9005111e94062c0ebaa47140adf809da to your computer and use it in GitHub Desktop.
Save bejaneps/9005111e94062c0ebaa47140adf809da to your computer and use it in GitHub Desktop.
#include <iostream> //std::cout
#include <vector> //std::vector
#include <algorithm> //std::find
#include <ctime> //std::time
#include <random> //std::mt19937
#include <functional> //std::bind
// в задании не указано какой массив использовать и можно ли вообще использовать стандартные библиотеки C++ , так что для удобности и простоты я использую массив std::vector и алгоритм std::find
int same_elements_1(const std::vector<int> &, const std::vector<int> &);
// во второй функции я не использую алгоритм std::find
int same_elements_2(const std::vector<int> &, const std::vector<int> &);
// тест для функций
void testing();
int main() {
testing();
}
// функция по сравнению которая использует функции стандартной библиотеки намного удобней, чем та которую я написал сам, к тому же лучше не переизобретать колесо когда уже оно изобретено
int same_elements_1(const std::vector<int> &a, const std::vector<int> &b) {
int elems {}; //количество общих элементов
for(int i = 0; i < a.size(); ++i) {
if(std::find(b.begin(), b.end(), a.at(i)) != b.end())
++elems;
}
return elems;
}
// функция по сравнению которая использует мой алгоритм, это простой алгоритм по поиску элемента a в массиве b, время нужное для функции O(n).
int same_elements_2(const std::vector<int> &a, const std::vector<int> &b) {
int elems {}; //количество общих элементов
for(int i = 0; i < a.size(); ++i) {
for(int j = 0; j < b.size(); ++j) {
if(a.at(i) == b.at(j)) {
++elems;
break; //выйти из лупа, если элемент найден
}
}
}
return elems;
}
void testing() {
/* 1. Тест функций с преодопределенными числами */
std::vector<int> a {0};
std::vector<int> b {0, 1};
std::vector<int> c {0, 1, 2};
std::cout << "Количество общих элементов a & b: " << same_elements_1(a, b) << std::endl;
std::cout << "Количество общих элементов b & c: " << same_elements_1(b, c) << std::endl;
std::cout << "Количество общих элементов a & b: " << same_elements_2(a, b) << std::endl;
std::cout << "Количество общих элементов a & c: " << same_elements_2(a, c) << std::endl;
/* 2. Тест функций со случайными числами (100 элементов) */
std::vector<int> random_1;
std::vector<int> random_2;
(random_1.reserve(1000), random_2.reserve(1000));
std::mt19937::result_type seed = time(0);
auto generator_1000 = std::bind(std::uniform_int_distribution<int>(1, 1000), std::mt19937(seed));
int number {};
for(int i = 0; i < 100; ) {
if(i > 0) {
number = generator_1000();
//чтобы случайные числа не повторялись в массиве
if((std::find(random_1.begin(), random_1.end(), number)) != random_1.end())
continue;
}
random_1.push_back(number);
++i;
}
for(int i = 0; i < 100; ) {
if(i > 0) {
number = generator_1000();
//чтобы случайные числа не повторялись в массиве
if((std::find(random_2.begin(), random_2.end(), number)) != random_2.end())
continue;
}
random_2.push_back(number);
++i;
}
std::cout << "Количество общих элементов random_1 & random_2: " << same_elements_1(random_1, random_2) << std::endl;
std::cout << "Количество общих элементов random_1 & random_2: " << same_elements_2(random_1, random_2) << std::endl;
(random_1.clear(), random_2.clear());
/* 3. Тест функций со случайными числами (1000 элементов) */
auto generator_10000 = std::bind(std::uniform_int_distribution<int>(1, 10000), std::mt19937(seed));
for(int i = 0; i < 1000; ) {
if(i > 0) {
number = generator_10000();
//чтобы случайные числа не повторялись в массиве
if((std::find(random_1.begin(), random_1.end(), number)) != random_1.end())
continue;
}
random_1.push_back(number);
++i;
}
for(int i = 0; i < 1000; ) {
if(i > 0) {
number = generator_10000();
//чтобы случайные числа не повторялись в массиве
if((std::find(random_2.begin(), random_2.end(), number)) != random_2.end())
continue;
}
random_2.push_back(number);
++i;
}
std::cout << "Количество общих элементов random_1 & random_2: " << same_elements_1(random_1, random_2) << std::endl;
std::cout << "Количество общих элементов random_1 & random_2: " << same_elements_2(random_1, random_2) << std::endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment