Wenn Fibonacci die Königinnen trifft

18

(inspiriert von Helkas Reaktion auf meine zufällige Paarung von "Schach" - und "Fibonacci" -Tags im Chat)


Fibonacci

Die Fibonacci-Zahlen sind eine der bekanntesten Sequenzen in der Mathematik, bei der jede Zahl durch Addition der beiden vorhergehenden Zahlen zusammengesetzt wird. Nachfolgend finden Sie eine Definition der nullindexierten Sequenz:

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)

Daraus ergibt sich die Reihenfolge 0, 1, 1, 2, 3, 5, 8, 13, 21, ...( OEIS-Link ). Bei dieser Herausforderung konzentrieren wir uns nur auf die streng positiven Werte (so 1, 1, 2, 3, ...), und Sie können zwischen einer Indexierung ohne Indexierung und einer Indexierung mit einem Index wählen.

Die Fibonacci-Zahlen können verwendet werden, um die Ebene zu kacheln, indem Quadrate aufeinanderfolgender f(n)Größe verwendet und ihre Kanten aneinander ausgerichtet werden. Das Kacheln erfolgt gegen den Uhrzeigersinn, indem Quadrate in dem Muster "Rechts-Auf-Links-Ab" von dem aktuellen Quadrat platziert werden. Ein Beispiel für diese teilweise Kachelung f(8)=21mit dem blau hervorgehobenen Startquadrat lautet wie folgt:
Fibonacci-Quadrate

Sie können das sehen f(1)=1, die als Startfeld (blau markiert) f(2)=1auf den Platz gestellt rechts davon, der f(3)=2Platz platziert oben von dort, der f(4)=3platziert Platz links und so weiter. Das nächste Quadrat wäre f(9)=21+13=34und würde ganz unten liegen. Dies ist die Partial-Tiling-Methode, die wir in dieser Herausforderung verwenden werden.


Die Königinnen

Im Schachspiel ist die Königin die mächtigste Figur, da sie eine beliebige Anzahl von Feldern horizontal, vertikal oder diagonal bewegen kann. Im Diagramm unten zeigen die Quadrate mit einem schwarzen Kreis, wohin sich die Königin bewegen kann:
Königin zieht in Schach

Wir definieren den Begriff Abdeckung als

Der Prozentsatz der Quadrate, auf die sich die Dame bewegen kann, im Vergleich zur Gesamtzahl der Quadrate, wenn die jeweilige Position der Dame auf einem leeren Brett und die eigene Startposition der Dame angegeben sind.

Für das obige Beispiel ist die Abdeckung der Königin 28/64 = 43.75%. Wenn die Königin im oberen rechten h8Quadrat wäre, wäre die Abdeckung 22/64 = 34.375%. Wenn die Königin dabei e7wäre, wäre die Berichterstattung 24/64 = 37.5%.


Die Herausforderung

Wir werden die oben gezeigten Fibonacci-Kacheln als Schachbrett für diese Herausforderung verwenden. Sie erhalten zwei positive Ganzzahlen als Eingabe nund x:

  • Das nstellt dar, wie groß die Kacheln sind. Das Beispiel oben mit dem 21Quadrat links ist eine Tafel mit der Größe von n = 8da f(8) = 21(wenn mit dem Index Null).
  • Das xstellt dar, welches der Fibonacci-Quadrate für die Platzierung der Dame (n) verwendet wird, um die Abdeckung zu berechnen. Die Damen werden einzeln auf jedes Feld in diesem bestimmten Fibonacci-Quadrat gelegt, und die Gesamtabdeckung ist die Summe der einzelnen (eindeutigen) Abdeckung.

Hier ist zum Beispiel ein Bild von n = 8(die gleiche Kachelung wie oben) und x = 4(entsprechend dem f(4) = 3Quadrat, blau schattiert). Indem die Königinnen nacheinander eine Dame auf jedes dieser neun blauen Felder setzen, können sie (kombiniert) jedes orange schattierte Feld abdecken. Die Gesamtabdeckung in diesem Beispiel beträgt daher 309/714 = 43.28%.

n = 8, x = 4

Es ist klar, dass n = xdie Abdeckung zu jedem Zeitpunkt vorhanden sein wird 100%(zum Beispiel mit n=8und x=8können Sie sehen, dass jedes Quadrat auf dem gesamten Brett mindestens einmal abgedeckt wird). Umgekehrt wird sich mit einem angemessen großen nund x=1oder x=2die Abdeckung nähern (aber niemals erreichen) 0%(zum Beispiel mit n=8und x=1ist die Abdeckung dürftig 88/714 = 12.32%).

Bei zwei derartigen Eingaben müssen Sie den Erfassungsprozentsatz mit einer Genauigkeit von zwei Dezimalstellen ausgeben. Bitte geben Sie an, wie Ihr Code die Rundung handhabt.


Regeln

  • Die Eingabe und Ausgabe kann in einem beliebigen Format erfolgen , muss jedoch auf zwei Dezimalstellen genau sein. Bitte geben Sie an, wie Ihr Code die Rundung handhabt.
  • Angenommen, keine anderen Teile sind auf dem Brett oder stören auf andere Weise die Bewegungen.
  • Es ist entweder ein vollständiges Programm oder eine Funktion zulässig. Bei einer Funktion können Sie die Ausgabe zurückgeben, anstatt sie zu drucken.
  • Fügen Sie nach Möglichkeit einen Link zu einer Online-Testumgebung hinzu, damit andere Benutzer Ihren Code ausprobieren können!
  • Standardlücken sind verboten.
  • Dies ist daher gelten alle üblichen Golfregeln, und der kürzeste Code (in Byte) gewinnt.

Beispiele

n = 8, x = 4
43.28

n = 8, x = 8
100 or 100.00

n = 8, x = 1
12.32

n = 4, x = 1
66.67

n = 4, x = 2
60 or 60.00

n = 5, x = 3
75 or 75.00

n = 5, x = 1
47.5 or 47.50
AdmBorkBork
quelle
Mein Profilbild ist semi-relevant
Stephen
„Wenn Fibonacci traf die Queens“? Oder "Fibonacci trifft die Königinnen"?
Jonathan Allan
@ JonathanAllan Der Titel ist korrekt wie er ist. Es ist eine Indikativform wie in "Dies ist, was passiert, wenn X passiert." Vergleiche "Wenn Henry Sally zum Mittagessen trifft, essen sie immer Hamburger."
AdmBorkBork
Ah, du meinst "Wenn Fibonacci die Königinnen trifft ..."!
Jonathan Allan

Antworten:

2

VB.NET (.NET 4.5), 1238 1229 Byte

-9 Bytes dank @totallyhuman

Function A(n,x)
Dim g=New List(Of List(Of Long))
g.Add(New List(Of Long))
g(0).Add(1)
For i=2To n
Dim b=1
If i>2Then 
Dim w=0,y=1
b=w+y
For j=3To i
w=y
y=b
b=w+y
Next
End If
Select Case i Mod 4
Case 1
For j=1To b
Dim l=New List(Of Long)
For k=1To b
l.Add(i)
Next
g.Add(l)
Next
Case 2
For Each r In g
For j=1To b
r.Add(i)
Next
Next
Case 3
For j=1To b
g.Insert(0,New List(Of Long))
For k=1To b
g(0).Add(i)
Next
Next
Case 0
For Each r In g
For j=1To b
r.Insert(0,i)
Next
Next
End Select
Next
For i=0To g.Count-1
Dim c=g(i)
For j=0To c.Count-1
Dim e=c(j)
If e=x Then
For k=1To Math.Max(g.Count,g(0).Count)
If j-k>=0AndAlso c(j-k)<>x Then c(j-k)=0
If i-k>=0AndAlso g(i-k)(j)<>x Then g(i-k)(j)=0
If j+k<c.Count AndAlso c(j+k)<>x Then c(j+k)=0
If i+k<g.Count AndAlso g(i+k)(j)<>x Then g(i+k)(j)=0
If i-k>=0AndAlso j-k>=0AndAlso g(i-k)(j-k)<>x Then g(i-k)(j-k)=0
If i-k>=0AndAlso j+k<c.Count AndAlso g(i-k)(j+k)<>x Then g(i-k)(j+k)=0
If i+k<g.Count AndAlso j-k>=0AndAlso g(i+k)(j-k)<>x Then g(i+k)(j-k)=0
If i+k<g.Count AndAlso j+k<c.Count AndAlso g(i+k)(j+k)<>x Then g(i+k)(j+k)=0
Next
End If
Next
Next
Dim hits=0
For Each r In g
For Each c In r
If c=x Or c=0Then hits+=1
Next
Next
Return Math.Round(hits*100/(g.Count*g(0).Count),2)
End Function

Simulation der Problemstellung. Ich beginne mit der Erstellung des Rasters und durchlaufe jede neue Fibonacci-Zahl, um das Quadrat zu vergrößern. Ich speichere den Index in jeder Zelle, damit man im nächsten Schritt leicht findet, wohin die Königinnen gehen.

Dann finde ich jede Zelle, in der sich eine Dame befinden sollte, und markiere jedes bedrohte Feld mit einer Null. Ich überspringe die Zellen, in denen sich die Königinnen befinden, damit ich mich nicht um das Zurückverfolgen kümmern muss.

Am Ende zähle ich die gelöschten Zellen und die Zellen mit den Königinnen auf und teile sie dann durch die Gesamtzahl der Leerzeichen. Multiplizieren Sie mit 100, um den Prozentsatz zu erhalten, und runden Sie auf die nächsten zwei Dezimalstellen.

Brian J
quelle
Können Sie nicht hitszu einem kürzeren Variablennamen wechseln ? Ich kenne VB.NET nicht, aber ich gehe davon aus, dass dies eine Variable ist.
Totalhuman
@totallyhuman yep, das ist richtig. Ich ging von Hand durch und musste es verpasst haben. Vielen Dank!
Brian J
2

Python 2 , 524 499 Bytes

def Q(n,x):
 global w,h,f;f,R,L=0,range,len
 for d in R(n):s=x-1==d;f=f or[[s]];w=L(f[0]);W,H=R(w),R(L(f));exec"for j in "+("W:f.append([s]*w)","f:\n\tfor k in H:j.append(s)","W:f.insert(0,[s]*w)","f:\n\tfor k in H:j.insert(0,s)","f:0")[d%4-(d==0)]
 w,h=L(f[0]),L(f);l=0,1,-1
 for Y in R(h):
	for X in R(w):exec("""def F(u,v,x,y):
 while(u==v==0)==0<=x<w!=0<=y<h:f[y][x]=1+(f[y][x]!=1);x+=u;y+=v
for s in l:
 for t in l:F(s,t,X,Y)""","")[f[Y][X]!=1]
 q=w*h;return(q-sum(j.count(0)for j in f))*100./q

Probieren Sie es online!

Definieren einer Funktion, die sowohl die Kachelgröße nals auch die Fibonacci-Quadratzahl der Dame berücksichtigt x. Der Ausgabeleistungsprozentsatz wird möglicherweise auf zwei Dezimalstellen gerundet (in der Fußzeile, in der die gesamte Ausgabe erfolgt).

fist ein zweidimensionales Array, das die Informationen der Karte enthält, auf die initiiert wird 0. Dann wird das Fibonacci-Schachbrett berechnet und mit Königinnen besetzt, wo Königinnen sein sollen. Diese Königinnen werden dann an jeden Ort versetzt, an den sie versetzt werden können. Alle Positionen werden als Prozentsatz der gesamten Tafel gezählt und gedruckt.

Jonathan Frech
quelle
1

Mathematica 11.1, 336 Bytes, 1-basiert

R=Rectangle[#,+##]&;f=Fibonacci;o=Join@@Outer[##,1]&;r=RegionUnion;s=RegionMeasure;p[1]={0,0};p[i_]:=p[i-1]+{{-f@i,-f[i-2]},{0,-f@i},{f[i-1],0},{f[i-1]-f@i,f[i-1]}}[[i~Mod~4+1]];t[i_]:=r[R[p@#,f@#]&/@Range@i];k[n_,x_]:=Round[100s@RegionIntersection[r[R[#,f@x]&/@((#+p@x)&/@o[1##&,o[List,{-1,0,1},{-1,0,1}],Range[2f@n]])],t@i]/s@t@i,.01]

Verbrauch: k[n, x]. Achten Sie darauf, dass die Funktion 1-basiert ist. Die Rundung erfolgt durchRound[100x,0.01]

Grundsätzlich p[i]ist eine Funktion zur Bestimmung der Position jedes Quadrats. Und Bereich von der oberen Ebene berechnet Funktionen wie RegionIntersection, RegionUnion,RegionMeasure

Ergebnis

Keyu Gan
quelle