c++ Binomialkoeffizient berechnen und Überlauf verhindern

Hallo,

habe ein Problem mit folgendem C++-Code:

long long binom ( int n, int k )
{
    long long b = n - k + 1 ;

    for ( int i = 2 ;  i (kleiner gleich) k ;  ++i )
    {
        b = ( b * ( n - k + i ) ) / i ;
    }
    
    return b ;
}  // binom()

Das funktioniert ohne Überlauf für 66 über 23 = 348524321356411200 Bei etwas höheren Werten, z.B. 66 über 33, gibt es aber einen Überlauf.

Hat jemand eine Idee, wie ich den Überlauf verhindern kann, auch noch für etwas höhere Werte?

Danke

3 Antworten

DoTheBounce

15.12.2013, 13:11

Die Standard-C++ Typen haben eine maximale Größe, und wenn du - wie in deinem Fall - sehr große Zahlen berechnen willst, die nichtmehr innerhalb diese Größe passen, dann kannst du auch einen Überlauf nicht verhindern, wenn du weiterhin diese Datentypen benutzt.

Abhilfe für dein Problem schaffen sog. Big Integer Librarys. Eine bekannte und weit-verbreitete solche Library ist Gnu MP https://gmplib.org/ - diese wird unter anderem auch für die Boost.Multiprecision-Lib genutzt (falls du Boost verwenden willst)

chaostheorie314

Beitragsersteller

15.12.2013, 13:13

Also das Ergebnis von 66 über 33 passt definitiv in den Wertebereich des long long. Daher muss das auch gehen. Der Überlauf passiert irgendwann bei der Schleife bei b = (...). Also muss ich den Wert von b während der Rechnung irgendwie kleiner halten, damit kein Überlauf passiert.

DoTheBounce

15.12.2013, 13:22

@chaostheorie314

66 über 33 ist ~7 * 10^18 und die Grenze für long long ist ~9 * 10^18. Das heißt ganz offensichtlich, dass das Zwischenergebnis, bevor durch i geteilt wird, nichtmehr in den Wertebereich passt.

Du hast also 2 Möglichkeiten:

Du nimmst eine Library
Du passt deinen Algorithmus an, der die Zwischenergebnisse kleiner hält. Der offensichtlichste Schritt wäre die Berechnung anders zu klammern:
```
b =  b *  (( n - k + i ) / i) ;
```

Damit sind die Zwischenwerte kleiner. Solange du diesen Algorithmus verwendest, glaube ich geht auch nicht viel mehr (auf den ersten Blick).

Du könntest in deinem speziellen Fall auch unsigned long long nehmen, das erhöht den Wertebereich nochmal, aber natürlich auch nicht unbegrenzt

chaostheorie314

Beitragsersteller

15.12.2013, 14:06

@DoTheBounce

Funktioniert leider auch nicht. Es ist eben (n - k + i) nicht restlos durch i teilbar, sondern nur (b * ( n - k + i )). Das führt bei deiner Klammermethode zu erheblichen Ungenauigkeiten durch die Rundungen.

Also mathematisch berechnet der Algorithmus ja

(n-k+1)/1 * (n-k+2)/2 * (n-k+3)/3 * ...

Dabei steht im Zähler ja eine Fakultät. Wenn n = 66, k = 23 ist das z.B.

(66-23+1)/1 * (66-23+2)/2 * (66-23+3)/3 * ...

= 43/1 * 44/2 * 45/3 * ...

Es ist 43 * 44 durch 2 teilbar, ( (43 * 44)/2 ) * 45 restlos durch 3 teilbar bzw. 434445 durch 6 teilbar usw., weswegen der Algorithmus auch nirgends runden muss und dadurch keine Ungenauigkeiten auftreten.

Also n * ( n + 1 ) mit n gerade ist 2a * (2a + 1) = 4a^2 + 2a = 2(2a^2 + a) durch 2 teilbar. Mit n ungerade: (2a+1) * (2a + 2) = 4a^2 + 4a + 2a + 2 = 2(2a^2 + 3a + 1) durch 2 teilbar.

Dass n * (n+1) * (n+2) durch 6 teilbar ist, lässt sich genauso zeigen usw.

Juliahn

15.12.2013, 15:42

Die Zahlen der Fakultät explodieren dir ziemlich schnell im Programm. Ein anderer Ansatz wäre es den Bruch zuerst zu kürzen um so die riesigen Zahlen zu vermeiden.

Beispiel binom(7,3)

    7!
-----------
3! * (7-3)!

=

 1*2*3*4*5*6*7
---------------
1*2*3 * 1*2*3*4

=

5*7
---
 1

Und damit haben wir nurnoch die Zahlen 5*7 übrig anstelle von 5040 / 144.

Ist zwar ein wenig aufwendiger zu programmieren aber dadurch bist du nurnoch durch den Wert des Ergebnis nach oben hin beschränkt.

Das Ergebnis zu binom(66,33) wäre hierbei

37*41*43*47*17*53*7*19*59*61*7*2*65*6 = 7219428434016265740

Anstelle von

             5,443449390......e+92
---------------------------------------------
8,683317618......e+36 * 8,683317618......e+36

chaostheorie314

Beitragsersteller

15.12.2013, 19:26

Okay, das hat nicht geholfen, weil wir diesen bestimmten Algorithmus verwenden mussten. Ich habe es allerdings gelöst! (yeah! Saß lange dran :P) Und zwar so :

        if ( b % i == 0 )
            b = (b/i) * (n-k) + b ;
        else if ( (n-k) % i == 0 )
            b = b * ((n-k)/i) + b ;
        else
            b = (b * (n - k))/i + b ;

Das hält die Zwischenergebnisse kleiner, so dass 66 über 33 noch korrekt berechnet werden kann.

apachy

15.12.2013, 13:32

Wahrscheinlich wird der Fehler bei:

( b * ( n - k + i ) )

auftreten.

Gibt es ein bestimmten Grund warum dies so gerechnet werden sollte?

b = (n - k + i)  * (b / i);

Sollte das selbe Ergebnis geben wie:

b = ( b * ( n - k + i ) ) / i ;

Und du verhinderst das große Zwischenergebnis aus obersten Beispiel.

Woher ich das weiß:Berufserfahrung – Softwareentwickler/Projektleiter seit 2012

chaostheorie314

Beitragsersteller

15.12.2013, 13:54

Das funktioniert leider nicht. Deine Methode b = (n-k+i) * (b/i) schränkt die Genauigkeit ein, da b nicht immer durch i teilbar ist und (b/i) gerundet wird. b * (n-k+i) ist aber immer durch i restlos teilbar.

Ähnliche Beiträge

Problem bei C++ Programmierung (natürliche Zahl umrechnen in binäre Zahl)?

Hallo

Ich muss ein Programm schreiben welches eine natürliche Zahl in ein binäre Zahl umrechnet. Mein Problem ist aber, dass die binäre Zahl rückwärts ausgegeben wird.

Kann mir da jemand helfen?

ps: Ich will den Code so simpel wie nur möglich halten.

int main()

{

long long int n;

long long int b;

std::cout << "Enter a decimal number: ";

std::cin >> n;

std::cout << "The binary equivalent of " << n << " is ";

while (n > 0)

{

b = n % 2;

n /= 2;

std::cout << b;

}

return 0;

}

...zum Beitrag

Array nach Wert prüfen rekrusiv (java)?

Hi sagen wir mal ich habe einen COde der so aussieht:

  public static int calculateBinomialCoefficient (int n, int k)
   {
      if (k == 1)
         return n;
      else if (n >= k && k == 0)
         return 1;
      else
       return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
 
   }
}

Nun hat mein Prof gemeint, dass die rekursion nicht linear ist und zu vielen gleichen Aufrufen mit gleichen Parameterkombis führt. EIne Möglichkeit damit das besser läuft ist es berechente Binomialkoeffizienten in einem zwei dimensionalen Array zu speichern und vor einem rekursiven Aufruf zu prüfen, ob die Lösung bereits 1x exisitert hat. EInen Array haben wir schon gegeben, mit der perfekten Länge.Dann habe ich mir das überlegt:

 public static int calculateBinomialCoefficient (int n, int k)
  {
   if (k == 1)
     return n;
   else if (n >= k && k == 0)
     return 1;
   else
for (int a=0; a<array.length;a++)
{
for (int b=0; b<array.length;b++)
{
if (array[a][b]==(n * calculateBinomialCoefficient(n - 1, k - 1) / k)
{
return array[a][b];
}else{
return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
if(array[a][b]==0){
array[a][b]==(n * calculateBinomialCoefficient(n - 1, k - 1) / k);
}
}
}
}
     
 
  }
}

(Ich hoffe kann man erkennen Tabs sind bisschen verrückt.)

Aber warum funktioniert das nun nicht? Habe doch alles beachtet oder?

...zum Beitrag

C++: Eigener "Zufallsgenerator"?

Achtung Anfänger am Werk:

Ich habe versucht einen eigenen "Zufallsgenerator" zu schreiben, dafür habe ich folgenden Code benutzt:

long time();
long random(long max, long seed = time());

//zählt welche Zahl bei 100 generierten Zufallszahlen wie oft vorkommt
int main() {...}

//liefert die aktuelle Zeit
long time() {...}

long random(long max, long seed) {
    
    return seed%max;
}

Wie zu erwarten waren die Ergebnisse zwar irgendwie zufällig jedoch nicht gleichmäßig verteilt, hier eine Beispielausgabe :

Zahl 0: 0 mal | Zahl 1: 63 mal | Zahl 2: 37 mal | Zahl 3: 0 mal | Zahl 4: 0 mal

Danach wollte ich aber aus reiner Interesse wissen welcher Seed denn jeweils übermittelt wird und habe dem Code nur eine Zeile hinzugefügt:

long time();
long random(long max, long seed = time());

//zählt welche Zahl bei 100 generierten Zufallszahlen wie oft vorkommt
int main() {...}

//liefert die aktuelle Zeit
long time() {...}

long random(long max, long seed) {
    
    std::cout << seed << std::endl;

    return seed%max;
}

Und mit Verwunderung musste ich feststellen, dass die Werte nun relativ gleichmäßig verteilt ausgegeben wurden (nach den einzelnen Seeds natürlich), eine Beispielausgabe:

Zahl 0: 19 | Zahl 1: 24 | Zahl 2: 18 | Zahl 3: 20 | Zahl 4: 19

Warum sind die Werte beim 2. Codebeispiel gleichmäßiger verteilt?
Kann ich es irgendwie hinbekommen dass die Werte so verteilt sind wie im 2. Codebeispiel, ohne dabei etwas in der Konsole ausgeben zu müssen?

PS. Ich dachte dass die bessere Verteilung im 2. Codebeispiel möglicherweise damit zusammenhängt, dass der cout-Befehl eine gewisse Zeit beansprucht, und somit die Seeds indirekt beeinflusst. Deshalb habe ich versucht an der selben Stelle wo im 2. Beispiel der cout-Befehl steht eine kurze Wartezeit einzubauen, jedoch war das Ergebnis ähnlich wie beim 1. Beispiel.

...zum Beitrag

Java Methode gibt falschen Wert aus?

Ich habe die Klasse Vehicle und eine Klasse VehicleApp. In der Klasse Vehicle App erzeuge ich eine Instanz der Klasse Vehicle mit dem Namen Audi.

public class VehicleApp{
Vehicle audi = new Vehicle("Audi", "S5",2012, Color.RED);
System.out.println(audi.getAlter());
}

Das Alter ist bei meiner Klasse eigentlich dadurch bestimmt durch "aktuellesJahr-baujahr" -> 2019 - 2012 = 7. Bei der Ausgabe wird mir jedoch 2019 angezeigt.

import java.util.Calendar;
import javafx.scene.paint.Color;
public class Vehicle {
//aktuelles Jahr
	Calendar cal = Calendar.getInstance();
	int aktuellesJahr = cal.get(Calendar.YEAR);
//Klassenattribute
	private String marke;
	private String typ;
	private int baujahr;
	private Color farbe;
	private int alter = aktuellesJahr-baujahr;
//Konstruktor
	public Vehicle(String marke, String typ, int baujahr, Color farbe) {
		this.marke = marke;
		this.typ = typ;
		this.baujahr = baujahr;
		this.farbe = farbe;
	}
//Setter- und Gettermethoden
	public int getAlter() {
		return alter;
		//return aktuellesJahr-baujahr;
	}
}

Ändere ich das return-Statement von "return alter;" zu "return aktuellesJahr-baujahr," tritt das gewünschte Ergebnis (Ausgabe 7) ein. Könnt ihr mir eklären warum das return-Statement "return alter;" nicht das gewünschte Ergebnis erzeugt?

...zum Beitrag

c++ for schleife bei jedem durchlauf um 2 erhöhen. wie geht das ?

Hallo zusammen,

beschäftige mich zurzeit mit der for schleife in c++

möchte das bei jedem schleifendurchlauf der wert der variable um 2 erhöht wird.

was ist an meinem code falsch ?

include

using namespace std;

int main() { int zahl1;

for(int zahl1=1;zahl1<=20;zahl1+2)
{
    cout<<"Der Wert von zahl1 lautet: "<<zahl1<<endl;
}
system("PAUSE");
return 0;

}

...zum Beitrag

Pointer in C?

Hallo,

Ich habe diesen Code gefunden:

Erst wird einer Variable ein Wert zugeteilt.

Dann wird die Adresse der Variable an eine Funktion übergeben.

In dieser Funktion wird die Adresse der Variable einem Pointer zugewiesen.

Dann wird der Wert der Adresse auf die der Pointer zeigt um 10 erhöht.

DANACH soll die Funktion den Wert 0 wieder zurückgeben.

Warum wurde damit nicht die Variable Brief erst um 10 erhöht und ihr dann der Wert 0 zugeteilt?

Diese Funktion soll schließlich den Wert den sie durch einen Parameter erhalten hat entsprechend verändert wieder an den selben Parameter zurückgeben wenn sie endet oder nicht?

Hier der Code:

#include <stdio.h>

int briefkasten(int *pointer){

*pointer += 10;

return 0;

}

int main(){

int brief = 100;

briefkasten(&brief);

printf("%d\n", brief);

return 0;

}

...zum Beitrag

java aufgaben helfen?

static double monom(double a, double x, int e): es soll der Ausdruck axe berechnet werden.
static int signum(long x): Es soll die Signum (auch Vorzeichenfunktion) realisiert werden.

wie kann ich die Aufgabe in java darstellen einfach?

static double monom(double a, double x, int e){

return Math.pow(a,x); ist richtig oder muss ich e auch deklarieren?

}

static int signum(long x){

return???;

}

...zum Beitrag

Java selbstgeschrieben Klasse in Methode zurückgeben?

Hey, ich habe eine eigene Klasse geschrieben die in etwa so aussieht:

public class Übung{
    public final int wert1;

    public Übung(int wert) {
        wert1= wert;
    }
}

Jetzt möchte ich in einer anderen Klasse diese selbst geschriebene klasse returnen aber wie genau geht das? Habt ihr dafür ein Beispiel? Welchen Wert brauche ich bspw für die Methode testeDieÜbung(), damit ich dort die Klasse Übung zurückgeben kann?

public class Test {

    public static void main(String[] args) {
        Test test = new Test();
        test.testeDieÜbung();
      }

    private Übung testeDieÜbung() {
        return Übung;
    }
}

Könnt ihr mir dabei helfen?

...zum Beitrag

Hat jemand eine Lösung für diese Übung (Java)?

Das ist die Aufgabe:

Implementieren Sie eine Klasse rectangle (=Rechteck), deren Konstruktor die Höhe und die Breite verlangt. Eine Methode getArea der Klasse Rechteck gibt dessen Fläche zurück. Implementieren Sie zudem eine Klasse square (=Quadrat), die sich von Rechteck ableitet. square hat keine eigenen Attribute oder Methoden. Im Konstruktor von Quadrat wird die Höhe und die Breite des Rechtecks gesetzt. Beim Aufruf der Methode getArea für eine Instanz von square soll dessen Fläche zurückgegeben werden.

Das ist meine bisherige Lösung, aber mir kommt die irgendwie falsch vor:

public class rectangle{

public rectangle (int hoehe, int breite){

}

public double getArea(){

return hoehe x breite;

}

public class square extends rectangle{

public square(){

hoehe = 20;

breite = 30;

}

...zum Beitrag

Java kann nicht aus .txt-Datei lesen?

Hallo,

ich möchte gern einen Wert aus einer Textdatei lesen. Das klappt allerdings noch nicht. Hier die Methode und der Fehler (die sysouts sind zum Debugging da):

public int getIndex(String path) throws IOException {
  File file = new File(path);
  System.out.println(file.exists()); //Es kommt true raus.
  Scanner sc1 = new Scanner(file, "cp1252");

  if (sc1.hasNext()) {
    index = sc1.nextInt();
  }

  sc1.close();
  System.out.println(index); // es sagt, die Datei ist leer
  return index;
}

In der Textdatei steht eine Zahl: 235.

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "Measurement.getCharge()" because the return value of "Database.getMeasurement(int)" is null

Hier die im Fehler genannten Methoden:

public Measurement getMeasurement(int index) {
  return measurementDB.get(index + 1);
}

public String getCharge() {
  String temp = "";

  for (MeasurementEntry m: entries) {
    temp += m.getcharge() + "\n";
  }

  return temp;

public String getcharge() {
  return charge;

...zum Beitrag

Raute rekursiv programmieren?

Hallo ich habe hier ein Problem bei der Programmierung. Hier ist meine Aufgabenstellung:

Schreiben Sie eine Anwendung Raute.java, welche ein Raute ausgibt. Der Nutzer soll zuvor die Größe n der Raute eingeben können. Bei geraden Eingaben (n gerade) soll der Text: „Das Programm arbeitet nur mit ungeraden Werten.“ ausgegeben werden. Bei ungeraden Eingaben (n ungerade) soll eine Raute der Höhe n ausgegeben werden.

Das ist mein Quellcode (allerdings kommt nicht ganz das raus was ich brauche^^):

/* 
 * Erzeugen einer Raute-rekursiv
 */
 
import java.util.Scanner; 

public class Raute {
  
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
 
    // Eingabe
    System.out.println("Geben Sie die Größe Ihrer Raute ein(nur ungerade Werte):");
    int groesse = scan.nextInt();

    // Bedingung --> gerade Werte werden nicht
    // vom Programm bearbeitet (+ Ausgabe)
    if (groesse % 2 == 0) {
       System.err.println("Das Programm arbeitet nur mit ungeraden Werten!");
    }
    else {
       // Berechnung:
       resultat(groesse);
    }
  }

  public static String methode1(int groesse) {

    if (groesse > 0) {
       return "* " + methode1(groesse - 1);
    }
    else {
       return " ";
    }
  }

  public static String methode2(int groesse) {

    if (groesse > 0) {
      return "* " + methode1(groesse - 1);
    }
    else {
      return " ";
    }
  }

  public static String space(int groesse) {

    if (groesse > 0) {
      return " " + space(groesse - 1);
    } 
    else {
      return " ";
    }
  }

  public static void resultat(int groesse) {
    
    for (int i = 1; i < groesse; i++) {
      System.out.println(space(groesse - i));
      System.out.println(methode1(i));
    }

    for (int i = 0; i < groesse; i++) {
      System.out.println(methode2(groesse - i));
      System.out.println(space(i));
    }
  }
}

Z.B.: groesse = 5

Ausgabe:

*   

  

* *   

  

* * *   

* * * *  

 

* * *  

 

* *

  

*

...zum Beitrag

C Ziffernsumme mit while Schleife?

Könnte mir wer helfen was da falsch ist? Sobald ich 10 oder mehr Zeichen eingebe stimmt es nicht/rechnet komplett falsche Werte aus.

#include <stdio.h>

int main()

{

int number;

int digitSum = 0;

int i;

printf("Bitte eine ganze Zahl eingeben: ");

scanf("%d", &number);

while(number != 0)

{

digitSum = digitSum + number % 10;

number = number / 10;

}

printf("Ziffernsumme: %d", digitSum);

return 0;

}

...zum Beitrag

C++: Kann ich diesen Code irgendwie noch vereinfachen?

Guten Abend,

ich schreibe gerade in C++ an einem kleinen Kniffelspiel. Im Moment bin ich soweit, dass ich mir fünf zufällige Zahlen (Würfel) über die rand()-Funktion erstelle, diese dann in einem Vektor speichere und anschließend über die Funktion auswertung() den höchsten Pasch zurückgebe. Jedoch ist der Code nicht gerade sehr kompakt. Hat jemand Vorschläge für Optimierungen?

Vielen Dank im Voraus!

#include <iostream>
#include <ctime>
#include <vector>
#include <random>

using namespace std;

vector<int> würfe()
{
  vector<int> list; // Ermittelt über die aktuelle Systemzeit 5 Zufallszahlen und übergibt sie dem Vektor list
  srand(time(0));

  for (int i = 0; i < 5; i++) {
    list.push_back(1 + rand() % 6);
    cout << list[i];
  }

  cout << endl;
  return list;
}

int auswertung(vector<int> ergebnis)
{
  int pasch = 0;

  // Verschachtelte for-Schleife iteriert durch Vektor und vergleicht alle Elemente miteinander
  for (vector<int>::iterator it = ergebnis.begin(); it != ergebnis.end(); ++it) {
    for (vector<int>::iterator it1 = ergebnis.begin(); it1 != ergebnis.end(); ++it1) {
      // Nur wenn die Werte gleich sind (Pasch) und nicht auf dasselbe Element zeigen, geht es weiter
      if (*it1 == *it && it != it1) {
        // Nur wenn der gefundene Pasch höher als der Höchste bereits gefundene ist, wird er ausgewertet
        if (*it > pasch) {
          switch (*it) {
            case 1: pasch = 1;
              break;
            case 2:
              pasch = 2;
              break;
            case 3: pasch = 3;
              break;
            case 4: pasch = 4;
              break;
            case 5: pasch = 5;
              break;
            case 6: pasch = 6;
              break;
          }
        }
      }
    }
  }

  return pasch;
}

int main()
{
  int pasch;
  vector<int> random = würfe();
  pasch = auswertung(random);

  cout << "Pasch: " << pasch << endl;
}

...zum Beitrag

Chudnovsky Algorithmus in C?

Ich versuche gerade den Chudnovsky Algorithmus in C zu implementieren um die nachkommastellen von Pi zu rechnen. Jedoch sind die häufigsten Ergebnisse immer nan, -nan, inf oder was wie 3.827783e-647. Ich hab auch verschiene print formate verwendet um das ergebnis auszugeben, aber da kam entweder 0.0000 oder inf raus.

Wie bekomm ich es hin das eine 'normale' Zahl rauskommt, quasi 3.14159...... usw.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

long double fact(long double n) {
  long double fac = 1.00;
  for (int i = 1; i<=n; i++) {
    if (i) {
      fac = fac * i;
    }
  }
  return fac;
}


int main(int argc, char* argv[]) {

  long double n, i;
  long double sum, pi, term;
  sum = 0.00;
  pi = 0.00;

  n = (atoi(argv[1]));

  for (i=0; i < n; i++) {
    term = (powl((-1.00), n) * fact(6.00*n) * (545140134.00*n + 13591409)) / (fact(3.00*n) * powl(fact(n), 3.00) * powl(640320.00, 3*n+3/2));

    sum += term;
  }
  sum = sum * 12;

  pi = 1 / sum;


  printf("PI: %Lf\n", pi);
  

  return 0;
}

...zum Beitrag

Was möchtest Du wissen?

Deinen Beitrag erstellen