# Binomialkoeffizient unter Verwendung des ggT



## densei (31. Okt 2010)

Hallo liebe Forums Mitglieder,

ich habe ein Problem - ich soll ein Programm vervollständigen das den Binominalkoeffizient errechnen und den Überlauf verhindern unter Verwendung des ggT. Ich habe soweit auch das Programm geschrieben nur bekomme ich es nicht zum laufen. Ich wäre für jeden Tip dankbar. 

```
public class Binom {

    private static long binom(int m, int k) {
        long binom = 1;
        long i,fac;
        long res = 1;

        k = Math.min(k, m-k);

        for ( i=1; i<=k; i++){
        	fac = m-i+1;
        	binom = Binom.ggT(fac, i);
        	res /= i/binom;
        	res *= fac/binom;
        
        					
        	}
        
        return binom;
    }


	private static long ggT(long a, long b) {
		if (b==0){
	        return a;
		}
	    else
	    {
	    	return ggT(b, a%b);
	    }
	}


    public static void main(String[] args) {
       [B] int m = Integer.parseInt(args[0]);[/B]
            
        System.out.printf("%21d = %s%n",  Long.MAX_VALUE, "Long.MAX_VALUE");
        System.out.printf("%21d = %s%n",  m,              "m");

        for (int k = 0;   k <= m;   ++k) {
            System.out.printf("%21d = (%2d aus %2d)%n", binom(m,k), k, m);
        }
    }
}
```


sobald ich das in Eclipse oder auch mit der Konsole ausführe bekomme ich diese Meldung:


```
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
	at Binom.main(Binom.java:35)
```

Ich wäre euch sehr dankbar wenn mir jemand sagen könnte ob ich mit dem Programm komplett auf dem Holzweg bin oder warum diese doof Fehlermeldung kommt. Die besagte Zeile habe ich mal hervorgehoben.

Beste Grüße 
Dennis


----------



## Haave (31. Okt 2010)

Meine ganz blöde Vermutung:
Du übergibst beim Starten des Programmes kein Argument, so dass es für Integer.parseInt() nichts zu parsen gibt?

Wenn du es mit der Konsole ausführst, schreibst du dann etwas wie [c]java Binom 4711[/c]?


----------



## densei (1. Nov 2010)

Vielen Dank für den Tip ... die Vermutung war gold richtig 

Habe das ganze jetzt noch einmal neu gecodet und es funktioniert Einwand frei. Aber ohne den Tip wär ich nicht drauf gekommen. Also noch mal sehr vielen Dank . 

Fals es jemand interessiert:


```
public class Binom {

    private static long binom(int m, int k) {
    	
    	long binom = 1;                        
    	long i = 1;
    	long nenner, zähler;
        long binom_test;

        k = Math.min(k, m-k);                     // Ganzzahlige Binomialkoeffizienten sind symmetrisch im Sinne von (m,k) = (m, m-k) für alle nicht negativen m und k!      
        
        if (k==0){
            return binom = 0;
        }

        else{
        
        while (i<=k){                           // Rekursion: ((m/1) * ((m-1)/2) * ((m-2)/3)) = (m-k+1)/k  -> hier i = k
        	
        	zähler = m-i+1;
        	nenner = i;                                        
        	zähler = zähler / Binom.ggT(i, m-i+1);     // Kürzen mit ggT(nenner,zähler) um Überlauf zu verhindern
        	nenner = nenner / Binom.ggT(i, m-i+1);
        	binom = binom/nenner;
        	binom_test = binom;                   // Vorheringer Binomialkoeffizient sichern zum späteren vergleich ob Überauf statt fand ( wenn neuer Koeffizient kleiner als der alter!)  
        	binom = binom*zähler;					
        	i++;
        	
        	if (binom_test>binom){             // Test ob Überlauf statt fand!
        		binom = -1 ;
        		break;
        	}
        	
        }
        
        	
        return binom;                       // Rückgabe Binominalkoeffizient: Bei Überlauf: -1 | 
        }
        
    }
        


	private static long ggT(long a, long b) {              // Rekursiver Bestimmung ggT 
		if (b==0){
	        return a;
		}
	    else
	    {
	    	return ggT(b, a%b);
	    }
	}


    public static void main(String[] args) {
        int m = Integer.parseInt(args[0]);
            
        System.out.printf("%21d = %s%n",  Long.MAX_VALUE, "Long.MAX_VALUE");
        System.out.printf("%21d = %s%n",  m,              "m");

        for (int k = 0;   k <= m;   ++k) {
            System.out.printf("%21d = (%2d aus %2d)%n", binom(m,k), k, m);
        }
    }
}
```


----------



## Rheumakay (1. Nov 2010)

Hallo,

hab gerade diesen Eintrag hier gefunden und der hat mir ansich schon sehr weitergeholfen, danke dafür schon mal.
Allerdings hab ich noch folgendes Problem:

Ich habe den oben stehenden Code per copy&paste in meinen Editor übernommen und will ihn nun in der Konsole mit javac Binom.java compilieren. Nun gibt mir aber die Konsole folgende Fehlermeldungen aus:

1. ERROR in Binom.java (at line 58)
	System.out.printf("%21d = %s%n",  Long.MAX_VALUE, "Long.MAX_VALUE");
	           ^^^^^^
The method printf(Locale, String, Object[]) in the type PrintStream is not applicable for the arguments (String, long, String)
----------
2. ERROR in Binom.java (at line 59)
	System.out.printf("%21d = %s%n",  m,              "m");
	           ^^^^^^
The method printf(Locale, String, Object[]) in the type PrintStream is not applicable for the arguments (String, int, String)
----------
3. ERROR in Binom.java (at line 62)
	System.out.printf("%21d = (%2d aus %2d)%n", binom(m,k), k, m);
	           ^^^^^^
The method printf(String, Object[]) in the type PrintStream is not applicable for the arguments (String, long, int, int)

da ich leider absoluter Javanoob bin, kann ich damit nix anfangen, wäre nett wenn jmd von Euch eine Idee hat warum das ned funktioniert bzw. mir das erklären kann.

Vielen Dank schon mal im Vorraus 

Mit freundlichen Grüssen 

Rheumakay


----------



## Andi_CH (2. Nov 2010)

Rheumakay hat gesagt.:


> 1. ERROR in Binom.java (at line 58)
> System.out.printf("%21d = %s%n",  Long.MAX_VALUE, "Long.MAX_VALUE");
> ^^^^^^
> The method printf(Locale, String, Object[]) in the type PrintStream is not applicable for the arguments (String, long, String)



Bei mir funktioniert das problemlos

9223372036854775807 = Long.MAX_VALUE

Auch wenn ich vermute, dass da bei %n noch was hingehört


----------



## isjetzegal (2. Nov 2010)

ich hab auch ne frage: ich hab desselbe problem:
ich hab desselbe Programm, anders geschrieben und jetz wollt ich fragen, was ich falsch hab
eclipse sagt mir, dass keine formalen fehler drin sin, ich kanns schließlich auch kompilieren, wenn ichs dann aber ausprobier sagt er mir: main class: Binom (wrong name) not found program will exit. ...und noch viele andere sachen 
könnt ihr mir vllt sagen, was da mein fehler is... ich komm einfach nicht mehr weiter -.-


----------



## Andi_CH (2. Nov 2010)

Schon mal Project - clean gemacht?

Ohne den ganzen Code zu haben kann ich sicher nichts sagen .....

zippen und Mailen? dann kann ich mal reinschauen


----------

