3

指定された数のいわゆる「三角数」を生成するこの関数があります。dequeのあとがきを印刷すると、数字が増え、ジャンプして、再び増えます。三角数は私が上がるにつれて決して低くならないはずなので、ある種のオーバーフローが起こっているに違いありません。if(toPush > INT_MAX) return i - 1;結果がオーバーフローした場合に関数がそれ以上の数値を生成しないようにする（そして生成された数値を返す）ように行を追加して修正しようとしました。ただし、これは機能していませんが、出力は引き続き正しくありません（しばらくの間増加し、低い数値にジャンプしてから、再び増加します）。私が追加した行は、実際には何もしていないようです。返品に到達していません。誰かがここで何が起こっているのか知っていますか？

#include <iostream>
#include <deque>
#include <climits>
int generateTriangleNumbers(std::deque<unsigned int> &triangleNumbers, unsigned int generateCount) {
    for(unsigned int i = 1; i <= generateCount; i++) {
         unsigned int toPush = (i * (i + 1)) / 2;
         if(toPush > INT_MAX) return i - 1;
         triangleNumbers.push_back(toPush);
    }
return generateCount;
}
4

3 に答える 3

2

INT_MAXの最大値ですsigned int。unsigned int（ ）の最大値の約半分UINT_MAXです。の計算は、値を2乗するtoPushよりもはるかに高くなる可能性があります（結果が近い場合は、保持できる値よりもはるかに大きくなります）。この場合、ラップアラウンドし、前の値よりも小さい値になります。UINT_MAXINT_MAXUINT_MAXtoPushtoPush

まず第一に、あなたのタイプはではなく、であるため、との比較にINT_MAXは欠陥があります。第2に、 （比較式の左のオペランド）が最大値を超える値を保持できることを意味するため、との比較でさえ正しくありません。これは不可能です。正しい方法は、生成された番号を前の番号と比較することです。それが低い場合は、オーバーフローが発生していることがわかっているので、停止する必要があります。unsigned intsigned intUINT_MAXtoPush

さらに、より広い範囲の値を保持できるタイプ（などunsigned long long）を使用することもできます。

于 2013-03-08T09:59:03.323 に答える
1

92682番目の三角数はすでに。より大きくなっていますUINT32_MAX。しかし、ここでの犯人は、の計算においてはるかに早いですi * (i + 1)。そこで、65536番目の三角数の計算がオーバーフローします。Pythonにネイティブのbignumサポートを要求すると：

>>> 2**16 * (2**16+1) > 0xffffffff
True

おっと。次に、保存されている数値を調べると、シーケンスが低い値に戻っていることがわかります。Pythonで、このケースの動作について標準が述べていることをエミュレートしようとするには、次のようにします。

>>> (int(2**16 * (2**16+1)) % 0xffffffff) >> 1
32768

これは、65536番目の三角数に表示される値ですが、これは正しくありません。

ここでオーバーフローを検出する1つの方法は、生成する数列が単調であることを確認することです。つまり、生成されたN番目の三角数が（N-1）番目の三角数よりも厳密に大きい場合です。

オーバーフローを回避するには、64ビット変数を使用してそれらを生成および保存するか、大量の三角数が必要な場合は大きな数のライブラリを使用できます。

于 2013-03-08T09:58:22.027 に答える
0

Visual C ++ int（そしてもちろんunsigned int）では、64ビットコンピューターでも32ビットです。

unsigned long longまたはを使用uint64_tして64ビット値を使用します。

于 2013-03-08T09:47:23.027 に答える