Aufgabe 11: Motivation: Auf dem Tisch liegen n äußerlich völlig gleiche Münzen, von denen n-1 gleiches Gewicht haben, während eine, die gefälschte Münze, leichter ist. Dem Computer soll ein Verfahren beigebracht werden, das ihn befähigt, im Dialog mit dem Benutzer, dem eine Balkenwaage mit zwei Waagschalen aber ohne Wägesatz zur Verfügung steht, die gefälschte Münze mit möglichst wenig Fragen zu finden.
Lösungsidee: Wir nutzen das Halbierungsverfahren. Wenn die Anzahl n der Münzen auf dem Tisch gerade ist, lassen wir den Nutzer jeweils die Hälfte der Münzen auf jede der beiden Waagschale legen: in der sich hebenden Schale befindet sich die gefälschte Münze. Ist die Münzenzahl ungerade, so reduzieren wir sie um eins und gehen wie eben beschrieben vor. Ergibt sich ein Gleichgewicht, war die beiseite gelegte Münze die gesuchte.
Aufgabe: Schreiben Sie ein Java-Programm zur Lösung des Problems. Die Münzen – 1000 Stück - werden dabei durch Zahlen von 1 – 1000 ersetzt. Denken Sie sich vor Programmstart eine Zahl zwischen 1 und 1000 aus (die gefälschte Münze!) und
lassen Sie den Computer die Zahl suchen. Der Computer soll dabei gemäß des Halbierungsverfahrens vorgehen. Er kann Ihnen dazu Ja-Nein-Fragen der Art „Ist der Münzhaufen rechts schwerer?“ oder „Sind die beiden Münzhaufen gleichschwer?“ stellen.
Folgenden Ansatz habe ich dazu:
/* ----------Hauptmethode---------- */
public static void main(String[] args) {
int linksMin = 1; /* Die niedrigste Münze auf der linken Seite */
int linksMax = 500; /* Die höchste Münze auf der linken Seite */
int rechtsMin = 501; /* Die niedrigste Münze auf der rechten Seite */
int rechtsMax = 1000; /* Die höchste Münze auf der rechten Seite */
int antw = 0; /* Variable für die Antworten: 0 = Ja, 1 = Nein */
int x = 0; /* Beiseite gelegte Münze */
boolean gefunden = false; /* Wurde die falsche Münze gefunden? */
System.out.println("0 = Ja, 1 = Nein");
while (gefunden == false) {
System.out.println("Links liegen die Münzen von "+linksMin+" bis "+linksMax+". Rechts liegen die Münzen von "+rechtsMin+" bis "+rechtsMax+".");
antw = IO.readInt("Ist der Münzhaufen rechts schwerer?: ");
if (antw == 0) {
linksMax = linksMax / 2;
rechtsMin = rechtsMin - linksMax;
rechtsMax = rechtsMax / 2;
}
if (antw == 1) {
linksMax = rechtsMax - linksMax;
linksMin = rechtsMin;
rechtsMax = linksMax + 1;
}
if (linksMax % 2 != 0) {
x = rechtsMax;
rechtsMax = rechtsMax - 1;
antw = IO.readInt("Sind die beiden Münzhaufen gleich schwer?: ");
if (antw == 0) {
System.out.println(x);
gefunden = true;
}
}
}
}
}```
Irgendwie funktioniert der ganze Spaß aber nicht wirklich.
Seht ihr vielleicht direkt irgendwelche Fehler oder habt andere Lösungsansätze?
Ganzganz großes Danke schonmal vorweg :)
Ich glaube du hast die Aufgabenstellung allgemein etwas verfehlt.
Denken Sie sich vor Programmstart eine Zahl zwischen 1 und 1000 aus (die gefälschte Münze!) und
lassen Sie den Computer die Zahl suchen.
Du hingegen frägst den Benutzer welche Seite schwerer ist. Das ist aber nicht die Aufgabe. Du sollst als Benutzer nur eine Münze auswählen und dann schauen wie der Computer sie findet.
Edit: Lese den letzten Satz jetzt erst, aber zumindest fehlt ja anfangs die Eingabe für die „richtige“ Münze und irgendwie macht es keinen Sinn wenn man einerseits sagt „Lass den Computer machen“ und dann „Der Computer darf Fragen stellen“… aber gut, das ist Sache des Aufgabenstellers.
[QUOTE=black_droid;29687]Okay, ich bin grad irgendwie blind ._.[/QUOTE]Was ist der Unterschied zwischen:a = b und a == b ?
Und noch nen Tipp: Verwenden keine negativ formulierten Variablen. Entweder du nennt die Variable „gefunden“ und negierst alle Abfragen, oder du nennst sie „suche“. Aber „nichtGefunden“ macht dir irgendwann nen Knoten ins Hirn, den ich persönlich gerne zu vermeiden suche.
Äehm… „while(bool = true) {“ → Semantic Error No.1.
Das sollte in Java normalerweise mit ner Warnung angemäkelt werden. Eigentlich verwendet man bei derartigen Bedingungen nur den boolschen Wert, ohne ihn mit irgendwas zu vergleichen.
Unabhängig von der letzten (wichtigeren) Antwort, das Detail: Bei
while (nichtGefunden = true)
ist das nichtGefunden= true eine Zuweisung. Es müßte wenn dann
while (nichtGefunden == true)
heißen, oder kurz
while (nichtGefunden)
(…oder … semantisch näher liegend
while (gefunden == false)
bzw
while (!gefunden)
aber … das nur nebenbei )
EDIT: Das mit der „letzten Antwort“ bezog sich auf das von Gonzo. Hatte den PrettyFace-Effekt DOCH noch unterschätzt… :rolleyes:
zwei Werte mit == vergleichen. = ist eine Zuweisung.
Tipp: nimm statt boolean nichtGefunden doch etwas wie boolean gefunden.
Muss man nicht ständig umdenken. Beispiel: Ist das Licht an oder aus? Und nicht: Ist das Lich nicht an oder nicht nicht an?
Edit: Jetzt hab ich so lange zum Tippen gebraucht das ich der letze bin :(. Dafür dürfte nun aber die Antwort recht eindeutig sein:o)
public class Aufgabe_11 {
/* ----------Hauptmethode---------- */
public static void main(String[] args) {
int linksMin = 1; /* Die niedrigste Münze auf der linken Seite */
int linksMax = 500; /* Die höchste Münze auf der linken Seite */
int rechtsMin = 501; /* Die niedrigste Münze auf der rechten Seite */
int rechtsMax = 1000; /* Die höchste Münze auf der rechten Seite */
int antw = 0; /* Variable für die Antworten: 0 = Ja, 1 = Nein */
int x = 0; /* Beiseite gelegte Münze */
boolean gefunden = false; /* Wurde die falsche Münze gefunden? */
System.out.println("1 = Ja, 0 = Nein");
while (gefunden == false) {
System.out.println("Links liegen die Münzen von "+linksMin+" bis "+linksMax+". Rechts liegen die Münzen von "+rechtsMin+" bis "+rechtsMax+".");
if (linksMax % 2 != 0) {
x = rechtsMax;
rechtsMax = rechtsMax - 1;
antw = IO.readInt("Sind die beiden Münzhaufen gleich schwer?: ");
if (antw == 1) {
System.out.println(x);
gefunden = true;
}
}
antw = IO.readInt("Ist der Münzhaufen rechts schwerer?: ");
if (antw == 1) {
linksMax = linksMax / 2;
rechtsMin = rechtsMin - linksMax;
rechtsMax = rechtsMax / 2;
}
if (antw == 0) {
linksMin = rechtsMin;
linksMax = ((rechtsMax - rechtsMin) / 2) + linksMin;
rechtsMin = linksMax + 1;
}
}
}
}```
Mein größtes Problem ist der Fall, wenn die Münzanzahl ungerade ist.
[QUOTE=black_droid;29681]Seht ihr vielleicht direkt irgendwelche Fehler oder habt andere Lösungsansätze[/QUOTE]Besser ist, die Menge dritteln:
[ul]
[li]Drei Haufen bilden, von denen 2 die gleiche Mengen beinhalten.
[/li][li]Die beiden Haufen mit gleicher Anzahl auf die Waage legen[LIST]
[/li][li]sind sie gleich schwer ist die gesuchte Münze im Rest
[/li][li]schlägt die Waage aus ist die gesuchte Münze im leichteren haufen
[/li][/ul]wie auch immer: nach der Wäägung muss ich mich nur noch um ein drittel der Münzen kümmern, nicht um die Hälfte…[/LIST]
bye
TT
Hatte mal so eine Frage bei einem Telefoninterview.
9 Kugeln, eine davon ist schwerer als der Rest.
Eine Balkenwaage ohne Einheiten.
F: Wie oft muss man wiegen bis man die schwerste Kugel gefunden hat?
Man wiegt erst 4 gegen 4 Kugeln ab.
Wenn diese gleichviel wiegen, ist die nicht-gewogene Kugel die schwerste.
Ansonsten weiss man zumindest auf welcher Seite der Schale die schwerste Kugel wiegt.
Ungerade Anzahl von Kugeln heisst nur, dass beim ersten wiegen eben eine Kugel nicht gewogen wird.
