Поиск среднего массива ints

Question

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

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

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

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

Answer 1

Вычислить сумму путем сложения чисел, и деления на число их, с округлением:

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 2

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

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

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

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

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

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

В вашем примере числа добавить сумму до 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) 

Answer 4

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

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, затем найдите потолок.

Edit: Обновление требований (без переполнения)

Answer 5

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

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 6

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

// 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 7

Гарантированный не переполнить:

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

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

Answer 8

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