ТОП-15 алгоритмических задач, реализованных на C++

6
43406
Добавить в избранное

В статье собрано 15 базовых алгоритмических задач, которые должен уметь решать каждый программист. Прилагаем реализацию на C++.

алгоритмических задач

Решение алгоритмических задач с использованием различных сортировок

1. Сортировка пузырьком

Определите, сколько обменов сделает алгоритм пузырьковой сортировки по возрастанию для данного массива.

Формат входных данных:

На первой строке дано целое число n (1 ≤ n ≤ 1000) – количество элементов в массиве. На второй строке – сам массив. Гарантируется, что все элементы массива – различные целые числа, не превышающие по модулю 10^9.

Формат выходных данных:

Выведите одно число – количество обменов пузырьковой сортировки.

Примеры:

Входные данные Выходные данные
3
1 2 3
0
2
2 1
1
4
4 1 5 3
3

Реализация:

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

Реализация:

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

Реализация:

4. Разброс

Дано N целых чисел, которые требуется отсортировать в порядке неубывания. Среди чисел не будет двух, различных больше чем на 10^7. В задаче необходимо использовать сортировку подсчётом.

Формат входных данных:

Первая строка входных данных содержит целое число N (1 ≤ N ≤ 100000), вторая строка – N целых чисел, не превышающих по модулю 2⋅10^9. Никакие два не различаются более, чем на 10^7.

Формат выходных данных:

Выведите данные числа в порядке неубывания.

Примеры:

Входные данные Выходные данные
1
863961129
863961129
2
1559168841 1559168839
1559168839 1559168841

Реализация:

5. Быстрая сортировка

Отсортируйте заданный массив с помощью быстрой сортировки.

Формат входных данных:

Первая строка входных данных содержит одно натуральное число nn (1 ≤ n ≤ 10^5) – количество элементов в массиве. В следующей строке находятся элементы массива – n целых чисел, не превосходящих по абсолютной величине 10^9.

Формат выходных данных:

Выведите элементы массива в порядке неубывания.

Примеры:

Входные данные Выходные данные
3
2 1 3
1 2 3

Реализация:

Решение алгоритмических задач с использованием бинарного поиска

6. Корень числа

Дано действительное число a и натуральное n. Вычислите корень n-й степени из числа a, используя вещественный бинарный поиск.

Формат входных данных:

С клавиатуры через пробел вводится два числа:
1. a – действительное, неотрицательное, не превосходит 1000, задано с точностью до 6 знаков после десятичной точки;
2. n – натуральное, не превосходящее 10.

Формат выходных данных:

Требуется вывести число с точностью не менее 6 знаков после запятой.

Примеры:

Входные данные Выходные данные
2
2
1.41421356237

Реализация:

7. Квадратный корень и квадратный квадрат

Найдите такое число x, что x^2 + sqrt(x) = C, с точностью не менее 6 знаков после точки.

Формат входных данных:

В единственной строке содержится вещественное число C (1 ≤ C ≤ 10^10).

Формат выходных данных:

Выведите одно число — искомый x.

Примеры:

Входные данные Выходные данные
2.0000000000 1.000000000
18.0000000000 4.000000000

Реализация:

Решение алгоритмических задач на графы

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

Реализация:

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

Реализация:

 

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

Реализация:

 

11. Степени вершин

Неориентированный граф задан матрицей смежности. Найдите степени всех вершин графа.

Формат входных данных:

Сначала вводится число nn (1≤n≤100) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Формат выходных данных:

Выведите n чисел – степени вершин графа.

Примеры:

Входные данные Выходные данные
3
0 1 0
1 0 1
0 1 0
1 2 1

Реализация:

Решение алгоритмических задач на графы с использованием поиска в глубину

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

Реализация:

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

Реализация:

 

Решение алгоритмических задач на нахождение путей в графе

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

Реализация:

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

Реализация:

Заключение

Надеемся, что людям, начинающим изучать алгоритмы, пригодится этот материал. Ведь умение находить решение алгоритмических задач – навык, которым обязан обладать программист, претендующий на хорошую должность.

Статьи по теме:

Интересуетесь программированием на C++?

Подпишитесь на нашу рассылку, чтобы получать больше интересных материалов:

И не беспокойтесь, мы тоже не любим спам. Отписаться можно в любое время.




Комментариев: 6

  1. Мне кажется, надо как-то расширить задание про петли, как-то лучше обьяснить, что автор имеет в виду, предоставляя такое решение. Скорее всего тут имеется в виду совершенно частная задача, где петлей считается связь двух вершин в обе стороны двумя ребрами или вершина, инцидентная сама себе через одно ребро

    1. ребро, инцидентное одной и той же вершине*

  2. Не очень понял решение про петли в графе. По-моему, согласно определению петли в графе, нужно проверить только ребра, замыкающие одну и ту же вершину, другими словами проверить диагональ матрицы смежности на содержание единиц

  3. Решение задачи на проверку является ли граф дереыом дурацкое. У нас нет никакой необходимости проверять циклы в нем, граф является деревом если в нем n-1 ребро и он связный, а это проверяется в разы легче чем приведенный код

Добавить комментарий