4

int の配列があるとします (固定サイズの int を持つ任意の言語で)。平均値に最も近い int をどのように計算しますか?

編集：明確にするために、結果は配列に存在する必要はありません。つまり、入力配列 [3, 6, 7] の場合、期待される結果は 5 です。また、特定の丸め方向を指定する必要があると思います。2 つの数値が等しく近い場合は、切り捨てます。

編集：これは宿題ではありません。私は5年間宿題を出していません。スタックオーバーフローは初めてなので、よろしくお願いします！

編集:合計と除算の明らかなアプローチはオーバーフローする可能性があるため、大きな配列と大きな整数の両方について、オーバーフローセーフなアプローチを考えようとしています。オーバーフローを正しく処理すること (ごまかしたり別の型を使用したりせずに) は、この問題の最も難しい部分だと思います。

4

8 に答える 8

5

これは、高速で、適度にオーバーフローセーフであり、要素の数が事前にわからない場合に機能する方法です。

// 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);
}
于 2009-02-21T03:32:36.137 に答える
2

ええと...平均を計算してから整数に丸めるのはどうですか？round(mean(thearray))ほとんどの言語には、丸め方法を指定できる機能があります。

編集：したがって、この質問は実際には、丸めではなく、オーバーフローを回避することに関するものであることがわかります。（コメントで）実際には心配することはめったにないので、心配する必要はないと言っている人たちに同意します。そうなると、より大きなデータ型を使用することでいつでも回避できます。

基本的に、配列内の各数値を配列の数で割ってから、それらを合計するという答えを他の何人かが与えていることがわかります。それも良いアプローチです。しかし、キックのためだけに、ここに代替案があります（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より大きい場合に発生する可能性があります。その場合、最後の4行を次のように置き換えます。

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

雑学：この方法、またはそのような方法は、要素が密集している配列の平均を精神的に計算する場合にも非常にうまく機能します。

于 2009-02-21T02:45:22.523 に答える
2

数値を合計し、それらの数値で割って、四捨五入して合計を計算します。

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

これはあまり高速ではないことに注意してください。

于 2009-02-21T02:34:56.790 に答える
1

オーバーフローしないことが保証されています:

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

切り捨てが原因で int を使用している場合、精度に重大な問題があります (6 つの 4 の平均は 0 になります)。

于 2009-02-21T03:40:04.153 に答える
0

いらっしゃいませ。魚、あなたの滞在が楽しいものであることを願っています。

次の擬似コードは、合計が整数型に収まる場合にこれを行う方法を示しており、最も近い整数に丸められます。

サンプルでは、​​数値は合計を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)
于 2009-02-21T02:54:39.160 に答える
0

平均を取得するための擬似コード：

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を引いてから、上限を求めます。

編集：更新された要件（オーバーフローなし）

于 2009-02-21T03:00:18.227 に答える
0

この疑似コードは平均を見つけ、オーバーフローの問題をカバーします。

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
于 2009-02-21T03:17:33.833 に答える
0

アームの組み立て。=] 未テスト。オーバーフローしません。これまで。（私は願います。）

おそらく少し最適化できます。(多分 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
于 2009-02-21T04:44:27.277 に答える