Frage Wegen Binomialkoeffizienten

[kannkeinjava]

Also ich möchte das Programmieren.

Nur mein Problem ist ich weiß nicht genau wie.

Ich möchte keine direkte Lösung möchte nur paar Hinweise

Ich versuche es über die Fakultäten, aber irgendwie kommt es mir komisch vor.

könnt ihr mir helfen????????????????????????????? :cry:

 

[Gast]

Was wilst du jetzt genau haben? Einen effektiven Algo zur Binomialkoffzienten Berechnung? Eine Datenstruktur? Tipps zur Performance?...

 

[kannkeinjava]

am besten alle drei Sachen

1.Wie sollte man es Programmieren
also wie sollte ich da rangehen.

 

[Prismapanda]

Wie sehen denn deine Versuche bisher aus? Du findest eigentlich alles was du brauchst auch im Wikipedia Artikel. Wenn du konkrete Probleme hast (z.B. beim Berechnen einer Fakultät) dann bennene diese doch...

 

[kannkeinjava]

class Binomial
{
	public static void main(String args[])
	{
		int k;/*Zahl k*/
		int n;/*Zahl n über*/
		int i;/*Zähler*/
		int u;/*Hilfvariable*/
		int g;/**/
		System.out.println("Geben sie eine Zahl für n ein");
		n=IO1.einint();/*Zahl wird von der Tastatur eingelesen*/
		do
		{
			System.out.println("Bitte geben sie eine Zahl für k ein die nicht größer als n ist");
			k=IO1.einint();/*Zahl wird von der Tastatur eingelesen.*/
			if(k>n)
			System.out.println("Fehler geben sie einen kleiner Werte als n ein");
		}	while(k>n);
	}
}

bin noch ganz am Anfang

weiß jetzt erstmal nicht weiter muss mir glaube ich noch einiges überlegen und

 

[Final_Striker]

du hast doch jetzt n, k und die formel zur berechnung des binominalkoeffizienten, was ist denn genau das problem?

 

[SlaterB]

löse vielleicht erstmal eine einfachere Aufgabe:

Schreibe ein Programm, welches genau eine Fakultät ausrechnet.

 

[xysawq]

also die Definition:

(n über k) = (n/1) * ((n-1)/2) * ... * ((n -k +1)/k)
finde ich schonmal super, wer mitgedacht hat kann ne schöne Schleife draus bauen.

int nUeberK = 0;
int n = 0;
int k = 0;

//n und k Einlesen und auf Richtigkeit überprüfen

for(int i=1; i<=k ; i++)
{
	nUeberK += ((n -i +1)/i);
}

Und das wars dann glaube ich.

 

[kannkeinjava]

löse vielleicht erstmal eine einfachere Aufgabe:

Schreibe ein Programm, welches genau eine Fakultät ausrechnet.

Fakultät kann ich auswenig

 

[kannkeinjava]

du hast doch jetzt n, k und die formel zur berechnung des binominalkoeffizienten, was ist denn genau das problem?

Die formel weiß nicht wie ich sie shcreiben soll

 

[0x7F800000]

@xysawq:
die idee aus der wikipedia ist schonmal besser als die mit fakultäten, allerdings kannst du das mit integern nicht direkt durchziehen, denn: obwohl am ende eine ganze zahl rauskommt, sind alle zwischenergebnisse echte brüche, und diese werden durch rundungsfehler kaputtgemacht. Wenn du es so direkt rechnen willst, brauchst du eine eigene klasse für Rationale zahlen, die Bruchrechnung ohne rundungsfehler beherrscht.

...Oder aber auch, man schreibt sich nur die ggT-methode, und betrachtet den zaehler und nenner separat, und kürzt hin und wieder, damit die zahlen nicht explodieren:

import java.util.*;
import java.io.*;

public class MathForNaturalNumbers {
	
	/** gcd
	 * calculates the greatest common divisor of two numbers
	 * @param:		natural numbers a and b
	 * @return:		greatestCommonDivisor of a and b
	 */
	public static long gcd(long a, long b){
		while((b=a%(a=b))!=0);
		return a;
	}

	/** binomial coefficient
	 * 
	 * @param n 	cardinality of a finite set
	 * @param k      cardinality of a subset
	 * @return		number of subsets with cardinality k from a set with cardinality n
	 */
	public static long binomialCoefficient(long n, long k){
		
		if(k<0 || k>n) return 0L;			//nonsence input
		
		long n_minus_k=n-k;					//does not make sense to calculate it all the time
		long numerator=1, denominator=1;	//fraction
		long gcd=1;
		for(long i=1; i<=k; i++){
			numerator*=(i+n_minus_k);
			denominator*=i;
			
			//divide the greatest common divisor out of the fraction
			//to prevent overflow errors
			gcd=gcd(numerator,denominator);
			numerator/=gcd;
			denominator/=gcd;
		}
		return numerator;					//in the end, denominator is always 1
	}
	
	/** main
	 * 
	 */
	public static void main(String[] args){
		long n=7;
		for(long i=0; i<=n; i++){
			System.out.print(binomialCoefficient(n,i)+" ");
		}
	}
}

@kannkeinjava:

Fakultät kann ich auswenig

du held^^ :autsch:
dir sollte man verwendung der main-methode, variablennamen die kürzer als 24 buchstaben sind, sowie alle deutschen wörter verbieten, andernfalls gewöhnst du dir diesen mist wohl nie ab

 

[Marco13]

.... woran man die Problematik besonders deutlich sieht, die hinter dem Wort "auswen(d)ig" steckt....

 

[kannkeinjava]

Das ist mein Programm

class Binomial
{
	public static void main(String args[])
	{
		int k;/*Zahl k*/
		int n;/*Zahl n über*/
		int i;/*Zähler*/
		int u;/*Hilfvariable*/
		int g;/**/
		int NüberK=0;/*N über k*/
		System.out.println("Geben sie eine Zahl für n ein");
		n=IO1.einint();/*Zahl wird von der Tastatur eingelesen*/
		do
		{
			System.out.println("Bitte geben sie eine Zahl für k ein die nicht größer als n ist");
			k=IO1.einint();/*Zahl wird von der Tastatur eingelesen.*/
			if(k>n)
			System.out.println("Fehler geben sie einen kleiner Werte als n ein");
		}	while(k>n);
		for(i=0;i<=k;i++)
		{
			NüberK+=((n-i+1)/i);
		}
		System.out.println("Ihr n über k lautet:"+NüberK);	
	}
}

Geben sie eine Zahl f³r n ein
4
Bitte geben sie eine Zahl f³r k ein die nicht gr÷▀er als n ist
3
Exception in thread "main" java.lang.ArithmeticException: / by zero
at Binomial.main(Binomial.java:22)

Was hat dieser Fehler zu bedeuten????????

 

[0x7F800000]

ääh? welches der drei wörter ist dir denn unklar "Arithmetic", "Exception" oder "zero" ? http://dict.leo.org/

 

[Marco13]

Dass in Zeile 22 irgendwas durch 0 geteilt wird. Durch was wird da geteilt? Durch 'i'. Was ist i am Anfang der Schleife? 0. Könnte da ein kausaler Zusammenhang bestehen? Hat xysawq vielleicht was anderes gepostet?

 

[kannkeinjava]

class Binomial
{
	public static void main(String args[])
	{
		int k;/*Zahl k*/
		int n;/*Zahl n über*/
		int i;/*Zähler*/
		int u;/*Hilfvariable*/
		int g;/**/
		int NüberK=0;/*N über k*/
		System.out.println("Geben sie eine Zahl für n ein");
		n=IO1.einint();/*Zahl wird von der Tastatur eingelesen*/
		do
		{
			System.out.println("Bitte geben sie eine Zahl für k ein die nicht größer als n ist");
			k=IO1.einint();/*Zahl wird von der Tastatur eingelesen.*/
			if(k>n)
			System.out.println("Fehler geben sie einen kleiner Werte als n ein");
		}	while(k>n);
		for(i=1;i<=k;i++)
		{
			NüberK+=((n-i+1)/i);
		}
		System.out.println("Ihr n über k lautet:"+NüberK);	
	}
}

habe jetzt ein Ergebnis
doch leider ist es falsch

hier ist mein Ergebnis ,aber es ist leider falsch

Geben sie eine Zahl f³r n ein
4
Bitte geben sie eine Zahl f³r k ein die nicht gr÷▀er als n ist
3
Ihr n ³ber k lautet:5

 

[0x7F800000]

Durch was wird da geteilt? Durch 'i'. Was ist i am Anfang der Schleife? 0. Könnte da ein kausaler Zusammenhang bestehen?

Aber keineswegs doch! Was für abstruse vermutungen versuchen Sie hier durch ihre Frage zu suggerieren? Teilung durch 0 löst doch nie im Leben eine ArithmetikException aus, ich bitte Sie, hören Sie doch uf damit, Marco13^^ :lol:

hier ist mein Ergebnis ,aber es ist leider falsch

garbage in=garbage out
würdest du dir (und dem rest der menschheit) bitte den gefallen machen, und die formel mal in der wikipedia nachschlagen, wenn du nicht in der lage bist, diese selbst ordentlich aufzustellen?

 

[kannkeinjava]

o.k. jetzt habe ich es glaube ich verstanden

 

[Guest]

Jetzt müßte alles stimmen

class Binomial 
{ 
   public static void main(String args[]) 
   { 
      int k;/*Zahl k*/ 
      int n;/*Zahl n über*/ 
      int i;/*Zähler*/ 
      int u;/*Hilfvariable*/ 
      int g;/**/ 
      int gfak=1;
      int NüberK=0;/*N über k*/ 
      int nfak=1;
      int kfak=1;
      System.out.println("Geben sie eine Zahl für n ein"); 
      n=IO1.einint();/*Zahl wird von der Tastatur eingelesen*/ 
      do 
      { 
         System.out.println("Bitte geben sie eine Zahl für k ein die nicht größer als n ist"); 
         k=IO1.einint();/*Zahl wird von der Tastatur eingelesen.*/ 
         if(k>n) 
         System.out.println("Fehler geben sie einen kleiner Werte als n ein"); 
      }   while(k>n); 
      g=n-k;
      System.out.println("ihr g lautet:"+g);
      for(i=1;i<=g;i++)
      {
      	gfak=gfak*i;
      }	System.out.println("Ihr gfak lautet:"+gfak);
      for(i=1;i<=n;i++)
      {
      	
      	nfak=nfak*i;
      }	System.out.println("nfak lautet:"+nfak);
      for(i=1;i<=k;i++)
      {
      	kfak=kfak*i;      	
      }	System.out.println("kfak=:"+kfak);
      NüberK=nfak/(kfak*(g));
      System.out.println("Ihr Nüberk lautet:"+NüberK);
    } 
}

Meine Ausgaben lauten:
Geben sie eine Zahl f³r n ein
4
Bitte geben sie eine Zahl f³r k ein die nicht gr÷▀er als n ist
3
ihr g lautet:1
Ihr gfak lautet:1
nfak lautet:24
kfak=:6
Ihr N³berk lautet:4

Danke an alle und sorry wenn ich einige Leue genervt haben sollte

 

[SlaterB]

schreibe dir wenn überhaupt eine Hilsfmethode

public int rechneFakAus(int k) {
..
}

aber mehr als Fakultät von 15 passt in int gar nicht rein,
wenn du die intelligente gekürzte Formal nehmen würdest, wäre etwas mehr möglich,
z.B.
(16 über 1) = 16 // zweimal editiert, ich kann eben schlecht raten ob nun 16 über 0 oder 16 über 1..

sowas kannst du schon nicht mehr ausrechnen

edit: ich sehe gerade, dass es auch weiter unten nicht hinhaut 5 über 0 oder 5 über 5 ..,
gfak benutzt du überhaupt nicht..

 

[Ariol]

http://www.galileocomputing.de/open...02_001.htm#mjb48da7da4c1eb8483942a9c4a980d8d5

 

[Guest]

class Binomial 
{ 
   public static void main(String args[]) 
   { 
      int k;/*Zahl k*/ 
      int n;/*Zahl n über*/ 
      int i;/*Zähler*/ 
      int u;/*Hilfvariable*/ 
      int g;/**/ 
      int gfak=1;
      int NüberK=0;/*N über k*/ 
      int nfak=1;
      int kfak=1;
      System.out.println("Geben sie eine Zahl für n ein"); 
      n=IO1.einint();/*Zahl wird von der Tastatur eingelesen*/ 
      do 
      { 
         System.out.println("Bitte geben sie eine Zahl für k ein die nicht größer als n ist"); 
         k=IO1.einint();/*Zahl wird von der Tastatur eingelesen.*/ 
         if(k>n) 
         System.out.println("Fehler geben sie einen kleiner Werte als n ein"); 
      }   while(k>n); 
      g=n-k;
      System.out.println("ihr g lautet:"+g);
      for(i=1;i<=g;i++)
      {
      	gfak=gfak*i;
      }	System.out.println("Ihr gfak lautet:"+gfak);
      for(i=1;i<=n;i++)
      {
      	
      	nfak=nfak*i;
      }	System.out.println("nfak lautet:"+nfak);
      for(i=1;i<=k;i++)
      {
      	kfak=kfak*i;      	
      }	System.out.println("kfak=:"+kfak);
      NüberK=(nfak/(kfak*gfak));
      System.out.println("Ihr NüberK lautet:"+NüberK);
    } 
}

Geben sie eine Zahl f³r n ein
6
Bitte geben sie eine Zahl f³r k ein die nicht gr÷▀er als n ist
3
ihr g lautet:3
Ihr gfak lautet:6
nfak lautet:720
kfak=:6
Ihr N³berK lautet:20

 

[Gast]

danke an alle,aber jetzt müsste alles stimmen


bye

 

[0x7F800000]

      int k;/*Zahl k*/
      int n;/*Zahl n über*/
      int i;/*Zähler*/
      int u;/*Hilfvariable*/
      int g;/**/
      int gfak=1;
      int NüberK=0;/*N über k*/
      int nfak=1;
      int kfak=1;

hätte man's irgendwie noch abgefakter machen können^^ :autsch: :applaus: :autsch:

 

[Ariol]

public static void main(String[] args)
	{
		int k, n, i, g, gf = 1, nf = 1, kf = 1, nk = 1;
		String s1="Geben sie eine Zahl für n ein",
                         s2="Bitte geben sie eine Zahl für k ein die nicht größer als n ist",
                         s3="Fehler geben sie einen kleiner Werte als n ein",
                         s4="ihr g lautet:",
                         s5="Ihr gfak lautet:",
                         s6="nfak lautet:",
                         s7="kfak=:",
                         s8="Ihr NüberK lautet:";
		Scanner s = new Scanner(System.in);
		
		System.out.println(s1);
		n = s.nextInt();
		while(true)
		{
			System.out.println(s2);
			k = s.nextInt();
			if (k > n)System.out.println(s3);
			else break;
		}
		g = n - k;
		System.out.println(s4 + g);
		for (i = 1; i <= g; i++)gf *= i;
		System.out.println(s5 + gf);
		for (i = 1; i <= n; i++)nf *= i;
		System.out.println(s6 + nf);
		for (i = 1; i <= k; i++)kf *= i;
		System.out.println(s7 + kf);
		nk = (nf / (kf * gf));
		System.out.println(s8 + nk);
	}

 

[Gast]

ja hätte etwas weniger Variablen nehmen könne bzw. sollen so hätte ich mehr Rechenzeit gespart

 

[0x7F800000]

vergiss grad die rechenzeit... wenn du nach 100 Zeilen code in unsinnigen variablennamen, redundanten codestücken und mangelhaften commentaren absäufst, wirst du keine Aufgabe bekommen, bei der es auch im geringsten auf die performance ankommt. Schreib die Programme einfach so, dass sie für Menschen verständlich sind.

@Ariol: oohje, mach bitte die riesenzeile weg, wenn's dir keine umstände macht

 

[xysawq]

Ich entschuldige mich wahnsinnig für meinen Fehler Integer zu wählen, obwohl ich Bruchrechnung durchführe, aber im Grunde soll unser JAVA-Frieak hier ja auch selber lernen und hätte das bei richtiger Umsetzung dann auch gemerkt... nicht... (Eigentlich hatte ich ja diese "blablabla... not"-Witze, aber hier passt es.)

EDIT: OH MEIN G... G... GÜTIGER MORGENKAFFEE!!! Was sehe ich denn da???

int NüberK;

Eine Variable mit Ü... MIT Ü!!!

Wer um alles in der Welt hat dir Programmieren beigebracht???

EDIT2: Müsste "Fehler geben sie einen kleiner Werte als n ein" nicht eigentlich "Fehler! Geben Sie einen kleineren Wert als n ein!" heißen?

 

[Landei]

Kleiner Tipp:
Niemals Schleifenvariablen außerhalb definieren. *Niemals*!
Also oben das i weglassen, und stattdessen

   for (int i = 1; i <= g; i++)gf *= i;

schreiben.
Das Problem ist, dass das i mit einem willkürlichen Wert außerhalb der Schleife sichtbar ist und Unheil stiften kann. Das Gleiche gilt für Iteratoren (insbesondere wenn man mit älterem Code zu tun hat). Habe schon so oft Bugs gesehen nach dem Schema:

Iterator i = ...;
while(i.hasNext()) {...}
...
Iterator ii=  ...;
while(i.hasNext()) {...} //ups, typo