Die folgende Druckanweisung würde "Hallo Welt" drucken. Könnte jemand das erklären?
System.out.println(randomString(-229985452) + " " + randomString(-147909649));
Und randomString()
sieht so aus:
public static String randomString(int i)
{
Random ran = new Random(i);
StringBuilder sb = new StringBuilder();
while (true)
{
int k = ran.nextInt(27);
if (k == 0)
break;
sb.append((char)('`' + k));
}
return sb.toString();
}
n
infor (int n = 0; ; n++)
. Sie könntenfor(;;)
oderwhile(true)
stattdessen verwenden!Antworten:
Wenn eine Instanz von
java.util.Random
mit einem bestimmten Startparameter (in diesem Fall-229985452
oder-147909649
) erstellt wird, folgt sie dem Zufallszahlengenerierungsalgorithmus, der mit diesem Startwert beginnt .Jeder,
Random
der mit demselben Samen konstruiert wurde, erzeugt jedes Mal das gleiche Zahlenmuster.quelle
"hello\0"
und"world\0"
. Wenn Sie von einem wirklich zufälligen Generator ausgehen würden, wäre die Wahrscheinlichkeit 1 zu 27 ^ 6 (387.420.489), die gesuchte Sequenz zu erhalten - also ziemlich beeindruckend, aber nicht ganz umwerfend!"Hello"
"World"
) versuchen oder122-k
anstelle von96+k
oder ...Die anderen Antworten erklären warum, aber hier ist wie.
Gegeben eine Instanz von
Random
:Die ersten 6 Zahlen, die
r.nextInt(27)
generiert werden , sind:und die ersten 6 Zahlen,
r.nextInt(27)
die gegeben werden,Random r = new Random(-147909649)
sind:Fügen Sie dann einfach diese Zahlen zur ganzzahligen Darstellung des Zeichens hinzu
`
(96):quelle
new Random(-229985452).nextInt(27)
immer 8 zurück.new Random()
überhaupt keine Nummer zurück.Random
nicht kryptografisch sicher ist (ich bin mir ziemlich sicher, dass es sich um einen Mersenne Twister handelt, zitiere mich aber nicht dazu), ist es wahrscheinlich möglich, von "Ich möchte diese Zahlen" bis "Dies ist die" rückwärts zu arbeiten Samen würde ich verwenden ". Ich habe etwas Ähnliches mit dem Standard-C-Linearkongruenzgenerator gemacht.Ich lasse es einfach hier. Wer viel (CPU-) Zeit übrig hat, kann gerne experimentieren :) Wenn Sie einige Fork-Join-Fu beherrschen, damit dieses Ding alle CPU-Kerne verbrennt (nur Threads sind langweilig, oder?), Teilen Sie dies bitte mit dein Code. Ich würde es sehr begrüßen.
Ausgabe:
quelle
nextInt(27)
bedeutet innerhalb des Bereichs[0, 26]
.Alle hier haben großartige Arbeit geleistet, um zu erklären, wie der Code funktioniert, und um zu zeigen, wie Sie Ihre eigenen Beispiele erstellen können. Hier ist jedoch eine informationstheoretische Antwort, die zeigt, warum wir vernünftigerweise erwarten können, dass es eine Lösung gibt, die die Brute-Force-Suche irgendwann finden wird.
Die 26 verschiedenen Kleinbuchstaben bilden unser Alphabet
Σ
. Um Wörter unterschiedlicher Länge zu generieren, fügen wir ein Terminatorsymbol hinzu⊥
, um ein erweitertes Alphabet zu erhaltenΣ' := Σ ∪ {⊥}
.Sei
α
ein Symbol und X eine gleichmäßig verteilte Zufallsvariable überΣ'
. Die Wahrscheinlichkeit, dieses Symbol zu erhalten,P(X = α)
und sein InformationsgehaltI(α)
sind gegeben durch:Für ein Wort
ω ∈ Σ*
und sein⊥-
terminiertes Gegenstückω' := ω · ⊥ ∈ (Σ')*
haben wirDa der Pseudozufallszahlengenerator (PRNG) mit einem 32-Bit-Startwert initialisiert wird, können wir die meisten Wörter mit einer Länge von bis zu erwarten
von mindestens einem Samen erzeugt werden. Selbst wenn wir nach einem 6-stelligen Wort suchen würden, wären wir in 41,06% der Fälle immer noch erfolgreich. Nicht zu schäbig.
Bei 7 Buchstaben sehen wir näher an 1,52%, aber ich hatte das nicht bemerkt, bevor ich es ausprobiert habe:
Siehe die Ausgabe: http://ideone.com/JRGb3l
quelle
I(⍵)
neu geordnete Gleichung.I(⍵)
ist 32 (Bits) und|⍵|
stellt sich als 5 (Symbole) heraus.Ich habe ein schnelles Programm geschrieben, um diese Samen zu finden:
Ich habe es jetzt im Hintergrund laufen lassen, aber es hat bereits genug Wörter für ein klassisches Pangram gefunden:
( Demo auf ideone. )
Ps.
-727295876, -128911, -1611659, -235516779
.quelle
Ich war fasziniert davon, ich habe diesen Zufallswortgenerator auf einer Wörterbuchwortliste ausgeführt. Bereich: Integer.MIN_VALUE bis Integer.MAX_VALUE
Ich habe 15131 Treffer.
Druckt
quelle
Die meisten Zufallszahlengeneratoren sind tatsächlich "pseudozufällig". Sie sind lineare kongruente Generatoren oder LCGs ( http://en.wikipedia.org/wiki/Linear_congruential_generator )
LCGs sind bei einem festen Startwert ziemlich vorhersehbar. Verwenden Sie grundsätzlich einen Startwert, der Ihnen Ihren ersten Buchstaben gibt, und schreiben Sie dann eine App, die weiterhin das nächste int (char) generiert, bis Sie den nächsten Buchstaben in Ihrer Zielzeichenfolge treffen, und notieren Sie, wie oft Sie die LCG aufrufen mussten. Fahren Sie fort, bis Sie jeden einzelnen Buchstaben generiert haben.
quelle
/dev/urandom
Gerät verwenden, um zufällige Daten zu lesen. Dies ist jedoch eine knappe Ressource. Daher werden solche zufälligen Daten normalerweise verwendet, um PRNGs zu setzen.urandom
ist immer noch pseudozufällig en.wikipedia.org/wiki//dev/random/dev/random
. In dem oben zitierten Artikel heißt es, dass der Linux-Kernel Entropie aus Tastatur-Timings, Mausbewegungen und IDE-Timings generiert und die zufälligen Zeichendaten über die speziellen Dateien / dev / random und / dev / urandom anderen Betriebssystemprozessen zur Verfügung stellt. Das lässt mich glauben, dass es wirklich zufällig ist. Vielleicht ist das nicht ganz richtig. Enthält aber/dev/random
zumindest etwas Entropie.Da Multithreading mit Java sehr einfach ist, finden Sie hier eine Variante, die mit allen verfügbaren Kernen nach einem Startwert sucht: http://ideone.com/ROhmTA
quelle
L
und den Argumenttyp in ändernlong
, dhrandomString(long i)
um herumzuspielen. :)Random gibt immer die gleiche Sequenz zurück. Es wird zum Mischen von Arrays und anderen Operationen als Permutationen verwendet.
Um verschiedene Sequenzen zu erhalten, muss die Sequenz an einer Position initialisiert werden, die als "Startwert" bezeichnet wird.
Das randomSting erhält die Zufallszahl an der i-Position (seed = -229985452) der "zufälligen" Sequenz. Verwendet dann den ASCII- Code für die nächsten 27 Zeichen in der Sequenz nach der Startposition, bis dieser Wert gleich 0 ist. Dies gibt das "Hallo" zurück. Die gleiche Operation wird für "Welt" durchgeführt.
Ich denke, dass der Code für keine anderen Wörter funktioniert hat. Der Typ, der programmiert hat und die zufällige Reihenfolge sehr gut kennt.
Es ist sehr toller Geek-Code!
quelle
Das Prinzip ist, dass die Zufallsklasse, die mit demselben Startwert erstellt wurde, jedes Mal dasselbe Zahlenmuster generiert.
quelle
Aus der Antwort von Denis Tulskiy abgeleitet , erzeugt diese Methode den Samen.
quelle
In den Java-Dokumenten ist dies eine beabsichtigte Funktion, wenn ein Startwert für die Random-Klasse angegeben wird.
http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Random.html
Seltsamerweise würden Sie denken, dass es implizite Sicherheitsprobleme gibt, wenn vorhersehbare Zufallszahlen vorliegen.
quelle
Random
"den Startwert des Zufallszahlengenerators auf einen Wert, der sich sehr wahrscheinlich von jedem anderen Aufruf dieses Konstruktors unterscheidet" ( javadoc ). In der aktuellen Implementierung ist dies eine Kombination aus der aktuellen Zeit und einem Zähler.Es geht um "Samen". Gleiche Samen ergeben das gleiche Ergebnis.
quelle
Hier ist eine kleine Verbesserung für Denis Tulskiy Antwort . Es halbiert die Zeit
quelle
Ausgabe
quelle