Binomialkoeffizient iterativ/rekursiv

[WIaimy]

Hey zusammen!
Sitze grade an der folgenden Aufgabe:

Geben Sie eine long-Methode zur iterativen und rekursiven Berechnung des Binomialkoeffizienten für zwei int-Argumente m und k mit m>=k>=0 an.

Da meine beiden Methoden ein Ergebnis liefern, dass bei der Berechnung von (49 über 6) ~150.000 kleiner ist als gewollt, habe ich mir eine Methode geschrieben, die mir mit Hilfe einer rekursiven Fakultät-Methode eben den Binomialkoeffizienten berechnet. Es ist eine double-Methode geworden, weil ich bei der gleiche methode als long nur Mist rausbekommen - kann es sein, dass ich mit 49! aus dem Bereich von long rausgehe?
Meine Frage ist also:
Wo liegt der Fehler bei meinen beiden ersten Methoden? Eine Zeilenangabe würde mir schon reichen, dann setzte ich mich wieder dran...

import java.util.Scanner;

public class Aufgabe2 {

	public static void main(String[] args) {

		Scanner einlesen = new Scanner(System.in);
		System.out.println("M = ");
		int m = einlesen.nextInt();
		System.out.println("K = ");
		int k = einlesen.nextInt();
		System.out.println("\nIterativ: " + iterativ(m , k));
		System.out.println("Rekursiv: " + rekursiv(m , k));
		System.out.println("Fakultät / Iterativ2: " + iterativ2(m , k));
		
	}

	private static double iterativ(final int m, int k) {
		if (k == 0)
			return 1.0;
		else {
			double ergebnis = 1.0;
			for (int i = 1; i <= k; i++) {
				ergebnis *= 1.0*((m + (1 - i)) / i);
			}
			return ergebnis;
		}
	}

	private static double rekursiv(final int m, int k){
		if(k == 0)
			return 1.0;
		else
			return rekursiv(m, (k - 1)) * ((m + (1 - k)) / k);
		
	}
	
	private static double fakultät(int zahl){
		if(zahl == 0 || zahl == 1){
			return 1.0;
		}
		return 1.0*fakultät((zahl - 1)) * zahl;
	}
	
	private static double iterativ2(int m, int k){
		return 1.0*(fakultät(m) / (fakultät(k) * fakultät((m - k ))));
	}
}

edit: habe probeweise die oberen Methoden auch double gemacht, mit gleichem falschen Ergebnis

 

[Haave]

kann es sein, dass ich mit 49! aus dem Bereich von long rausgehe?

Ja, und zwar bei weitem. Lass dir mal Long.MAX_VALUE ausgeben, da komme ich auf 9223372036854775807. Fakultät 49 hingegen bringt es auf 6.082818640342675 * 10^62 - also deutlich mehr.

Deine fakultät()-Methode lässt sich übrigens kürzer schreiben; es genügt abzufragen, ob zahl == 0, denn wenn zahl == 1, wird ohnehin mal 1 gerechnet. Das "mal 1.0" im else kannst du dir auch sparen.

public static double factorial(int n) {
	if(n == 0) return 1.0;
	return n * factorial(n-1);
}

Zu Binomialkoeffizienten konkret kann ich leider nicht helfen.

 

[Andi_CH]

Hm also google bringt ausnahmsweise viele gute Treffer:

Das ist einer davon

Falls du die Fakultät wirklich für riesige Werte brauchst - das wurde hier schon einmal behandelt und damals habe ich eine Klasse geschrieben die beliebig grosse innteger Zahlen multibplizieren kann.
Ist allerdings schon eine Weile her und ich müsste die Klasse sicher genauer anschauen.