✔ n über k

3

3Cyb3r

Erfahrenes Mitglied
Hi
ich bin gerade dabei eine möglichst gute n über k funktion zu schreiben

Code: 
int nubk (int n, int k) {
int i, erg=1;
    if((k==0)&&(n>=0))
        return 1;
    else if((k>=1)&&(k<=n)){
        for(i=1;i<=k;i++)
                erg*=(n-i+1)/i;
        //printf("%d \n",koeff);
        return erg;
    };          
  return 0; 
}

Dies funktionoiert nur beil kleine zHalen warum?
Mein Problem ist die Zeit vorher hatte ich das ganze iteratif gelöst nur ab einenm n von 30 rechnet sich ein Taschenrehcner Tod, da die Zeit exponetiell wächst -.-

Für alle die es nicht wissen n über k =
n! / k! * (n-k)!

so nun habe ich mir gedachte


Beispiel: nubk(30, 5) = 430!/(5!*(30-5)!) = (30*29*28...) / (1*2*3*4*5) = 30 / 1 * 29 / 2 * 28 / 3 ... / 5

Was ist an meiner Überlegung oder dem Code falsch?
bitte um Hilfe bei einem kleinen n kommt auch das richtige raus.
 
hmm meine Überlegung is ja falsch da können ja Brüche rauskomme hmm
d.h wenn ich nach gerade und ungerader Zahl unterscheide, erchne ich entweder von lniks nach rechts oder umgekehrt. damit ich auf genaue ergebnisse komme?
 
So mit folgendem Code funktioniert noch mehr aber dennoch nciht alles -.-

C: 
int nubk (int n, int k) {
/*  if( k == 0 && n >= 0)
    return 1;
  else if(k >= 1 && k <= n)
    return nubk(n-1, (k-1)) + nubk(n-1, k);
  return 0;*/
  
  
int i, erg=1,j=0;
    if((k==0)&&(n>=0))
        return 1;
    else if(n%2 == 1){
    if((k>=1)&&(k<=n)){
        for(i=1;i<=k;i++)
                erg*=(n-i+1)/i;
        //printf("%d \n",koeff);
        return erg;
    }}   
    else{
    if((k>=1)&&(k<=n)){
        for(i=k;i>=1;i--){
                erg*=(n-j)/i;
                j++;
        }
        //printf("%d \n",koeff);
        return erg;
    	}
    }
  return 0;  
}
 
Hallo,

probier es mal so:
C: 
int nubk (int n, int k) {
    int i, erg=1;
    if((k==0)&&(n>=0))
        return 1;
    else if(2*k>n)
        return nubk(n,n-k);
    else if((k>=1)&&(k<=n)){
        for(i=1;i<=k;i++) {
            erg*=n-i+1;
            erg/=i;
        }
        return erg;
    };
    return 0;
}

Grüße,
Matthias
 
Der Algorithmus ist schon gut, aber es gibt noch drei Verbesserungsmöglichkeiten:
1. Gegenüber dem Test if(2*k>n) ist der Test if(k>n/2) gegen Bereichsüberschreitung robuster.
2. Wenn man erg mit n statt mit 1 initialisiert, braucht die for-Schleife erst mit i=2 zu starten.
3. Wenn mindestens ein Parameter (n und/oder k) negativ ist, sollte die Funktion den Fehlerwert -1 zurückgeben.
 
Zuletzt bearbeitet:
Ok danke an alle habe das ganze jetzt soweit Optimiert,
doch mein Problem bleibt bestehen unzwar:

Ich führe das Programm auf einem CAS-Taschenrechner aus und wenn nun die Zahlen zu groß werden bei der Rechnung bekomme ich nur "schwachsinn",
da (meine Vermutung) der Microprozessor wahrscheinlich nur mit 8bit(evtl 16) Zahlen rechnen kann.

Meine Lösung ist ja nun Zwischenergebnisse in 2 oder mehr Variablen zu speicher und diese immer wieder zusammenzufügen wenn ich das richtig sehe
hmm nur wie?

Bin für weitere Hilfe dankbar
mfg
 
Das Problem bei obigem Algorithmus ist, dass wegen der Multiplikation Zwischenergebnisse generiert werden, die größer sind als das eigentliche Ergebnis. Um das zu vermeiden, kann man doppelte Rekursion verwenden. Der Binomialkoeffizient kann direkt aus dem Pascal'schen Dreieck abgelesen werden, und es gilt die Formel:

NüberK = N-1überK + N-1überK-1

Hier ist ein (ungetestets) Programm, das diese Vorgehensweise implementiert; die Zwischenwerte sind niemals größer als das Endergebnis. Eine Abfrage, ob 2*k>n ist, erübrigt sich, da dies den Rechenaufwand nicht beeinflusst.
C: 
int nubk (int n, int k)
{
  int erg;
  if ( n < 0 || k < 0 )
  { return -1; }
  if ((k==0) || (n==0))
  { return  1; }
  erg  = nubk(n-1,k  );
  erg += nubk(n-1,k-1);
  return erg;
}
Man kann sich die Zwischenvariable erg sparen und den Berechnungsterm direkt hinter das return-Statement schreiben, aber ich empfand es so als lebarer und ästhetischer :)
 
Sorry, ich würde auf nem Taschenrechner nicht empfehlen das Ganze mittels Rekursion zu lösen. Du wirst irgendwann an den Punkt kommen, da gibts nen Stackoverflow. Die Funktion ruft sich rekursiv immer wieder auf. Dabei wird jedes mal ein neuer Stackbereich für die Funktion reserviert und wird unvorhersehbar wieviel Speicher der braucht. Ich wette der erschöpft sich beim Taschenrechner schnell. Hab mal nen Algorithmus für Fibonacci zahlen rekursiv geschrieben und dann mit größeren Zahlen probiert. Der Stackoverflow kommt schneller als du glaubst.
Überhaupt mit ner Baumrekursion so wie du sie gebaut hast (2 Rekursionspfade - einer links einer rechts) wirds da aber schneller zu nem Stackoverflow kommen als du "bad practice" sagen kannst. Rekursionen sind bad practice. Du brauchst so gut wie nie Rekursionen - sie sind komplexer, schwerer zu verstehen. Genauso ist es schwachsinn Fibonacci Zahlen (so wie ichs probiert hab) oder die Fakultät rekursiv zu berechnen.
Hier ist ein interessantes Paper zum Vergleich von Fibonacci/Binomial Coefficient - Iterative vs. recursive. Und anhand der Berechnungen ist beim Binomial Koeffizient die iterative Variante effizienter.

http://www.google.de/url?sa=t&sourc...7KHPBA&usg=AFQjCNF_mLopBb5UE0R5dx5USZCbDcw0tw
 
Dass Rekursion den Stack belastet ist richtig, aber ganz so schlimm wie du es darstellst, ist es nicht. Die Rekursionstiefe ist maximal n, und die Rekursion ist linear, da die Aufrufe sequentiell abgearbeitet werden, ähnlich wie bei der Traversierung eines Baumes. Die Rekursion ist deswegen ineffizient, weil k*(n-k) Werte berechnet werden müssen, um das Ergebnis zu bekommen; ich habe sie auch nur darum angegeben, weil so nur Werte verwendet werden, die kleiner als das Ergebnis sind, damit ein Overflow möglichst vermieden wird, und Rekursion eine einfache Implementierung ermöglicht. Trotzdem kann ich deine Argumentation nachvollziehen und biete als Kompromiss eine iterative Version an.
Inwieweit das malloc auf dem Taschenrechner verwendet werden kann, kann ich nicht beurteilen. Wenn er kein eigenes Datensegment hat, muss der Speicherplatz dadurch reserviert bzw. freigegeben werden, dass der Stackpointer entsprechend erhöht bzw. erniedrigt wird, was allerdings wieder einen Stack-Overflow begünstigt.
C: 
#include <stdio.h>
#include <malloc.h>

// Berechnung des Binomialkoeffizienten
// mit Hilfe des Pascalschen Dreiecks
// ACHTUNG: Overflow wird nicht abgefangen
int KausN (int n, int k)
{
  // parameter check
  if ( n<0 || k<0 || n<k ) return 0;

  register int l1, l2;
  // l1 = min(k,n-k)
  // l2 = max(k,n-k)
  l1 = n-k;
  if ( l1 > k )
  { l2 = l1; l1 = k; }
  else     { l2 = k; }
  // triviale Werte abfragen
  // nicht notwendig, hilft aber nutzlose Berechnungen zu vermeiden,
  // unter anderem brauchen die Zeilen 0 bis 3 nicht berechnet zu werden
  if ( l1 == 0 ) return 1;
  if ( l1 == 1 ) return n;
  // Speicherplatz anfordern
  int *arr = (int*)malloc (sizeof(int)*(l1+1));
  if ( arr == NULL ) return -1;
  // Initialisierung
  // zur Berechnung der Zeile 4 ist die Einbeziehung der Zeile 2 notwendig,
  // um die Schrumpfung komplett abzuarbeiten (4/2=2)
  register int i,j;
  i = 0;
  arr[i++] = 1;
  arr[i++] = 2;
  arr[i++] = 1;
  for ( ; i <= l1; i++ )
  { arr[i] = 0; }
  // anwachsenden Rautenteil berechnen
  for ( j = 3; j <= l1; j++ )
  for ( i = j; i >  0 ; i-- )
  { arr[i] += arr[i-1]; }
  // konstanten Rautenteil berechnen
  for ( ; j <= l2; j++ )
  for ( i = 0; i < l1; i++ )
  { arr[i] += arr[i+1]; }
  // schrumpfendes Rautenteil berechnen
  for ( ; j <= n; j++, l1-- )
  for ( i = 0; i <= l1; i++ )
  { arr[i] += arr[i+1]; }
  // Ergebnis speichern
  l1 = arr[0];
  // Speicher freigeben
  free(arr);
  // Ergebnis liefern
  return l1;
}

// Hauptprogramm
// Einlesen von n und k
// Berechnen und Ausgeben des Binomialkoeffizienten 
int main()
{
  int n,k;
  printf("\nBerechnung k aus n");
  printf("\n------------------\n");
  do
  {
    // n einlesen
    printf("\nn: ");
    fscanf(stdin,"%d",&n);
    if ( n < 1 ) break;
    // k einlesen
    printf("k: ");
    fscanf(stdin,"%d",&k);
    if ( k < 0 ) break;
    // Berechnung und Ausgabe
    printf("%d aus %d = %d\n", k, n, KausN(n,k));
  } while ( n>1 && k>0 );
  // fertig
  printf("\nFERTIG\n");
  return 0;
}
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück