Von Andreas' answer:
Hier ist ein alter Algorithmus, der genau ist und nicht überläuft, wenn das Ergebnis für eine long long zu groß ist
unsigned long long
choose(unsigned long long n, unsigned long long k) {
if (k > n) {
return 0;
}
unsigned long long r = 1;
for (unsigned long long d = 1; d <= k; ++d) {
r *= n--;
r /= d;
}
return r;
}
Dieser Algorithmus auch in Knuth ist „The Art der Computerprogrammierung, 3. Auflage, Band 2: Seminumerische Algorithmen "Ich denke.
UPDATE: Es gibt eine kleine Möglichkeit, dass der Algorithmus auf der Linie überlaufen wird:
r *= n--;
für sehr große n. Eine naive obere Grenze ist sqrt(std::numeric_limits<long long>::max()), was eine n weniger als ungefähr 4.000.000.000 bedeutet.
Betrachten Sie n == 67 und k == 33. Der obige Algorithmus überläuft mit einem 64 Bit unsigned long long. Und dennoch ist die richtige Antwort in 64 Bits darstellbar: 14,226,520,737,620,288,370. Und der obige Algorithmus ist um seine Überlauf still, wählen (67, 33) zurückgibt:
8.829.174.638.479.413
Eine glaubwürdige, aber falsche Antwort.
Der obige Algorithmus kann jedoch leicht modifiziert werden, um niemals zu überlaufen, solange die endgültige Antwort darstellbar ist.
Der Trick besteht darin zu erkennen, dass bei jeder Iteration die Division r/d genau ist. Vorübergehend Umschreiben:
r = r * n/d;
--n;
Für diese genau zu sein, bedeutet es, wenn Sie r erweitert, n und d in ihre Primfaktorzerlegung, dann könnte man leicht d zunichte machen und mit einem modifizierten Wert für n gelassen werden, rufen es t, und dann ist die Berechnung von r einfach:
// compute t from r, n and d
r = r * t;
--n;
Eine schnelle und einfache Möglichkeit, dies zu tun, ist der größte gemeinsame Teiler von r und d, rufen sie finden g:
unsigned long long g = gcd(r, d);
// now one can divide both r and d by g without truncation
r /= g;
unsigned long long d_temp = d/g;
--n;
Jetzt können wir die s machen ame Sache mit d_temp und n (Finde den größten gemeinsamen Teiler). Da wir a-priori wissen, dass r * n/d genau ist, wissen wir auch, dass gcd (d_temp, n) == d_temp, und daher müssen wir es nicht berechnen. So können wir n durch d_temp teilen:
unsigned long long g = gcd(r, d);
// now one can divide both r and d by g without truncation
r /= g;
unsigned long long d_temp = d/g;
// now one can divide n by d/g without truncation
unsigned long long t = n/d_temp;
r = r * t;
--n;
Reinigung:
unsigned long long
gcd(unsigned long long x, unsigned long long y)
{
while (y != 0)
{
unsigned long long t = x % y;
x = y;
y = t;
}
return x;
}
unsigned long long
choose(unsigned long long n, unsigned long long k)
{
if (k > n)
throw std::invalid_argument("invalid argument in choose");
unsigned long long r = 1;
for (unsigned long long d = 1; d <= k; ++d, --n)
{
unsigned long long g = gcd(r, d);
r /= g;
unsigned long long t = n/(d/g);
if (r > std::numeric_limits<unsigned long long>::max()/t)
throw std::overflow_error("overflow in choose");
r *= t;
}
return r;
}
Jetzt können Sie berechnen, wählen (67, 33) ohne Überlauf. Und wenn Sie versuchen, wählen Sie (68, 33), erhalten Sie eine Ausnahme anstelle einer falschen Antwort.
für großes int siehe:
[http://stackoverflow.com/questions/1188939/representing-128-bit-numbers-in-c ] (http://stackoverflow.com/questions/1188939/representing-128-bit-numbers-in-c)
[http://stackoverflow.com/questions/1055661/bigint-bigbit-library](http: //stackoverflow.com/questions/1055661/bigint-bigbit-library)
[http://stackoverflow.com/questions/238343/big-number-in-c](http://stackoverflow. com/Fragen/238343/big-number-in-c)
– SjB