Beiträge von henriknikolas

Ich habe mich mal ein bisschen nach dem Algorithmus umgeschaut und bin dabei auf das hier gestoßen:
http://jbc-utn-frc.googlecode.com/svn/4to/dlc/Cl…73-chandler.pdf
Das sieht sehr gut aus!
Vielleicht weißt du ja noch andere Quellen, die sich mit diesem Algorithmus beschäftigen, vielleicht auch in deutscher Sprache.

Nein nein, du hast vollkommen recht, ist mir vorhin auch aufgefallen, deshalb hab ich meinen Kommentar geändert (16.48).
Das überprüfen ob eine Permutation bereits vorher auftrat, habe ich schon eingebaut.

Zitat von emptyvi

Ansonsten schau dir mal http://stackoverflow.com/questions/1277…elements-from-n (und dort bei der ersten Antwort "Chase's Twiddle" an) - ist wohl das was du suchst

Bin mir auch nicht sicher, ob ich dein Problem richtig verstanden, denn folgende beiden Punkte verstehe ich offen gestanden nicht:

• Du hast für 26 Buchstaben _alle_ Permutationen berechnen lassen? Kann ich mir nicht vorstellen.. das wären 26! = 403.291.461.126.605.635.584.000.000 Kombinationen. Selbst bei 100 Milliarden Kombinationen pro Sekunde würde das 127882883 Jahre dauern.
• Warum genau überprüfst du bei einer Permutation, ob ein Element in den ersten k Elementen doppelt Auftritt. Kann bei einer Permutation eigentlich nicht sein, siehe http://www.cplusplus.com/reference/algo…xt_permutation/

Chase's twiddle hört sich gut an. Ich habe zum testen die Menge meiner Buchstaben erstmal auf 10 reduziert. Dann hat es etwa 30 s gedauert alle Variationen auszurechnen.
Die Überprüfung auf doppelte Elemente ist natürlich schwachsinn, kein Wunder, dass der Vorgang 30s braucht.
Ich werde das gleich mal ausprobieren, vielen dank nochmal für die Anmerkung.

Hallo,
ich habe eine Menge von 26 Buchstaben und möchte daraus Wörter bilden. Die Länge des Wortes (k) wird jeweils eingelesen. Außerdem muss jedes Wort aus unterschiedlichen Zeichen bestehen. Jetzt suche ich einen Algorithmus, der mir alle Kombinationen von Wörtern für eine bestimmte Menge generiert. Das ist vergleichbar mit dem ziehen von k-Kugeln aus einer Urne ohne zurücklegen, die n unterschiedliche Kugeln enthält.
In der STL gibt es die Funktion next_permutation, die alle Permutationen generiert. Dann habe ich für jede generierte Permutation die ersten k Elemente genommen und geprüft ob ein Element doppelt auftrat. Jetzt ist das Problem, dass diese Vorgehensweise extrem lange dauert, vielleicht gibt es dafür ja einen speziellen Algorithmus, da das bestimmt ein Standardproblem ist.

So, ich hab jetzt meinen Code schön dokumentiert, hier ist er:

bool Int::compare_size(char *a, char*b, unsigned long long a_max, unsigned long long b_max)
{
    //Diese FUnktion liefert a >= b zurück
    //Nullen am Anfang von a und b entfernen
    check(a, a_max);
    check(b, b_max);
    //Überprüft ob a >= b gilt
    //Wenn a länger ist als b ist a > b
    if(a_max > b_max) return true;
    //Wenn b länger als ist als a ist b > a bzw. a < b
    else if(b_max > a_max) return false;
    /*Da a und b die gleiche Länge haben, werden jeweils zwei Zeichen a[i] und b[i] überprüft,
    ist a[i] > b[i] ist auch a größer b und es wird true zurückgegeben
    ist b[i] > a[i] ist b auch größer als a und es wird false zurückgegeben*/
    for(unsigned long long i = 0; i < a_max; i++)
        if(a[i] > b[i]) return true;
        else if(b[i] > a[i]) return false;
    //Es stimmen alle Zeichen überein, also ist a = b und somit a >= b
    return true;
}
bool Int::positiv_sub(char *a, char *b, unsigned long long& a_max, unsigned long long& b_max)
{
    //Die Funktion überprüft ob a >= b gilt, und rechnet wenn dies gilt a-= b aus. Es wird a >= b zurückgegeben, 
    //also ob die Subtraktion moeglich war
    //Wenn b größer ist, ist keine Subtraktion möglich
    if(!compare_size(a, b, a_max, b_max)) return false;
    //a_pos ist die aktuelle Position für die Subtraktion in a, b_pos die aktuelle Position in b
    //val ist die Ziffer die dann im Ergebnis an der Position j steht
    long long a_pos =  a_max - 1, b_pos = b_max - 1, val = 0, uebertrag = 0;
    for(int j = a_max - 1; j >= 0; j--) 
    { 
        val = -uebertrag; 
        uebertrag = 0;
 
        if(b_pos >= 0 && a_pos >= 0)   
        {             //Wenn die untere Ziffer kleiner als die obere Ziffer ist
            if(b[b_pos] <= a[a_pos])
            {
                val += (a[a_pos] - 48);
                val -= b[b_pos] - 48;
            }
            //Wenn die untere Ziffer größer als die obere Ziffer ist
            else if(b[b_pos] > a[a_pos])
            {
                val +=  10 + a[a_pos] - b[b_pos];                 uebertrag = 1;             }


        }


        if(b_pos >= 0 && a_pos < 0)
        {
            val +=  b[b_pos] - 48;             uebertrag = 1;


        }
        else if(a_pos >= 0 && b_pos < 0)
        {
            val += a[a_pos] - 48;
        }
        a[j] = val + 48;
        a_pos--;
        b_pos--;
    }
    //Überflüssige Nullen in a am Anfang entfernen
    check(a, a_max);
    return true;
}
Int Int::operator/=(const Int& a)
{
    //Wenn a falsch initialisiert wurde, oder a größer als this ist, oder a = 0, dann wird abgebrochen
    if(badformat || a.badformat || operator<(a) || a[0] == 0) return Int(0);
    unsigned long long divisor_max = 0;
    char *divisor;
    //Wenn das erste Zeichen von this größer ist, als das erste Zeichen von a
    if(operator[](0) < a[0])
    {
        divisor_max = max - 1;
        divisor = new char[divisor_max];
        //divisor übernimmt alle Zeichen von a
        for(long long m = 0; m < a.max; m++)
            divisor[m] = a[m]  + 48;
        //Es werden solange Nullen angefügt, wie divisor <= *this gilt
        for(long long m = a.max; m < divisor_max; m++)
            divisor[m] = 48;
    }
    else if(operator[](0 )>= a[0] )
    {
        divisor_max = max;
        divisor = new char[divisor_max];
        //divisor übernimmt alle Zeichen von a
        for(long long m = 0; m < a.max; m++)
            divisor[m] = a[m] +48;
        //Es werden solange Nullen angefügt, wie divisor <= *this gilt
        for(long long m = a.max; m < divisor_max; m++)
            divisor[m] = 48;
    }
    unsigned long long dividend_max = max;
    char * dividend = new char[dividend_max];
    //dividend übernimmt alle Ziffern von *this
    for(long long m = 0; m < dividend_max; m++) dividend[m] = operator[](m) + 48;
    //Das ergebnis kann maximal max + 1 - a.max Stellen haben
    char * ergebnis = new char[max - a.max + 1];
    long long temp = divisor_max;
    unsigned long long anzahl_ziffern = 0;
    //divisor_max - a.max ist die Anzahl der angefügten Nullen, solange die >= 0 ist wird die Schleife ausgeführt
    for(long long i = divisor_max - a.max; i >= 0; i--)
    {
        unsigned long long anzahl = 0;

        while(true)
        {
            //Die Schleife wird solange ausgefüht, wie dividend -= divisor >= 0 ist
            if(!positiv_sub(dividend, divisor, dividend_max, divisor_max)) break;
            anzahl++;
        }
        //Die letzte Null aus Divisor entfernen
        char *tmp = new char[--divisor_max];
        for(long long m = 0; m < divisor_max; m++)
            tmp[m] = divisor[m];
        delete divisor;
        divisor = new char[divisor_max];
        for(long long m = 0; m < divisor_max; m++) divisor[m] = tmp[m];
        //Das Ergebnis an der Stelle anzahl_ziffern ist die Anzahl, wie oft
        //die Subtraktion durchgeführt werden konnte
        ergebnis[anzahl_ziffern++] = anzahl + 48;
    }
    //das interne Array zum Speichern der Ziffern wird gelöscht, ihm wird ergebnis zugewiesen
    delete z;
    z = new char[anzahl_ziffern];
    for(unsigned long long i = 0; i < anzahl_ziffern; i++) 
        z[i] = ergebnis[i];
    if(vorzeichen != a.vorzeichen) vorzeichen = '-';
    else vorzeichen = '+';
    return *this;
}

Kann man das noch irgendwo optimieren oder verbessern, ich bin dankbar für jeden Ratschlag:thumb:

Ich hab die Division implementiert wie im folgenden Link beschrieben, volkards 2. Algorithmus eher am Ende:http://www.c-plusplus.de/forum/110407-full
Ich werde dann wenn ich wieder Zeit habe meinen Code hier posten, damit ihr nochmal rübergucken könnt, dann werde ich noch versuchen Bradons Variante zu implementierten und beide hinsichtlich ihrer Geschwindigkeit vergleichen. Das wird natürlich etwas dauern, da für mich jetzt die Schule wieder anfängt.

Vielen dank, werde ich mal ausprobieren, ich habe gestern noch eine andere Variante gefunden, dann kann ich die beiden Varianten mal vergleichen

Zitat von Bradon

Die Beschreibung ist etwas verworren, ich sehe aber spontan keinen Fehler
Du kannst auch gerne deinen Code posten, wenn du Hilfe beim Debuggen brauchst

JA, so sah auch der Code aus, ich hab alles wieder gelöscht und wollte die ganze Methode noch mal sauber programmieren. Wie würdest du die Methode umsetzen? Du musst jetzt keinen fertigen Code schreiben, nur so ein Pseudocode, also so formuliert wie ein Backrezept beispielsweise.

Ich hab gestern und vorgestern probiert die Methode für die Division zu machen, und habs irgendwie nicht geschafft:wein:
Ich beschreib euch nochmal meinen Ansatz, vielleicht ist daran ja etwas falsch:
1.Führe die folgenden Schritte solange durch, wie man eine geeignete Zahl hat, um durch den Divisor zu dividieren
2. Subtrahiere von dem gefundenen Dividenden den Divisor, solange wie der Dividend >= Divisor ist
3. Merke dir die Anzahl in einer Variable, die i-te Stelle der Ergebnis ist die Anzahl
4. Zähle i um eins hoch
5. Versuche an den Rest, der bei der Subtraktion geblieben ist, geeignete Ziffern von a anzuhängen, sodass man wieder eine
geeignete Zahl findet, die durch den Divisor dividiert werden kann.

Ist das richtig so, oder wie würdet ihr das Problem lösen

Zitat von Bradon

Verwende ein n-dimensionales Array, um die Anzahl der Stellen mit n zu potenzieren

Das verstehe ich jetzt irgendwie nicht, kannst du es mir genauer erklären

Mir ist grad noch was aufgefallen, ich speichere die Ziffern meiner Klasse in einem char array, das kann ja maximal so groß werden wie der größte unsigned long long, das ist zwar gewaltig und diese Zahl hat dann wesentlich mehr Stellen als die größte bis jetzt gefundene Primzahl, aber kann man das irgendwie umgehen?

Das ist eine super Idee, darauf muss man erst mal kommen. Ich mache die ganze Klasse zum Üben, aber auch weil ich sie später verwenden will. Ich mach das sozusagen als Freizeitprojekt, man kann ja immer etwas verbessern. Außerdem hab ich dann was eigenes, worauf ich stolz sein kann.

Eine andere Idee wäre sooft wir es geht Dividend-=Divisor zu machen, solange das größer 0 ist. Aber für große Differenzen dauert da ja ewig...

Bei der schriftlichen Multiplikation multiplizierst du ja immer nur 2 Ziffern das bedeutet das Ergebnis ist maximal 81 groß passt also immer in ein int. Bei der schriftlichen Division "nimmst" du dir aus dem Dividend immer Ziffern, dann teilst du diese Zahl durch den Divisor. Das ergibt dann immer eine Stelle des Ergebnis. Da der Divisor aber auch so groß sein kann, dass er nicht mehr in ein long long reinpasst, brauch ich eine andere Vorgehensweise.

Kann mir keiner helfen?

Hallo, ich arbeite gerade an einer Klasse für sehr große Zahlen, dabei verwende ich intern ein dynamisches char array wo die einzelnen Ziffern gespeichert sind. Ich habe bereits die Operatoren für Addition, Subtraktion und Multiplikation implementiert, nur bei der Division hab ich kein Plan.Als erstes dachte ich an die schriftliche Division, die man in der Schule lernt, aber die setzt sich ja auch aus Division zusammen.Ich kann aber nicht ausschließen, dass der Divisor so groß wird, dass er nicht mehr in ein long long reinpasst, und es einen Überlauf gibt.Hat jemand vielleicht eine Idee wie man die Division machen könnte, es gibt hier ja bestimmt einige, die schon mal solch eine Klasse geschrieben haben.

Kannst du mir nicht helfen:confused:

Ich brauch noch einmal deine Hilfe. Ich schreibe jetzt an einer Klasse für Gleichungssysteme. Eingabe und Ausgabe funktioniert auch, nur wollte ich noch einen Indexzugriff einbauen. Ich hab aber gesehen, dass es keinen [][] Operator gibt, ich hab dafür auch schon Lösungen im Internet gefunden, aber die funktionierten bei mir nicht so richtig, das liegt wohl wahrscheinlich daran, dass ich es nicht verstanden hab. Meine Klasse sieht so aus:

class Gleichungssystem
{
public:


        Gleichungssystem(long long anzahl);
        Gleichungssystem();
        void solve();                                   //Gleichungssystem lösen
        bool kleiner(groesse);                          //Array vergrößern
        bool groesser(groesse);                         //Array verkleinern
        //überladene Operatoren
        //Indexzugriff


        //Ein- und Ausgabe
        friend istream& operator>>(istream &s, Gleichungssystem &L);
        friend ostream& operator<<(ostream &s, Gleichungssystem L);
private:
        void tausche(int i, int j);
        void diagonalisieren();
        void einsetzen();
        void read();
        Bruch** Matrix;                                 //Hier werden die Werte gespeichert
        Bruch *Ergebnis;
        long long max;
        bool initialized;
};

Ich möchte jetzt zum Beispiel schreiben können:

Gleichungssystem L;
cin >> L[0][1];

Weißt du wie ich das hinkriegen kann?

So jetzt funktioniert das Einlesen als ganze Zahl oder als Bruch sehr gut. Eigentlich ein ziemlich simpler Weg:coolsmile:

//Ein- und Ausgabe
istream& operator>>(istream &is, Bruch &b)
{
        string ausdruck;
        long long zaehler, nenner;
        is >> ausdruck;
        zaehler = atoi(ausdruck.c_str());
        int pos = ausdruck.find('/');
        if(pos == -1)
        {
                b = Bruch(zaehler, 1);
                return is;
        }
        ausdruck.erase(0, pos+1);
        nenner = atoi(ausdruck.c_str());
        b = Bruch(zaehler, nenner);
        return is;
}

Ja, muss ich mal sehen ob ich noch einen Weg finde um das zurück zu schreiben.