Binomialkoeffizient



  • Kurze Frage, warum habe ich beim Nicht Rekursiven wenn ich n:13 über k:10 nehme das Ergebnis 88? und wenn ich hier beim Rekursiven n:13 über k:10 nehme erhalte ich das richtige Ergebnis mit 286.

    Wenn ich zb kleine Zahlen wähle, n:7 über k:2 dann kommt bei beiden 21 als Ergebnis, das ja stimmt. Woher kommt dass, das beim Nicht Rekursiven das Ergbnis bei "größeren" Zahlen falsch ist?

    Nicht Rekrusiv:

    #include <stdio.h>
    
    int binomialCoefficient(int n, int k);
    int factorial(int n);
    
    int main(void)
    {
      int n;
      int k;
      int binCoeff;
    
      printf("\n Calculating n chooses k \n" );
      printf("\n Value of n: ");
      scanf("%d", &n);
      printf("\n Value of k : ");
      scanf("%d", &k);
      binCoeff = binomialCoefficient(n, k);
      printf("\n n chooses k of %d and %d", n, k);
      printf(" is: %d \n", binCoeff);
      return 0;
    }
    
    int binomialCoefficient(int n, int k)
    {
      if(n<0 || k<0)
        return -1;
      if(n<k)
        return 0;
      else
        return factorial(n)/(factorial(k)*factorial(n-k));
    }
    
    int factorial(int n)
    {
      int i,f=1;
      for(i=1;i<=n;i++)
        f=f*i;
      return f;
    }
    

    Rekrusiv:

    #include <stdio.h>
    
    int binK(int n, int k)
    {
      if( n < 0 || k < 0 )
        return -1;
      if( k == n || k == 0 )
        return 1;
      return binK( n - 1, k ) + binK( n - 1, k - 1 );
    }
    
    int main(void)
    {
      int n, k, bk;
    
      printf("Berechnung des Binomialkoeffizienten n ueber k\n");
      printf("Bitte Wert fuer n eingeben: ");
      scanf(" %d", &n);
      printf("Bitte Wert fuer k eingeben: ");
      scanf(" %d", &k );
      bk = binK( n, k);
      printf( "Der Binomialkoeffizient n ueber k von %d und %d ist %d\n", n, k, bk);
      return 0;
    }
    


  • Laß dir mal den Rückgabewert von

    factorial(13)
    

    ausgeben 😉



  • Ohje, bei meinem komischen CodeBlocks weiß ich garnicht wie das geht .... peinlich. 😞
    was passiert den mit dem Ausgabewert?



  • Binomialkoeffizient schrieb:

    Ohje, bei meinem komischen CodeBlocks weiß ich garnicht wie das geht .... peinlich. 😞

    Dann speicherst du den Wert in einer (Extra-)Variablen ab und gibst den per printf aus



  • Dann ruf mal die Funktion direkt so in deinem Programm auf und laß dir den Rückgabewert ausgeben.

    Wenn ich mich nicht verrechnet habe, dann kommt 1932053504 anstatt 6227020800 dabei raus.
    Der Wertebereich eines "int" umfaßt bei den üblichen Systemen nur 32 Bit, d.h. -2147483648 bis 2147483647.

    Evtl. unterstützt dein System "long long", welches meistens 64 Bit groß ist.



  • Ok, das ist eine riesiege Zahl. Bzw er gibt drei mal hintereinander eine riesen Zahl aus. Drei Kommas sind enthalten.



  • okay jap macht sinn, danke


  • Mod

    Binomialkoeffizient schrieb:

    okay jap macht sinn, danke

    Ist dir denn auch klar, dass die Lösung nicht da drin besteht, einen größeren Datentyp zu benutzen? Denn auch 64-Bit reichen nur bis 20!. Die wahre Lösung ist, die Formel für den Binomialkoeffizient umzuschreiben, so dass die großen Fakultäten entfallen. Ein bisschen Kürzen sollte reichen, schließlich kommen sehr viele der Glieder der Fakultäten sowohl im Zähler als auch im Nenner vor.



  • Dieser findet sich im Wiki-Artikel dazu: Binomialkoeffizient: 4 Algorithmus zur effizienten Berechnung

    Mit Umstellung auf "long long" wollte ich auch nur den Hinweis geben, daß der Algorithmus per se so für binomialCoefficient(13, 10) richtig funktioniert. Bei größeren Zahlen gäbe es dann selbstverständlich wieder das gleiche Problem.


Log in to reply