Kiedy Fibonacci spotyka królowe

18

(zainspirowany odpowiedzią Helki na moją losową parę tagów „szachy” i „Fibonacci” na czacie)


Fibonacciego

Te numery Fibonacciego to jeden z bardziej znanych sekwencji matematycznych, z których każda składa się z dwóch dodanie poprzedniego numeru razem. Poniżej znajduje się definicja sekwencji o indeksie zerowym:

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

Powoduje to sekwencję 0, 1, 1, 2, 3, 5, 8, 13, 21, ...( łącze OEIS ). W tym wyzwaniu skupimy się tylko na wartościach ściśle dodatnich (więc 1, 1, 2, 3, ...) i możesz wybrać indeksowanie zerowe lub jednoindeksowe, ale proszę podać, które z nich w swoim zgłoszeniu.

Liczby Fibonacciego można wykorzystać do kafelkowania płaszczyzny, używając kwadratów o kolejnych f(n)rozmiarach i wyrównując ich krawędzie razem. Kafelkowanie odbywa się w kierunku przeciwnym do ruchu wskazówek zegara, poprzez umieszczenie kwadratów we wzorze „prawo-góra-lewo-dół” od bieżącego kwadratu. Przykład częściowego kafelkowania dla f(8)=21, z kwadratem początkowym podświetlonym na niebiesko, jest następujący:
Kwadraty Fibonacciego

Można zobaczyć f(1)=1, jak na placu wyjściowej (zaznaczony na niebiesko), na f(2)=1placu umieszczonym na prawo od, tym f(3)=2kwadrat umieszczony w górę Stamtąd f(4)=3kwadratowy Złożone w lewo i tak dalej. Następny kwadrat byłby f(9)=21+13=34i byłby umieszczony na dole. Jest to metoda częściowego kafelkowania, której będziemy używać w tym wyzwaniu.


Królowe

W grze w szachy najpotężniejszym pionkiem jest królowa, ponieważ może poruszać się o dowolną liczbę pól w poziomie, w pionie lub po przekątnej. Na poniższym schemacie planszy kwadraty z czarnym kółkiem pokazują, gdzie królowa może się poruszać:
Królowa porusza się w szachach

Określimy zakres ochrony jako

Procent kwadratów, do których królowa może się poruszać, w stosunku do całkowitej liczby kwadratów, biorąc pod uwagę szczególną pozycję królowej na pustej planszy, w tym własną pozycję początkową królowej.

W powyższym przykładzie zasięg królowej wynosi 28/64 = 43.75%. Gdyby królowa znajdowała się w prawym górnym h8kwadracie, zasięg byłby 22/64 = 34.375%. Gdyby królowa tam była e7, zasięg byłby 24/64 = 37.5%.


Wyzwanie

Użyjemy pokazanego powyżej kafelka Fibonacciego jako naszej szachownicy do tego wyzwania. Otrzymasz dwie dodatnie liczby całkowite jako dane wejściowe ni x:

  • nReprezentuje jak duży Dachówka jest. Przykładowy kafelek powyżej, z 21kwadratem po lewej, jest tablicą wielkości n = 8od f(8) = 21(po zindeksowaniu).
  • xReprezentuje który kwadratów Fibonacciego służy do królowej (ów) docelowego, do obliczania zasięgu. Królowe są umieszczane pojedynczo na każdym kwadracie w tym konkretnym kwadracie Fibonacciego, a całkowity zasięg jest sumą indywidualnego (unikalnego) zasięgu.

Na przykład, tutaj jest obraz n = 8(ten sam kafelek jak powyżej) i x = 4(odpowiadający f(4) = 3kwadratowi, zacieniowany niebieski). Umieszczając królową pojedynczo w każdym z tych dziewięciu niebieskich kwadratów, królowe mogą (łącznie) zakryć każdy kwadrat, który ma odcień pomarańczowy. Całkowity zasięg w tym przykładzie wynosi zatem 309/714 = 43.28%.

n = 8, x = 4

Oczywiście, za każdym razem n = x, zasięg będzie 100%(na przykład za pomocą n=8i x=8, i widać, że każdy kwadrat na całej planszy zostanie objęty przynajmniej raz). I odwrotnie, przy odpowiednio dużym ni x=1lub x=2, zasięg zbliża się (ale nigdy nie osiąga) 0%(na przykład przy n=8i x=1, zasięg jest marny 88/714 = 12.32%).

Biorąc pod uwagę dwie takie liczby wejściowe, musisz wyprowadzić procent pokrycia, z dokładnością do dwóch miejsc po przecinku. Podaj, jak Twój kod obsługuje zaokrąglanie.


Zasady

  • Dane wejściowe i wyjściowe mogą być podawane w dowolnym dogodnym formacie , ale muszą być dokładne z dokładnością do dwóch miejsc po przecinku. Podaj, jak Twój kod obsługuje zaokrąglanie.
  • Zakładaj, że na planszy nie ma żadnych innych elementów ani w żaden inny sposób nie zakłócać ruchów.
  • Dopuszczalny jest pełny program lub funkcja. Jeśli funkcja, możesz zwrócić dane wyjściowe zamiast je drukować.
  • Jeśli to możliwe, dołącz link do internetowego środowiska testowego, aby inni mogli wypróbować Twój kod!
  • Standardowe luki są zabronione.
  • To jest więc obowiązują wszystkie zwykłe zasady gry w golfa, a wygrywa najkrótszy kod (w bajtach).

Przykłady

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
źródło
Moje zdjęcie profilowe jest częściowo trafne
Stephen
„Kiedy Fibonacci spotkał królowe”? A może „Fibonacci spotyka królowe”?
Jonathan Allan
@JonathanAllan Tytuł jest taki, jaki jest. Jest obecny czas indykatywny, jak w „to właśnie dzieje się, gdy X się dzieje”. Porównaj „Kiedy Henry spotyka Sally na lunch, zawsze jedzą hamburgery”.
AdmBorkBork
Ach, masz na myśli „Kiedy Fibonacci spotyka królowe ...”!
Jonathan Allan

Odpowiedzi:

2

VB.NET, (.NET 4.5), 1238 1229 bajtów

-9 bajtów dzięki @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

Symulacja opisu problemu. Zaczynam od utworzenia siatki, zapętlając każdą nową liczbę fibonacci, aby zwiększyć rozmiar kwadratu. Przechowuję indeks w każdej komórce, aby łatwo było znaleźć miejsce, w którym pójdą królowe w następnym kroku.

Następnie znajduję każdą komórkę, w której powinna znajdować się królowa, i zaznaczam każdy zagrożony kwadrat zerem. Pomijam komórki tam, gdzie są królowe, aby nie musiałem się martwić o powrót.

Na koniec zliczam wyczyszczone komórki i komórki z królowymi, a następnie dzielę je przez całkowitą liczbę spacji. Pomnóż przez 100, aby uzyskać procent, i zaokrąglij do najbliższych dwóch miejsc po przecinku.

Brian J.
źródło
Czy nie możesz zmienić hitsna krótszą nazwę zmiennej? Nie znam VB.NET, ale zakładam, że to zmienna.
totalnie ludzki,
@ całkowicie ludzki tak, to prawda. Przeszedłem ręcznie i chyba tego przegapiłem. Dzięki!
Brian J
2

Python 2 , 524 499 bajtów

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

Wypróbuj online!

Zdefiniowanie funkcji uwzględniającej zarówno wielkość kafelków, jak ni liczbę kwadratową fibonacciego królowej x. Procent wypływów jest poręcznie zaokrąglany do dwóch miejsc po przecinku (w stopce, gdzie odbywa się cała produkcja).

fjest dwuwymiarową tablicą zawierającą inicjowane informacje o płycie 0. Następnie oblicza się szachownicę Fibonacciego i zapełnia ją królowymi tam, gdzie powinny być królowe. Te królowe są następnie przenoszone do każdego miejsca, w którym można je przenieść; wszystkie pozycje są liczone i drukowane jako procent całej planszy.

Jonathan Frech
źródło
1

Mathematica 11.1, 336 bajtów, 1-oparty

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]

Stosowanie: k[n, x] . Zwróć uwagę, że funkcja jest oparta na 1. Zaokrąglanie jest osiągane przezRound[100x,0.01]

Zasadniczo p[i]jest funkcją określania pozycji każdego kwadratu. A obszar jest obliczany przez górnym poziomie funkcji, takich jak RegionIntersection, RegionUnion,RegionMeasure

wynik

Keyu Gan
źródło