Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1] 2  Все   Вниз
  Печать  
Автор Тема: Как найти макс мин средн в массиве неизвестной длины?  (Прочитано 38578 раз)
0 Пользователей и 2 Гостей смотрят эту тему.
Aleck D.Shadow
Опытный

tr
Offline Offline
Пол: Мужской

« : 09-09-2003 05:57 » 

Еще необходимо убрать 4 первых и 4 последних значения.
Способ двумя циклами не совсем подходит.
1 цикл собираем данные.
2 цикл ищем мин,макс,средн.

Кто предложит оптимальнее?
Записан
NetRaider
Гость
« Ответ #1 : 09-09-2003 06:12 » 

Что значит неизвестной длины ? Понятно что может быть произвольное кол-во элементов, но некое завершающее значение присутствует ?
Записан
Sommer
Молодой специалист

us
Offline Offline

« Ответ #2 : 09-09-2003 06:31 » 

Aleck D.Shadow,
ээээээээээ
ну можно в первом же цикле и инфу собирать и искать нужные нам значения...

и мне тоже непонятно как у массива не известна длина...
Записан

когда-нибудь, я верю, ты будешь ехать по этому городу и поймёшь, что хочешь увидеть меня за рулём мчащейся по соседней полосе машины.
но тогда меня уже не будет
в этом городе
forever yours.
Aleck D.Shadow
Опытный

tr
Offline Offline
Пол: Мужской

« Ответ #3 : 09-09-2003 06:33 » 

Да, конечно! Но мы это узнаем только после сбора данных. Т.е. 1 цикл.
2 цикл снова пробегаем по тем же данным но уже с известным числом.
Записан
sh_m
Гость
« Ответ #4 : 09-09-2003 06:35 » 

И зачем два цикла?
Массив двумерный?
Записан
Aleck D.Shadow
Опытный

tr
Offline Offline
Пол: Мужской

« Ответ #5 : 09-09-2003 06:35 » 

Читайте ограничение в том что нужно убрать первые Н и последние К значений!
Среднее особенно!
Записан
Aleck D.Shadow
Опытный

tr
Offline Offline
Пол: Мужской

« Ответ #6 : 09-09-2003 06:39 » 

Зачем нужен 2 цикл? Для того что бы посчитать Мин,Макс,Средн.
Записан
sh_m
Гость
« Ответ #7 : 09-09-2003 06:46 » 

Цитата: Aleck D.Shadow
Зачем нужен 2 цикл? Для того что бы посчитать Мин,Макс,Средн.


И все равно. Все можно сделать одним циклом.
Нужно только завести дополнительные переменные (максимум, минимум, количество элементов, общая сумма, значения четырех первых и четырех последних). Не очень ясно всетаки в каком виде задается массив.
Записан
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии

il
Offline Offline
Пол: Мужской
Бодрый птах


« Ответ #8 : 09-09-2003 06:47 » 

Задай нам параметры в коде для массива - скажем функция получает указатель идлину или еще что-то - я тебе напишу поиск....
Записан

А птичку нашу прошу не обижать!!!
Aleck D.Shadow
Опытный

tr
Offline Offline
Пол: Мужской

« Ответ #9 : 09-09-2003 06:53 » 

To sh_m:
Дак ведь если же будет необходимо обрезать больше чем 4 например 120.
При этом первые еще более менее понятно как сохранить.А вот последние
их каждый раз придется двигать до достижения конца. Тогда эффективность сильно упадет. Или я ошибаюсь.
То Гром: длина заведомо неизвестна. Если бы была известна то и вопроса бы не возникло.  Ага
Записан
sh_m
Гость
« Ответ #10 : 09-09-2003 07:00 » 

Цитата: Aleck D.Shadow
To sh_m:
Дак ведь если же будет необходимо обрезать больше чем 4 например 120.
При этом первые еще более менее понятно как сохранить.А вот последние
их каждый раз придется двигать до достижения конца. Тогда эффективность сильно упадет.


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

Дописал позже.

Это я уже запутался: все равно нужно хранить всю заднюю "обрезку".
Записан
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии

il
Offline Offline
Пол: Мужской
Бодрый птах


« Ответ #11 : 09-09-2003 07:01 » 

Ты эта....
Не бывает массива с неизвестной длиной - тогда это связный список - но смысл не меняется совершенно..
Поэтому и спрашиваю - работы минут на 10 писать....
Распиши саму задачу какие данные откуда и как приходят, что у тебя есть реально - чего нет - ....
Записан

А птичку нашу прошу не обижать!!!
Aleck D.Shadow
Опытный

tr
Offline Offline
Пол: Мужской

« Ответ #12 : 09-09-2003 07:10 » 

Цитата

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

А что это даст. Как вычислить макс, мин?

Цитата

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

Короче говоря, у меня есть поток данных:
0 0 0 2
0 2 0 2
0 3 0 4
0 5 1 0
0 3 2 0
1 0 1 0
2 0 2 0
2 0 0 0
2 0 0 3

Необходимо скалькулировать данные в каждом столбце, отбросив 0.
При этом обрезать начальные Н и конечные К значения.
Конечно, в этом массиве мы знаем скоко данных ( их 9 ) а сколько данных в каждом столбце мы не знаем. Вот такая ситуация.  Вот такой я вот
Записан
sh_m
Гость
« Ответ #13 : 09-09-2003 07:11 » 

Цитата: Гром
Ты эта....
Не бывает массива с неизвестной длиной - тогда это связный список - но смысл не меняется совершенно..
Поэтому и спрашиваю - работы минут на 10 писать....
Распиши саму задачу какие данные откуда и как приходят, что у тебя есть реально - чего нет - ....


Может это не готовый массив? А просто поступают значения, которые нужно обрабатывать "на лету".

Ну тогда тем более нужно делать все одним циклом.
Записан
sh_m
Гость
« Ответ #14 : 09-09-2003 07:17 » 

Цитата: Aleck D.Shadow
А что это даст. Как вычислить макс, мин?


С передней "обрезкой" думаю вопросов нет, просто отбрасываешь значения до достижения нужного количества. А что касается задней, то число нужно обрабатывать не сразу после поступления, а когда оно "вытолкнется" из буфера для задней "обрезки".
Записан
Aleck D.Shadow
Опытный

tr
Offline Offline
Пол: Мужской

« Ответ #15 : 09-09-2003 07:28 » 

sh_m : "а когда оно "вытолкнется" из буфера для задней "обрезки"."
Я хочу заметить, что "вытолкнется" это означает нужно будет двигать циклом.
Например, 120 значений нужно обрезать, с каждой итерацией нужно пробежать 120 значений и подвинуть на один. Так ?
Записан
sh_m
Гость
« Ответ #16 : 09-09-2003 07:48 » 

Цитата: Aleck D.Shadow
sh_m : "а когда оно "вытолкнется" из буфера для задней "обрезки"."
Я хочу заметить, что "вытолкнется" это означает нужно будет двигать циклом.
Например, 120 значений нужно обрезать, с каждой итерацией нужно пробежать 120 значений и подвинуть на один. Так ?


Верно, но этот процесс можно оптимизировать сам по себе. Например не двигать весь массив, а манипулировать только индексами. Как именно, я сейчас ответить затрудняюсь, но Гром тут упоминал связные списки, по-моему оно как раз из этой серии.
Записан
SlavaI
Главный специалист

ru
Offline Offline

« Ответ #17 : 09-09-2003 07:52 » 

Цитата

При этом обрезать начальные Н и конечные К значения.


C начальными вроде проблем нет- и так ясно, а для конечных создай стек(попросту массив) из K значений и запихивай на каждом шаге туда. Когда массив закончится, то то что в стеке и есть то что надо отбросить.
Записан
SlavaI
Главный специалист

ru
Offline Offline

« Ответ #18 : 09-09-2003 07:58 » 

Я до сих пор не пойму какой макс мин ты имеешь в виду? Убрать K максимальных элементов? Если да, то отдельный массив на K элементов решает эту проблему- суй туда последние K максимальных элементов, найти их не трудно, когда данные последовательно идут- это элементы, которые больше наименьшего, находящегося в массиве. Если убрать последние K элементов- тоже отдельный массив на K элементов поможет.
Записан
Pu
Большой босс

ru
Offline Offline
78


« Ответ #19 : 09-09-2003 08:27 » 

для вычисления среднего совсем не обязательно знать количество значений в массиве просто считать на каждом шаге n -  
Записан

Насколько я опытен? Достаточно, чтобы понимать, что дураков нельзя заставить думать по–другому, но недостаточно, чтобы отказаться от попыток это сделать.
(с) Артур Джонс
NetRaider
Гость
« Ответ #20 : 09-09-2003 08:36 » 

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

Код:
#include <iostream>
#include <vector>

template<typename T>
class min_max_average
{
T min, max, total;
std::vector<T> array;

public:

min_max_average<T>():total(0){}
~min_max_average<T>()| array.clear(); }

T get_min() const { return min; }
T get_max() const { return max; }
T get_average() const { return (total/get_count());}
T get_count() const { return array.size();}

min_max_average<T>& operator << (const T& value)
{
array.push_back(value);

if(total == 0) {
total = min = max = value;
return *this;
}

total += value;
if(value < min) { min = value; return *this; }
if(value > max) { max = value; return *this; }
return *this;
}
};

int main(int argc, char* argv[])
{
min_max_average<int> a;

a << 45 << 2 << 12 << 54 << 71 << 13 << 21 << 0 ;

std::cout << "Max: " << a.get_max() << std::endl;
std::cout << "Min: " << a.get_min() << std::endl;
std::cout << "Average: "<< a.get_average() << std::endl;
std::cout << "Count: " << a.get_count() << std::endl;

return 0;
}

Про "обрезание": всегда должны удаляться 4 элемента или возможно другое кол-во ?

Удаленные элементы должны участвовать в нахождении мин, макс. и среднего значения или нет ?
« Последнее редактирование: 19-11-2007 18:13 от Алексей1153++ » Записан
Pu
Большой босс

ru
Offline Offline
78


« Ответ #21 : 09-09-2003 08:47 » 

2NetRaider - резонные вопросы про участие обрезаемых значений в расчетах.
Записан

Насколько я опытен? Достаточно, чтобы понимать, что дураков нельзя заставить думать по–другому, но недостаточно, чтобы отказаться от попыток это сделать.
(с) Артур Джонс
Pu
Большой босс

ru
Offline Offline
78


« Ответ #22 : 09-09-2003 08:50 » 

и есть ли смысл в классе делать этот массив воочию, достаточно количества отрезаемых элементов по моему
Записан

Насколько я опытен? Достаточно, чтобы понимать, что дураков нельзя заставить думать по–другому, но недостаточно, чтобы отказаться от попыток это сделать.
(с) Артур Джонс
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии

il
Offline Offline
Пол: Мужской
Бодрый птах


« Ответ #23 : 09-09-2003 09:20 » 

По моему все езе проще - при наличии связного списка - или любого признака конца массива - ставится ограничение - т.е. проверка стартовая что массив не меньше 4+4+1 - удаляемые элементы и один как минимум для наличия среднего.
Затем имеем 1 массив 4 элемента = MININT для минимальных. 1 массив 4 элемента MAXINT где MAXINT & MININT в данном случае максимальное и минимальное числов в массиве int если там другие значения - то и заполнять по типу.

Соответственно массив минимальных значений заполняется MAXINT а максимальных MININT

После чего идет перебор элементов
Код:
int i =0;
do{
Условие проверки в максимальных элементах
если нет места в массиве максимальных переходим в массив минимальных элементов
Если нет места - ничего не делаем.

}while (признак конца массива);


В массивах МАХ и MIN держим не только сами элементы а структуру

typedef struct __MAXMIN
{
    int Element;
    unsigned long index_in_base_array;
}

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

Как только пробег закончен вырезаем - вырезание при доступе по индексу можно проводить 100 путями - есть целая теория сдвигов или оптимизаций массивов, кстати применяемая в оптимизациях SQL баз данных

Если же массив пременной лины то наверняка есть связные ссылки - ибо это связный список - тогда удаление и перенос элементов сводятся к переписыванию ссылок и освобождению памяти.
« Последнее редактирование: 19-11-2007 18:15 от Алексей1153++ » Записан

А птичку нашу прошу не обижать!!!
Aleck D.Shadow
Опытный

tr
Offline Offline
Пол: Мужской

« Ответ #24 : 09-09-2003 09:31 » 

Слава, я тебя понял. Это решит проблему среднего. А максимум и минимум значения в массиве как!?
Записан
Pu
Большой босс

ru
Offline Offline
78


« Ответ #25 : 09-09-2003 09:31 » 

а если дпнные просто из потока например с RS порта и неизвестно когда закончатся? Не мне вариант с шаблоном очень понравился Щас пытаюсь присобачить к одной своей проге  Ага , только у меня вопрос с вычислением минимаксов не стоит . просто слэйв прогоняет через себя поток и ищет свой адрес.
Записан

Насколько я опытен? Достаточно, чтобы понимать, что дураков нельзя заставить думать по–другому, но недостаточно, чтобы отказаться от попыток это сделать.
(с) Артур Джонс
Aleck D.Shadow
Опытный

tr
Offline Offline
Пол: Мужской

« Ответ #26 : 09-09-2003 09:39 » 

Так. Pu и NetRaider, Вы хоть выше читаете или мне каждый раз переписывать одно и тоже.

Насчет выделения среднего по предложенной схеме Pu
Записан
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии

il
Offline Offline
Пол: Мужской
Бодрый птах


« Ответ #27 : 09-09-2003 09:42 » 

Погодь я еще подумаю.... но ты насчет мин и макс - посмотри написанное...
Записан

А птичку нашу прошу не обижать!!!
Aleck D.Shadow
Опытный

tr
Offline Offline
Пол: Мужской

« Ответ #28 : 09-09-2003 09:46 » 

Цитата

2NetRaider - резонные вопросы про участие обрезаемых значений в расчетах.

Да уж. Зачем спрашивается обрезать?
Прошу прощения если грубовато!
Записан
Aleck D.Shadow
Опытный

tr
Offline Offline
Пол: Мужской

« Ответ #29 : 09-09-2003 09:51 » 

Грому: Это ж сколько пространства надо на поддержку массивов макс и мин?
И опять же проблема со средним. Жаль
Записан
Страниц: [1] 2  Все   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines