guided Probieren à la Mastermind

2 Lösungen

#121

Fortgeschrittener - Java von Veigar - 13.01.2016 um 17:42 Uhr

Liebe Leute,

Schreibt ein Programm das für eine 8-stellige Binärzahl durch ausprobieren herausbekommt.

Schreibt dafür zunächst eine Funktion die für eine Zahl die Anzahl der "korrekten Bits" (Also Bits die mit der zu findenden Zahl übereinstimmen) zurück gibt. (zum Beispiel bei zu findender Zahl:11111111; deinefunktion(00110011)=4) und entwickel dann ein Probier-System das zunächst eine "Anfangszahl" verwendet und dann den nächsten Versuch auf die Übereinstimmung der Zahl mit der zu findenden Zahl anpasst.

ps: Bitte keine Codes die simpel 256 (2**8) mögliche Integer überprüfen!
pss: Diese Aufgabe ist eine Variation des Spiels "Mastermind"!

Viel Erfolg!

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von DaBaschdi (120 Punkte) - 25.10.2016 um 14:26 Uhr

Hier zwei Funktionen/Lösungsansätze.
Die Strings mit den Binärzahlen totalNumber und guessedNumber lasse ich in einer seperaten Klasse zufällig generieren.
totalNumber ist die zu erratende Zahl, guessedNumber ist ein erster Lösungsversuch.
Ich bitte die etwas umständliche Umwandlung der einzelnen Ziffern in Strings/Chars etc. zu entschuldigen, das geht bestimmt auch schöner.

Das Programm gleicht zunächst die Ziffern ab und speichert die Anzahl der richtigen Nummern. Danach wird Ziffer für Ziffer geprüft, ob sich bei einer Änderungen (von 0 auf 1 oder von 1 auf 0) die Anzahl der richtigen Nummern erhöht, falls nicht wird die Ziffer wieder zurückgesetzt.

Die Klasse beherbergt weiter oben zwei Variablen

Java-Code

static int tries = 0;

(Versuche/Vergleiche) und

Java-Code

static int positionOfTrying = 0;

(aktueller Index der Ziffer, die überprüft wird).

Hier also einmal die rekursive Lösung:

Java-Code

private static int SolvingRecursive(String totalNumber, String guessedNumber) {

		int number;
		int rightNumbers;
		int switchedNumber;
		char numberInChar;
		String newGuessedNumber;
		StringBuilder guessedNumberSB = new StringBuilder(guessedNumber);

		rightNumbers = HowManyRightNumbers(totalNumber, guessedNumber);

		if (rightNumbers < totalNumber.length()) {
			number = guessedNumber.charAt(positionOfTrying) - 48;
			switchedNumber = SwitchNumbers(number);
			numberInChar = Character.forDigit(switchedNumber, 10);
			guessedNumberSB.setCharAt(positionOfTrying, numberInChar);
			newGuessedNumber = guessedNumberSB.toString();
			tries++;
			positionOfTrying++;

			if (rightNumbers < HowManyRightNumbers(totalNumber, newGuessedNumber)) {
				SolvingRecursive(totalNumber, guessedNumberSB.toString());
			} else {
				SolvingRecursive(totalNumber, guessedNumber);
			}

		} else {
			return tries;
		}
		return tries;
	}

Und einmal die iterative:

Java-Code

private static int SolvingIterative(String totalNumber, String guessedNumber) {

		int number;
		int rightNumbers;
		int switchedNumber;
		char numberInChar;
		String newGuessedNumber;

		rightNumbers = HowManyRightNumbers(totalNumber, guessedNumber);

		while (rightNumbers < totalNumber.length()) {
			StringBuilder guessedNumberSB = new StringBuilder(guessedNumber);
			number = guessedNumber.charAt(positionOfTrying) - 48;
			switchedNumber = SwitchNumbers(number);
			numberInChar = Character.forDigit(switchedNumber, 10);
			guessedNumberSB.setCharAt(positionOfTrying, numberInChar);
			newGuessedNumber = guessedNumberSB.toString();
			tries++;
			positionOfTrying++;
			if (rightNumbers < HowManyRightNumbers(totalNumber, newGuessedNumber)) {
				rightNumbers = HowManyRightNumbers(totalNumber, newGuessedNumber);
				guessedNumber = newGuessedNumber;
			}
		}
		return tries;
	}

Folgende Funktionen werden hierbei verwendet:

Java-Code

private static int HowManyRightNumbers(String totalNumber, String guessedNumber) {
		int amountOfRightGuessedNumbers = 0;

		for (int i = 0; i < totalNumber.length(); i++) {
			if (totalNumber.charAt(i) == guessedNumber.charAt(i)) {
				amountOfRightGuessedNumbers++;
			}
		}
		return amountOfRightGuessedNumbers;
	}

private static boolean AreTheStringsOfEqualLength(String totalNumber, String guessedNumber) {
		if (totalNumber.length() == guessedNumber.length()) {
			return true;
		}
		return false;
	}

private static int SwitchNumbers(int number) {
		if (number == 0) {
			number = 1;
		} else {
			number = 0;
		}
		return number;
	}

Bei 1Mio. Durchläufen kann man feststellen, dass die iterative Lösung im Durchschnitt 0,1ms schneller ist. Die Einzelwerte schwanken allerdings stark.