459 просмотров
От 25 февраля

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

1. Бинарный поиск: найдите элемент в отсортированном массиве

Постановка: Бинарный поиск (Binary Search) - это эффективный алгоритм для поиска значения в отсортированном массиве. Принцип алгоритма очень прост. Мы всегда имеем дело с упорядоченным массивом. Это позволяет прибегать к хитрости - на каждой итерации цикла, который мы запускаем, мы вычисляем индекс среднего элемента. Этот элемент сравниваем с искомым. Если элемент из середины массива оказался меньше, чем тот, что мы ищем, значит нужный нам находится правее по массиву, ведь массив упорядочен. Соответственно, нам нужно перейти в следующую итерацию цикла, "оставляя" ей лишь правую часть массива - в ней снова будет найден средний элемент и алгоритм повторится. Если же элемент из середины массива оказался больше искомого, то мы переходим к следующей итерации, отбрасывая правую часть массива, а оставляя левую. Если же элемент совпадает с искомым, мы выходим из цикла. Дан отсортированный массив, найдите в нём искомый элемент. Решение: int binsearch_array(vector<int>& a, int val) { int l = 0, r = a.size() - 1; while (r > l) { int m = (l + r) / 2; if (a[m] < val) { l = m + 1; } else if (a[m] > val) { r = m - 1; } else { return m; } } if (a[l] == val) { return l; } else { return -1; } }

2. Бинарный поиск: найдите корень числа

Постановка: Дано действительное число a и натуральное n. Вычислите корень n-й степени из числа a, используя вещественный бинарный поиск. С клавиатуры через пробел вводится два числа: 1. a – действительное, неотрицательное, не превосходит 1000, задано с точностью до 6 знаков после десятичной точки; 2. n – натуральное, не превосходящее 10. Требуется вывести число с точностью не менее 6 знаков после запятой. Решение: #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; }

3. Бинарный поиск: квадратный корень и квадратный квадрат

Постановка: Найдите такое число x, что x^2 + sqrt(x) = C, с точностью не менее 6 знаков после точки. В единственной строке содержится вещественное число C (1 ≤ C ≤ 10^10). Выведите одно число — искомый x. Решение: #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; }

4. Реализуйте сортировку пузырьком

Постановка: Определите, сколько обменов сделает алгоритм пузырьковой сортировки по возрастанию для данного массива. На первой строке дано целое число n (1 ≤ n ≤ 1000) – количество элементов в массиве. На второй строке – сам массив. Гарантируется, что все элементы массива – различные целые числа, не превышающие по модулю 10^9. Выведите одно число – количество обменов пузырьковой сортировки. Решение: #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; }

5. Реализуйте сортировку вставками

Постановка: Продемонстрируйте работу метода сортировки вставками по возрастанию. Для этого выведите состояние данного массива после каждой вставки на отдельных строках. Если массив упорядочен изначально, не нужно ничего выводить. На первой строке дано целое число n (1 ≤ n ≤ 100) – количество элементов в массиве. На второй строке задан сам массив: последовательность натуральных чисел, не превышающих 10^9. В выходной файл выведите строки (по количеству вставок) по n чисел каждая. Решение: #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; }

6. Реализуйте сортировку подсчётом

Поддержи проект и получи доступ ко всему контенту всего за 290

7. Реализуйте алгоритм быстрой сортировки

Постановка: Отсортируйте заданный массив с помощью быстрой сортировки. Первая строка входных данных содержит одно натуральное число n (1 ≤ n ≤ 10^5) – количество элементов в массиве. В следующей строке находятся элементы массива – n целых чисел, не превосходящих по абсолютной величине 10^9. Выведите элементы массива в порядке неубывания. Решение: #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; }

8. Графы: найдите длину мин. пути между двумя вершинами

Постановка: В неориентированном графе требуется найти длину минимального пути между двумя вершинами. Первым на вход поступает число N – количество вершин в графе (1≤N≤100). Затем записана матрица смежности («0» обозначает отсутствие ребра, «1» – наличие ребра). Далее задаются номера двух вершин – начальной и конечной. Выведите L – длину кратчайшего пути (количество ребер, которые нужно пройти). Если пути не существует, выведите одно число «-1». Решение: #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; }

9. Графы: найдите минимальный путь между двумя вершинами

Поддержи проект и получи доступ ко всему контенту всего за 290

10. Графы: выведите представление графа в виде списка ребер

Поддержи проект и получи доступ ко всему контенту всего за 290

11. Графы: определите наличие петель в графе

Поддержи проект и получи доступ ко всему контенту всего за 290

12. Графы: выведите представление графа в виде матрицы смежности

Поддержи проект и получи доступ ко всему контенту всего за 290

13. Графы: найдите степени всех вершин графа

Поддержи проект и получи доступ ко всему контенту всего за 290

14. Графы: подсчитайте количество компонент связности в графе

Поддержи проект и получи доступ ко всему контенту всего за 290

15. Графы: определите, является ли граф деревом

Поддержи проект и получи доступ ко всему контенту всего за 290

16. Реализуйте сжатие строки

Поддержи проект и получи доступ ко всему контенту всего за 290

17. Подсчитайте кол-во гласных в строке

Поддержи проект и получи доступ ко всему контенту всего за 290

18. Проверьте, является ли строка палиндромом

Поддержи проект и получи доступ ко всему контенту всего за 290

19. Реализуйте проверку на анаграмму

Поддержи проект и получи доступ ко всему контенту всего за 290

20. Найдите факториал числа

Поддержи проект и получи доступ ко всему контенту всего за 290

21. Последовательность Фибоначчи

Поддержи проект и получи доступ ко всему контенту всего за 290

22. Найдите НОД с помощью алгоритма Евклида

Поддержи проект и получи доступ ко всему контенту всего за 290

23. Найдите НОК

Поддержи проект и получи доступ ко всему контенту всего за 290

24. Найдите сумму цифр числа

Поддержи проект и получи доступ ко всему контенту всего за 290

25. Определите, является ли число степенью двойки

Поддержи проект и получи доступ ко всему контенту всего за 290

26. Поменяйте переменные значениями без дополнительной

Поддержи проект и получи доступ ко всему контенту всего за 290

27. Вычислите угол падения тела

Поддержи проект и получи доступ ко всему контенту всего за 290

28. Отсортируйте результаты олимпиады

Поддержи проект и получи доступ ко всему контенту всего за 290

29. Реализуйте возведение в степень без pow()

Поддержи проект и получи доступ ко всему контенту всего за 290

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

Поддержи проект и получи доступ ко всему контенту всего за 290

31. Определите номер четверти плоскости по координатам

Поддержи проект и получи доступ ко всему контенту всего за 290

32. Преобразуйте десятичное число в шестнадцатеричное

Поддержи проект и получи доступ ко всему контенту всего за 290
Хочешь стать частью сообщества Девстанции?
Вступай в наш чат в Telegram

Также в этой категории

Шпаргалка
  26 вопросов

Шпаргалка по вопросам о C++

Вопросы для собеседования C++ разработчика

272 просмотра
От 29 января
Шпаргалка
  17 вопросов

Шпаргалка по вопросам о C

Вопросы для собеседования Си-разработчика

183 просмотра
От 30 мая 2023

Вам может быть интересно

Шпаргалка
  60 вопросов

60 вопросов про базы данных и SQL

Вопросы и ответы с собеседования по базам данных и SQL

312 просмотров
От 20 февраля
Викторина
  20 вопросов

Викторина по Django - Junior/Middle

Базовые вопросы с собеседования по Django

15 просмотров
От 2 июня 2023
Шпаргалка
  7 вопросов

Коллекция полезных команд для Docker

Большая шпаргалка по всем командам Docker

200 просмотров
От 12 октября 2023
Задачник
  43 задачи

Топ 45 алгоритмических задач по Python

Разбор решений для задач с собеседований Python-разработчиков

3295 просмотров
От 15 февраля
Шпаргалка
  11 вопросов

Теория шардинга баз данных

О распределении данных между серверами

243 просмотра
От 10 октября 2023
Викторина
  26 вопросов

Викторина по Python - Junior

Вопросы на собеседовании по Python для Junior-позиции

54 просмотра
От 30 мая 2023

Топ тредов

Gravatar for 9tokio
Tokio:
то что раньше было бесплатным теперь платное - вот это я понимаю

Последнее сообщение:
Логотип Девстанции
Девстанция:
Спасибо за поддержку проекта :) Повышение качества контента - один из важнейших приоритетов. Этому м...
3 сообщения
213 просмотров

Логотип Девстанции
Девстанция:
Поиск людей для совместной разработки IT-стартапов

Последнее сообщение:
В этом треде пока нет сообщений
0 сообщений
108 просмотров

Логотип Девстанции
Девстанция:
Какой язык программирования выбрать в качестве первого?

Последнее сообщение:
Gravatar for 2kokke
Kokke:
Python или JS - универсально. Но по уму надо бы с чего-то строгого начинать и достаточно низкоуровне...
1 сообщение
140 просмотров

Все категории