LINUX.ORG.RU
решено Форум — Development  

[c++]Поиск минимального значение: инициализация

 


0

1

Меня тревожит, вот что:

Когда ищу минмально и максимальное значение обрабатывая данные, как инициализировать минимальное значение? Тоесть да я могу сделать проверку на первый элемент, но в while это кажется очень расточительно.

Вообщем как задать минимально возможное или максимальное значение для переменно int?

★

Последнее исправление: Trieforce (всего исправлений: 1)

Для числовых типов - numeric_limits. В общем случае, когда минимальное значение неочевидно, можно инициализировать первым элементом и перебирать со второго (лишний if останется за пределами цикла).

const86 ★★★★★
()

std::min_element

std::max_element

как инициализировать минимальное значение

Если уж хочется изобретать велосипед, то инициализировать переменную первым элементом, а итерации начинать со второго.

anonymous
()
Ответ на: комментарий от const86

Да спасибо. Странно, что не пришло мне в голову.

Trieforce ★
() автор топика

Ну в дополнение могу посоветовать заюзать unsigned, там от 0 до ~0UL. В принципе (int)((unsigned)(~0UL)>>1) может дать максимальное int...

но этот способ лучше:

инициализировать переменную первым элементом, а итерации начинать со второго.

drBatty ★★
()

Тоесть да я могу сделать проверку на первый элемент, но в while это кажется очень расточительно.

ты о чем?

int min = array[0];
for (int i = 1; i < MAX; i++)
    if (array[i] < min) min = array[i];

ЧЯДНТ?

(анонимус об этом сказал ранее)

fork_you
()
Ответ на: комментарий от Trieforce

ты ищешь минимум среди массива значений постоянно меняющихся величин? О_о

fork_you
()
Ответ на: комментарий от fork_you

программа сохраняет в list<int> значение, если вводим -1, удаляет, если вводим -2(только одно поторение). При каждом вводе надо что бы выводился минимум, максимум и средняя арифм. Если list пуст, выводим ноль. 

#include <list>
#include "nice_utils"
using namespace std;

void update(list<int> &l, int aux, int &min, int &max, int &mid) {
    l.insert(l.end(), aux);
    if (l.size() == 1) min = max = mid = aux;
    else {
        if (aux > max) max = aux;
        else if (aux < min) min = aux;
        mid = mid + aux;
    }
}

void erase(list<int> &l, int aux, int &min, int &max, int &mid) {
    list<int>::iterator it = l.begin();
    while((*it) != aux and it != l.end()) ++it;
    if (it != l.end()) {
        l.erase(it);
        if (l.size() == 1) max = min = mid = (*l.begin());
        else if (l.size() != 0){
            mid -= aux;
            if (aux == max) {
                it = l.begin();
                bool found = false;
                max = (*it);
                while (it != l.end() and not found) {
                    if ((*it) == aux) {
                        found = true;
                        max = aux;
                    }
                    else if ((*it) > max) {
                        max = (*it);
                    }
                    ++it;

                }
            }
            else if (aux == min) {
                it = l.begin();
                bool found = false;
                min = (*it);
                while (it != l.end() and not found) {
                    if ((*it) == aux) {
                        found = true;
                        min = aux;
                    }
                    else if ((*it) < min) {
                        min = (*it);
                    }
                    ++it;

                }
            }
        }

    }
}


int main() {
    list<int> l;
    int i = readint();
    int max, min, mid;
    while (i == -1 or i == -2) {
        int aux = readint();
        if (i == -1) update(l, aux, min, max, mid);
        else if (i == -2) erase(l, aux, min, max, mid);
        if (l.size() != 0) cout << "min " << min << "; max " << max << "; mid " << double(mid)/l.size() << endl; 
        else cout << '0' << endl;
        i = readint();
    }

}[[/code]]

Trieforce ★
() автор топика
Ответ на: комментарий от Trieforce

боже мой, я чуть глаза не сломал. извини, но я не хочу в это углубляться, слишком скобок много.

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

/* assume(list.size() != 0) */

min = max = sum = *it++;

while (it != list.end()) {
    if (*it == aux) {
        it = list.remove(it);
        continue;
    }
    if (*it < min) min = *it;
    if (*it > max) max = *it;
    sum += *it;
}

  • проще понять что ты хотел сделать
  • скорее всего даже и работать быстрее будет (у тебя почти всегда 2 прохода по списку)

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

да, и переименуй l в list, а mid в sum

fork_you
()
Ответ на: комментарий от Trieforce

даже если меньше одного. все равно. лучше напиши читаемый код и потом его оптимизируй, чем пиши «быстрый» код, в котором через полчаса не сможешь разобраться.

fork_you
()
Ответ на: комментарий от Trieforce 
void erase(list<int> &l, int aux, int &min, int &max, int &mid) {
    ...
    while((*it) != aux and it != l.end()) ++it; // как минимум один есть, N проверок
    if (it != l.end()) {
       ...
        if (l.size() == 1) max = min = mid = (*l.begin());
        else if (l.size() != 0){ // второй проход ниже. size почти всегда больше нуля
            mid -= aux;
       ...
fork_you
()
Ответ на: комментарий от fork_you

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

void remove(list<int> &list, int &cur, int &min, int &max, int &sum) {
    if (list.size() == 0) return;
    list<int>::iterator it = list.begin();
    if (cur == min or cur == max) { // пересчитываем, надеемся, что это происходит не часто
        min = max = sum = *it++;
        while (it != list.end()) {
            if (*it == cur) {
                it = list.remove(it);
                continue;
            }
            if (*it < min) min = *it;
            else if (*it > max) max = *it;
            sum += *it++;
        }
    } else {
        while (it != list.end()) {   // простой случай - вычитаем из общей суммы, если такое число присутствует в массиве
            if (*it == cur) {
                it = list.remove(it);
                sum -= cur;
                break;
            } else ++it;
        }
    }
    
}

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

fork_you
()
Ответ на: комментарий от Trieforce

в смысле? какой фрагментации?

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

fork_you
()
Ответ на: комментарий от fork_you

Да там были указатели. Просто в векторе было бы правильней зная размер элемента делать прыжок. Ну это так.

Trieforce ★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development