Форум » C/C++ для начинающих (C/C++ for beginners) » Получить индексы двух наибольших элементов последовательности. » Ответить
Получить индексы двух наибольших элементов последовательности.
Сыроежка: В теме с названием Рекурсивное вычисление суммы элементов массива, предшествующих заданному значению. я уже писал, что порой простые задания некоторые даже квалифицированные программисты выполняют слишком вычурно и сложно. Вот еще один пример с сайте Stackoverflow, демонстрирующий правоту мною сказанного: Get index of two biggest values В задании требуется определить индексы двух наибольших элементов последовательности. В самом задании в качестве последовательности используется массив, но в общем случае это может быть любая последовательность, например, список. Индексы могут потребоваться, к примеру, для установления связей между двумя последовательностями по индексу. Опять-таки, ответы к указанному вопросу на Stackoverflow, не выдерживают критики. Я хотел бы заметить, что сайт Stackoverflow в настоящее время деградирует Например, из-за открытой русофобии модераторов на этом сайте, я на год заблокирован, указав в комментарии, что автору неверного ответа следует обратиться к описании стандарта C, в котором ясно указано, почему его ответ неверен. Этого было достаточно, чтобы меня заблокировать, так как англо-язычный автор неверного ответа на меня обиделся, посчитав оскорбительным, что я отослал его к стандарту C. Но, вернемся к исходному вопросы. В ответе, который был выбран в качестве лучшего, предлагается создать вспомогательный вектор std::vector, заполненный из пар значений элементов исходного массива и, соответственно, их индексов, а затем этот вектор отсортировать. Очевидно, что такой подход совершенно не эффективный, так как он потребляет дополнительную память, которая в общем случае может иметь большой объем,и к тому же тратится время на саму сортировку. Более того, следует заметить, что также в общем случае исходная последовательность может быть пустой или содержать только один элемент. В этом случае необходимо иметь возможность быстро определить, что по, крайней мере, второго максимального элемента не существует. Вот код, который представлен в "лучшем" ответе, автором которого является некий Zeyad Etman. [pre2]#include <iostream> #include <vector> #include<algorithm> using namespace std; int main() { double myArray[4] = { 10, 3, -5, 30 }; vector<pair<double, double > >vec; for(int i=0;i<4;i++){ vec.push_back(make_pair(myArray,i)); } sort(vec.begin(), vec.end()); for(int i=0;i<vec.size();i++){ cout<<vec.first<<" "<<vec.second<<endl; } cout<< vec[vec.size()-1].second<< ", "<<vec[vec.size()-2].second; } [/pre2] Решение чрезмерно усложнено. Для определения двух максимальных элементов массива требуется создавать объект шаблона std::vector и сортировать его. Другие ответы вообще не заслуживают обсуждения, так как ничего конкретного относительно поставленной задачи в них нет. Очевидно, что, принимая во внимание, что исходной последовательностью может быть любая последовательность, обладающая последовательными итераторами, то следует написать шаблонную функцию, которая на вход будет получать два итератора и возвращать на выходе пару индексов. Альтернативой могла быть функция с теми же входными параметрами, но возвращающая пару итераторов, соответствующих двум максимальным элементам последовательности. Но в этом случае пользователю пришлось бы самому вычислять индексы, используя стандартную функцию std::distance, что не всегда является эффективным в случае, если последовательность не имеет итераторов произвольного доступа. Вот реализация требуемой функции, показанная в демонстрационной программе. [pre2] #include <iostream> #include <utility> template <typename ForwardIterator> std::pair<size_t, size_t> max_two_elements( ForwardIterator first, ForwardIterator last ) { std::pair<size_t, size_t> two_max_n = { 0, 0 }; std::pair<ForwardIterator, ForwardIterator> two_max_it = { first, last }; if ( first != last ) { for ( size_t i = 1; ++first != last; ++i ) { if ( *two_max_it.first < *first ) { two_max_it.second = two_max_it.first; two_max_n.second = two_max_n.first; two_max_it.first = first; two_max_n.first = i; } else if ( two_max_it.second == last || *two_max_it.second < *first ) { two_max_it.second = first; two_max_n.second = i; } } if ( two_max_it.second == last ) ++two_max_n.second; } return two_max_n; } int main() { double a[] = { 10, 3, -5, 30 }; const size_t N = sizeof( a ) / sizeof( *a ); auto p = max_two_elements( a, a + N ); std::cout << "The first max is " << a[p.first] << " at position " << p.first << std::endl; if ( p.second != N ) { std::cout << "And the second max is " << a[p.second] << " at position " << p.second << std::endl; } return 0; } [/pre2] Вывод программы на консоль: [pre2] The first max is 30 at position 3 And the second max is 10 at position 0 [/pre2]
Ответов - 0
полная версия страницы