n - for-Schleifen durchlaufen



  • Hallo 🙂
    ich bin mit rekursiven Sachen noch nicht so gut (ich weiß was es ist, aber je nach Algorithmus ist es noch brainfuck für mich) und ich kann mir denken, dass für mein folgendes Problem Rekursion die Lösung sein könnte. Ich möchte es das Prinzip der Lösung allgemein verwenden können, aber um zu erklären woran ich hänge, nehmen wir folgendes Beispiel:

    Ich möchte alle Kombinationen von Zahlen durchlaufen, die n Ziffern haben. Die Funktion dafür nenne ich mal f.

    Wenn ich weiß, wie groß n ist, z.B. 2, dann würde man das so machen:

    for (int i = 1; i <= length; i++) {
        for (int j = 1; j <= length; j++) {
            std::string number = std::to_string(i) + std::to_string(j);
            // work with number...
            functionPointer(number);
        }
    }
    

    Für n = 3:

    for (int i = 1; i <= length; i++) {
        for (int j = 1; j <= length; j++) {
            for (int k = 1; k <= length; k++) {
                std::string number = std::to_string(i) + std::to_string(j) + std::to_string(k);
                // work with number...
                functionPointer(number);
            }
        }
    }
    

    In meinem Code rufe ich es dann so auf:

    f(2);
    f(3);
    // ...
    

    Macht euch bitte keine Gedanken wo functionPointer herkommt usw. Es geht mir einfach darum, nicht für jede Zahl die for-Schleifen zu copy-pasten und um eine for-Schleife zu erweitern.



  • Du möchtest also nicht Zahlen haben, sondern Strings.

    Wenn du zahlen haben willst, dann geht die Loop nämlich einfach von 10n110^{n-1} (inklusive) bis 10n10^n (exklusive). Das ist ein wesentlich einfacheres Problem.

    int start = stol("1" + string(n-1, '0'));
    int ende_inklusive = stol(string(n, '9'));
    // schlagt mich nicht... man suche sich eine pow-Funktion für Ganzzahlen aus einer
    // Mathe-lib oder schreibe das natürlich selbst, ohne über string zu gehen ;)
    
    for (int i = start; i <= ende_inklusive; ++i) 
        cout << i << '\n'; // bzw. function_ptr(i);
    

    Was du machen kannst, wenn du aber doch Strings brauchst und keine Zahlen:

    void permutation_internal(string &s, const string &allowedChars, size_t pos) {
        if (pos == s.size()) { 
            cout << s << '\n'; // bzw function_ptr(s)
            return;
        }
        for (char c: allowedChars) { 
            s[pos] = c; 
            permutation_internal(s, allowedChars, pos + 1);
        }
    }
    
    void ich_lerne_rekursion(int length, const string &allowedChars) {
        if (allowedChars.empty() || length == 0) return;
        string s(length, allowedChars[0]);
        permutation_internal(s, allowedChars, 0);
    }
    
    // Beispielaufruf:
    ich_lerne_rekursion(3, "012"); // printet alle 3-stelligen Zahlen (eigentlich strings) mit den Ziffern 0,1,2
    ich_lerne_rekursion(2, "ab"); // printet alle 2-stelligen Strings mit den Zeichen a und b, d.h. aa, ab, ba, bb
    

    Und noch ein Tipp, falls du Strings nur permutieren willst: Siehe https://en.cppreference.com/w/cpp/algorithm/next_permutation

    Edit:
    ah, ich sehe gerade, ich habe dich nicht ganz richtig verstanden. Du möchtest wirklich Zahlen, also z.B. 11. Dann soll es geben
    1+1 = 11
    11+1 = 111
    aber auch
    1 + 11 = 111?

    Jedenfalls kannst du es eigentlich genauso machen wie gezeigt, nur dass du den String s nicht von der Länge her festlegen kannst.

    void foo(int von, int bis, int n, string s = {}) {
        if (n == 0) { cout << s << '\n'; return; }
        for (int i = von; i <= bis; ++i)
            foo(von, bis, n-1, s + to_string(i));
    }
    
    foo(9, 11, 2);
    // gibt aus: 99, 910, 911, 109, 1010, 1011, 119, 1110, 1111
    


  • Du brauchst nur 2 verschachtelte Schleifen, eine zählt alle Zahlen durch, die andere die Ziffern. Also Beispiel n = 5 und length = 10 zählt die äussere Schleife von 10000-99999 und die innere von 0 bis 4.



  • @Solix0x sagte in n - for-Schleifen durchlaufen:

    Ich möchte alle Kombinationen von Zahlen durchlaufen, die n Ziffern haben. Die Funktion dafür nenne ich mal f.

    ich habe vor langer zeit mal etwas ähnliches gecodet
    (ohne rekursion)
    vielleicht hilft es dir ja.

    
    void counter (int n, int min, int max)
    {
        int* num = new int[n];
        for (int i = 0; i < n; i++)
            num[i] = min;
        while (1)
        {
            int *ptr = num + n - 1;
            for (int i = 0; i < n; i++)
                cout << num[i] << " ";
            cout << endl;
            int a = (*ptr)++;
            while (a == max)
            {
                *ptr = min;
                if (ptr-- == num)
                {
                    delete num;
                    return;
                }
                a = (*ptr)++;
            }
        }
    }
    
    

    n ist die anzahl der stellen, min und max geben den bereich einer einzelnen ziffer an.

    beispiele:
    counter (3, 0, 9) zählt von 0 bis 1000
    counter (8, 0, 1) 8 bit binärzähler


Log in to reply