Bei dieser Aufgabe geht es darum, Code zu schreiben, um eine Wahrscheinlichkeit genau 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. Verketten Sie nun mit A
ihrem ersten Wert. Das heißt, A[1] = A[n+1]
wenn die Indizierung von 1. A
jetzt Länge hat n+1
. 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 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 beiden inneren Produkte 0
und 2
.
Betrachten Sie nun das innere Produkt von A[1,...,n]
und B
und das innere Produkt von A[2,...,n+1]
und B
.
Ihr Code muss die Wahrscheinlichkeit ausgeben, dass beide inneren Produkte Null sind.
Für n=1
diese Wahrscheinlichkeit ist klar 1/2
.
Es macht mir nichts aus, wie n
im Code angegeben ist, aber es sollte sehr einfach und offensichtlich sein, wie man es ändert.
Sprachen und Bibliotheken
Sie können jede Sprache und Bibliothek verwenden, die Sie mögen. Ich möchte Ihren Code ausführen, daher geben Sie bitte eine vollständige Erklärung an, wie Sie Ihren Code unter Linux ausführen / kompilieren können, wenn dies überhaupt möglich ist.
n
wären hilfreich. Vielleicht hilft auch ein explizites Beispiel für A, B und die beiden inneren Produkte.n=4
zählt sie dann als null, zwei oder drei Bytes? Muss die Ausgabe genau seina/b
oder wäre[a b]
zB erlaubt?n
? Ansonsten denke ich, dass das nicht erlaubt ist.Antworten:
Pyth,
48474644 BytesProbieren Sie es online aus: Demonstration
Die Online-Version berechnet wahrscheinlich nicht
n=6
. Auf meinem Laptop (Offline-Version) dauert es ungefähr 45 Sekunden.Brute-Force-Ansatz.
Erläuterung:
quelle
+0r1_2
ist kürzer als/R2r2_2
.Mathematica,
159100878685 BytesZum Ändern ändern Sie
n
einfach die Variablendefinition am Anfang.Da es sich um Brute Force handelt, ist es ziemlich langsam, aber hier sind die ersten acht Ergebnisse:
Der letzte hat bereits 231 Sekunden gedauert und die Laufzeit ist schrecklich exponentiell.
Erläuterung
Wie gesagt, es ist rohe Gewalt. Im Wesentlichen zähle ich nur alle möglichen Punkte auf
A
undB
berechne die beiden Punktprodukte für jedes mögliche Paar und finde dann den Bruchteil der Paare, die sich ergeben haben{0, 0}
. Die kombinatorischen und linearen Algebra-Funktionen von Mathematica waren dabei sehr hilfreich:Dies erzeugt alle n-Tupel, die
1
oder enthalten-1
, dh alle möglichenA
. Dennn = 3
das ist:Um zu berechnen, machen
B
wir fast dasselbe:Durch Wiederholen
0
duplizieren wir jedes Tupel für jedes0
darin enthaltene, wodurch die0
Wahrscheinlichkeit doppelt so hoch wie1
oder wird-1
. Wieder amn = 3
Beispiel:Nun
A
wollen wir für jedes Mögliche das Punktprodukt jedes MöglichenB
, sowohl mitA[1 .. n]
als auchA[2 .. n+1]
. Wenn unser Strom beispielsweiseA
ist{1, 1, -1}
, möchten wir das Punktprodukt mit beiden{1, 1, -1}
und mit{1, -1, 1}
. Da alle unsereB
bereits bequemerweise die Zeilen einer Matrix sind, möchten wir die beiden UnterlistenA
als Spalten einer anderen Matrix, damit wir ein einfaches Punktprodukt zwischen ihnen berechnen können. Aber das Transponieren{{1, 1, -1}, {1, -1, 1}}
gibt einfach{{1, 1}, {1, -1}, {-1, 1}}
nur eine Liste aller zyklischen 2-Element-Unterlisten vonA
. Das macht das:Also berechnen wir das und nehmen das Punktprodukt mit unserer Liste von
B
. Da wir jetzt eine verschachtelte Liste erhalten (da jede möglicheA
einen eigenen Vektor ergibt), reduzieren wir diese mit##&@@
.Um herauszufinden, ob es sich um ein Paar
{x, y}
handelt{0, 0}
, berechnen wir,Sign[Norm[{x,y}]]
wo esNorm
gibt√(x²+y²)
. Dies gibt0
oder1
.Da wir jetzt nur die Brüche von
1
s in einer Liste von0
s und1
s kennen wollen, brauchen wir nur das arithmetische Mittel der Liste. Dies ergibt jedoch die Wahrscheinlichkeit, dass beide mindestens ein Punktprodukt ungleich Null sind, sodass wir es subtrahieren1
, um das gewünschte Ergebnis zu erhalten.quelle
Pyth -
6555 BytesFehler mit Bruchreduzierung auf Kosten von einem Byte behoben.
Verwendet Brute-Force-Ansatz und kann enorm Golf gespielt werden, wollte aber nur etwas rausholen. Sehr langsam
Es verwendet kartesische Produkte, um beides zu generieren,
A
undB
führt die variablen Wahrscheinlichkeiten aus, indem es0
zweimal in der Quellliste angezeigt wird, und zählt dann diejenigen, die das innere Produkt sind, auf Null. Das innere Produkt wird durch denV
syntaktischen Zucker der Ektorisierung erleichtert. Die Vereinfachung der Fraktion hat mich anfangs erschreckt, aber mit derP
Raureiffaktorisierungsfunktion und der Erkenntnis, dass wir nur um Potenzen von 2 reduzieren müssen, war es ziemlich einfach .Probieren Sie es hier online aus .
quelle
n
?CJam,
5857545146 BytesFügen Sie zum Ausführen die gewünschte Ganzzahl zwischen
WX]
und einm*
.Vielen Dank an @ jimmy23013 für das bisschen Magie und für das Golfen von 5 Bytes!
Probieren Sie es online im CJam-Interpreter aus .
Idee
Die meisten Teile dieser Antwort sind unkompliziert, aber es werden zwei nette Tricks verwendet:
Anstatt alle Vektoren von {-1, 1} n mit allen Vektoren von {-1, 0, 1} n mit den gewünschten Wahrscheinlichkeiten zu paaren , wird die Anzahl der Tripletts von Vektoren in {-1, 1} n berücksichtigt , die erfüllen eine bestimmte Bedingung.
Wenn wir die letzten beiden Vektoren eines Tripletts addieren, ist das Ergebnis ein Vektor von {-2, 0, 2} n .
Da (-1) + 1 = 0 = 1 + (-1) , treten 0 s doppelt so oft auf wie -2 s und 2 s.
Das Teilen jeder Komponente durch 2 würde einen Vektor von {-1, 0, 1} n mit den gewünschten Wahrscheinlichkeiten ergeben.
Da wir nur interessiert sind, ob das Skalarprodukt 0 ist oder nicht, können wir die Division durch 2 überspringen .
Nachdem wir alle Drillinge gezählt haben, die die Bedingung der Frage und die Gesamtzahl der Drillinge erfüllen, müssen wir den resultierenden Bruch reduzieren.
Anstatt die GCD beider Zahlen zu berechnen, reicht es aus, beide Zahlen durch die höchste Potenz von 2 zu teilen, die den Zähler teilt, da der Nenner immer eine Zweierpotenz ist.
Um die höchste Potenz von 2 zu erhalten, die x teilt , können wir das bitweise UND von x und ~ x + 1 nehmen .
~ x kehrt alle Bits von x um , sodass alle nachfolgenden 0 s zu 1 s werden. Durch Hinzufügen von 1 zu ~ x werden diese 1 s wieder zu 0 s und die letzte 1 in ~ x + 1 stimmt mit der letzten 1 in x überein .
Alle anderen Bits sind entweder beide 0 von verschieden, also gibt das bitweise UND die ganze Zahl zurück, die aus der letzten 1 von x und allen darauf folgenden 0 s besteht. Dies ist die höchste Potenz von 2, die x teilt .
Code
quelle
WX]m*Zm*_{~.+2,@fm<\f.*::+0-!},,__W*&:T/'/@,T/
.