Fakultaet mit n= 60 berechnen



  • Hallo Zusammen. Ich hab folgende Aufgabenstellung. Ich muss die Fakultaet n= 60 zu berechnen. Leider reicht keine Datentypvariabel aus um diese darzustellen,. Weiß jemand wier ich das Problem lösen kann, das mir kein Minuswert ausgegegeben wird? Danke für eure Hilfe.

    #include <iostream>
    using namespace std;
    
    
    long long fakultaet(int n)
    {
    //Berechnet  n!
        int y=1;
        for(int i=1; i<=n; ++i)
        y= y*i;
        return y;
    }
    
    
    int main(){
    
    
    cout << "Bitte gebe n ein: " << endl;
    
    int n;
    cin >> n;
    
    long long y= fakultaet(n);
    
    
    {
    
    cout << "Die Fakultaet von " << n << "ist: "  << y <<endl;
    }
    
    
    }
    


  • Einfache Lösung:
    Du kannst double benutzen, der geht bei 64 bit bis 10e308. Da die Fakultät immer ganzzahlig ist bekommste auch keine Probleme mit Rundungsfehlern.

    Aufwändige Lösung:
    Schnapp dir ein BigInt Bibliothek und mach´s damit.



  • @steven-w sagte in Fakultaet mit n= 60 berechnen:

    kein Minuswert ausgegegeben wird?

    Das ist einfach: verwende unsigned

    Der Wert ist dann natürlich immer noch nicht korrekt!

    Was hilft es dir, wenn du zwar die Funktion fakulteat als long long definierst, innen aber immer noch int verwendest?

    Ansonsten: was @DocShoe sagt.


  • Mod

    Der Sinn der Aufgabe ist sicherlich, dass du eben nicht die eingebauten Datentypen benutzt. Die übliche Idee wäre, dass du mehrere Integer zu einem neuen Datentyp zusammenfasst, und für diesen dann die nötigen Grundrechenarten implementierst (wie schriftliches Rechnen in der Grundschule). Und damit implementierst du dann die Fakultät.

    Das ist keine Kleinigkeit. Erwarte nicht, das mit 30 Zeilen zu lösen.

    PS: https://www.c-plusplus.net/forum/topic/352433/eigenen-datentyp-in-c-anlegen
    Was ein Zufall. Die vorherige Aufgabe verlangt genau das, was ich oben schrieb.



  • @SeppJ

    ja das anlegen eines eigenen Datentypen wird auch in der Aufgabe verlangt, nur komm ich damit leider nicht weiter. Ich stell mich ziemlich schwer bei dieser Aufgabe an.


  • Mod

    @steven-w sagte in Fakultaet mit n= 60 berechnen:

    @SeppJ

    ja das anlegen eines eigenen Datentypen wird auch in der Aufgabe verlangt, nur komm ich damit leider nicht weiter. Ich stell mich ziemlich schwer bei dieser Aufgabe an.

    Tja, die Aufgaben bauen nun einmal aufeinander auf. Du wirst die zweite nicht ohne die erste lösen können. So etwas zu erkennen, ist auch etwas, was du als Schüler/Student können musst.

    Es ist auch ziemlich unhöflich, dass du das dann einfach so hier als Frage stellst und man dir diesen wichtigen Kontext unter Verfolgung deiner Beitragshistorie aus der Nase ziehen muss. DocShoe und manni66 haben sich Mühe für ernstgemeinte Antworten gegeben, aber deren Antworten sind direkt für die Tonne, wenn man diesen Kontext kennt.



  • @DocShoe sagte in Fakultaet mit n= 60 berechnen:

    Du kannst double benutzen, der geht bei 64 bit bis 10e308. Da die Fakultät immer ganzzahlig ist bekommste auch keine Probleme mit Rundungsfehlern.

    Da double aber auch nur 16 effektive Stellen hat, geht dann doch etwas verloren.

    Und ganzzahlig ist bei Fließkommazahlen mit mehr als einer Stelle (als ab 2) schon recht selten.

    Ist 1.5E1 ganzzahlig?



  • Für 60! kannst du auf jeden Fall schon ohne Probleme die Stirlingformel n!2πn(n/e)nn! \approx \sqrt{2\pi n} \, (n/e)^n nutzen.
    Ich frage mich jetzt aber, ob deine eigentliche Aufgabe ist, eine BigInt-Klasse zu entwickeln - oder eine zu ergooglen. 😉


  • Mod

    @wob sagte in Fakultaet mit n= 60 berechnen:

    Ich frage mich jetzt aber, ob deine eigentliche Aufgabe ist, eine BigInt-Klasse zu entwickeln - oder eine zu ergooglen. 😉

    Siehe meinen vorherigen Beitrag, bzw. Posthistorie von steven-w für die Antwort darauf. Der Sinn der Aufgabe ist nicht wirklich, den Wert der Fakultät von 60 kennen zu lernen, sondern dass der angehende Programmierer lernt, mit komplexen Datentypen und abstrakten Konzepten umzugehen. 60! ist bloß ein Beispiel, weil man (als Lehrer) die Ausgabe leicht kontrollieren kann, und es keinen realistischen Weg gibt, die Aufgabe auf anderem Weg zu lösen.



  • Danke für das Feedback. Das ganze sollte hier natürlich so nicht rüber kommen, das ich hier die anderen irgendwie ohne Infos stehen lasse. Die Aufgabe besteht aus mehreren Teilen und ich wollt mir halt hier Hilfe zu den unterschiedlichen Themen dazu holen. Danke trotzdem.



  • @steven-w sagte in Fakultaet mit n= 60 berechnen:

    @SeppJ

    ja das anlegen eines eigenen Datentypen wird auch in der Aufgabe verlangt, nur komm ich damit leider nicht weiter. Ich stell mich ziemlich schwer bei dieser Aufgabe an.

    Schön, dass du dieses unwichtige Detail doch noch erwähnst o.O


  • Mod

    Dann ist die Antwort: Du hast es hinbekommen, eine korrekte Fakultätsfunktion zu schreiben. Für Integer. Wenn du die gleiche 5-zeilige Funktion auf einen Datentypen überträgst, der beliebig große Zahlen darstellen kann, dann wirst du damit korrekt 60! ausrechnen können. Insofern: Aufgabe gelöst. Aber halt nur ~2% der Gesamtaufgabe.



  • @steven-w
    Schon mal überlegt eine eigene BitInt Klasse zu entwickeln, welche auf Strings arbeitet?

    Grundgerüst:

    class BigInt
    {
    private:
      std::string mIntRep;  ///< Interne Darstellung des BigInts (z.B. "13")
    
    public:
      void Set(unsigned int X)
      {  
         // Wandele X in einen String
      }
    
      void Add(const BigInt& x)
      {
        // Führe Addition auf beiden Strings per Hand wie in der Grundschule durch 
      }
    
      void Mul(unsigned int x)
      {
        // Wandele X in einen String
        // Führe Multiplikation auf beiden Strings per Hand wie in der Grundschule durch 
        // Also 
        // 12 * 32 
        // -------
        //     36
        //      24
        // -------
        //     384
      }
    
      std::string GetValue() 
      {
        // Fill me
      }
    };
    


  • @DirkB
    Jau. facepalm


  • Mod

    @Quiche-Lorraine sagte in Fakultaet mit n= 60 berechnen:

    @steven-w
    Schon mal überlegt eine eigene BitInt Klasse zu entwickeln, welche auf Strings arbeitet?

    Zwar möglich, aber würde ich mir nochmal genau überlegen. Mit String ist es zwar schön anschaulich, aber dafür handelt man sich zusätzliche Komplexität bei der Implementierung der Rechenoperationen ein (gegenüber dem vector<unsigned> als Alternative). Ich kann jetzt aber auch keine klare Empfehlung für das eine oder andere aussprechen, denn nach den vorherigen Fragen zu urteilen, hätte steven-w Schwierigkeiten sowohl mit der hohen Abstraktion von vector<unsigned> als auch mit der Komplexität von string. Muss er selber wissen, was ihn davon mehr anspricht. Aber die Alternative musste ich noch nennen. @steven-w : Eins von beidem muss es sein, alternative Lösungen wären nur noch komplexer.

    (und die Stringlösung ist natürlich viel weniger effizient, aber das spielt bei so kleinen Zahlen mit 80 Stellen wohl kaum eine Rolle 🙂 )



  • @SeppJ sagte in Fakultaet mit n= 60 berechnen:

    Mit String ist es zwar schön anschaulich,

    Und genau deswegen habe ich an Strings gedacht.

    Aber klar, dadurch bekomme ich eine zusätzliche Komlexität (Int zu String Wandlung, Addition zweier char Werte) hinzu.



  • Für 60! braucht man > 270 Bit.
    Mit zwei Teilen kommt man also nicht aus.
    Und sobald man mehr als zwei hat, kann man mMn. auch gleich beliebig viele machen.

    Was std::string angeht: das ist mMn. gar keine Schlechte Idee. Also wenn man das Dezimalsystem verwendet. Dann muss man die Zahl zur Ausgabe nämlich nicht nochmal umrechnen. D.h. man spart sich erstmal die Division zu implementieren. Addition und Multiplikation reichen aus.
    (OK, man kann die Umrechnung auch ohne Division implementieren. Ist vermutlich nichtmal so schlimm was Laufzeit angeht - zumindest nicht bei Umrechnung nach Basis 10.)


  • Mod

    @hustbaer sagte in Fakultaet mit n= 60 berechnen:

    Was std::string angeht: das ist mMn. gar keine Schlechte Idee. Also wenn man das Dezimalsystem verwendet. Dann muss man die Zahl zur Ausgabe nämlich nicht nochmal umrechnen. D.h. man spart sich erstmal die Division zu implementieren. Addition und Multiplikation reichen aus.
    (OK, man kann die Umrechnung auch ohne Division implementieren. Ist vermutlich nichtmal so schlimm was Laufzeit angeht - zumindest nicht bei Umrechnung nach Basis 10.)

    Kannst ja zur Basis 1,000,000,000 rechnen mit vector<uint32> 🙂



  • @steven-w sagte in Fakultaet mit n= 60 berechnen:

    @SeppJ

    ja das anlegen eines eigenen Datentypen wird auch in der Aufgabe verlangt, nur komm ich damit leider nicht weiter. Ich stell mich ziemlich schwer bei dieser Aufgabe an.

    Fangen wir mal am Anfang an. Du sollst die Fakultät von 60 berechnen. Die Zahlen von 1 bis 60 lassen sich mit 6Bit darstellen. D.h. das Ergebnis ist nicht größer als 360Bit (60×6Bit).

    Die Multiplikation zweier Zahlen a×b lässt sich in a×(c1 + c2) = a×c1 + a×c2 zerlegen. Deshalb darfst Du z.B. untersten 58 Bit mit der Zahl a (die hier 6Bit groß ist) multiplizieren, erhälst eine 64Bit Zahl, und addierst als Übertrag die oberen 6Bit dieser Teilmultipliktation auf das Ergebnis der Multiplikation der höherwertigen Bits auf.



  • @SeppJ sagte in Fakultaet mit n= 60 berechnen:

    Kannst ja zur Basis 1,000,000,000 rechnen mit vector<uint32> 🙂

    Das ginge auch gut, ja.
    Bleibt sich vom Programmieren her aber ziemlich gleich denke ich. Laufzeit sollte es natürlich ordentlich schneller sein.


  • Mod

    Da frage ich mich, was eigentlich die beste Basis wäre für minimalen Programmieraufwand (Laufzeit außer acht gelassen). Ich würde spontan so etwas vorschlagen wie die größte Zehnerpotenz die kleiner als sqrt(max value) ist, also 10,000 bei uint32 (weil sqrt(2^32) = 2^16 = 65536). Da hat man

    • triviale Darstellung im Dezimalsystem
    • genügend Platz nach oben, um Überläufe trivial zu handhaben bei Addition
    • selbiges sogar bei Multiplikation
    • Keine Ziffernwertumrechnung wie bei string

Log in to reply