3. 100! Fakultät exakt berechnen

100! Fakultät exakt berechnen

  • S

    Hi,
    Ich habe von meinem Prof die Aufgabe bekommen die Fakultät von 100 genau zu berechnen.

    Ich soll das mit Feldern und oder Strings lösen.
    Also keine Bibliothek wie GMP, NTL ...

    Ich habe schon einen Teil der Aufgabe gelöst.

    Mein Problem ist gerade, dass wenn ich die Fakultät von 5 berechnen will,ich einen Fehler mit dem Übertrag habe.

    Bsp.

    Ich schreibe die 5 in einen String um zu ermitteln in welches Feld ich die Zahl schreibe.
    Dann wird das Feld mit 4 multipliziert.
    5 * 4 = 20 --> wird in einen String geschrieben und dann in Felder verteilt.
    Feld[0] = 2
    Feld[1] = 0
    er nimmt also die 2 * 3 = 6 und schreib diese dann in das Feld.
    Feld[0] = 6
    Feld[1] wird nicht mit 3 multpilziert. Das bekomm ich nicht hin.
    Müsste also "nur" ein Schleifenproblem sein.

    Ich hoffe ich habe mein Problem verständlich geschildert.

    MFG

    #include <cstdlib>     //----------------------------------------//
#include <iostream>    //--------- Fakultaetsrechner ------------//
#include <string>      //----------------------------------------//
#include <sstream>     //----------------------------------------//
#include <math.h>      //----------------------------------------//

using namespace std;
//------------------------------- Prozeduren ---------------------------------//

    char wieder;                                   //Wiederholung des Programmes
    int Zahl;                                      //Ausgangszahl
    int a1,a2,a3,b,n,o,p;                          //Hilfvariablen
    int Feld[19]={0};                              //Felddeklaration mit Nullen
    stringstream Str;
    string str,str2,str9;

int main()
{
    cout<<"Dieses Programm berechnet die Fakultaet von n."<<endl;
    cout<<"Bitte geben Sie nun einen Wert fuer n ein."<<endl;
    cin>>Zahl;

    Str<<Zahl;
    string Benutzereingabe(Str.str());             //Zahl an String
    cout<<"Die laenge des Strings betraegt: "<<Benutzereingabe.length()<<endl;
    cout<<"Im String steht: "<<Benutzereingabe<<endl;
    a1=Benutzereingabe.length()-1;                 //Länge wird an Variable...
                                                   //...übergeben
    cout<<"Felderanzahl 1.a = "<<a1+1<<endl;

    for(n=0;n<=a1;n++)                             //Ermittlung der Elemente.
    {                                              //string
     str.assign(Benutzereingabe, n,1);             //
     stringstream Str1;
     Str1<<str;                                    //Übergabe an Hilfsstring.
     Str1>>b;
     Feld[n]=b;                                    //Feld mit Variable belegen.
     cout<<Feld[n]<<" <-- steht im Feld["<<n<<"]"<<endl;
    }
 do{     
//----------------------------- Fakultätsoperation ---------------------------//

    for(n=0;n<=a2;n++)
    {
     for(o=0;o<=a3;o++)
     {
      stringstream Str9;                           //Stringdeklaration
      Str9<<Feld[o];                               //Feld in String
      string verteilung(Str9.str());               //Berechnung der Elementezahl
      cout<<"Verteilung = "<<verteilung<<endl;     //Ausgabe am Bildschirm
      a3=verteilung.length()-1;                    //In Variable speichern
      str9.assign(verteilung,o,1);                 //Verteilung der Elemente...
      stringstream Str8;                           //...zu erst in einen String
      Str8<<str9;                                  //...dann in Hilfsstirng...
      Str8>>b;                                     //...dann in Variable...
      Feld[o]=b;                                   //..und zum schluss in Felder
     } 

     cout<<Feld[n]<<" * ";
     Zahl--;
     cout<<Zahl<<" = "; 
     Feld[n]=Feld[n]*Zahl;
     cout<<"Im Feld["<<n<<"] = "<<Feld[n]<<endl<<endl;
//---------------------------- Übertragsprüfung ------------------------------//
     stringstream Str2;
     Str2<<Feld[n];
     string Neuverteilung(Str2.str());
     cout<<"Zahl im String = "<<Neuverteilung<<endl<<endl;
     a2=Neuverteilung.length()-1;
     cout<<"Der String hat nun "<<a2+1<<" Stellen"<<endl<<endl;
     str2.assign(Neuverteilung,n,1);
     stringstream Str3;
     Str3<<str2;
     Str3>>b;
     Feld[n]=b;
     cout<<Feld[n]<<" <-- steht im Feld["<<n<<"]"<<endl;

     if(a3!=a2) n--;  //wenn Übertraq entsteht, wird schleife um 1 veringert

    }
  }while(Zahl>=3);
//--------------------------------- Ausgabe ----------------------------------//  

    int anzahl =(sizeof(Feld)/sizeof(Feld[19]));
    for(int i=0;i<anzahl;i++)  //Ausgabe der Elemente im Feld
    cout<<i+1<<".Wert= "<<Feld[i]<<endl;

cout<<endl;
//----------------------------------------------------------------------------// 
    system("PAUSE");
    return EXIT_SUCCESS;
}
    0
  • P

    machs andersrum. schreib die einser ins erste Feld, also s[0], die zehner nach s[1] usw. und dreh a Ende den ganzen Schmu um, dann lässt sich das leichter rechnen. Dann nimmste am Besten deinen Code und zerlegst ihn in Funktionen, um ihn lesbarer zu machen. So eine Mammutfunktion ist unübersichtlich, kein Wunder dass du da so ohne weiteres eventuelle Fehler nicht siehst.

    0
  • B

    Uh man, nicht bös gemeint, aber dein Code ist grauslig :p

    Ich finde du machst es dir etwas schwer. Vielleicht solltest du dir eine Klasse schreiben, die die großen Zahlen verwaltet, z.B. so

    class BigNumber
{
    public:
        BigNumber( unsigned int init );
        void MultiplyWith( unsigned int num );
        void Show();

    private:
        // Die Variablen, die du dafür brauchst
};

int main()
{
    cout << "Dieses Programm berechnet die Fakultaet von n." << endl;
    cout << "Bitte geben Sie nun einen Wert fuer n ein." << endl;

    unsigned int zahl;
    cin >> zahl;

    BigNumber fac( 1 );
    for ( unsigned int i=2; i<=zahl; i++ )
        fac.MultiplyWith( i );

    fac.Show();
}

    So hast du den ganzen Schrott nicht in der main-Funktion und kannst dich darauf konzentrieren, die MultiplyWith-Funktion zu implementieren. Musst dir halt vorher auf'm Papier überlegen, wie der Computer rechnen soll, dann kriegst du's sicherlich auch in Code-Form gegossen 🙂

    0
  • S

    Hey danke für die schnellen Antworten.

    Ja sry ich weiss, dass mein Programm grad sehr gruslig aussieht. Bin leider noch blutiger Anfänger
    Ich wollte auch meine Rechenschritte in eine Prozedur schreiben.
    Nur das wollte ich eben erst machen, wenn das Programm läuft, dass für den Fall es ich die Prozedur(en) nicht hinbekommen wenigstens etwas abgeben kann.

    Ich werd mal versuchen mich mit deinem Code (Badestrand) auseinanderzustezen.
    Steig da grad nicht so dahinter.

    Vielleicht seh ich den Wald vor lauter Bäumen nicht mehr.
    Bin schon seit über 1 Monat an der Aufgabe und das war bissher das beste was ich hinbekommen habe.

    0
  • *

    Badestrand schrieb:

    void MultiplyWith( unsigned int num );

    Bietet C++ nicht auch die Möglichkeit Operatoren wie bspw. * zu überladen, bzw. neu zu definieren? Wäre doch noch schöner!

    0
  • B

    ºgrimmsenº® schrieb:

    Badestrand schrieb:

    void MultiplyWith( unsigned int num );

    Bietet C++ nicht auch die Möglichkeit Operatoren wie bspw. * zu überladen, bzw. neu zu definieren? Wäre doch noch schöner!

    Ich dachte das wäre vielleicht ein bisschen viel für den Anfang 🙂 Aber sonst hast du natürlich vollkommen Recht!

    0
  • V

    man könnte auch einfach die GMP verwenden, die würd afaik inzwischen auch für C++ angeboten (wobei die Klassen glaub ich auch bloß Wrapper um die C Operationen sind)

    0
  • C

    Im produktiven Code wäre das eine Empfehlung, aber hier gilt:

    sepH2807 schrieb:

    Ich soll das mit Feldern und oder Strings lösen.
    Also keine Bibliothek wie GMP, NTL ...

    Ansonsten solltest du das schriftliche Multiplizieren nachbauen (vergiss dabei Überträge nicht).

    0
  • ?

    Hallo sepH2807,

    Ich habe Deinen Code nicht gelesen, aber was erwartest Du denn als Ergebniss, wenn Du Feld[1] mit 3 multiplizierst. 3*0=0.

    DJohn

    0
  • S

    DJohn@work schrieb:

    Hallo sepH2807,

    Ich habe Deinen Code nicht gelesen, aber was erwartest Du denn als Ergebniss, wenn Du Feld[1] mit 3 multiplizierst. 3*0=0.

    DJohn

    Ja genau. Somit sollte dann später in jedem Feld eine Zahl stehen.

    für Fakultaet von 10! = 3628800

    Also:
    Feld[6] = 3
    Feld[5] = 6
    Feld[4] = 2
    Feld[3] = 8
    Feld[2] = 8
    Feld[1] = 0
    Feld[0] = 0

    Das setzt natürlich auch überträge auf das nächste Feld voraus.

    0
  • F

    Im Grunde brauchst du folgendes:

    Ein dynamisches Array (zB std::map<int,Digit>) das die Digits beinhaltet und die erste Stelle der Zahl an Stelle 0 steht usw.

    Dann den * Operator der ein Digit mit einem anderen multipliziert. Den Übertrag gibst du dann an die nächste Stelle mit dem + Operator weiter und gehst mit diesem + so lange durch das Array bis kein Übertrag mehr da ist.

    Wenn du ohne temporäre Variablen arbeitest musst du folgendes beachten:
    Bei * gehe von der höchsten Stelle bis 0 durch.
    Bei + gehe von der aktuellen Stelle Richtung der höchsten.

    Ansonsten multiplizierst du den Übertrag immer gleich mit und ruinierst dir das Ergebnis.

    0
  • V

    sorry, das mit der GMP hatte ich übersehen (also, dass die nicht verwendet werden darf)

    0
Anmelden zum Antworten