Ich habe zuvor eine Frage gestellt, wie man eine Wahrscheinlichkeit schnell und genau berechnet. Offensichtlich war es jedoch zu einfach, da eine Lösung in geschlossener Form gegeben wurde! Hier ist eine schwierigere Version.
Bei dieser Aufgabe geht es darum, Code zu schreiben, um eine Wahrscheinlichkeit genau und schnell zu berechnen . Die Ausgabe sollte eine genaue Wahrscheinlichkeit sein, die als Bruch in ihrer am meisten reduzierten Form geschrieben wird. Das heißt, es sollte nie ausgegeben werden 4/8
, sondern 1/2
.
n
Betrachten Sie für eine positive Ganzzahl eine gleichmäßig zufällige Zeichenfolge mit einer Länge von 1s und -1s n
und nennen Sie sie A. Verknüpfen Sie sie jetzt mit A
einer Kopie von sich selbst. Das ist, A[1] = A[n+1]
wenn von 1 indiziert wird, A[2] = A[n+2]
und so weiter. A
hat jetzt länge 2n
. Nun auch eine zweite zufällige Zeichenfolge der Länge betrachten , n
deren erste n
Werte -1, 0 oder 1 , mit einer Wahrscheinlichkeit von 1 / 4,1 / 2, 1/4 und jedes nennen es B.
Betrachten Sie nun das innere Produkt von B
mit A[1+j,...,n+j]
für anders j =0,1,2,...
.
Betrachten Sie zum Beispiel n=3
. Mögliche Werte für A
und B
könnten A = [-1,1,1,-1,...]
und sein B=[0,1,-1]
. In diesem Fall sind die ersten beiden inneren Produkte 0
und 2
.
Aufgabe
Für jeden j
, beginnend mit j=1
, Code sollte eine Ausgabe , die Wahrscheinlichkeit , dass alle die ersten j+1
inneren Produkte sind Null für jeden n=j,...,50
.
Wenn Sie die von Martin Büttner erstellte Tabelle kopieren j=1
, erhalten Sie die folgenden Beispielergebnisse.
n P(n)
1 1/2
2 3/8
3 7/32
4 89/512
5 269/2048
6 903/8192
7 3035/32768
8 169801/2097152
Ergebnis
Ihre Punktzahl ist die größte, die j
Ihr Code in 1 Minute auf meinem Computer erreicht. Zur Verdeutlichung j
erhält jeder eine Minute. Beachten Sie, dass der dynamische Programmiercode in der vorherigen verknüpften Frage dies problemlos erledigt j=1
.
Tie Breaker
Wenn zwei Einträge die gleiche j
Punktzahl erhalten, ist der Gewinner derjenige, der n
in einer Minute auf meinem Computer den höchsten Wert erreicht j
. Wenn die beiden besten Beiträge auch nach diesem Kriterium gleich sind, ist der Gewinner die zuerst eingereichte Antwort.
Sprachen und Bibliotheken
Sie können jede frei verfügbare Sprache und Bibliothek verwenden, die Sie mögen. Ich muss in der Lage sein, Ihren Code auszuführen. Bitte geben Sie eine vollständige Erklärung an, wie Sie Ihren Code unter Linux ausführen / kompilieren können, wenn dies überhaupt möglich ist.
Meine Maschine Die Timings werden auf meiner Maschine ausgeführt. Dies ist eine Standard-Ubuntu-Installation auf einem AMD FX-8350 Eight-Core-Prozessor. Dies bedeutet auch, dass ich Ihren Code ausführen kann.
Gewinnerbeiträge
j=2
in Python von Mitch Schwartz.j=2
in Python von feersum. Derzeit der schnellste Eintrag.
quelle
Antworten:
Python 2, j = 2
Ich habe versucht, eine Art 'geschlossene Form' für j = 2 zu finden. Vielleicht könnte ich ein MathJax-Bild davon machen, obwohl es bei all dem Index-Fummeln wirklich hässlich wäre. Ich habe diesen nicht optimierten Code nur geschrieben, um die Formel zu testen. Der Vorgang dauert ca. 1 Sekunde. Die Ergebnisse stimmen mit dem Code von Mitch Schwartz überein.
Stellen Sie sich eine Sequenz vor, in der das i-te Element ist,
e
wenn A [i] == A [i + 1] odern
wenn A [i]! = A [i + 1].i
im Programm ist die Anzahl vonn
s. Wenn geradei
ist, muss die Sequenz mit beginnen und mit endene
. Wenn diesi
ungerade ist, muss die Sequenz mit beginnen und endenn
. Sequenzen werden weiter durch die Anzahl von Läufen aufeinanderfolgendere
s odern
s klassifiziert . Es gibtj
+ 1 von einem undj
dem anderen.Wenn die Zufallsbewegung Idee bis 3 Dimensionen ausgedehnt wird, gibt es ein unglückliches Problem , dass es 4 mögliche Richtungen laufen in (eine für jede der
ee
,en
,ne
, odernn
) , die Mittel , die sie nicht linear abhängig sind. Derk
Index summiert sich also über die Anzahl der Schritte in eine der Richtungen (1, 1, 1). Dann gibt es eine genaue Anzahl von Schritten, die in den anderen 3 Richtungen ausgeführt werden müssen, um es abzubrechen.P (n, p) gibt die Anzahl der geordneten Partitionen von n Objekten in p Teile an. W (l, d) gibt die Anzahl der Wege an, auf denen ein zufälliger
l
Schritt eine Strecke von genau zurücklegen kannd
. Nach wie vor gibt es 1 Chance, sich nach links zu bewegen, 1 Chance, sich nach rechts zu bewegen und 2, um dort zu bleiben.quelle
j=3
. Das wäre fantastisch!Python, j = 2
Der dynamische Programmieransatz für
j = 1
in meiner Antwort auf die vorherige Frage erfordert nicht viele Modifikationen, um für höhere zu arbeitenj
, sondern wird schnell langsam. Tabelle als Referenz:Und der Code:
Hier halten wir den Überblick über die ersten beiden Elemente
A
, die letzten beiden ElementeB
(wobeib2
das letzte Element), und die inneren Produkte von(A[:n], B)
,(A[1:n], B[:-1])
, und(A[2:n], B[:-2])
.quelle