Aleck D.Shadow
|
|
« : 09-09-2003 05:57 » |
|
Еще необходимо убрать 4 первых и 4 последних значения. Способ двумя циклами не совсем подходит. 1 цикл собираем данные. 2 цикл ищем мин,макс,средн.
Кто предложит оптимальнее?
|
|
|
Записан
|
|
|
|
NetRaider
Гость
|
|
« Ответ #1 : 09-09-2003 06:12 » |
|
Что значит неизвестной длины ? Понятно что может быть произвольное кол-во элементов, но некое завершающее значение присутствует ?
|
|
|
Записан
|
|
|
|
Sommer
Молодой специалист
Offline
|
|
« Ответ #2 : 09-09-2003 06:31 » |
|
Aleck D.Shadow, ээээээээээ ну можно в первом же цикле и инфу собирать и искать нужные нам значения...
и мне тоже непонятно как у массива не известна длина...
|
|
|
Записан
|
когда-нибудь, я верю, ты будешь ехать по этому городу и поймёшь, что хочешь увидеть меня за рулём мчащейся по соседней полосе машины. но тогда меня уже не будет в этом городе forever yours.
|
|
|
Aleck D.Shadow
|
|
« Ответ #3 : 09-09-2003 06:33 » |
|
Да, конечно! Но мы это узнаем только после сбора данных. Т.е. 1 цикл. 2 цикл снова пробегаем по тем же данным но уже с известным числом.
|
|
|
Записан
|
|
|
|
sh_m
Гость
|
|
« Ответ #4 : 09-09-2003 06:35 » |
|
И зачем два цикла? Массив двумерный?
|
|
|
Записан
|
|
|
|
Aleck D.Shadow
|
|
« Ответ #5 : 09-09-2003 06:35 » |
|
Читайте ограничение в том что нужно убрать первые Н и последние К значений! Среднее особенно!
|
|
|
Записан
|
|
|
|
Aleck D.Shadow
|
|
« Ответ #6 : 09-09-2003 06:39 » |
|
Зачем нужен 2 цикл? Для того что бы посчитать Мин,Макс,Средн.
|
|
|
Записан
|
|
|
|
sh_m
Гость
|
|
« Ответ #7 : 09-09-2003 06:46 » |
|
Зачем нужен 2 цикл? Для того что бы посчитать Мин,Макс,Средн. И все равно. Все можно сделать одним циклом. Нужно только завести дополнительные переменные (максимум, минимум, количество элементов, общая сумма, значения четырех первых и четырех последних). Не очень ясно всетаки в каком виде задается массив.
|
|
|
Записан
|
|
|
|
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии
Offline
Пол:
Бодрый птах
|
|
« Ответ #8 : 09-09-2003 06:47 » |
|
Задай нам параметры в коде для массива - скажем функция получает указатель идлину или еще что-то - я тебе напишу поиск....
|
|
|
Записан
|
А птичку нашу прошу не обижать!!!
|
|
|
Aleck D.Shadow
|
|
« Ответ #9 : 09-09-2003 06:53 » |
|
To sh_m: Дак ведь если же будет необходимо обрезать больше чем 4 например 120. При этом первые еще более менее понятно как сохранить.А вот последние их каждый раз придется двигать до достижения конца. Тогда эффективность сильно упадет. Или я ошибаюсь. То Гром: длина заведомо неизвестна. Если бы была известна то и вопроса бы не возникло.
|
|
|
Записан
|
|
|
|
sh_m
Гость
|
|
« Ответ #10 : 09-09-2003 07:00 » |
|
To sh_m: Дак ведь если же будет необходимо обрезать больше чем 4 например 120. При этом первые еще более менее понятно как сохранить.А вот последние их каждый раз придется двигать до достижения конца. Тогда эффективность сильно упадет. Если и количество обрезаемыых элементов нежесткое, то можно хранить их сумму, ну и текущие значения первого и последнего в "обрезке". Дописал позже.Это я уже запутался: все равно нужно хранить всю заднюю "обрезку".
|
|
|
Записан
|
|
|
|
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии
Offline
Пол:
Бодрый птах
|
|
« Ответ #11 : 09-09-2003 07:01 » |
|
Ты эта.... Не бывает массива с неизвестной длиной - тогда это связный список - но смысл не меняется совершенно.. Поэтому и спрашиваю - работы минут на 10 писать.... Распиши саму задачу какие данные откуда и как приходят, что у тебя есть реально - чего нет - ....
|
|
|
Записан
|
А птичку нашу прошу не обижать!!!
|
|
|
Aleck D.Shadow
|
|
« Ответ #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
|
|
« Ответ #15 : 09-09-2003 07:28 » |
|
sh_m : "а когда оно "вытолкнется" из буфера для задней "обрезки"." Я хочу заметить, что "вытолкнется" это означает нужно будет двигать циклом. Например, 120 значений нужно обрезать, с каждой итерацией нужно пробежать 120 значений и подвинуть на один. Так ?
|
|
|
Записан
|
|
|
|
sh_m
Гость
|
|
« Ответ #16 : 09-09-2003 07:48 » |
|
sh_m : "а когда оно "вытолкнется" из буфера для задней "обрезки"." Я хочу заметить, что "вытолкнется" это означает нужно будет двигать циклом. Например, 120 значений нужно обрезать, с каждой итерацией нужно пробежать 120 значений и подвинуть на один. Так ? Верно, но этот процесс можно оптимизировать сам по себе. Например не двигать весь массив, а манипулировать только индексами. Как именно, я сейчас ответить затрудняюсь, но Гром тут упоминал связные списки, по-моему оно как раз из этой серии.
|
|
|
Записан
|
|
|
|
SlavaI
Главный специалист
Offline
|
|
« Ответ #17 : 09-09-2003 07:52 » |
|
При этом обрезать начальные Н и конечные К значения.
C начальными вроде проблем нет- и так ясно, а для конечных создай стек(попросту массив) из K значений и запихивай на каждом шаге туда. Когда массив закончится, то то что в стеке и есть то что надо отбросить.
|
|
|
Записан
|
|
|
|
SlavaI
Главный специалист
Offline
|
|
« Ответ #18 : 09-09-2003 07:58 » |
|
Я до сих пор не пойму какой макс мин ты имеешь в виду? Убрать K максимальных элементов? Если да, то отдельный массив на K элементов решает эту проблему- суй туда последние K максимальных элементов, найти их не трудно, когда данные последовательно идут- это элементы, которые больше наименьшего, находящегося в массиве. Если убрать последние K элементов- тоже отдельный массив на K элементов поможет.
|
|
|
Записан
|
|
|
|
Pu
Большой босс
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
Большой босс
Offline
78
|
|
« Ответ #21 : 09-09-2003 08:47 » |
|
2NetRaider - резонные вопросы про участие обрезаемых значений в расчетах.
|
|
|
Записан
|
Насколько я опытен? Достаточно, чтобы понимать, что дураков нельзя заставить думать по–другому, но недостаточно, чтобы отказаться от попыток это сделать. (с) Артур Джонс
|
|
|
Pu
Большой босс
Offline
78
|
|
« Ответ #22 : 09-09-2003 08:50 » |
|
и есть ли смысл в классе делать этот массив воочию, достаточно количества отрезаемых элементов по моему
|
|
|
Записан
|
Насколько я опытен? Достаточно, чтобы понимать, что дураков нельзя заставить думать по–другому, но недостаточно, чтобы отказаться от попыток это сделать. (с) Артур Джонс
|
|
|
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии
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
|
|
« Ответ #24 : 09-09-2003 09:31 » |
|
Слава, я тебя понял. Это решит проблему среднего. А максимум и минимум значения в массиве как!?
|
|
|
Записан
|
|
|
|
Pu
Большой босс
Offline
78
|
|
« Ответ #25 : 09-09-2003 09:31 » |
|
а если дпнные просто из потока например с RS порта и неизвестно когда закончатся? Не мне вариант с шаблоном очень понравился Щас пытаюсь присобачить к одной своей проге , только у меня вопрос с вычислением минимаксов не стоит . просто слэйв прогоняет через себя поток и ищет свой адрес.
|
|
|
Записан
|
Насколько я опытен? Достаточно, чтобы понимать, что дураков нельзя заставить думать по–другому, но недостаточно, чтобы отказаться от попыток это сделать. (с) Артур Джонс
|
|
|
Aleck D.Shadow
|
|
« Ответ #26 : 09-09-2003 09:39 » |
|
Так. Pu и NetRaider, Вы хоть выше читаете или мне каждый раз переписывать одно и тоже.
Насчет выделения среднего по предложенной схеме Pu
|
|
|
Записан
|
|
|
|
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии
Offline
Пол:
Бодрый птах
|
|
« Ответ #27 : 09-09-2003 09:42 » |
|
Погодь я еще подумаю.... но ты насчет мин и макс - посмотри написанное...
|
|
|
Записан
|
А птичку нашу прошу не обижать!!!
|
|
|
Aleck D.Shadow
|
|
« Ответ #28 : 09-09-2003 09:46 » |
|
2NetRaider - резонные вопросы про участие обрезаемых значений в расчетах.
Да уж. Зачем спрашивается обрезать? Прошу прощения если грубовато!
|
|
|
Записан
|
|
|
|
Aleck D.Shadow
|
|
« Ответ #29 : 09-09-2003 09:51 » |
|
Грому: Это ж сколько пространства надо на поддержку массивов макс и мин? И опять же проблема со средним.
|
|
|
Записан
|
|
|
|
Pu
Большой босс
Offline
78
|
|
« Ответ #30 : 09-09-2003 09:55 » |
|
2Aleck D.Shadow - не за что , я просто использую эту формулу для получения среднего в RealTime мне на вход через произвольнойе время (1-60 сек)может попасть число и за смену 8 ч или там произвольное время надо получить среднее. (извини если не в тему - я подумал похоже)
|
|
|
Записан
|
Насколько я опытен? Достаточно, чтобы понимать, что дураков нельзя заставить думать по–другому, но недостаточно, чтобы отказаться от попыток это сделать. (с) Артур Джонс
|
|
|
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии
Offline
Пол:
Бодрый птах
|
|
« Ответ #31 : 09-09-2003 09:56 » |
|
Что??? Пространтсва? 4 элемента по 4 байта + 4 байта = 8 байт - максимум при 16 байт на unsigned long - содержимое + 16 байт при миллиардных индексах... Отрезая по 5 с каждого конца получится 5 * 32 * 2 = 320 БАЙТ это много :?:
|
|
|
Записан
|
А птичку нашу прошу не обижать!!!
|
|
|
Aleck D.Shadow
|
|
« Ответ #32 : 09-09-2003 10:07 » |
|
Не вообще вроде как Гром прав нужно делать массив из структур типа индекс,мин,макс,сумма. Потом сумму поделить на индекс есть среднее.
|
|
|
Записан
|
|
|
|
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии
Offline
Пол:
Бодрый птах
|
|
« Ответ #33 : 09-09-2003 10:08 » |
|
Естсественно
|
|
|
Записан
|
А птичку нашу прошу не обижать!!!
|
|
|
Aleck D.Shadow
|
|
« Ответ #34 : 09-09-2003 10:13 » |
|
Что??? Пространтсва? Ну это если в байтах, а если в двойных словах, да еще компьютер из себя представляет наладонник? А вообще точно Гром ты меня навел на правильный путь.Thanx. :!:
|
|
|
Записан
|
|
|
|
Aleck D.Shadow
|
|
« Ответ #35 : 09-09-2003 10:18 » |
|
Кстати, хочу заметить(или отметить ради справедливости) что всё таки SlavaI был первее, я просто не до конца его мысль понял. Зато Гром доходчивее прояснил. Всем спасибо. Похоже, что лучше варианта решения проблемы всё равно нет.
|
|
|
Записан
|
|
|
|
Never
|
|
« Ответ #36 : 10-09-2003 10:54 » |
|
Люди, я не въехала: если вы принимаете из потока, из потока ввода? Тогда вы когда-нибудь да прекратите ввод. Например по Enter? Можно же привязать к этой клавише определение длины получившегося массива. Или из другого потока?
|
|
|
Записан
|
не умеете летать- не мучайте метлу!
|
|
|
Aleck D.Shadow
|
|
« Ответ #37 : 10-09-2003 12:04 » |
|
To Never: Можно. Но это мне не надо.
|
|
|
Записан
|
|
|
|
sh_m
Гость
|
|
« Ответ #38 : 10-09-2003 12:14 » |
|
to Aleck D.ShadowТы когда проблему добьешь, напиши как-именно. Интересно всетаки
|
|
|
Записан
|
|
|
|
Ане4ка
Гость
|
|
« Ответ #39 : 11-11-2007 18:00 » |
|
Может, неправильно поняла (да и тема давнишняя), но, кажется, всё просто: Первые Н отбрасываем, дальше бежим по массиву двумя указателями (помним 2 индекса) с разницей в К элементов между ними. На каждой итерации (при переходе к следующему элементу) двигаем оба указателя на единичку. Первый указатель следит, чтобы не появился конец массива, а второй обозначает то число, которое сейчас рассматривается. Ещё у нас есть 4 переменные: текущий максимум, минимум, набранная сумма и кол-во расмотренных элементов. Если текущий больше максимума, переприсваиваем максимум, если меньше минимума, изменяем минимум, в любом случае прибавляем элемент к сумме и увеличиваем кол-во рассмотренных. Когда первый указатель наткнулся на конец массива, делим сумму на кол-во рассмотренных. Всё, у нас есть все ответы.
|
|
« Последнее редактирование: 11-11-2007 18:05 от Ане4ка »
|
Записан
|
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #40 : 11-11-2007 20:50 » |
|
Тему не помню, но щас прочитал...
Ане4ка, на первый взгляд всё верно говоришь, загвоздка в том (насколько я понял, поправьте если что) , что массив не лежит сразу в памяти, его вводят по циферке. И предлагается посчитать некоторые параметры в динамике. Конечно, можно брать текущий уже введённый отрезок и считать для него каждый раз по простому алгоритму - а почему бы, кстати, и нет ?
|
|
|
Записан
|
|
|
|
RXL
|
|
« Ответ #41 : 12-11-2007 07:16 » |
|
Даже в динамике разницы особой нет - алгоритм один и тот же. int n, min, max, sum, cnt; float avg;
sum = cnt = 0;
while (....ввод в n...) { if (n < min) min = n; if (n > max) max = n; cnt++; sum += n; }
avg = ((float)sum)/cnt;
|
|
|
Записан
|
... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #42 : 12-11-2007 07:23 » |
|
RXL, а первые N и последние M введённых не надо учитывать
|
|
|
Записан
|
|
|
|
RXL
|
|
« Ответ #43 : 12-11-2007 07:31 » |
|
Тогда два пути: 1. Буферизировать все и по окончанию ввода выбрать только нужный диапазон. 2. Пропустить N, а все последующее пропускать через FIFO глубиной M (буфер задержки). Что выходит из FIFO при переполнении пускать в расчет. #define N 5 #define M 4
int z[M]; int z_free = M; int z_pos = 0; int pass_free = N; int out_val, new_val; int min = 0, max = 0, sum = 0, cnt = 0; float avg = 0;
while (....ввод в new_val...) { if (pass_free) { pass_free--; } else if (z_free) { z[z_pos++] = new_val; z_free--; } else { if (z_pos >= M) z_pos = 0;
out_val = z[z_pos]; z[z_pos++] = new_val;
if (out_val < min) min = out_val;
if (out_val > max) max = out_val;
sum += out_val; cnt++; } }
avg = ((float)sum)/cnt;
|
|
« Последнее редактирование: 12-11-2007 07:43 от RXL »
|
Записан
|
... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
|
|
|
|