[C++] Реквестирую код для нахождения среднего медианного трёх чисел

Отсортируй их и возьми второе (центральное).

http://www.codelab.ru/task/stat:median/ (code #108)

site bookmarked, спасибо

OMG, что это??? Функции с названиями bs03r1_c - это сильно.

А! bs03r1.f -- translated by f2c, ну тогда ладно, олдскул :)

> Отсортируй их и возьми второе (центральное).

Это и будет среднее медианное? Ты уверен? Как-то слишком просто :(.

Абсолютно уверен. Расхождения в трактовках бывают только для массивов четной длинны.

Собственно википедия согласна :)

Проверю себя... для массива 3 34643 34 средним медианным будет 34, для 128 32 64 - 64?

Если да - больше спасибо! :)

Все верно :))

А всякие хитрые алгоритмы на фортране - это поиск этой медианы без собственно сортировки.

>Если да - больше спасибо! :)

Да. Классический вариант: Вирт Н. Алгоритмы+структуры данных=программы 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 элемента, то лучше всего просто if-ами.

> Если задано точно 3 элемента, то лучше всего просто if-ами.

Видимо, так и сделаю.

> Если эта задача - вся курсовая, то как-то странно :)

Нет, это её часть)

>Тогда ещё такой вопрос. В данном случае как лучше сортировать — методом пузырька или как-нибудь более топорно?

С тремя числами можно совершенно не заморачиваться, всё равно при любом раскладе разницу в производительности даже измерить не получится. Но я бы сделал 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 числа, обрабатывать и сразу выводить?

Второе, разумеется, так как не надо хранить в памяти никаких массивов (это тебе аукнется, когда ты будешь гигабайтный файл обрабатывать).

Что-то я не совсем осилил условия. В общем, если оба метода дают один и тот же результат, то второй предпочтительнее.

>("обрубание" по диапазону);

Можно выбирать медиану из 5 элементов (3 из файла+ 2 заданы пользователем)

>как выгоднее

Это сильно зависит от скорости r/w операций на всех уровнях обработки данных.

Возможно подойдёт http://ru.wikipedia.org/wiki/Блочная_сортировка

> Это сильно зависит от скорости r/w операций на всех уровнях обработки данных.

Это курсовая, где критерии оценки производительности и качества кода обычно далеки от реальных и определяются какими-то мифическими представлениями препода.

> И считывать по 3 не правильно. Если будет Хороший Плохой Хороший Плохой Хороший, то второй плохой нужно равнять по второму и третьему хорошим. Нужно скользящее окно.

Я это и имел в виду, просто выразился неправильно.

ну типа solved, решено через среднее арифметическое

#include <fstream>
#include <iostream>
#include <string>
using namespace std;

bool window(int *t, double *v)
{
	static fstream file;
	if(file.is_open()){
		int tt;
		double vv;
		file >> tt >> vv;
		if(file.eof()) {
			file.close();
			return false;
		}
		t[0] = t[1]; v[0] = v[1];
		t[1] = t[2]; v[1] = v[2];
		t[2] = tt; v[2] = vv;
	} else {
		string hello;
		file.open("INPUT",fstream::in);
		file >> hello;
		file >> t[0] >> v[0];
		file >> t[1] >> v[1];
		file >> t[2] >> v[2];
	}
	
	return true;
}

void med(int *t, double *v, double o)
{
	if(v[1]>v[0]+o || v[1]<v[0]-o)
		v[1] = (v[0]+v[2])/2;
}

void out(int t, double v)
{
	cout << "время:" << t << " значение:"  << v << endl;
}

int main(int argc, char *argv[])
{
	
	int t[3];
	double v[3],o;
	cout << "Пожалуйста введите максимально допустимое отклонение: ";
	cin >> o;
	
	while(window(t,v)){
		med(t,v,o);
		out(t[0],v[0]);
	}
	
	med(t,v,o);
	out(t[1],v[1]);
	out(t[2],v[2]);
	return 0;
}

Ещё раз спасибо! Правда, взят не диапазон от .. до .., но это исправимо :).

>взят не диапазон от .. до .., но это исправимо

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

>В общем же случае, ЕМНИП, применяется метод неполного HeapSort

алгоритм медианы всех медиан там применяется, имеющий линейную сложность по времени в худшем случае. в качестве реализации рекомендую смотреть std::nth_element из стандартной библиотеки C++

Вот почти готовый код:

#include <fstream>
#include <iostream>
#include <string>
#include <cstdlib>	//там exit
#include <algorithm> 	//там min и max
using namespace std;

int fixtype,minV=1,maxV=0;

void median(double *v)	//медианное
{
  if(v[1]<v[2] && v[1]<v[0]) v[1]=min(v[0],v[2]);
  else v[1]=max(v[0],v[2]);
}

void polosa(double *v)	//полоса
{
  if(v[1]<minV) v[1]=minV;
  else v[1]=maxV;
}

void armean(double *v)	//среднее арифметическое
{
  v[1] = (v[0]+v[2])/2;
}

void fixstuff(double *v)
{
  cout << "СКОРРЕКТИРОВАНО: ";
  switch(fixtype)
  {
    case 1:
      median(v);
      break;
    case 2:
      polosa(v);
      break;
    case 3:
      armean(v);
      break;
  }
}

void out(int t, double v)			//функция вывода
{
  cout << "время:" << t << " показание:"  << v << endl;
}

bool check(double v, double minV, double maxV)	//1, если число входит в диапазон
{
  return((v>=minV) && (v<=maxV));
}

void errorhere(string errortext)
{
  cerr << endl << "ОШИБКА! " << errortext << endl;
}

void suicide()
{
  cerr << endl << "Скорректируйте выбранный диапазон или входные данные." << endl;
  exit (1);
}

bool window(int *t, double *v, double minV, double maxV)
{
  static fstream file;
  if(file.is_open()){
    int tt;
    double vv;
    file >> tt >> vv;
    if(file.eof()) {
      file.close();
      return false;
    }
    t[0] = t[1]; v[0] = v[1];
    t[1] = t[2]; v[1] = v[2];
    t[2] = tt; v[2] = vv;
  } else {
    string devnull;
    file.open("data.txt",fstream::in);

    if (file==NULL)
    {
      errorhere("ОШИБКА! Невозможно открыть файл data.txt.");
      exit (1);
    }
    
    file >> devnull;
    file >> t[0] >> v[0];

    if(!check(v[0],minV,maxV))
    {
      errorhere("Первое показание не входит в заданный диапазон:");
      out(t[0],v[0]);
      suicide();
    }
    
    file >> t[1] >> v[1];
    file >> t[2] >> v[2];
  }
  return true;
}

int main(int argc, char *argv[])
{
  int t[3]; 				//массив окна времени
  double v[3];				//массив окна показаний
  
  while(minV >= maxV)			//узнаём диапазон
  {
    cout << "Введите минимальное допустимое значение: ";
    cin >> minV;
    cout << "Введите максимальное допустимое значение: ";
    cin >> maxV;
    if(minV >= maxV) printf("Некорректный диапазон! Попробуйте ещё раз.");
  }
  
  cout << ">>> Выбран диапазон " << minV << " .. " << maxV << endl;
  
  cout << "Выберите номер метода корректировки: 1) медианное; 2) полоса допустимых значений; 3) среднее арифметическое \"соседей\": ";
  
  while(fixtype!=1 && fixtype!=2 && fixtype!=3)
  {
    cin >> fixtype;
    switch(fixtype)
    {
      case 1:
	cout << ">>> Выбран первый метод: медианное с предыдущей и последующей точкам." << endl;
	break;
      case 2:
	cout << ">>> Выбран второй метод: полоса допустимых значений." << endl; 
	break;
      case 3:
	cout << ">>> Выбран третий метод: среднее арифметическое по предыдущей и последующей точкам." << endl;
	break;
      default:
	cout << "Некорректный выбор. Выберите номер от 1 до 3: ";
	break;
    }
  }
  
  cout << endl;

  while(window(t,v,minV,maxV))
  {
    out(t[0],v[0]);
    if(!check(v[1],minV,maxV))
    {
      if(!check(v[2],minV,maxV))
      {
	errorhere("Два не входящих в диапазон числа подряд:");
        out(t[1],v[1]);
	out(t[2],v[2]);	
	suicide();
      }
      fixstuff(v);
    }    
  }
  
  if(!check(v[1],minV,maxV)) fixstuff(v);
  if(!check(v[2],minV,maxV))
  {
    errorhere("Последнее показание не входит в заданный диапазон:");
    out(t[2],v[2]);
    suicide();
  }
  out(t[1],v[1]);
  out(t[2],v[2]);
  cout << endl << "Данные успешно скорректированы." << endl;
  getchar();
  return 0;
}

Осталось добавить проверки на правильность данных в файле. Пожалуйста, укажите быдлокодеру в кривые места.

Что-то я так и не вкурил, как проверять, является ли введёное с клавиатуры (в cin) числом. Как это сделать?

Исправил пропуск первой строки (вместо пропуска строки оно пропускало первое слово) и добавил проверку на выбор метода: http://pastebin.mozilla-russia.org/97965

Теперь не хватает 2 проверок:
1. Являются ли вводимые пользователем границы диапазона числами?
2. Действительно ли первый столбец в БД соответсвует int, а второй - double?

Со второй разберусь, а насчёт первой посоветуете что-нибудь?

Добавил проверялку для пункта 1. Как она, нормальная? http://pastebin.mozilla-russia.org/97966

Ковыряться в этом коде мне лень, если честно. Да и поздно наверное уже, но вот студенчество вспомнилось, тоже курсачи делать начинал вечером перед cдачей :)

Финальная версия: http://nopaste.com/p/ac1Tcopzk