wir (Schule) beginnen derzeit mit Java. Ich bin kein besonders guter Programmierer und das werde ich auch nie,
aber ich bemühe mich doch so einigermaßen gut dem Unterricht zu folgen.
Wir sollten ein Lottoprogramm (genauer eine Klasse), die zb. 6 Zahlen zwischen 1 und 49 zurückgibt. Soweit so
einfach, wären da nicht diese blöden Duplikate. Wenn man von dem Problem der Duplikate absieht, erstellt man
einfach eine Methode in der mit Random rand = new Random() und int zufallszahl = rand.nextInt(_maxZahl+1);
die Zahlen in der Schleife erstellt werden.
Ich habe einiges rumprobiert aber bin so auf keine Lösung mit den Duplikaten gekommen.
Dann ein anderer Einfall:
import java.util.ArrayList;
import java.util.Collections;
public class Lotto
{
//Instanzvariablen
private int _anzahl;
private int _minZahl;
private int _maxZahl;
private ArrayList<Integer> box;
private ArrayList<Integer> ziehung;
//Konstruktor(en)
public Lotto(){}
public Lotto(int anzahl, int minzahl, int maxzahl)
{
this._anzahl = anzahl;
this._minZahl = minzahl;
this._maxZahl = maxzahl;
}
//Getter und Setter
public int get_anzahl()
{
return _anzahl;
}
public void set_anzahl(int _anzahl)
{
this._anzahl = _anzahl;
}
public int get_minZahl()
{
return _minZahl;
}
public void set_minZahl(int _minZahl)
{
this._minZahl = _minZahl;
}
public int get_maxZahl()
{
return _maxZahl;
}
public void set_maxZahl(int _maxZahl)
{
this._maxZahl = _maxZahl;
}
//Methoden
public void befuelleBox()
{
box = new ArrayList<Integer>();
//befülle die Box
for (int i = this._minZahl; i < this._maxZahl + 1; i++)
{
box.add(i);
}
//Schüttel die Box mal ordentlich durch
Collections.shuffle(box);
}
public void zahlenZiehen()
{
ziehung = new ArrayList<Integer>();
//einfach eine nach der anderen ziehen
for (int i = 0; i < this._anzahl; i++)
{
ziehung.add(box.get(i));
}
}
public void printGezogeneZahlen()
{
//gezogene Zahlen vorlesen
for(Object teil : ziehung)
{
System.out.println("Zahl: " + teil);
}
}
In der Main-Methode des Programms werden die 3 Methoden nacheinander ausgeführt.
Ich habe versucht mir den Code möglichst praxisnah zu schreiben. Erst wird die Lottobox (ArrayList)
mit den Zahlen befüllt, dannach durcheinandergebracht. Dann werden die ersten 6 Zahlen (in diesen Fall)
aus der Box (ArrayList) gezogen und in die Ziehung (ArrayList) gefüllt. Dannach wird die Ziehung (ArrayList)
ausgegeben. Das war die für mich einfachste Lösung. Warscheinlich gibt es viele bessere Lösungen. Welche
Probleme können bei meiner Lösung auftreten? Es gibt hier jedenfalls keine Duplikate mehr und es ist leicht
verständlich, was man von vielen Lösungen, die im Internet rumschwirren leider nicht so behaupten kann.
Wenn man „die Lösung“ schreibt, die alle formalen Kritierien bezüglich Laufzeit und Speicherbedarf erfüllt, dann… ist die zwar auch nicht kompliziert (tatsächlich nur wenige Zeilen), aber warum diese Lösung dann „richtig“ ist, finde ich SEHR schwer durch reines Lesen zu erfassen.
Das wären auch die Nachteile bzw. Kritikpunkte an der aktuellen Lösung: Wenn du 5 Zahlen aus dem Bereich von 0 bis 100000000 Ziehen müßtest, dann müßten ALLE diese Zahlen gespeichert und auch ALLE geschufflet werden.
In diesem Fall ist das wohl nicht schlimm, … hängt aber vielleicht auch vom Lehrer und seinen Zielen ab, und ob es um die 5. oder die 13. Klasse geht
wieso nicht einfach jede gezogen zahl in einer arraylist speichern und dann bei einer neuen ziehung einfach do{ziehe zahl}while(gezogenezahlen.contains(neuezahl)} oder so?
[QUOTE=mymaksimus]wieso nicht einfach jede gezogen zahl in einer arraylist speichern und dann bei einer neuen ziehung einfach do{ziehe zahl}while(gezogenezahlen.contains(neuezahl)} oder so?[/QUOTE]…weil seine Methode bereits effektiver wäre, wenn…
if(this.ziehung == null) {
this.ziehung = new ArrayList<Integer>(6);
}
this.ziehung.clear();
ArrayList<Integer> tmpBox = new ArrayList<Integer>(this.box);
int m;
for(int n = 0; n < 6; n++) {
m = (int) (Math.random() * tmpBox.size());
this.ziehung.add(tmpBox.remove(m));
}
}```Obwohl... ein vorhergehendes "shuffle()" auf die Box und ein der Reihe nach ziehen müsste auch klappen. Hatte ich grad' übersehen... Also klar... das kann man so abliefern. Ein Ergebnis ist immer besser als keines. In meiner Ausbildung zum Mechatroniker gab es immer son Spruch: "Hauptsache Funktion!" ;)
Ja, @mymaksimus , das wäre die Alternative. Genaugenommen würde man da ein Set verwenden, weil darauf die contains-Methode nicht O(k) hat, sondern nur O(1). Das Problem bei dieser Methode ist aber, dass sie nicht total korrekt ist (sondern nur partiell korrekt). WENN das Programm terminiert, DANN liefert es die richtige Lösung. Man kann aber nicht beweisen, DASS es terminiert: Wenn man 6 aus 49 ziehen will, und als erstes wird die 1 gezogen, dann kann man nicht beweisen, dass der Zufallszahlengenerator irgendwann mal eine Zahl != 1 liefern wird. (Natürlich wird er das tun, aber man kann es nicht beweisen - scheiß Formalisten, ja ;))
Ich bin mal so frei, hier eine Lösung zu posten, die @Landei mal an anderer Stelle gepostet hatte:
public static Iterator<Integer> randomPickIterator(final int max){
return new Iterator<Integer>() {
private final Random random = new Random();
private final Set<Integer> set = new TreeSet<Integer>();
public boolean hasNext() { return set.size() < max; }
public Integer next() {
int r = random.nextInt(max - set.size());
for(Integer k : set) { if(r >= k) r++; }
set.add(r);
return r;
}
public void remove() { throw new UnsupportedOperationException(); }
};
}
Wenn man k aus n ziehen will (also n=max und k=Anzahl der ‘next’-Aufrufe) braucht das O(k) Speicher und hat eine Laufzeit von O(k) (?) oder so… (auf jeden Fall nicht O(n)).
Woher willst du das wissen? Es kann an so vielen Dingen liegen, dass dir Programmieren schwer fällt: Schlechte Lehrer, veraltetes Material, die falsche Sprache (oder besser gesagt, das falsche Paradigma). Vielleicht unterschätzt du dich auch (Dunning-Kruger Effekt). Oft braucht man mehrere Anläufe, um etwas zu verstehen. Zur Sprache Scala habe ich z.B. erst im zweiten Anlauf eine Zugang gefunden. Erst danach hat es auch mit Haskell geklappt, das ich vorher viele Male lernen wollte. Beim Studium hatten wir Prolog, und es hat lange Zeit für mich keinen Sinn ergeben - bis es eines Tages „klick“ gemacht hat (buchstäblich in einem einzigen Augenblick, wie eine Figur in einem Suchbild, auf dass man vorher ewig gestarrt hat).
Ich denke, du solltest die Flinte nicht zu schnell in Korn werfen. Wenn du Spaß daran hast, wenn du etwas selbst zum Laufen gebracht hast, ist das schon die erste Voraussetzung dafür, ein guter Programmierer zu werden (meiner Meinung nach ist Abstraktionsvermögen die zweite).
aber ich bemühe mich doch so einigermaßen gut dem Unterricht zu folgen.
[QUOTE=Marco13]Ja, @mymaksimus , das wäre die Alternative. Genaugenommen würde man da ein Set verwenden, weil darauf die contains-Methode nicht O(k) hat, sondern nur O(1). Das Problem bei dieser Methode ist aber, dass sie nicht total korrekt ist (sondern nur partiell korrekt). WENN das Programm terminiert, DANN liefert es die richtige Lösung. Man kann aber nicht beweisen, DASS es terminiert: Wenn man 6 aus 49 ziehen will, und als erstes wird die 1 gezogen, dann kann man nicht beweisen, dass der Zufallszahlengenerator irgendwann mal eine Zahl != 1 liefern wird. (Natürlich wird er das tun, aber man kann es nicht beweisen - scheiß Formalisten, ja ;))
[...][/QUOTE]
Sry, aber das habe ich jetzt nicht verstanden.
du meinst wenn du einem den code zeigst kannst du es nicht direkt beweisen oder wie?
aber es ist doch klar das solange eine neue zahl gezogen wird bis sie noch nicht neu ist?
Wie sähe die Invariante der Zeilen 9 bis 10 aus? Keine Duplikate, das sieht man, aber wirklich zufällige Zahlen? Die Laufzeit wäre 1+2+…+k, das entspräche k(k+1)/2=Theta(k²).
Meine Idee:
ArrayList<Integer> il1 = new ArrayList<Integer>(49);
ArrayList<Integer> il2 = new ArrayList<Integer>(49);
for (int i = 1; i <= 49; i++)
il1.add(i);
Random random = new Random();
for (int i = il1.size(); i > 0; i--) {
il2.add(il1.remove(random.nextInt(i)));
for (int i = 0; i < 6; i++) {
sout(il2.get(i))
}
Speicherplatzverhalten 2n=Theta(n), Laufzeit n. Bei ‘6 aus 49’ wäre 21 < 49. Aber Vergleich Äpfel und Birnen. Ansonsten java.util.Collections#shuffle(java.util.List).
