VPF::Определить максимальный элемент массива

BftS

Дата 25.11.2009, 19:09 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 2.10.2009

Репутация: нет
Всего: нет

Как можно определить позицию максимального элемента массива?
Элементы - целые числа, могут быть отрицательными.

Код


int getMaxElement(int M[], int N)
{
    int maxid=0;
    for(int i=0 ; i<N; i++)
    {
        if(M[i]>=M[maxid])maxid=i;
    }
    return maxid;
}

Как бы все просто. Но.
Если до этого максимально знаечение определялось, мы должны выбрать следующее за ним наибольшее значение
Т.е. если массив 0,1,2 , то в первый раз мы получаем 2, потом 1, а потом 0.
По идеи все тоже легко, просто добавить в if условие M[i]<LAST_MAX
Но, как мы получим изначально LAST_MAX. Оно должно быть необычайно огромным, что бы не обрезать ни один элемент.

Вроде звучить легко, но добиться от себя решения не могу...

mes

Дата 25.11.2009, 19:40 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(BftS @ 25.11.2009, 18:09

)

Но, как мы получим изначально LAST_MAX. Оно должно быть необычайно огромным, что бы не обрезать ни один элемент.

гораздо проще - берите значение первого (с индексом 0) элемента...

Только не забывайте перед началом проверить что массив не пустой, ну и придумать как вести себя в противной ситуации. smile

Это сообщение отредактировал(а) mes - 25.11.2009, 19:47

--------------------

http://opendots.net

Abyx

Дата 25.11.2009, 19:41 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 601
Регистрация: 3.11.2009

Репутация: 1
Всего: 10

Код


int getMaxElement(int M[], int N)
{
    int maxid=0;
    int max=INT_MIN;
    for(int i=0 ; i<N; ++i)
        if(M[i]>max)
        {
             maxid=i;
             max=M[i];
        }
    return maxid;
}

BftS

Дата 25.11.2009, 19:51 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 2.10.2009

Репутация: нет
Всего: нет

Цитата(mes @ 25.11.2009, 19:40)

Цитата(BftS @ 25.11.2009, 18:09

)

Но, как мы получим изначально LAST_MAX. Оно должно быть необычайно огромным, что бы не обрезать ни один элемент.

А что будет, если первый элемент больше третьего ? ))

Abyx

Дата 25.11.2009, 19:52 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 601
Регистрация: 3.11.2009

Репутация: 1
Всего: 10

BftS, тогда он максимальный %)

powerfox

Дата 25.11.2009, 19:55 (ссылка)

(голосов:1)

Загрузка ...

I wanna fork()

Профиль
Группа: Комодератор
Сообщений: 3990
Регистрация: 1.10.2005
Где: Санкт-Петербург

Репутация: 2
Всего: 97

Цитата(Abyx @ 25.11.2009, 20:41

)

int max=INT_MIN;

Зачем лишняя переменная, если индекс и так сохраняем?

--------------------

Abyx

Дата 25.11.2009, 19:58 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 601
Регистрация: 3.11.2009

Репутация: 1
Всего: 10

powerfox, так оптимальнее.

Добавлено через 7 минут и 1 секунду
вообще, надо наверное написать как-то так

Код


int getMaxElement(int M[], int N)
{
    if( N==0 )
        return -1;

    int* pmax=M;
    int max=*pmax;
    for(int* it=M+1, e=M+N ; it<e; ++it)
        if( *it>max )
        {
             max=*it;
             pmax=it;
        }

    return pmax-M;
}

Добавлено через 11 минут и 37 секунд

Цитата(powerfox @ 25.11.2009, 19:55

)

лишняя переменная

лишняя - в смысле объема исходного кода?

mes

Дата 25.11.2009, 20:12 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(Abyx @ 25.11.2009, 18:58

)

лишняя - в смысле объема исходного кода?

нет.. в смысле ухудшения читабельности и нагружения логики..

Добавлено @ 20:15

Цитата(Abyx @ 25.11.2009, 18:58

)

вообще, надо наверное написать как-то так

имхо, тогда надо довести идею с "итераторами" до конца :

Код



int * max_in_range (int * begin, int * end)
{
     int * max = begin;
     for (int *p=begin; p != end; ++p)
            if (*p > *max) max = p;

     return max;
}

Это сообщение отредактировал(а) mes - 25.11.2009, 20:17

--------------------

http://opendots.net

unicuum

Дата 27.11.2009, 12:06 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 830
Регистрация: 16.3.2005
Где: Рашка

Репутация: 1
Всего: 8

Монстр какой-то получается smile

да здравствует китайский код:

Код


#include <iostream>

using namespace std;

// Получить индекс с наибольшим значением
int getIndexMax(const int* const array, const unsigned int& size)
{
    unsigned int maxIndex;
    unsigned int index = 0;
    if (size > 0) maxIndex = index;
    else return -1;
    for(index = 1; index < size; index++)
        if (array[maxIndex] < array[index])
            maxIndex = index;
    return maxIndex;
}

void writeIndex(const int* const array, const unsigned int& size)
{
    cout << size << endl;
    cout << "Индекс с наибольшим значением: " << getIndexMax(array, size) << endl;
}

int main()
{
    int array0[] = {};
    int array1[] = {3};
    int array2[] = {7, 23};
    int array3[] = {15, 30, 70, 91};

    writeIndex(array0, sizeof(array0) / sizeof(int));
    writeIndex(array1, sizeof(array1) / sizeof(int));
    writeIndex(array2, sizeof(array2) / sizeof(int));
    writeIndex(array3, sizeof(array3) / sizeof(int));

    return 0;
}

Вывод:

Код


0
Индекс с наибольшим значением: -1
1
Индекс с наибольшим значением: 0
2
Индекс с наибольшим значением: 1
4
Индекс с наибольшим значением: 3

--------------------

обычный день на винграде

Earnest

Дата 27.11.2009, 18:55 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 53
Всего: 183

Если нужно последовательно получать максимальные значения, еще не использовавшиеся, то не проще ли один раз отсортировать массив? Или отсортировать индексы, если трогать сам массив нельзя. Общая производительность будет выше (т.к. вместо последовательный линийных поисков мы можем один раз сделать квик-сорт и свести дело к N log N)? да и как-то элегантне это...

Добавлено через 1 минуту и 58 секунд
Кроме того, если нужно получить не весь ряд "максимальных" значений, а только какую-то часть, можно ипользовать partial_sort.

--------------------

...

unicuum

Дата 28.11.2009, 00:00 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 830
Регистрация: 16.3.2005
Где: Рашка

Репутация: 1
Всего: 8

Цитата(Earnest @ 27.11.2009, 18:55

)

Для задачи автора топика так и надо делать. То есть задача сначала сформулирована в получении одного наибольшего элемента. Но внизу есть пояснение, что на самом деле надо получать индексы массива в порядке убывания значений на которые они ссылаются.

--------------------

обычный день на винграде

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »