Berechnung des Pascal'schen Dreiecks

_Ocin_

Hi Leute, hab ein Problem.

Es gehts ums pascal'sche Dreieck:

1. 1
2. 1 1
3. 1 2 1
4. 1 3 3 1
5. 1 4 6 4 1
6. 1 5 10 10 5 1
...

Ich brauch ne Formel um die Zahl im Dreieck an jeder Stelle in jeder Zeile zu berechnen!
Also wenn ich zum beispiel sag ich brauch die 17. Zahl in der 48. Spalte wie kann ich das dann berechnen ohne vorher alles durchzurechnen.

Ich brauch es mindestens bis Zeile 10.000 deshalb kommt zwischenspeichern oder jedesmal neu berechnen nicht in Frage.

Danke schonmal... mfg Nico

Jester

Im Pascalschen Dreieck steht in Zeile n, Spalte k die Zahl n über k. Das ist definiert als $\frac{n!}{(n-k)!k!}$

MfG Jester

_Ocin_

Also ich bin schonmal froh das es ne Möglichkeit gibt jede Zahl direkt zu berechnen!

Aber kannst du mir bitte etwas genauer erklären was

Das ist definiert als [latex]\frac{n!}{(n-k)!k!}[latex]

bedeutet ?
x! ist Fakultät das weis ich .... gibts da schon ne Funktion für (C++) sonst muss ich eine selber schreiben, ist ja nicht so schlimm ...

Danke

Jester

Ups, war ein Fehler in den Tags. Jetzt sollte es richtig zu lesen sein. Fakultät mußte Dir selbe schreiben, sollte ja aber kein Problem sein.

Viel Erfolg,
Jester

_Ocin_

ah danke jetzt wo ich das richtig lesen kann siehts ja ganz einfach aus ^^
Danke

PS: Faktultät bekomm ich hin! Wollte nur fragen obs da schon nen schnellen Alg. gibt ...

_Ocin_

Jetzt hab ich aber doch noch ne Frage:

Ich hab ja schon gesagt das ich bis mindestens 10.000 wollte, aber wenn ich dann Fakultät von 10.000 brauch wird das meine ints sicher sprengen.

Weist du vielleicht wie weit ich bei int komme oder wie ich es sonst machen kann (bigint) ?

Jester

Zum einen kannst Du natürlich mal anschaun was n!/(n-k)! ist. Das iost was wesentlich kürzeres, nämlich: n*(n-1)...(n-k+1), alles andere kürzt sich weg. Außerdem kannst Du versuchen frühzeitig auch k! rauszudividieren. Also das ganze Teil auf einem berechnen. Damit kommst Du schon ein bißchen weiter. Leider sind diese Binomialkoeffzienten trotzdem recht schnell sehr groß. Du kannst es je nach Compiler ja mal mit ner 64-Bit-Zahl versuchen, damit kommste auch shcon ein Stück weiter, aber bis 10000 auf keinen Fall. Mein Vorschlag wäre: schreib Dir den Code erstmal für int, dann machste aus dem int ein T und aus der Funktion ein template und dann schauste Dich mal um was es für Klassen für große Zahlen gibt.

Achso, möglocherweise bietet aber auch irgendeine Mathebibliothek die Möglichkeit an die Binomialkoeffizienten direkt rauszugeben.

MfG Jester

Walli

EDIT: Jester war schneller und dabei ausführlicher .

Spontaner Einfall

template<typename T>
T C(unsigned n, unsigned k)
{
	if(k > n)
		return 0;
	if(k == n)
		return 1;

	T rval = 1;
	for(unsigned i = n; i != k; --i)
		rval *= i;
	for(unsigned i = n - k; i != 1; --i)
		rval /= i;

	return rval;
}

ethereal

du kannst doch bestimmt aus n! ein produkt mit einem faktor k! * i bzw. (n-k)! * i
basteln und dann geschickt ein paar fakultaeten kuerzen.
die mathe-freaks koennen dir da bestimmt genauere anweisungen geben, viel mir nur dazu gerade so ein.
richtig ist natürlich, dass du sehr schnell an werte gelangst, die die 2^16 o. ^32 übersteigen, aber es gibt auch feine bibliotheken, die das rechnen mit dicken zahlen ermöglichen. auch dazu gibt's hier freaks

ethereal

walli schrieb:

EDIT: Jester war schneller und dabei ausführlicher (als walli)

... und der war schneller als ich

Jester

Auch ein netter Trick, wenn man weiß wie groß das gewünschte n über k ist bzw. ne obere Schranke hat. Dann sucht man sich ne Primzahl p, die auf jeden Fall größer ist. Dann rechnet man modulo p. Das Ergebnis stimmt dann modulo p und weil es im richtigen Bereich von 0 bis p liegt isses auch das echt richtige Ergebniss. Dann braucht man allerdings ne gute Methode zum Invertieren. Die restliche Implementierung ist allerdings dann straight forward und dürfte auch ziemlich flotts ein.