3. große Zahlen bei Fakultätsberechnung

große Zahlen bei Fakultätsberechnung

  • ?

    314159265358979 schrieb:

    Gibt da noch unsigned long long

    Ist das nicht nur auf manchen Systemen erlaubt? Könnte schwören, Ideones GCC 4.3.1 (glaub die haben LAMP) hat mich da mal böse überrascht.

    0
  • ?

    Gugelmoser schrieb:

    Hacker schrieb:

    Gugelmoser schrieb:

    Man nimmt doch keine Gleitkommazahl, wenn es sich um Ganzzahlen handelt.

    versteh nicht ganz.
    Größer als int wirst du keinen Integralen BDT finden, außer long und vielleicht long long (was nicht überall erlaubt ist).

    Jetzt verstehe ich nicht ganz, was du mir damit sagen willst. 😃

    Sorry, ich hätte ihn zitieren sollen, anstatt dich. Es kam mir im ersten Moment nur so vor, als würdest du ihn dabei unterstützen.

    BDT = Basis-DatenTyp (char, float, usw.)
    Integral: Kann nur Ganze Zahlen Speichern (hoffe du kannst Mathe 🙂 )

    0
  • 3

    Hacker schrieb:

    314159265358979 schrieb:

    Gibt da noch unsigned long long

    Ist das nicht nur auf manchen Systemen erlaubt? Könnte schwören, Ideones GCC 4.3.1 (glaub die haben LAMP) hat mich da mal böse überrascht.

    Ist seit C++11 Standard.

    0
  • ?

    314159265358979 schrieb:

    Hacker schrieb:

    314159265358979 schrieb:

    Gibt da noch unsigned long long

    Ist das nicht nur auf manchen Systemen erlaubt? Könnte schwören, Ideones GCC 4.3.1 (glaub die haben LAMP) hat mich da mal böse überrascht.

    Ist seit C++11 Standard.

    Mmhh, danke!

    0
  • ?

    Da Fließkommaberechnung scheinbar kein Problem für den TE darstellt, wäre

    double bincoeff(int n, int k) {
  return tgamma(n + 1) / tgamma(k + 1) / tgamma(n - k + 1);
}

    eine einfache Möglichkeit.

    0
  • R

    Hätte doch noch ne Frage.

    Wie sorgt man für ne Eingabewiederhohlung, wenn z.B. keine Zahlen sonder Buchstaben oder keine ganzen Zahlen eingegeben werden?

    Also wenn z.B. nur mit y oder n geantwortet werden soll, ist das ja kein Problem. Bei einstelligen Zahlen würde ich auch wissen, wie man die Eingabe von Buchstaben vermeidet. Aber bei 0.52 oder 30 habe ich keine Ahnung 😞

    0
  • ?

    ruhig_brauner schrieb:

    Wie sorgt man für ne Eingabewiederhohlung, wenn z.B. keine Zahlen sonder Buchstaben oder keine ganzen Zahlen eingegeben werden?

    int ganzzahl;
	cout << "Bitte eine Ganzzahl eingeben: ";
	while( !(cin>>ganzzahl) )
	{
		cin.clear();
        cin.ignore(numeric_limits<streamsize>::max(),'\n'); // #include <limits>
        cout << "Bitte eine Ganzzahl eingeben: ";
	}
    0
  • M

    Hacker schrieb:

    Integral: Kann nur Ganze Zahlen Speichern (hoffe du kannst Mathe 🙂 )

    Integrale sind Nudeln. Keine Ahnung, was man alles in Mathe können muss, um was mit ganzen Zahlen anfangen zu können.

    Ich hab auch noch nen Vorschlag:

    \begin{align*} n! = 2^{\sum_{i=1}^n \log_2 i} \end{align*}
    0
  • ?

    Was die zeilenweise Verarbeitung von Benutzereingaben angeht, da habe ich noch eine alte Funktionsvorlage rumliegen, die unter Fehlerbehandlungsgesichtspunkten robuster ist als die ignore-Variante:

    #include <iostream>
#include <sstream>
#include <string>
#include <stdexcept>

struct malformed_user_input : public std::runtime_error {
  inline malformed_user_input(std::string const &msg) : std::runtime_error(msg) { }
  virtual ~malformed_user_input() throw() { }
};

struct stream_broken : public std::runtime_error {
  inline stream_broken(std::string const &msg) : std::runtime_error(msg) { }
  virtual ~stream_broken() throw() { }
};

template<typename result_t>
result_t &cli_read_ref(result_t          &dest,
                       std::string const &prompt,
                       unsigned           max_tries,
                       std::istream      &in  = std::cin,
                       std::ostream      &out = std::cout) {
  std::istringstream parser;
  std::string line;
  unsigned tries = 0;

  do {
    parser.clear();

    if(tries < max_tries) {
      ++tries;
    } else {
      throw malformed_user_input("cli_read_ref: More than 'max_tries' parse failures");
    }

    out << prompt << std::flush;
    if(!out) {
      throw stream_broken("cli_read_ref: Cannot write to ouput stream");
    }

    if(!std::getline(in, line)) {
      throw stream_broken("cli_read_ref: Cannot read from input stream");
    }

    parser.str(line);
    parser >> dest;
  } while(!parser);

  return dest;
}

template<typename result_t>
result_t cli_read(std::string const &prompt,
                  unsigned           max_tries,
                  std::istream      &in  = std::cin,
                  std::ostream      &out = std::cout) {
  result_t result;
  return cli_read_ref(result, prompt, max_tries, in, out);
}

// Anwendungsbeispiel:

int main() {
  // Lies einen int ein; drei Versuche.
  int x = cli_read<int>("Zahl: ", 3);

  std::cout << 2 * x << std::endl;
}

    Hintergrund ist, dass, wenn mal etwas tiefer liegendes mit std::cin nicht stimmen sollte, die cin.clear()-cin.ignore()-cin>>-Variante in einer Endlosschleife endet. Das kann beispielsweise passieren, wenn stdin in eine Datei umgeleitet wird, deren Inhalt als Benutzereingabe nicht funktioniert - irgendwann ist halt eof, und dann bringt cin.clear() einen nicht weiter.

    0
  • C

    http://de.wikipedia.org/wiki/Stirling-Formel

    wikipedia.de schrieb:

    Die Stirling-Formel ist eine mathematische Formel, mit der man für große Fakultäten Näherungswerte berechnen kann.

    0
  • 3

    Hast du das selbst geschrieben seldon?

    0
  • ?

    ruhig_brauner schrieb:

    Dann hätte ich nochmal ne andere Frage, an Leute, die beruflich mit C++ arbeiten. Macht das Spaß? (Mich würde mal die rein subjektive Antwort interessieren. Will auch kein "kommt auf den Bereich an" hören. 😉 )

    macht sex spaß?
    glaubst du prostituierte haben spaß?

    überlege dreimal bevor du ein hobby zum beruf machst...

    0
  • ?

    Michael E. schrieb:

    Hacker schrieb:

    Integral: Kann nur Ganze Zahlen Speichern (hoffe du kannst Mathe 🙂 )

    Integrale sind Nudeln. Keine Ahnung, was man alles in Mathe können muss, um was mit ganzen Zahlen anfangen zu können.

    Ich hab auch noch nen Vorschlag:

    \begin{align*} n! = 2^{\sum_{i=1}^n \log_2 i} \end{align*}

    Damit kann wieder ich nichts anfangen. Aber nicht jeder weiß, wie die Menge der Ganzen Zahlen definiert ist.

    0
  • M

    Nach ner Definition der ganzen Zahlen hat keiner gefragt. Aber um zu wissen, was ganze Zahlen im umgangssprachlichen Sinn sind, braucht man nicht "Mathe zu können".

    Worauf ich hinaus will: Niemand sagt im Deutschen Integral für Ganzzahl.

    0
  • ?

    Hacker, das mit der Formel hat der nur als Jux gemeint. Da steht auch nur 2*3*4*...*n

    0
  • ?

    Michael E. schrieb:

    Nach ner Definition der ganzen Zahlen hat keiner gefragt. Aber um zu wissen, was ganze Zahlen im umgangssprachlichen Sinn sind, braucht man nicht "Mathe zu können".

    Zahlenmengen sind ja auch nur "Teilgebiet der Mathematik".
    Egal, du hast Recht, aber ich will mich fachlich ausdrücken. 😃

    0
  • ?

    314159265358979 schrieb:

    Hast du das selbst geschrieben seldon?

    Ja, die Grundfassung ist aber lange her und hieß anders (read_type, wenn ich das richtig im Kopf habe). Du kannst das Ding gerne benutzen, wenn du es für irgendwas gebrauchen kannst. Ich habe für mich festgestellt, dass ich im Laufe der Zeit immer weniger Verwendung dafür hatte, aber eine Weile hat es mir gute Dienste geleistet (Performance ist ja an dieser Stelle von nachrangiger Bedeutung).

    0
  • M

    gastgast schrieb:

    Hacker, das mit der Formel hat der nur als Jux gemeint. Da steht auch nur 2*3*4*...*n

    Natürlich ist das dasselbe, sonst hätte ichs wohl nicht geschrieben. Aber es war kein Jux. Denn in vielen Fällen, hier auch, kann man mit dem Logarithmus der Fakultät rechnen, sodass man mit deutlich größeren Zahlen zurechtkommt.

    0
  • P

    Also eigentlich kann man bei den Binominalkoeffs numerisch sehr gut kürzen!

    n über k = n! / ( k!*(n-k)!): mit n >= k

    Für n > 2k ist der zweite Faktor im Nenner größer, ansonsten, der erste Faktor.

    Und den größeren Faktor rechnest du sofort mit n! entgegen, dann sparst du dir schon mal 2*k, bzw 2*(n-k) Multiplikationen, weil du es sowohl für n! als auch für den größeren Faktor nicht berechnen musst.

    Beispiel: 100 über 3

    100! / (3! * (100-3)!) => n > 2k also über (100-3)! kürzen

    100!/97! * 1/3! = 100*99*98 * 1/(1*2*3) = 161700
    so kann man es sogar fast im Kopf rechnen.

    Anders hat der numerische Wert von 100! 158 Stellen vor dem Komma 😉
    Da müsstest dann von Java BigInt benutzen 😃 !

    0
  • ?

    @Michael: Die Idee ist prinzipiell nicht ganz blöde, aber man kann die Berechnung des Binomialkoeffizienten so aufziehen, dass kein Zwischenergebnis größer ist als das Endergebnis:

    unsigned long bincoeff(int n, int k) {
  if(k > n - k) {
    return bincoeff(n, n - k);
  }

  unsigned long result = 1ul;
  for(int i = 1; i <= k; ++i) {
    if((n - k) % i == 0) {
      result *= (n - k) / i + 1;
    } else {
      result /= i;
      result *= n - k + i; // Merke: n - k + i > i
    }
  }

  return result;
}

    ...womit die Notwendigkeit für den Logarithmus-Trick verschwindet, denn wenn das Endergebnis nicht mehr in den Zieldatentyp passt, hat man noch ein ganz anderes Problem.

    0
Anmelden zum Antworten