Hallo ich habe mir einen 8x8x8 Led Cube gebaut.Jetzt möchte ich mit
rand() eine Zufallszahl zwischen 0 und 511 ziehen und damit nach und
nach jede Led einschalten bis alle leuchten.Ich habe mir also ein 512
zeichen grosses array angelegt,lasse rand eine zahl berechnen,schaue im
array nach ob auf diesem arrayplatz eine 0 steht.Wenn ja,diesen Platz
mit einer 1 beschreiben und entsprechende Led einschalten.Klappt auch
alles,nur wird das einschalten einer neuen led immer langsamer,da er ja
immer öfters eine schon gezogene Zahl zieht.Die letzten Leds dauern
ewig.Grübel jetzt schon einige zeit darüber nach,wie man das ändern
könnte.MC ist ein mega644.
Hier die kurze for schleife.
for(uint16_t a = 0;a<512;a++) //array nullen
{
komplett [a] = 0;
}
uint16_t zufall;
for(uint16_t t = 0;t < 512;)
{
zufall = rand()%512;
if(komplett[zufall] == 0)
{
komplett[zufall] = 1;
t++;
ebene = zufall / 64; //ab hier nur berechnung welche led es ist
test = zufall - (ebene * 64);
reihe = test / 8;
ergebniss = reihe * 8;
test = test - ergebniss;
anzeige [ebene] [reihe] |= (1<<test);
zeig_bild(2);
}
else
{
zeig_bild(1);
continue;
}
}
Wäre super,wenn jemand helfen könnte.
gruss
andy
> Grübel jetzt schon einige zeit darüber nach,wie man das ändern> könnte.
Du legst dir ein Array der Größe 512 an.
In dieses Array schreibst du nacheinander die Zahlen 0 bis 511.
Dann lässt du dir mittels rand() Zufallszahlen erzeugen und (AChtung
jetzt kommts) fasst die Werte als Index in dieses Array auf. Diese Werte
vertauscht du dann ganz einfach.
Im Grund mischt du die Zahlen in deinem Array einfach durch in dem du
die Reihenfolge zufällig vertauscht, so wie beim Kartenspielen.
Ist das Array gemischt, dann gehst du es von vorne nach hinten durch und
die Zahl an der jeweiligen Stelle sagt dir, welche LED einzuschalten
ist.
Hallo,danke für die antwort.Das hört sich ja sehr gut an.
Ich verstehe nur das mit dem Index und dem vertauschen nicht so ganz.
Könntest du mir das etwas anschaulicher erklären?
gruss
andy
andy schrieb:> Könntest du mir das etwas anschaulicher erklären?
Sicher.
(Siehe Code)
Beitrag "Re: array mit rand() füllen"
ANgenommen, du hast nicht 512 sondern 8 (sonst zeichne ich mir einen
Wolf)
So gehts los
+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+---+
Die 2.te Schleife beginnt.
Die erste Zufallszahl sei 5.
Also wird Element 0 mit Element 5 vertauscht
+-------------------+
v v
+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+---+
+---+---+---+---+---+---+---+---+
| 5 | 1 | 2 | 3 | 4 | 0 | 6 | 7 |
+---+---+---+---+---+---+---+---+
nächster Schleifendurchgang: Die Zufallszahl sei 3
+-------+
v v
+---+---+---+---+---+---+---+---+
| 5 | 1 | 2 | 3 | 4 | 0 | 6 | 7 |
+---+---+---+---+---+---+---+---+
+---+---+---+---+---+---+---+---+
| 5 | 3 | 2 | 1 | 4 | 0 | 6 | 7 |
+---+---+---+---+---+---+---+---+
Nächster Durchgang: Tausche Element 2 mit ..... 7
+-------------------+
v v
+---+---+---+---+---+---+---+---+
| 5 | 3 | 2 | 1 | 4 | 0 | 6 | 7 |
+---+---+---+---+---+---+---+---+
+---+---+---+---+---+---+---+---+
| 5 | 3 | 7 | 1 | 4 | 0 | 6 | 2 |
+---+---+---+---+---+---+---+---+
Nächster Durchgang: Tausche Element 3 mit .... 2
+---+
v v
+---+---+---+---+---+---+---+---+
| 5 | 3 | 7 | 1 | 4 | 0 | 6 | 2 |
+---+---+---+---+---+---+---+---+
+---+---+---+---+---+---+---+---+
| 5 | 7 | 3 | 1 | 4 | 0 | 6 | 2 |
+---+---+---+---+---+---+---+---+
Nächster Durchgang: Tausche Element 4 mit ..... 6
+-------+
v v
+---+---+---+---+---+---+---+---+
| 5 | 7 | 3 | 1 | 4 | 0 | 6 | 2 |
+---+---+---+---+---+---+---+---+
+---+---+---+---+---+---+---+---+
| 5 | 7 | 3 | 1 | 6 | 0 | 4 | 2 |
+---+---+---+---+---+---+---+---+
.....
Durch die for-Schleife wird jedes Array Element mit irgendeinem anderen
getauscht (kann auch mit sich selbst 'getauscht' werden). Am Ende hast
du ein Array, in dem die Zahlen 0 bis 7 in irgendeiner zufälligen
Reihenfolge drinnenstehen. Das muss so sein, denn du hast ja nur Werte
getauscht und die Werte an sich ja nicht verändert; und am Anfang waren
die Werte von 0 bis 7 drinnen, also sind sie auch zum Schluss noch
drinnen. Nur eben vertauscht.
zb
+---+---+---+---+---+---+---+---+
| 0 | 7 | 3 | 4 | 2 | 5 | 1 | 6 |
+---+---+---+---+---+---+---+---+
Du schaltest also die LED in der Reihenfolge
LED 0
LED 7
LED 3
LED 4
LED 2
LED 5
LED 1
LED 6
ein. Die Reihenfolge ist zufällig und jede LED kommt irgendwann drann.
Anstelle, dass du während des Einschaltens abprüfst, ob du eine zufällig
gewählte LED schon eingeschaltet hast oder nicht, legst du die
Reihenfolge aller LEDs schon ganz am Anfang komplett fest. Das geht aber
schnell.
Vielen Dank.Seit zwei Tagen brüte ich darüber und du schüttelst das so
aus dem ärmel.Es läuft schon und sieht klasse aus.Jetzt werde ich deine
erklärung durchgehen bis ich sie richtig begriffen habe.
Nochmals vielen Dank.
gruss
andy
andy schrieb:> Vielen Dank.Seit zwei Tagen brüte ich darüber und du schüttelst das so> aus dem ärmel.
Tja.
Ich hab auch Algorithmenbücher studiert :-)
Ist eine Standardaufgabe.
(Das ist ja auch nicht auf meinem Mist gewachsen. Ich hab das auch von
anderen gelernt. Lang lang ists her.
Viele dieser Standardaufgaben wurden in den 60.er Jahren des letzten
Jahrhunderts entwickelt, als Informatik die große Blütezeit hatte und
man praktisch überall Neuland betrat. Die großen Namen der Informatik
sind zum Teil mit genau diesen kleinen Algorithmen untrennbar verknüpft)
> Es läuft schon und sieht klasse aus.Jetzt werde ich deine> erklärung durchgehen bis ich sie richtig begriffen habe.
Ich hoffe mal, die Zeichnungen machen es klarer
Hallo,jetzt ist alles klar.Ich hätte gerne Algorithmenbücher studiert
durfte es aber nicht (Vater meinte nur Handwerk taugt was,war in den 70
Jahren).Habe damals mit einem Schneider CPC und Schildkröt Basic
rumgemacht.
Danach Frau,Kind und Haus.Jetzt ist Haus fertig,Kind erwachsen und Frau
immer noch da.Also kann ich jetzt da weitermachen wo ich damals leider
nicht weitermachen durfte.
gruss
andy
Ist zwar schon alt und wenn du nichts gegen PASCAL hast, kann man da
viel lernen. Ich hab Wirth immer sehr gemocht, weil ich mit seiner
Erklärweise gut zurecht gekommen bin.
http://www.amazon.de/Algorithmen-Datenstrukturen-Niklaus-Wirth/dp/3519022508
Ein anderes Standardwerk ist zb der Sedgewick
http://www.amazon.de/Algorithmen-C-Robert-Sedgewick/dp/3893193766
Aber im Grunde sind meine Literaturkentnisse schon lang veraltet. Heute
gibt es sicher modernere und didaktisch besser aufbereitete
'Standardwerke'. Wenn du mal 30 oder 40 Euro übrig hast, kauf dir was.
Du und deine Programmierweise kann davon nur profitieren.
:-)
Irgendwann kauf ich mir auch noch den Knuth. Den dann allerdings als
Sammlerstück, das man einfach haben muss :-)
Karl Heinz Buchegger schrieb:> Nächster Durchgang: Tausche Element 3 mit .... 2
Das ist aber keine korrekte Implementierung (oder die Implementierung
eines nicht so guten Algorithmus) und führt nicht zu gleichen
Wahrscheinlichkeiten für alle Verteilungen.
Man iteriert über das Array und tauscht nur zwischen dem aktuellen Index
und dem Bereich aktueller Index bis letzter Index. Das ist der
Fisher-Yates Algorithmus.
Ob das jetzt beim LED Cube eine spürbare Verzerrung darstellt wenn man
den falschen Algorithmus verwendet, darüber lässt sich streiten. Gerade
bei solchen Mustern könnte ich mir aber vorstellen, dass man
Ungleichgewichte sieht.
Andreas B. schrieb:> Karl Heinz Buchegger schrieb:>> Nächster Durchgang: Tausche Element 3 mit .... 2>> Das ist aber keine korrekte Implementierung (oder die Implementierung> eines nicht so guten Algorithmus) und führt nicht zu gleichen> Wahrscheinlichkeiten für alle Verteilungen.>> Man iteriert über das Array und tauscht nur zwischen dem aktuellen Index> und dem Bereich aktueller Index bis letzter Index. Das ist der> Fisher-Yates Algorithmus.
AH, ja. Richtig da war noch was. Danke
> Ob das jetzt beim LED Cube eine spürbare Verzerrung darstellt wenn man> den falschen Algorithmus verwendet, darüber lässt sich streiten. Gerade> bei solchen Mustern könnte ich mir aber vorstellen, dass man> Ungleichgewichte sieht.
Na ja. wenn man es ganz genau nimmt, dann ist ja auch
rand() % 512
bzw. dann eben
i + rand() % ( 512 - i )
nicht der Weisheit letzter Schluss.
Spielhöllentauglich ist das alles nicht, aber für den Hausgebrauch gut
genug.
Wenn es darum geht, eine gegebene Menge durchzuschütteln, dann verwende
ich folgendes Verfahren. Hier ein Beispiel mit 4 Werten A, B, C und D.
Zunächst schreibt man die 4 zu permutierenden Objekte hin:
1
Liste : A, B, C, D
Dann zieht man eine Zufallszahl 1..4 (hier 3) und nimmt diese Element
aus der Liste und schreibt es in die Permutation:
1
Zufall = 3
2
Liste : A, B, C, D -> A, B, D
3
^
4
Permu : C
Dann eine Zufallszahl 1..3 (hier 3)
1
Zufall = 3
2
Liste : A, B, D -> A, B
3
^
4
Permu : C, D
Dann eine Zufallszahl 1..2 (hier 1)
1
Zufall = 1
2
Liste : A, B -> B
3
^
4
Permu : C, D, A
Schließlich gibt's nur noch eine Möglichkeit:
1
Zufall = 1
2
Liste : B -> {}
3
^
4
Permu : C, D, A, B
Nach Konstruktion sind die erzeugten Folgen gleichverteilt (unter der
Voraussetzung, daß die Zufallszahlen 1..n gleichverteilt sind).
Wenn man keine Listen mag, kann man auch Arrays nehmen und merken,
welche Elemente bereits gestrichen sind. In C ist das zum Beispiel viel
einfacher als Listen anzupacken.
Dieses Verfahren kann auch dazu verwendet werden, bei 10 Elementen die
10000-te Permutation zu bestimmen, ohne eine vorherigen Permutation
erzeugen zu müssen. Dazu bringt man man 10000 in ihre faktorielle
Darstellung und wendet das obige Verfahren an, siehe
http://de.wikipedia.org/wiki/Faktorielles_Stellenwertsystem
Auf der faktoriellen Darstellung kann man auch eine Arithmetik aufbauen,
die ebenso einfach ist wie die Arithmetik im 10er oder 2er System. Indem
man 1 aufaddiert, bekommt man die Ziffern (welche den Zufallszahlen von
oben entsprechen) für die Auswahl der Elemente der nächsten
Permutation etc.
Indem man das Verfahren (bzw. die faktorielle Darstellung) etwas
verallgemeinert, kann man auch leicht alle Teilmengen gleichverteilt
erzeugen bzw. enumerieren. D.h. ebenso wie bei den Permutationen kann
man z.B. die 1000-te Teilmenge (von 10-elementige Teilmenge einer
50-elementigen Menge etwa) erzeugen, ohne eine vorherigen Teilmengen
erzeugt haben zu müssen.
Ist die ursprüngliche Liste in lexikographischer Ordnung, so trifft dies
auch für die so erzeugten Teilmengen zu (wobei Permutationen nur den
Spezialfall einer n-elementigen Teilmenge einer n-elementigen Menge
bilden).
> Wenn man keine Listen mag, kann man auch Arrays nehmen und merken,> welche Elemente bereits gestrichen sind. In C ist das zum Beispiel> viel einfacher als Listen anzupacken.
Das ist völlig äquivalent zu der Tausch-Variante (wenn man sie richtig
macht, wie Andreas angemerkt hat). Nur das man in der Tausch Variante
keine Liste braucht. Die 'Buchführung' welche Elemente bereits
gestrichen wurden, steckt im Zusamennspiel aus for-Schleife und Tauschen
drinnen - die bereits gezogenen Elemente wandern durch das Tauschen an
den Anfang (oder an das Ende, wenn man von der anderen Seite anfängt)
des Arrays.
Vorteil: man arbeitet in-Place und auch die O-Komplexität ist geringer.
Das kann ich dir nicht beantworten, weil ich die Sache mit der
faktoriellen Darstellung noch nicht durchdacht habe. Mir gings nur
darum, dass man nicht notwendigerweise 2 Arrays braucht, sondern auch
alles in 1 abwickeln kann, was Vorteile bringt weil die Verwaltung
dadurch einfacher wird, bzw anstelle von O(n^2) man bei O(n) landet.
O(n^2) weil man ja das Ausgangsarray immer wieder zusammenschieben muss
um die Lücke durch die Entnahme zu schliessen. Vom statistischen Punkt
der Gleichverteilung aller Permutationen, sind die beiden Verfahren
gleichwertig.
http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
Karl Heinz Buchegger schrieb:> Das kann ich dir nicht beantworten, weil ich die Sache mit der> faktoriellen Darstellung noch nicht durchdacht habe. Mir gings nur> darum, dass man nicht notwendigerweise 2 Arrays braucht, sondern auch> alles in 1 abwickeln kann, was Vorteile bringt weil die Verwaltung> dadurch einfacher wird, bzw anstelle von O(n^2) man bei O(n) landet.
Das ist bei der faktoriellen Darstellung auch der Fall. Man muss das
Array nicht zusammenschieben sondern kann einfach ein Element als
entnommen markieren. Damit hat es Laufzeit O(n) unter der Annahme, daß
Arrayzugriff O(1) kostet.
Johann L. schrieb:> Karl Heinz Buchegger schrieb:>> Das kann ich dir nicht beantworten, weil ich die Sache mit der>> faktoriellen Darstellung noch nicht durchdacht habe. Mir gings nur>> darum, dass man nicht notwendigerweise 2 Arrays braucht, sondern auch>> alles in 1 abwickeln kann, was Vorteile bringt weil die Verwaltung>> dadurch einfacher wird, bzw anstelle von O(n^2) man bei O(n) landet.>> Das ist bei der faktoriellen Darstellung auch der Fall. Man muss das> Array nicht zusammenschieben sondern kann einfach ein Element als> entnommen markieren.
Und landet damit wieder beim Problem, dass der TO in erster Linie hatte:
Das man gegen Ende hin 'unendliche' viele Zufallszahlen generieren muss,
bis man dann endlich irgendwann eine findet, deren Element noch nicht
benutzt wurde.
Oder versteh ich dich jetzt falsch?
Karl Heinz Buchegger schrieb:> Johann L. schrieb:>> [faktorielle Darstellung]>> Und landet damit wieder beim Problem, dass der TO in erster Linie hatte:> Das man gegen Ende hin 'unendliche' viele Zufallszahlen generieren muss,> bis man dann endlich irgendwann eine findet, deren Element noch nicht> benutzt wurde.
Nö. Im ersten Schritt braucht man eine Zufallszahl 1..n, im 2. Schritt
eine 1..n-1, ... im n-1-ten Schritt eine 1..2 und schliesslich eine 1..1
(also 1).
Wie oben geschrieben, braucht man gleichverteilte Zufallszahlen 1..m;
ansonsten sind die erzeugten Teilmengen/Permutationen nicht
gleichverteilt. Diese Voraussetzung hat man bei FY aber doch auch?
Johann L. schrieb:> Nö. Im ersten Schritt braucht man eine Zufallszahl 1..n, im 2. Schritt> eine 1..n-1, ... im n-1-ten Schritt eine 1..2 und schliesslich eine 1..1> (also 1).
Jetzt verwirrst du mich.
Ich dachte du willst nicht das Array zusammenschieben?
Ah, du gehst das Array von vorne nach hinten durch und suchst die i-te
Zahl die noch nicht benutzt wurde.
Damit sind wir wieder bei O(n^2) (2 ineinander geschachtelte
for-Schleifen, deren Endwerte, wenn auch über Umwege, von n abhängen)
Karl Heinz Buchegger schrieb:> Johann L. schrieb:>>> Nö. Im ersten Schritt braucht man eine Zufallszahl 1..n, im 2. Schritt>> eine 1..n-1, ... im n-1-ten Schritt eine 1..2 und schliesslich eine 1..1>> (also 1).>> Jetzt verwirrst du mich.> Ich dachte du willst nicht das Array zusammenschieben?>> Ah, du gehst das Array von vorne nach hinten durch und suchst die i-te> Zahl die noch nicht benutzt wurde.> Damit sind wir wieder bei O(n^2) (2 ineinander geschachtelte
Ahhhh ja *Birne-aufdotz* jetzt seh' ich auch daß es O(n^2) ist.
Johann L. schrieb:>> Damit sind wir wieder bei O(n^2) (2 ineinander geschachtelte>> Ahhhh ja *Birne-aufdotz* jetzt seh' ich auch daß es O(n^2) ist.
Hätte ja auch sein können, dass du da noch einen Trick kennst, den ich
nicht kenne.
Karl Heinz Buchegger schrieb:> Johann L. schrieb:>>>> Damit sind wir wieder bei O(n^2) (2 ineinander geschachtelte>>>> Ahhhh ja *Birne-aufdotz* jetzt seh' ich auch daß es O(n^2) ist.>> Hätte ja auch sein können, dass du da noch einen Trick kennst, den ich> nicht kenne.
Man kann es natürlich so machen wie bei Fisher-Yates, bzw. es ist dann
im Endeffekt Fisher-Yates. Allerdings verliert man dann die nette
Sortierung der Ergebnisse, und ich sehe nicht, wie man das
zurückbekommt, ohne Array-Teile verschieben zu müssen bzw. Listen
einzusetzen oder zu durchmustern.
Thread beobachten
Seitenaufteilung abschalten