Примечание: Пожалуйста, не интерпретируйте это как "вопрос о домашнем задании". Мне просто интересно узнать:)
Медиана пяти иногда используется как упражнение в дизайне алгоритма и, как известно, вычислима , используя только 6 сравнений.
Каков наилучший способ реализовать эту "медиану из пяти, используя 6 сравнений в С#? Все мои попытки, похоже, приводят к неловкому коду:( Мне нужен хороший и читаемый код, хотя мы используем только 6 сравнений.
public double medianOfFive(double a, double b, double c, double d, double e){
//
// return median
//
return c;
}
Примечание: Я думаю, что я должен также предоставить "алгоритм":
Я обнаружил, что не могу четко объяснить алгоритм, как это сделал Азереал на своем форуме. Поэтому я расскажу здесь об этом. Из http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085
Ну, я поставил эту проблему в один моих заданий, и я обратился к этому форум для помощи, но никакой помощи здесь не было. В конце концов я узнал, как это сделать.
Начните объединение с четырьмя четырьмя элементами и закажите каждую пару (2 сравнение)
Сравните два нижних из каждой пары и устраните самый низкий из возможности (3 сравнения)
Добавьте в пятый номер, отведенный на номер без пары, и сравните два (4 сравнения)
Сравните две самые низкие из двух новых пар и устраните нижнюю (5 сравнений)
Сравните один сам по себе и нижний из последней пары, а нижний число - медиана
Возможная медиана находится в пределах parentesis
(54321)
5: 4 3: 2 2 сравнения
(4 < 5 2 < 3 1)
4: 2 3 сравнения
2 (4 < 5 3 1)
1: 3 4 сравнения
2 (4 < 5 1 < 3)
4: 1 5 сравнений
1,2 (4 < 5 3)
4: 3 6 сравнений
1,2 (3) 4,5
Три - это медиана
РЕДАКТИРОВАТЬ: Как ваш запрос и чтобы я не мог получить больше downvotes, это код С++, который я написал, чтобы найти медиану из пяти. Не возражайте против неловкости:
double StageGenerator::MedianOfFive(double n1, double n2, double n3, double n4, double n5){
double *a = &n1, *b = &n2, *c = &n3, *d = &n4, *e = &n5;
double *tmp;
// makes a < b and b < d
if(*b < *a){
tmp = a; a = b; b = tmp;
}
if(*d < *c){
tmp = c; c = d; d = tmp;
}
// eleminate the lowest
if(*c < *a){
tmp = b; b = d; d = tmp;
c = a;
}
// gets e in
a = e;
// makes a < b and b < d
if(*b < *a){
tmp = a; a = b; b = tmp;
}
// eliminate another lowest
// remaing: a,b,d
if(*a < *c){
tmp = b; b = d; d = tmp;
a = c;
}
if(*d < *a)
return *d;
else
return *a;
}
Он должен быть более компактным, не так ли?
EDIT:
Как отметил @pablito в своем ответе. Встроенный List.Sort() не может выполнить это требование, так как он использует до 13 сравнений:]