Одновременное минимальное и максимальное
Я попытался реализовать алгоритм, который будет искать как минимальные, так и максимальные элементы в данном массиве, и использовал идеи Кормена Введение в алгоритмы. Мой код компилируется и начинает работать, выводит сгенерированный случайный массив и затем ничего не делает в течение очень долгого времени.
Почему это может быть?
Код такой:
// fast min and max --cormen exercise 1.cpp: entry point
//implemented from a verbal description in cormen's book, p 243
#include "stdafx.h"#include <vector>
#include <ctime>
#include <cstdlib>
#include <iostream>
struct min_and_max
{
int min, max;
};min_and_max find_min_and_max(std::vector<int>& A)
{
int n = A.size();
int min, max;
if (n%2 == 1)
min = max = A[0];
if (n%2 == 0)
if (A[0] < A[1])
{
min = A[0];
max = A[1];
}
else
{
min = A[1];
max = A[0];
}
for(int i = 2; i < A.size(); (i + 2))
{
if (A[i] < A[i+1])
{
if (min > A[i])
min = A[i];
if (max < A[i+1])
max = A[i+1];
}
else
{
if (min > A[i+1])
min = A[i+1];
if (max < A[i])
max = A[i];
}
}
min_and_max result;
result.min = min;
result.max = max;
return result;
}
int main()
{
std::srand(std::time(0));
std::vector<int> A(10);
for (auto i = 0; i < A.size(); i++)
{
A[i] = rand() % 1000;
std::cout << A[i] << " ";
}
std::cout << std::endl; //IT GOES AS FAR AS THIS
std::cout << "The array has been analyzed; its' minimum is " << find_min_and_max(A).min << "and its' maximum is " << find_min_and_max(A).max << std::endl;
return 0;
}
Решение
for(int i = 2; i < A.size(); (i + 2))
i + 2 не изменит значение iнужно использовать i += 2,
Другие решения
Проблема заключается здесь:
for(int i = 2; i < A.size(); (i + 2))
Вы никогда не увеличиваете i, таким образом вызывая бесконечный цикл.
измените это на:
for(int i = 2; i < A.size(); i+=2)
В дополнение к данным ответам, если вы используете c ++ 11, вы можете упростить свой алгоритм, используя лямбды и std::for_each функция:
#include <algorithm>
#include <iostream>
#include <cmath>
int main() {
int array[] = { -8, 8, 0, 9, 5, -3, 4, 6, -1, 15, 31 };
int min, max;
// User std::for_each(v.begin(), v.end(), ...) for either vector or list
std::for_each(std::begin(array), std::end(array), [&min, &max](int elem) {
max = std::max(max, elem);
min = std::min(min, elem);
});
std::cout << min << ", " << max << std::endl;
return 0;
}
А может быть, это может быть еще проще
Обновить: Как @Blastfurnace указал, что std::minmax_element Функция может быть использована для дальнейшего сокращения кода, необходимого для поиска как минимального, так и максимального элемента, что приводит к сокращенной версии:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values = { -8, 8, 0, 9, 5, -3, 4, 6, -1, 15, 31 };
auto minAndMax = std::minmax_element(values.begin(), values.end());
std::cout << *minAndMax.first << ", " << *minAndMax.second << std::endl;
return 0;
}
Важно отметить, что все, что сделано в этом ответе, кроме того, что оно является ОТ, предназначено для обучения, чтобы дать альтернативы ОП, чтобы улучшить его (или ее) работу и помочь другим пользователям, которые могут иметь такое же требование.
В любом случае алгоритм неверен, потому что вектор может иметь размер, равный 0. В этом случае 1) вы пытаетесь получить доступ к элементам, которые не существуют, и 2) вы возвращаете неопределенные значения из функции. Более правильный подход — вернуть индексы минимального и максимального элементов, а в случае, если вектор пуст, вернуть пару A.size ().