Last active
May 9, 2019 22:33
-
-
Save bejaneps/9005111e94062c0ebaa47140adf809da to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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