(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:
Można zobaczyć f(1)=1
, jak na placu wyjściowej (zaznaczony na niebiesko), na f(2)=1
placu umieszczonym na prawo od, tym f(3)=2
kwadrat umieszczony w górę Stamtąd f(4)=3
kwadratowy Złożone w lewo i tak dalej. Następny kwadrat byłby f(9)=21+13=34
i 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ć:
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 h8
kwadracie, 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 n
i x
:
n
Reprezentuje jak duży Dachówka jest. Przykładowy kafelek powyżej, z21
kwadratem po lewej, jest tablicą wielkościn = 8
odf(8) = 21
(po zindeksowaniu).x
Reprezentuje 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) = 3
kwadratowi, 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%
.
Oczywiście, za każdym razem n = x
, zasięg będzie 100%
(na przykład za pomocą n=8
i x=8
, i widać, że każdy kwadrat na całej planszy zostanie objęty przynajmniej raz). I odwrotnie, przy odpowiednio dużym n
i x=1
lub x=2
, zasięg zbliża się (ale nigdy nie osiąga) 0%
(na przykład przy n=8
i 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 golf golfowy, 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
Odpowiedzi:
VB.NET, (.NET 4.5),
12381229 bajtów-9 bajtów dzięki @totallyhuman
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.
źródło
hits
na krótszą nazwę zmiennej? Nie znam VB.NET, ale zakładam, że to zmienna.Python 2 ,
524499 bajtówWypróbuj online!
Zdefiniowanie funkcji uwzględniającej zarówno wielkość kafelków, jak
n
i liczbę kwadratową fibonacciego królowejx
. Procent wypływów jest poręcznie zaokrąglany do dwóch miejsc po przecinku (w stopce, gdzie odbywa się cała produkcja).f
jest dwuwymiarową tablicą zawierającą inicjowane informacje o płycie0
. 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.źródło
Mathematica 11.1, 336 bajtów, 1-oparty
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 jakRegionIntersection
,RegionUnion
,RegionMeasure
źródło