ТОП-15 алгоритмических задач, реализованных на C++
В статье собрано 15 базовых алгоритмических задач, которые должен уметь решать каждый программист. Прилагаем реализацию на C++.
Если хочешь подтянуть свои знания, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:
- углубишься в решение практических задач;
- узнаешь все про сложные алгоритмы, сортировки, сжатие данных и многое другое.
Ты также будешь на связи с преподавателем и другими студентами.
В итоге будешь браться за сложные проекты и повысишь чек за свою работу 🙂
Решение алгоритмических задач с использованием различных сортировок
1. Сортировка пузырьком
Определите, сколько обменов сделает алгоритм пузырьковой сортировки по возрастанию для данного массива.
Формат входных данных:
На первой строке дано целое число n (1 ≤ n ≤ 1000) – количество элементов в массиве. На второй строке – сам массив. Гарантируется, что все элементы массива – различные целые числа, не превышающие по модулю 10^9.
Формат выходных данных:
Выведите одно число – количество обменов пузырьковой сортировки.
Примеры:
| Входные данные | Выходные данные |
| 3 1 2 3 |
0 |
| 2 2 1 |
1 |
| 4 4 1 5 3 |
3 |
Реализация:
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_SIZE = 1000;
void input(int *a, int size) {
for(int i = 0; i < size; ++i) {
cin >> a[i]; // ввод массива
}
}
void bubbleSort(int *array, int size) {
int swap_counter = 0;
for(int i = 1; i < size; ++i) {
for(int j = 1; j <= size - i; ++j) {
if(array[j - 1] > array[j]) {
swap(array[j - 1], array[j]);
swap_counter++;
}
}
}
cout << swap_counter;
}
int main() {
int mainArray[MAX_SIZE], size;
cin >> size;
input(mainArray, size);
bubbleSort(mainArray, size);
return 0;
}
2. Результаты олимпиады
Во время проведения олимпиады каждый из участников получил свой идентификационный номер. Необходимо отсортировать список участников олимпиады по количеству набранных ими баллов.
Формат входных данных:
На первой строке дано число n (1 ≤ n ≤ 1000) – количество участников. На каждой следующей строке даны идентификационный номер и набранное число баллов соответствующего участника. Все числа во входном файле целые и не превышают 10^5.
Формат выходных данных:
Выведите исходный список в порядке убывания баллов. Если у некоторых участников одинаковые баллы, то их нужно отсортировать в порядке возрастания идентификационного номера.
Примеры:
| Входные данные | Выходные данные |
| 3 101 80 305 90 200 14 |
305 90 101 80 200 14 |
| 3 20 80 30 90 25 90 |
25 90 30 90 20 80 |
Реализация:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct res {
int number;
int mark;
};
bool cmp(res a, res b) {
if(a.mark == b.mark) return a.number < b.number;
return a.mark > b.mark;
}
int main() {
int amount;
cin >> amount;
vector <res> table(amount);
for (int i = 0; i < amount; i++) {
int temp;
int s_temp;
cin >> temp >> s_temp;
res struct_temp;
struct_temp.number = temp;
struct_temp.mark = s_temp;
table[i] = struct_temp;
}
sort(table.begin(), table.end(), cmp);
for (auto now : table) { // выводим таблицу
cout << now.number << " " << now.mark << endl;
}
return 0;
}
3. Библиотечный метод
Продемонстрируйте работу метода сортировки вставками по возрастанию. Для этого выведите состояние данного массива после каждой вставки на отдельных строках. Если массив упорядочен изначально, не нужно ничего выводить.
Формат входных данных:
На первой строке дано целое число n (1 ≤ n ≤ 100) – количество элементов в массиве. На второй строке задан сам массив: последовательность натуральных чисел, не превышающих 10^9.
Формат выходных данных:
В выходной файл выведите строки (по количеству вставок) по n чисел каждая.
Примеры:
| Входные данные | Выходные данные |
| 2 2 1 |
1 2 |
| 4 2 1 5 3 |
1 2 5 3 1 2 3 5 |
Реализация:
#include <iostream>
#include <algorithm>
const int MAIN_SIZE = 100;
void input(int *array, int size) {
for(int i = 0; i < size; ++i) {
std::cin >> array[i];
}
}
void output(int *array, int size) {
for(int i = 0; i < size; ++i) {
std::cout << array[i] << " ";
}
std::cout << "\n";
}
bool checker(int *array, int size) {
for(int i = 0; i < size - 1; ++i) {
if(array[i] > array[i + 1]) {
return false;
}
}
return true;
}
void insertionSort(int *array, int size) {
for(int i = 1; i < size; ++i) {
int j = i;
if(j && array[j] < array[j - 1]) {
while(j && array[j] < array[j - 1]) {
std::swap(array[j], array[j - 1]);
--j;
}
output(array, size);
}
}
}
int main(){
int mainArray[MAIN_SIZE], size;
std::cin >> size;
input(mainArray, size);
if(!checker(mainArray, size)) {
insertionSort(mainArray, size);
}
return 0;
}
4. Разброс
Дано N целых чисел, которые требуется отсортировать в порядке неубывания. Среди чисел не будет двух, различных больше чем на 10^7. В задаче необходимо использовать сортировку подсчётом.
Формат входных данных:
Первая строка входных данных содержит целое число N (1 ≤ N ≤ 100000), вторая строка – N целых чисел, не превышающих по модулю 2⋅10^9. Никакие два не различаются более, чем на 10^7.
Формат выходных данных:
Выведите данные числа в порядке неубывания.
Примеры:
| Входные данные | Выходные данные |
| 1 863961129 |
863961129 |
| 2 1559168841 1559168839 |
1559168839 1559168841 |
Реализация:
#include <iostream>
const int ARRAY_SIZE = 100000;
const long long int MIN = -9223372036854775807;
const long long int MAX = 9223372036854775807;
void input(long long int *a, long long int size) {
for(int i = 0; i < size; ++i){
std::cin >> a[i];
}
}
void output(long long int *a, long long int size) {
for(int i = 0; i < size; ++i){
std::cout << a[i] << " ";
}
}
long long int maxFinder(long long int *a, long long int size) {
long long int max = MIN;
for(int i = 0; i < size; ++i){
if(a[i] > max){
max = a[i];
}
}
return max;
}
long long int minFinder(long long int *a, long long int size) {
long long int min = MAX;
for(int i = 0; i < size; ++i){
if(a[i] < min){
min = a[i];
}
}
return min;
}
void zeroFill(long long int *zero, long long int size) {
for(int i = 0; i < size; ++i){
zero[i] = 0;
}
}
void counting_sort(long long int* vec, long long int len, long long int min, long long int max) {
int *cnt = new int[max - min + 1];
for (int i = min; i <= max; ++i) {
cnt[i - min] = 0;
}
for (int i = 0; i < len; ++i) {
++cnt[vec[i] - min];
}
for (int i = min; i <= max; ++i) {
for(int j = cnt[i - min]; j--;) {
*vec++ = i;
}
}
delete [] cnt;
}
int main(){
long long int mainArray[ARRAY_SIZE], zero[ARRAY_SIZE], size;
std::cin >> size;
input(mainArray, size);
zeroFill(zero, size);
long long int max = maxFinder(mainArray, size);
long long int min = minFinder(mainArray, size);
counting_sort(mainArray, size, min, max);
output(mainArray, size);
return 0;
}
5. Быстрая сортировка
Отсортируйте заданный массив с помощью быстрой сортировки.
Формат входных данных:
Первая строка входных данных содержит одно натуральное число nn (1 ≤ n ≤ 10^5) – количество элементов в массиве. В следующей строке находятся элементы массива – n целых чисел, не превосходящих по абсолютной величине 10^9.
Формат выходных данных:
Выведите элементы массива в порядке неубывания.
Примеры:
| Входные данные | Выходные данные |
| 3 2 1 3 |
1 2 3 |
Реализация:
#include <iostream>
#include <algorithm>
const int SIZE = 100000;
void input(int *a, int size) {
for(int i = 0; i < size; ++i) {
std::cin >> a[i];
}
}
void output(int *a, int size) {
for(int i = 0; i < size; ++i) {
std::cout << a[i] << " ";
}
}
void quickSort(int *tempArray, int first, int last) {
int middle;
middle = tempArray[(first + last) / 2];
int f = first, l = last;
while (f < l) {
while (tempArray[f] < middle) f++;
while (tempArray[l] > middle) l--;
if (f <= l) {
std::swap(tempArray[f], tempArray[l]);
f++;
l--;
}
}
if (first < l) quickSort(tempArray, first, l);
if (f < last) quickSort(tempArray, f, last);
}
int main(){
int size, mainArray[SIZE];
std::cin >> size;
input(mainArray, size);
quickSort(mainArray, 0, size - 1);
output(mainArray, size);
return 0;
}
Решение алгоритмических задач с использованием бинарного поиска
6. Корень числа
Дано действительное число a и натуральное n. Вычислите корень n-й степени из числа a, используя вещественный бинарный поиск.
Формат входных данных:
С клавиатуры через пробел вводится два числа:
1. a – действительное, неотрицательное, не превосходит 1000, задано с точностью до 6 знаков после десятичной точки;
2. n – натуральное, не превосходящее 10.
Формат выходных данных:
Требуется вывести число с точностью не менее 6 знаков после запятой.
Примеры:
| Входные данные | Выходные данные |
| 2 2 |
1.41421356237 |
Реализация:
#include <iostream>
#include <cmath>
#include <iomanip>
long double firBinSearch(double a, int n, double R) {
double L = 0;
while (R - L > 1e-10) {
double M = (L + R) / 2;
if (pow(M, n) < a) {
L = M;
}
else {
R = M;
}
}
return R;
}
int main() {
int n;
double a;
std::cin >> a >> n;
if(a >= 1) {
double result = firBinSearch(a, n, a);
std::cout << std::fixed << std::setprecision(6) << res;
}
else {
if(a < 1) {
double result = secBinSearch(a, n, 1);
std::cout << std::fixed << std::setprecision(6) << res;
}
}
return 0;
}
7. Квадратный корень и квадратный квадрат
Найдите такое число x, что x^2 + sqrt(x) = C, с точностью не менее 6 знаков после точки.
Формат входных данных:
В единственной строке содержится вещественное число C (1 ≤ C ≤ 10^10).
Формат выходных данных:
Выведите одно число — искомый x.
Примеры:
| Входные данные | Выходные данные |
| 2.0000000000 | 1.000000000 |
| 18.0000000000 | 4.000000000 |
Реализация:
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
long double check(long double x) {
return pow(x, 2) + sqrt(x);
}
long double binSearch(double c) {
double R = 1e10, L = 0, M;
while(fabs(R - L) > 1e-10) {
M = (L + R) / 2;
if(check(M) - c < 0) {
L = M;
}
else {
R = M;
}
}
return R;
}
int main() {
double c;
cin >> c;
double result = binSearch(c);
cout << fixed << setprecision(6) << result;
return 0;
}
Решение алгоритмических задач на графы
8. Петли
По заданной матрице смежности неориентированного графа определите, содержит ли он петли.
Формат входных данных:
На вход программы поступает число n (1 ≤ n ≤ 100) – количество вершин графа, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.
Формат выходных данных:
Выведите «YES», если граф содержит петли, и «NO» в противном случае.
Примеры:
| Входные данные | Выходные данные |
| 3 0 1 1 1 0 1 1 1 0 |
NO |
| 3 0 1 0 1 1 1 0 1 0 |
YES |
Реализация:
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_SIZE = 100;
bool check(int arr[][MAX_SIZE], int size)
{
for(int i = 0; i < size; ++i)
{
for(int j = 0; j < size; ++j)
{
if(arr[i][j] == arr[j][i] && i != j)
{
continue;
}
else{
if(arr[i][j] != arr[j][i])
{
return false;
}
else
{
if(i == j)
{
if(arr[i][j] == 0 && arr[j][i] == 0)
{
continue;
}
else
{
return true;
}
}
}
}
}
}
return false;
}
int main()
{
int mainSize, matrix[MAX_SIZE][MAX_SIZE];
cin >> mainSize;
for(int i = 0; i < mainSize; ++i)
{
for(int j = 0; j < mainSize; ++j)
{
cin >> matrix[i][j];
}
}
if(check(matrix, mainSize))
{
cout << "YES";
}
else
{
cout << "NO";
}
return 0;
}
9. От матрицы смежности к списку рёбер
Простой неориентированный граф задан матрицей смежности: выведите его представление в виде списка ребер.
Формат входных данных:
Входные данные включают число nn (1 ≤ n ≤ 100) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрицу смежности.
Формат выходных данных:
Выведите список ребер заданного графа (в любом порядке).
Примеры:
| Входные данные | Выходные данные |
| 3 0 1 1 1 0 1 1 1 0 |
1 2 2 3 1 3 |
Реализация:
#include <iostream>
#include <algorithm>
using namespace std;
const int SIZE = 100;
void matrixInput(int matrix[][SIZE], int size)
{
for(int i = 0; i < size; ++i)
{
for(int j = 0; j < size; ++j)
{
cin >> matrix[i][j];
}
}
}
void matrtixOutput(int matrix[][SIZE], int size)
{
for(int i = 0; i < size; ++i)
{
for(int j = 0; j < size; ++j)
{
cout << matrix[i][j] << " ";
}
cout << "\n";
}
}
int main()
{
int mainMatrix[SIZE][SIZE], size;
cin >> size;
matrixInput(mainMatrix, size);
for(int i = 0; i < size; ++i)
{
for(int j = 0; j < size; ++j)
{
if(mainMatrix[i][j] == 1)
{
cout << i + 1 << " " << j + 1 << "\n";
mainMatrix[j][i] = 0;
}
}
}
return 0;
}
10. От списка рёбер к матрице смежности
Простой неориентированный граф задан списком ребер: выведите его представление в виде матрицы смежности.
Формат входных данных:
На вход программы поступают числа nn (1 ≤ n ≤ 100) – количество вершин в графе и m (1 ≤ m ≤ (n*(n - 1)) / 2) – количество ребер. Затем следует m пар чисел – рёбра графа.
Формат выходных данных:
Выведите матрицу смежности заданного графа.
Примеры:
| Входные данные | Выходные данные |
| 3 3 1 2 2 3 1 3 |
0 1 1 1 0 1 1 1 0 |
Реализация:
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
const int SIZE = 100;
void matrixInput(int matrix[][SIZE], int size)
{
for(int i = 0; i < size; ++i)
{
for(int j = 0; j < size; ++j)
{
cin >> matrix[i][j];
}
}
}
void matrtixOutput(int matrix[][SIZE], int size)
{
for(int i = 0; i < size; ++i)
{
for(int j = 0; j < size; ++j)
{
cout << matrix[i][j] << " ";
}
cout << "\n";
}
}
int main()
{
int mainMatrix[SIZE][SIZE], size;
cin >> size;
matrixInput(mainMatrix, size);
for(int i = 0; i < size; ++i)
{
for(int j = 0; j < size; ++j)
{
if(mainMatrix[i][j] == 1)
{
cout << i + 1 << " " << j + 1 << "\n";
mainMatrix[j][i] = 0;
}
}
}
return 0;
}
11. Степени вершин
Неориентированный граф задан матрицей смежности. Найдите степени всех вершин графа.
Формат входных данных:
Сначала вводится число nn (1≤n≤100) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.
Формат выходных данных:
Выведите n чисел – степени вершин графа.
Примеры:
| Входные данные | Выходные данные |
| 3 0 1 0 1 0 1 0 1 0 |
1 2 1 |
Реализация:
#include <iostream>
using namespace std;
const int SIZE = 100;
void matrix_input(int matrix[][SIZE], int size)
{
for(int i = 0; i < size; ++i)
{
for(int j = 0; j < size; ++j)
{
cin >> matrix[i][j];
}
}
}
void node_extend_output(int matrix[][SIZE], int size)
{
for(int i = 0; i < size; ++i)
{
int counter = 0;
for(int j = 0; j < size; ++j)
{
if(matrix[i][j] == 1)
{
counter++;
}
}
cout << counter << " ";
}
}
int main()
{
int mainMatrix[SIZE][SIZE], size;
cin >> size;
matrix_input(mainMatrix, size);
node_extend_output(mainMatrix, size);
return 0;
}
Решение алгоритмических задач на графы с использованием поиска в глубину
12. Дерево?
Дан неориентированный граф. Необходимо определить, является ли он деревом.
Формат входных данных:
В первой строке входного файла содержится одно натуральное число N (1≤N≤100) – количество вершин в графе. Далее в N строках по N чисел дана матрица смежности графа: в i-ой строке на j-ом месте стоит 1, если вершины i и j соединены ребром, и 0, если ребра между ними нет. На главной диагонали матрицы стоят нули. Матрица симметрична относительно главной диагонали.
Формат выходных данных:
Требуется вывести «YES», если граф является деревом, и «NO» иначе.
Примеры:
| Входные данные | Выходные данные |
| 6 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 |
NO |
| 3 0 1 0 1 0 1 0 1 0 |
YES |
Реализация:
#include <iostream>
#include <algorithm>
using namespace std;
const int SIZE = 100;
bool dfs(int currentPoint, int matrix[SIZE][SIZE], bool color[SIZE])
{
if (color[currentPoint])
{
return 0;
}
color[currentPoint] = true;
for (int j = 0; j < SIZE; ++j)
{
if (matrix[currentPoint][j])
{
dfs(j, matrix, color);
}
}
}
bool IsTree(int matrix[SIZE][SIZE], int size)
{
int edges = 0;
for (int i = 0; i < size; ++i)
{
for (int j = i + 1; j < size; ++j)
{
if (matrix[i][j])
{
edges++;
}
}
}
if (edges != size - 1)
{
return false;
}
bool color[SIZE];
memset(color, 0, sizeof(color));
dfs(0, matrix, color);
for (int i = 0; i < size; ++i)
{
if (!color[i])
{
return false;
}
}
return true;
}
void input(int matrix[SIZE][SIZE], int size)
{
for(int i = 0; i < size; ++i)
{
for(int j = 0; j < size; ++j)
{
cin >> matrix[i][j];
}
}
}
int main()
{
int amountOfPoints, mainMatrix[SIZE][SIZE];
cin >> amountOfPoints;
input(mainMatrix, amountOfPoints);
if(IsTree(mainMatrix, amountOfPoints))
{
cout << "YES";
}
else cout << "NO";
return 0;
}
13. Компоненты связности
Дан неориентированный граф. Необходимо посчитать количество его компонент связности в нем.
Формат входных данных:
Во входном потоке записано два числа N и M (1 ≤ N ≤ 100, 0 ≤ M ≤ 10000). В следующих M строках записаны по два числа i и j (1 ≤ i, j ≤ N), которые означают, что вершины i и j соединены ребром.
Формат выходных данных:
В единственной строке выходного потока выведите количество компонент связности.
Примеры:
| Входные данные | Выходные данные |
| 6 4 3 1 1 2 5 4 2 3 |
3 |
Реализация:
#include <iostream>
using namespace std;
const int MAX = 100;
int temp;
int col[MAX];
int matrix[MAX][MAX];
void DFS(int v) {
if (col[v]) {
return;
}
col[v] = 1;
for (int i = 0; i < temp; ++i) {
if (matrix[v][i]) DFS(i);
}
col[v] = 2;
}
int main() {
int c;
cin >> temp >> c;
for (int i = 0; i < c; ++i) {
int a, b;
cin >> a >> b;
matrix[a - 1][b - 1] = 1;
matrix[b - 1][a - 1] = 1;
}
int counter = 0;
for (int i = 0; i < temp; ++i) {
if (col[i] == 0){
counter++;
DFS(i);
}
}
cout << counter;
return 0;
}
Решение алгоритмических задач на нахождение путей в графе
14. Длина минимального пути
В неориентированном графе требуется найти длину минимального пути между двумя вершинами.
Формат входных данных:
Первым на вход поступает число N – количество вершин в графе (1≤N≤100). Затем записана матрица смежности («0» обозначает отсутствие ребра, «1» – наличие ребра). Далее задаются номера двух вершин – начальной и конечной.
Формат выходных данных:
Выведите L – длину кратчайшего пути (количество ребер, которые нужно пройти). Если пути не существует, выведите одно число «-1».
Примеры:
| Входные данные | Выходные данные |
| 5 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 3 5 |
3 |
Реализация:
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int SIZE = 100;
int main()
{
int size;
int start, end;
cin >> size;
vector<int> from(size, -1);
vector<int> used(size, 0);
vector<int> dist(size);
int mainMatrix[SIZE][SIZE];
int way[SIZE];
int counter = 0;
for(int i = 0; i < size; ++i)
{
for(int j = 0; j < size; ++j)
{
cin >> mainMatrix[i][j];
}
}
cin >> start >> end;
--start; --end;
queue<int> Queue;
Queue.push(start);
dist[start] = 0;
used[start] = 1;
while (!Queue.empty())
{
int hold = Queue.front();
Queue.pop();
for (int i = 0; i < size; ++i)
{
if (mainMatrix[hold][i] && !used[i])
{
dist[i] = dist[hold] + 1;
from[i] = hold;
Queue.push(i);
used[i] = true;
}
}
}
if (used[end])
cout << dist[end];
else
cout << -1;
return 0;
}
15. Путь в графе
В неориентированном графе требуется найти минимальный путь между двумя вершинами.
Формат входных данных:
Первым на вход поступает число N – количество вершин в графе (1≤N≤100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 – наличие ребра). Далее задаются номера двух вершин – начальной и конечной.
Формат выходных данных:
Выведите сначала L – длину кратчайшего пути (количество ребер, которые нужно пройти), а потом сам путь. Если путь имеет длину 0, то его выводить не нужно, достаточно вывести длину. Если пути между вершинами не существует, то требуется вывести одно число – «-1».
Примеры:
| Входные данные | Выходные данные |
| 5 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 3 5 |
3 3 2 1 5 |
Реализация:
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int SIZE = 100;
void matrix_input(int matrix[][SIZE], int size)
{
for(int i = 0; i < size; ++i)
{
for(int j = 0; j < size; ++j)
{
cin >> matrix[i][j];
}
}
}
int main()
{
int size;
int start, end;
cin >> size;
vector<int> from(size, -1);
vector<int> used(size, 0);
vector<int> dist(size);
int mainMatrix[SIZE][SIZE];
int way[SIZE];
int counter = 0;
matrix_input(mainMatrix, size);
cin >> start >> end;
--start; --end;
queue<int> Queue;
Queue.push(start);
dist[start] = 0;
used[start] = 1;
while (!Queue.empty())
{
int hold = Queue.front();
Queue.pop();
for (int i = 0; i < size; ++i)
{
if (mainMatrix[hold][i] && !used[i])
{
dist[i] = dist[hold] + 1;
from[i] = hold;
Queue.push(i);
used[i] = true;
}
}
}
if (used[end])
{
if(dist[end] == 0)
{
cout << dist[end] << endl;
}
else
{
cout << dist[end] << endl;
vector <int> way;
for(int i = end; i != -1; i = from[i])
{
way.push_back(i);
}
reverse (way.begin(), way.end());
for(int i = 0; i < way.size(); ++i)
{
cout << way[i] + 1 << " ";
}
}
}
else
{
cout << -1 << endl;
}
return 0;
}
Заключение
Надеемся, что людям, начинающим изучать алгоритмы, пригодится этот материал. Ведь умение находить решение алгоритмических задач – навык, которым обязан обладать программист, претендующий на хорошую должность.