Введение
В этом лабораторном задании мы создадим программу на C++, которая будет искать минимальный элемент в отсортированном векторе, который может быть повернут вокруг некоторого элемента-осевого, заранее неизвестного вам.
Подключить необходимые библиотеки и объявить пространство имен
Сначала нам нужно подключить необходимые библиотеки и объявить пространство имен. Этот код будет написан в файле ~/project/main.cpp. Полный код для шага 1 приведен ниже:
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
Создать функцию для нахождения минимального элемента
Мы создадим функцию под названием findMin, чтобы найти минимальный элемент в отсортированном векторе, который был повернут. В этой функции мы будем перебирать каждый элемент вектора и проверять, является ли этот элемент минимальным. Логика проверки того, является ли элемент минимальным, объясняется в комментариях в кодовом блоке. Полный код для шага 2 приведен ниже:
int findMin(vector<int> &m)
{
int i;
int n = m.size();
for (i = 0; i < n; i++)
{
if (i == 0)
{
// проверить первый элемент
if (m[i] < m[n - 1] && m[i] < m[1])
break;
}
else
{
// проверить все остальные элементы
if (m[i] < m[i - 1] && m[i] < m[(i + 1) % n])
break;
}
}
return m[i % n];
}
Написать главную функцию для тестирования кода
В главной функции мы создадим вектор под названием v и инициализируем его некоторыми элементами. Затем мы вызовем функцию findMin, чтобы найти минимальный элемент в векторе. Наконец, мы выведем минимальный элемент. Полный код для шага 3 приведен ниже:
int main()
{
vector<int> v = {4, 5, 6, 7, 1, 3, 2};
int n = v.size();
int minimum = 0;
cout << "The elements of the given vector are: ";
for (int i = 0; i < n; i++)
{
cout << v[i] << " ";
}
minimum = findMin(v);
cout << "\n\nThe Minimum element in the given vector is: " << minimum << endl;
return 0;
}
Компилировать и запускать код
В окне терминала перейдите в директорию, в которой находится файл main.cpp, с помощью команды cd. Затем скомпилируйте код с помощью следующей команды:
g++ main.cpp -o main
Если ошибок нет, запустите исполняемый файл с помощью следующей команды:
./main
Вы должны увидеть вывод:
The elements of the given vector are: 4 5 6 7 1 3 2
The Minimum element in the given vector is: 1
Этот вывод подтверждает, что наша программа нашла правильный минимальный элемент в векторе.
Резюме
В этом практическом занятии мы создали программу на C++, которая находит минимальный элемент в отсортированном векторе, который был повернут. Мы добились этого, перебирая каждый элемент в векторе и проверяя, является ли этот элемент минимальным. Наконец, мы вывели минимальный элемент в консоль. Надеемся, что это практическое занятие поможет вам в изучении программирования.
