C++: "Raten" simulieren (Bruteforce)

[Zuckerbaum]

Sorry vorweg - meine Frage ist wahrscheinlich etwas dämlich für geübte Programmierer:

Ich habe zu verschiedenen Problemen verschiedene Lösungsansätze programmiert und möchte nun aus Spaß den Zeitaufwand mit schlichtem "raten" vergleichen (also Bruteforce sozusagen). Folgendes Problem:

Ich habe ein Array "int array[n]" und eine Prüfroutine "bool pruef(int size, int *array_geraten, int *array_vorgabe)" welche die Einträge des Arrays eben überprüft. Dabei stammen alle Einträge des Arrays aus einem Intervall [a,b] der natürlichen Zahlen, n selbst ist ebenfalls eine natürliche Zahl (größergleich 1).

Wie bekomme ich es nun möglichst elegant hin, alle n Stellen des Arrays mit Einträgen aus [a,b] durchzuprobieren? Mir fallen da so Sachen wie rekursive Funktionen ein - aber das ist bei mir schon so lange her...

Noch interessanter wäre es, wenn man das Ratearray mit zufälligen Werten füllt - was "Raten" ja eher simulieren würde. Aber das sture durchprobieren würde mir für den Anfang auch ausreichen.

Kann mir kurz jemand helfen?

 

[moagnus]

Schleife mit Funktionsaufruf?

 

[Zuckerbaum]

Und wie erfasse ich damit alle (b-a+1)^n Möglichkeiten? Sei i mit 1<...<i<...<n die i-te Stelle im Array, dann muß ich doch (wenn ich bei n beginne) für alle i+1<...<n nochmal alle vorigen Schleifen durchlaufen um alles zu erfassen. Also ich müßte die Schleife ja irgendwie rekursiv aufrufen?

Vielleicht stehe ich auch nur total auf dem Schlauch. Kannst du das mal etwas ausführen was du meinst?

 

[Simpson474]

Ich versteh irgendwie deine Aufgabe nicht so ganz, aber reicht da nicht eine geschachtelte Schleife?

Für alle Einträge in array_vorgabe
	Für alle Einträge in array_geraten
		Überprüfen
	Ende Schleife
Ende Schleife

 

[moagnus]

Hm, lass mich dein Problem nochmal zusammenfassen. Nur, dass ichs genau kapier... Hab vllt. ein bisschen schnell gelesen.

Zulässige Intervallwerte sind a als Untergrenze und b als Obergrenze und in jedem Fall größer 0. Dann würde es sich schon mal anbieten, das Array als "unsigned int" zu deklarieren.
Jetzt willst du bei deinem Array der Größe n (>0) jedes Arrayfeld mit allen zulässigen Werten vergleichen. Also bspw. array[10] == 3 und array[10] == 4 usw.

Verstehe ich dein Problem richtig?

Und wenn ja: welchen Sinn hat das?

 

[Zuckerbaum]

Also mal konkret (meine Arrays beginnen bei [1]):
n=3, a=1, b=2
Dann möchte ich durchprobieren:

1 1 1, 1 1 2, 1 2 1, 1 2 2, 2 1 1, 2 1 2, 2 2 1, 2 2 2

wobei eben jede Ziffer ein eigenes Feld im Array hat. Für feste, kleine n ist das ja nicht schwer, aber wie programmiere ich das für variables, u.U. sehr großes n?

Ziel ist es, einen möglichst guten Startwert für gewisse numerische Probleme zu finden/erraten. Wäre jetzt müßig, das genau auszuführen. Ersteinmal wäre ich schon glücklich, wenn ich alle Möglichkeiten mit einem vorgegebenen Wert vergleichen könnte.

Kurz: Du (moagnus) hast mein Problem erkannt

 

[Raechaer]

Wenn ich dein Problem richtig verstanden habe sollte das mit Rekursion recht einfach zu lösen sein, eine Funktions- und/oder Korrektheitsgarantie gibt's um die Uhrzeit aber nicht

#include <iostream>
using namespace std;

void printArray(unsigned int* arr, unsigned int n)
{
	for (unsigned int i = 0; i < n; ++i)
		cout << arr[i] << " ";
	cout << endl;
}

void createArraysHelper(unsigned int* arr, unsigned int n, unsigned int a, unsigned int b, unsigned int pos)
{
	if (pos == n)
	{
		printArray(arr, n);
		return;
	}

	for (unsigned int i = a; i <= b; ++i)
	{
		arr[pos] = i;
		createArraysHelper(arr, n, a, b, pos + 1);
	}
}


void createArrays(unsigned int n, unsigned int a, unsigned int b)
{
	unsigned int* arr = new unsigned int[n];
	createArraysHelper(arr, n, a, b, 0);
	delete[] arr;
}

int main()
{
	createArrays(3, 1, 2);
}

 

[Zuckerbaum]

Schaut gut aus. "So ähnlich" hatte ich es auch versucht, aber auf die Idee mit "int pos" bin ich nicht gekommen

Wenn ich mich nicht mehr melde, hat es funktioniert

Dankeschön!