Да. Классический вариант: Вирт Н. Алгоритмы+структуры данных=программы
http://lib.mexmat.ru/books/9225 (Алгоритм поиска медианы - стр. 103)
>средним медианным будет
В мат.статистике нет "среднего медианного", а есть просто медиана. Иногда используют линейную комбинацию центральных порядковых статистик, т.е. усреднение центральной выборки отсортированного ряда.
Тогда ещё такой вопрос. В данном случае как лучше сортировать — методом пузырька или как-нибудь более топорно? Просто задачу будет препод (не мой! я её знакомому делаю, у которого проблема с курсовой - времени не хватает) смотреть...
Метод пузырька - это так (к слову, а как массивы в качестве параметров функции использовать?):
void bubblesort(ЧТО_ТУТ_ПИСАТЬ arr, const int& n)
{
int i;
int j;
double tmp;
for(i = 0; i <= n-1; i++)
{
for(j = 0; j <= n-2-i; j++)
{
if( arr(j)>arr(j+1) )
{
tmp = arr(j);
arr(j) = arr(j+1);
arr(j+1) = tmp;
}
}
}
}
void main()
{
int a[3];
a(0) = 2;
a(1) = 1;
a(2) = 4;
bubblesort(a, 3);
x = a(1);
cout << x << endl;
}
>Тогда ещё такой вопрос. В данном случае как лучше сортировать — методом пузырька или как-нибудь более топорно?
С тремя числами можно совершенно не заморачиваться, всё равно при любом раскладе разницу в производительности даже измерить не получится. Но я бы сделал 3 попарных сравнения. В общем же случае, ЕМНИП, применяется метод неполного HeapSort.
Летит самолёт, за ним болтается в люльке какой-то геофизический прибор (любой) и снимает показания в определённые моменты времени t. Но тут, то ли из-за раздолбайства работников завода, то ли из-за не слишком трезвого лётчика некоторые значения выходят за некоторые пределы, определяемые пользователем программы.
Условие программы.
Необходимо отсеять "кривые" значения 3-мя различными способами, на выбор самого пользователя. Эти значения находятся путём сравнения с некими 2-мя значениями, которые вводит пользователь: если оно (значение) оказывается больше или меньше (забыл сказать - ф-ция от t описывается некоей периодической функцией), то программа его обрабатывает:
1) с помощью среднего медианного;
2) с помощью полосы допустимых значений ("обрубание" по диапазону);
3) взять среднее арифметическое по предыдущей и последующей точкам и присвоить это число "кривому" значению.
2-х и более "кривых" чисел подряд во входном файле нет.
Устройство входного файла.
Первой строкой идёт вводное сообщение, которое считываем в строку и забываем. Или можно не считывать, как угодно.
Далее - 2 столбца значений, разделитель пробел. Первый столбец - время (переменная типа integer), 2-ой - собственно зн-ния (тип double). После всей этой обработки нужно вывести всю получившуюся байду с исправленными зн-ниями на экран.
Нужно задействовать ф-ции (т. е. все способы, чтение/вывод должны быть ф-циями), использовать динамическое выделение памяти (если понадобится) и написать все необходимые проверки (на чтение, на выделение памяти и т. д.).
Осталось разобраться со считыванием файла... тут ни у кого готового решения нет? Я с С++ на уровне hello world знаком :).
Т.е., если конкретнее:
Есть файл вида (его длина неизвестна)
----------------------
ненужная строка 423234235423 4353 435к на неё мы и не смотрим.
1 21.2
2 23.3
4 33.1
5 21.8
9 26.5
12 56.9
19 26.1
24 22.6
----------------------
Надо из него сделать 2 массива. В первом - первый столбец (int), во втором - второй столбец (double). Плюс тут проверки на выделение памяти нужны и на правильность входных данных.
Вот тут у меня ещё вопрос - а надо ли, как считаете, считывать всё в 2 массива, потом обрабатывать второй и выводить всё это? Может, проще считывать по 3 значения и проверять среднее на "кривость"? Изменять его, если требует, и выводить всё это?..
Условия отбраковывания мне не понятны, а читать можно примерно так:
FILE *f=stdin;
fscanf(f, "%*[^\n]\n");
while (!feof(f))
{
fscanf(f, "%ld %f", &t, &val);
fscanf(f, "%*[^\n]\n"); // прочитать мусор в конце строки, можно объединить с предидущим выражением.
// .....
}
1. Насчет %f не уверен, нужно проверять.
2. Это не ++.
3. Все эти scanf - сильно не безопасны, но думаю для курсовой пойдет.
Условие отбраковывания - число не входит в заданный диапазон. Если число не входит в заданный диапазон, то оно считается "кривым" и его надо заменить. Заменяем одним из трёх перечисленных способов.
Например, второй столбец у нас выглядит так:
10
23
12
11
9
-10
2
И пользователь задаёт диапазон 0..15. Тогда "кривыми" считаются числа -10 и 23.
При замене методом медиан получится такое:
10
12
12
11
9
2
2
Методом полосы значений:
10
15
12
11
9
0
2
Методом срзнач:
10
11
12
11
9
5.5
2
Ну собственно методы мне не важны, с ними у меня проблем теперь нет :). Теперь буду курить считывание из файла.
И вопрос был такой: как выгоднее - считывать всё целиком, после чего обрабатывать и выводить? Или же считывать ступеньками по 3 числа, обрабатывать и сразу выводить?
> И вопрос был такой: как выгоднее - считывать всё целиком, после чего обрабатывать и выводить? Или же считывать ступеньками по 3 числа, обрабатывать и сразу выводить?
Если объем выборки не большой, то я бы считал все. Придется возиться с граничными значениями, а делать это проще когда все в памяти лежит уже.
И считывать по 3 не правильно. Если будет Хороший Плохой Хороший Плохой Хороший, то второй плохой нужно равнять по второму и третьему хорошим. Нужно скользящее окно.
PS: для справки: медианную фильтрацию обчно делают без вских предварительных сравнений. просто ползут окном нужной длинны (задает уровень фильтрации) по данным и выбирают медиану в окне. "Плохие" значения сами уйдут.
> И вопрос был такой: как выгоднее - считывать всё целиком, после чего обрабатывать и выводить? Или же считывать ступеньками по 3 числа, обрабатывать и сразу выводить?
Второе, разумеется, так как не надо хранить в памяти никаких массивов (это тебе аукнется, когда ты будешь гигабайтный файл обрабатывать).
> Это сильно зависит от скорости r/w операций на всех уровнях обработки данных.
Это курсовая, где критерии оценки производительности и качества кода обычно далеки от реальных и определяются какими-то мифическими представлениями препода.
> И считывать по 3 не правильно. Если будет Хороший Плохой Хороший Плохой Хороший, то второй плохой нужно равнять по второму и третьему хорошим. Нужно скользящее окно.
Я это и имел в виду, просто выразился неправильно.
>В общем же случае, ЕМНИП, применяется метод неполного HeapSort
алгоритм медианы всех медиан там применяется, имеющий линейную сложность по времени в худшем случае. в качестве реализации рекомендую смотреть std::nth_element из стандартной библиотеки C++
Исправил пропуск первой строки (вместо пропуска строки оно пропускало первое слово) и добавил проверку на выбор метода: http://pastebin.mozilla-russia.org/97965
Теперь не хватает 2 проверок:
1. Являются ли вводимые пользователем границы диапазона числами?
2. Действительно ли первый столбец в БД соответсвует int, а второй - double?
Со второй разберусь, а насчёт первой посоветуете что-нибудь?
Ковыряться в этом коде мне лень, если честно. Да и поздно наверное уже, но вот студенчество вспомнилось, тоже курсачи делать начинал вечером перед cдачей :)