Problem beim Bruteforce algo

Keksman

Hallo,

momentan versuche ich mich gerade an einem Bruteforce Algorithmus für den ASCII Zeichensatz. Allerdings weiß ich nicht wie ich es hinbekommen kann, dass das Programm nachdem es alle Zeichen von a-z (voerst nur das abc) überprüft hat, danach auch aa, ab, ac ... u.s.w. überprüft. Ich bin Anfänger und im c++ Primer auf Seite 260. Vielleicht hilft euch diese Angabe um zu bestimen ob ich überhaupt in der Lage wäre so einen Code zu schreiben.
Hier der Code von mir:

#include <iostream>
using namespace std;

int main()
{
    char abc[] = {"abcdefghijklmnopqrstuvwxyz"};
    for(size_t ix = 0; ix != (sizeof(abc)/sizeof(char))-sizeof(char); ++ix){
        //cout << abc[ix] << endl;
        if(ix == sizeof(abc)-(2*sizeof(char)))
            ix=-1;
    }
    return 0;
}

SeppJ

Zwei Ansätze:
Rekursiv: Immer ein weiteres der möglichen Zeichen anhängen.
Iterativ: Abzählen der Kombinationen

Jeweils beide sind in unzähligen Varianten machbar. Hier jeweils ein Beispiel:

#include <iostream>
#include <string>
using namespace std;

void brutalize_recursive(size_t max_length, const string &alphabet, string current = string())
{
  cout << current << '\n';
  if (current.size() < max_length)
    {
      for (size_t i = 0; i < alphabet.size(); ++i)
        brutalize_recursive(max_length, alphabet, current + alphabet[i]);
    }
}

void brutalize_iterative(size_t max_length, const string &alphabet)
{
  size_t num_combinations = 1;
  for (size_t i = 0; i < max_length; ++i) num_combinations *= alphabet.size();

  for (size_t combination = 0; combination < num_combinations; ++combination)
    {
      size_t i = combination;
      while (i)
        {
          cout << alphabet[i % alphabet.size()];
          i /= alphabet.size();
        }

      cout << '\n';
    }
}

int main()
{
  string alphabet = "abcde";
  cout << "rekursiv:\n";
  brutalize_recursive(3, alphabet);
  cout << "iterativ:\n";
  brutalize_iterative(3, alphabet);
}

Fragen? Sprachlos? Alles klar?

Zu Variante 1 weiß ich nicht, was ich da noch erklären sollte, außer eventuell technischen Dingen, die du noch nicht gesehen hast, wie dem Defaultargument. Variante 2 benutzt einen einfachen Algorithmus zum Berechnen der Darstellung eines Ziffernsystems, um von der Kombinationsnummer auf die tatsächliche Kombination zu kommen. Die Ziffern sind dabei die Buchstaben des Alphabets.

Vorteile Variante 1:
- Einfach zu programmieren und zu verstehen
- Robust gegenüber vielen möglichen Kombinationen, so lange der Speicher reicht
Nachteile Variante 1:
- Belegt viel mehr Speicher als Variante 2 und braucht im Programmverlauf immer mehr
- Dürfte langsamer sein als Variante 2

Vorteile Variante 2:
- Keine Probleme mit Speicher, kann auch auf kleinsten Computern laufen
- Dürfte viel schneller sein als Variante 1, da keinerlei Kopier-, Allokier- und Funktionsaufrufoverhead
Nachteile Variante 2:
- Wenn die Anzahl der möglichen Kombinationen groß wird, muss man zu Datentypen greifen, die entsprechend große Zahlen aufnehmen können. Ohne Hilfsbibliothek ist das vergleichsweise ekelig zu programmieren

Keksman

Danke Dir für dein schnelles Codebeispiel.
Fragen habe ich. Vorweg möchte ich jedoch erwähnen, dass ich das Kapitel Funktionen noch nicht hatte. Das dauert noch ca 40 Seiten.
In deiner Funktion

void brutalize_recursive(size_t max_length, const string &alphabet, string current = string())

Was macht "const string &alphabet" und was macht die Funktion "string()"?
Wieso muss bei

const string &alphabet

kein * vor const stehen? Es ist doch ein Zeiger auf ein String Objekt.?
Wo wird eigentlich defineirt welche Zeichen "gebruteforced" werden? // Sorry habe ich übersehen.
So ganz kann ich deinen Code nicht verstehen. Mir fehlt einfach noch Erfahrung.

SeppJ

Nun, ohne Funktionen zu kennen, ist Rekursion natürlich unmöglich zu verstehen, da wäre wohl eher das zweite Beispiel etwas für dich, das man auch problemlos aus der Funktion herausnehmen könnte:

int main()
{
  string alphabet = "abcde";
  size_t max_length = 3;
  size_t num_combinations = 1;
  for (size_t i = 0; i < max_length; ++i) num_combinations *= alphabet.size();

  for (size_t combination = 0; combination < num_combinations; ++combination)
    {
      size_t i = combination;
      while (i)
        {
          cout << alphabet[i % alphabet.size()];
          i /= alphabet.size();
        }

      cout << '\n';
    }
}

Zu den konkreten Fragen:

was macht die Funktion "string()"?

Das ist der Aufruf des Konstruktors der Stringklasse. Der erzeugt einen leeren String. Die Syntax mit dem GLeichheitszeichen ist ein Defaultargument, das benutzt wird, wenn sonst nichts angegeben wurde. Dies wird hier als Anfangszustand der Rekursion benutzt.

Was macht "const string &alphabet" [...] Wieso muss bei
const string &alphabet
kein * vor const stehen? Es ist doch ein Zeiger auf ein String Objekt.?

Nicht ganz. Es ist eine Referenz auf einen (konstanten) String, kein Zeiger. Eine Referenz ist von der Funktion her ganz was ähnliches wie ein Zeiger, aber mit angenehmerer Syntax und ein paar anderen Kleinigkeiten, die sie als Funktionsparameter (meistens) besser geeignet machen als ein Zeiger.

Wo wird eigentlich defineirt welche Zeichen "gebruteforced" werden?

Zeile 38 und 40 wird den Funktionen jeweils mitgegeben, welches Alphabet benutzt werden soll. Konkret wird hier das Alphabet ein paar Zeilen vorher definiert.

void funktion(const datentyp& variablenname)

Das nennt sich call-by-reference (manchmal auch pass-by-reference). Das bedeutet einfach, dass das Argument, das du einer Funktion übergibst, nicht kopiert wird, sondern die Funktion eine Referenz (Aliasname) auf jenes Argument erhält. ist eine Referenz (Aliasname) für einen const std::string . Unterm Strich heißt das, dass deine Funktion mit der originalen Variable arbeitet. Das const hat dabei den Sinn, dass du innerhalb der Funktion die originale Varialbe nicht (aus Versehen) manipulierst.

Eine Funktion kann Defaultparameter haben (von rechts her). Das heißt, es wird ein Defaultargument erzeugt, wenn du deiner Funktion kein Argument übergibst. string() ruft den Standardkonstruktor von string auf. Es wird also einfach ein string-Objekt erzeugt, wenn der Funktion kein string-Objekt übergeben wird.

krümelkacker

SCNR!

#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <cassert>

struct brute_force_word
{
  std::string as_string;       // Zeichenkette
  std::vector<int> as_indices; // die Indizes der einzelnen Zeichen
                               // bzgl eines Alphabets
};

void brute_force_next(brute_force_word & w, std::string const& alphabet)
{
  assert(w.as_string.size() == w.as_indices.size());
  assert(alphabet.size() > 0);
  int s = w.as_indices.size();
  int i = 0;
  int b = alphabet.size();
  while (i<s) {
    int index = w.as_indices[i]+1;
    if (index >= b) {
      w.as_indices[i] = 0;
      w.as_string [i] = alphabet[0];
      ++i;
    } else {
      w.as_indices[i] = index;
      w.as_string [i] = alphabet[index];
      return;
    }
  }
  w.as_indices.push_back(0);
  w.as_string .push_back(alphabet[0]);
}

int main()
{
  std::string alphabet = "xo";
  brute_force_word w;
  while (w.as_string.size()<=3) {
    std::cout << "\"" << w.as_string << "\"\n";
    brute_force_next(w,alphabet);
  }
}

Keksman

Ich denke es ist besser wenn ich weiter mit dem Buch arbeite und das Thema Bruteforce erstmal sein lassen. Den Code von SeppJ verstehe ich aber, ich wüsste selber nicht wie ich so einen Code schreiben sollte. Danke auch für alle anderen Antworten. Eine Frage an SeppJ: In welchem Alter hast du Angefangen zu Programmieren, spezziel jetzt c++? Ich mit 15.

SeppJ

Keksman schrieb:

Eine Frage an SeppJ: In welchem Alter hast du Angefangen zu Programmieren,

So um die 13.

spezziel jetzt c++?

So um die 26 . Dazwischen waren aber auch mal 5 Jahre Pause.