Нахождение среднего значения массива целых

Question

Скажем, у вас есть массив int (на любом языке с фиксированным размером int). Как бы вы вычислили int, ближайший к их среднему значению?

Редактировать: чтобы быть понятным, результат не обязательно должен присутствовать в массиве. То есть для входного массива [3, 6, 7] ожидаемый результат равен 5. Также я предполагаю, что нам нужно указать конкретное направление округления, так что округлять вниз, если вы одинаково близки к двум числам.

Редактировать: Это не домашняя работа. У меня не было домашней работы пять лет. И это мой первый раз в стеке, поэтому, пожалуйста, будьте добры!

Изменить: Очевидный подход суммирования и деления может переполниться, поэтому я пытаюсь придумать подход, который является безопасным при переполнении, как для больших массивов, так и для больших целых. Я думаю, что правильная обработка переполнения (без мошенничества и использования другого типа) - безусловно, самая трудная часть этой проблемы.

Answer 1

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

// The length of someListOfNumbers doesn't need to be known in advance.
int mean(SomeType someListOfNumbers) {  
    double mean = 0, count = 0;
    foreach(element; someListOfNumbers) {
        count++;
        mean += (element - mean) / count;
    }
    if(count == 0) {
        throw new UserIsAnIdiotException(
                  "Problem exists between keyboard and chair.");
    }
    return cast(int) floor(mean);
}

Answer 2

хм ... как насчет вычисления среднего значения и округления до целого числа? round(mean(thearray)) В большинстве языков есть средства, позволяющие указать метод округления.

РЕДАКТИРОВАТЬ: Таким образом, получается, что этот вопрос действительно о предотвращении переполнения, а не о округлении. Позвольте мне прояснить, что я согласен с теми, кто сказал (в комментариях), что на практике беспокоиться не о чем, так как это происходит очень редко, и когда это происходит, вы всегда можете избежать неприятностей, используя больший тип данных

Я вижу, что несколько других людей дали ответы, которые в основном состоят из деления каждого числа в массиве на число в массиве, затем , суммируя их. Это тоже хороший подход. Но только для пинка, вот альтернатива (в псевдокоде C-ish):

int sum_offset = 0;
for (int i = 1; i < length(array); i++)
     sum_offset += array[i] - array[i-1];
// round by your method of choice
int mean_offset = round((float)sum_offset / length(array));
int mean = mean_offset + array[0];

Или другой способ сделать то же самое:

int min = INT_MAX, max = INT_MIN;
for (int i = 0; i < length(array); i++) {
     if (array[i] < min) min = array[i];
     if (array[i] > max) max = array[i];
}
int sum_offset = max - min;
// round by your method of choice
int mean_offset = round((float)sum_offset / length(array));
int mean = mean_offset + min;

Конечно, вам нужно убедиться, что sum_offset не переполняется, что может произойти, если разница между самым большим и самым маленьким элементами массива больше, чем INT_MAX. В этом случае замените последние четыре строки чем-то вроде этого:

// round by your method of choice
int mean_offset = round((float)max / length(array) - (float)min / length(array));
int mean = mean_offset + min;

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

Answer 3

Рассчитайте сумму, сложив числа и разделив их на число, с округлением:

mean = (int)((sum + length/2) / length;

Если вас беспокоит переполнение, вы можете сделать что-то вроде:

int mean = 0, remainder = 0
foreach n in number
   mean += n / length
   remainder += n % length
   if remainder > length
       mean += 1
       remainder -= length
if remainder > length/2
   mean += 1
print "mean is: " mean

обратите внимание, что это не очень быстро.

Answer 4

Гарантируется, что не переполнится:

length ← length of list
average ← 0
for each result in the list do:
    average ← average + ( result / length )
end for

Это приводит к значительным проблемам с точностью, если вы используете целые числа из-за усечения (среднее значение по шести четвертям равно 0)

Answer 5

ARM сборка. =] Не проверено. Не переполнится Когда-либо. (Надеюсь.)

Возможно, можно немного оптимизировать. (Может быть, использовать FP / LR?) = S Может быть, THUMB будет работать лучше здесь.

.arm

; r0 = pointer to array of integers
; r1 = number of integers in array
; returns mean in r0
mean:
stmfd sp!, {r4,r5}
mov r5, r1

mov r2, 0          ; sum_lo
mov r3, 0          ; sum_hi

cmp r1, 0          ; Check for empty array
bz .end

.loop:
ldr r4, [r0], #4
add r2, r2, r4
adc r3, r3, #0     ; Handle overflow
sub r1, r1, #1     ; Next
bnz .loop

.end:
div r0, r2, r3, r5 ; Your own 64-bit/32-bit divide: r0 = (r3r2) / r5
bx lr

Answer 6

Этот псевдокод находит среднее значение и покрывает проблему переполнения:

double avg = 0
int count = 0
for x in array:
    count += 1
    avg = avg * (count - 1) / count   // readjust old average
    avg += x / count                  // add in new number

После этого вы можете применить свой код округления. Если на вашем языке нет простого способа округления, то сработает что-то вроде этого (округляется, когда больше .5):

int temp = avg - int(avg)   // finds decimal portion
if temp <= 0.5
    avg = int(avg)          // round down
else
    avg = int(avg) + 1      // round up

Answer 7

Псевдокод для получения среднего :

double mean = 0
int count = 0
foreach int number in numbers
    count++
    mean += number - mean / count

round(mean) // rounds up
floor(mean + 0.5) // rounds up
ceil(mean - 0.5) // rounds down

Округление обычно включает добавление 0,5, затем усечение (пол), поэтому 3,5 округляет до 4. Если вы хотите от 3,5 до округлить до 3, выполните код округления самостоятельно, но в обратном порядке: отнимите 0,5, затем найдите потолок.

Редактировать: Обновленные требования (без переполнения)

Answer 8

Добро пожаловать. рыба, надеюсь, ваше пребывание будет приятным.

Следующий псевдокод показывает, как это сделать в случае, если сумма будет соответствовать целочисленному типу, и округлять до ближайшего целого числа.

В вашей выборке числа добавляют сумму к 16, деление на 3 дает вам 5 1/3, что округляет до 5.

sum = 0
for i = 1 to array.size
    sum = sum + array[i]
sum = sum / array.size
sum = round (sum)