On-line: гостей 0. Всего: 0 [подробнее..]
Программисты всех стран, объединяйтесь!

АвторСообщение



ссылка на сообщение  Отправлено: 11.05.18 17:12. Заголовок: Получить индексы двух наибольших элементов последовательности.


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

Вот еще один пример с сайте Stackoverflow, демонстрирующий правоту мною сказанного: Get index of two biggest values

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

Опять-таки, ответы к указанному вопросу на Stackoverflow, не выдерживают критики.

Я хотел бы заметить, что сайт Stackoverflow в настоящее время деградирует Например, из-за открытой русофобии модераторов на этом сайте, я на год заблокирован, указав в комментарии, что автору неверного ответа следует обратиться к описании стандарта C, в котором ясно указано, почему его ответ неверен. Этого было достаточно, чтобы меня заблокировать, так как англо-язычный автор неверного ответа на меня обиделся, посчитав оскорбительным, что я отослал его к стандарту C.

Но, вернемся к исходному вопросы.

В ответе, который был выбран в качестве лучшего, предлагается создать вспомогательный вектор std::vector, заполненный из пар значений элементов исходного массива и, соответственно, их индексов, а затем этот вектор отсортировать.

Очевидно, что такой подход совершенно не эффективный, так как он потребляет дополнительную память, которая в общем случае может иметь большой объем,и к тому же тратится время на саму сортировку.

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

Вот код, который представлен в "лучшем" ответе, автором которого является некий Zeyad Etman.

#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;
}



Решение чрезмерно усложнено. Для определения двух максимальных элементов массива требуется создавать объект шаблона std::vector и сортировать его.

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

Очевидно, что, принимая во внимание, что исходной последовательностью может быть любая последовательность, обладающая последовательными итераторами, то следует написать шаблонную функцию, которая на вход будет получать два итератора и возвращать на выходе пару индексов. Альтернативой могла быть функция с теми же входными параметрами, но возвращающая пару итераторов, соответствующих двум максимальным элементам последовательности. Но в этом случае пользователю пришлось бы самому вычислять индексы, используя стандартную функцию std::distance, что не всегда является эффективным в случае, если последовательность не имеет итераторов произвольного доступа.

Вот реализация требуемой функции, показанная в демонстрационной программе.

 
#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;
}


Вывод программы на консоль:

 
The first max is 30 at position 3
And the second max is 10 at position 0


Спасибо: 0 
ПрофильЦитата Ответить
Новых ответов нет


Ответ:
1 2 3 4 5 6 7 8 9
большой шрифт малый шрифт надстрочный подстрочный заголовок большой заголовок видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки моноширинный шрифт моноширинный шрифт горизонтальная линия отступ точка LI бегущая строка оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 11
Права: смайлы да, картинки да, шрифты да, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет