(вдохновленный ответом Хелки на мою случайную пару тегов "шахматы" и "Фибоначчи" в чате)

Фибоначчи

Эти числа Фибоначчи являются одним из наиболее известных последовательностей в математике, где каждое число состоит путем сложения двух предыдущих чисел вместе. Ниже приведено определение последовательности с нулевым индексом:

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

Это приводит к последовательности 0, 1, 1, 2, 3, 5, 8, 13, 21, ...( ссылка OEIS ). В этой задаче мы сконцентрируемся только на строго положительных значениях (поэтому 1, 1, 2, 3, ...), и вы можете выбрать нулевую или одну индексацию, но, пожалуйста, укажите, какие именно в вашем представлении.

Числа Фибоначчи можно использовать для разбиения на плоскости, используя квадраты, которые имеют последовательный f(n)размер, и выравнивая их края вместе. Черепица выполняется против часовой стрелки путем размещения квадратов по шаблону «справа-вверх-вниз-вниз» от текущего квадрата. Пример этого частичного разбиения для f(8)=21, с начальным квадратом, выделенным синим цветом, выглядит следующим образом:

Вы можете видеть f(1)=1начальный квадрат (выделенный синим цветом), f(2)=1квадрат справа от него, f(3)=2квадрат оттуда вверх , f(4)=3квадрат слева и так далее. Следующий квадрат будет f(9)=21+13=34и будет помещен на дно. Это частичный метод листов, который мы будем использовать в этой задаче.

Королевы

В игре в шахматы самая мощная фигура - королева, потому что она может перемещать любое количество мест по горизонтали, вертикали или диагонали. На приведенной ниже схеме доски квадраты с черным кружком показывают, куда королева может двигаться:

Мы определим термин покрытие как

Процент квадратов, на которые королева может переместиться, по отношению к общему количеству квадратов, учитывая конкретную позицию ферзя на пустой доске и включая собственную стартовую позицию ферзя.

Для примера выше, охват ферзя 28/64 = 43.75%. Если бы королева была в верхнем правом h8квадрате, охват был бы 22/64 = 34.375%. Если королева была в e7, покрытие будет 24/64 = 37.5%.

Соревнование

Мы собираемся использовать тайлинг Фибоначчи, показанный выше, в качестве нашей шахматной доски для этой задачи. Вам дадут два положительных целых числа в качестве входных данных, nи x:

• nПредставляет , насколько большой замощение. Пример выше, с 21квадратом слева, является доской размера n = 8с тех пор f(8) = 21(при нулевой индексации).
• xПредставляет какой из квадратов Фибоначчи используется для размещения Королева (ы), для расчета покрытия. Королевы размещаются по одному на каждом квадрате в этом конкретном квадрате Фибоначчи, и общее покрытие представляет собой сумму отдельного (уникального) покрытия.

Например, вот изображение n = 8(та же мозаика, что и выше) и x = 4(соответствующее f(4) = 3квадрату, затенено синим цветом). Размещая королеву по одному в каждом из этих девяти синих квадратов, королевы могут (вместе) покрывать каждый квадрат, заштрихованный оранжевым цветом. Общий охват в этом примере, поэтому 309/714 = 43.28%.

Совершенно очевидно, что в любое время n = xохват будет 100%(например, с помощью n=8и x=8, вы можете увидеть, что каждый квадрат на всей доске будет покрыт хотя бы один раз). И наоборот, при достаточно большом nи x=1или x=2, охват будет приближаться (но никогда не достигнет) 0%(например, с n=8и x=1, покрытие является ничтожным 88/714 = 12.32%).

Учитывая два таких числа ввода, вы должны вывести процент покрытия с точностью до двух десятичных знаков. Пожалуйста, укажите, как ваш код обрабатывает округление.

правила

• Ввод и вывод могут быть даны в любом удобном формате , но должны быть с точностью до двух знаков после запятой. Пожалуйста, укажите, как ваш код обрабатывает округление.
• Предположим, что на доске нет других фигур или иным образом мешают ходам.
• Либо полная программа или функция приемлемы. Если функция, вы можете вернуть вывод, а не распечатать его.
• Если возможно, укажите ссылку на среду онлайн-тестирования, чтобы другие люди могли опробовать ваш код!
• Стандартные лазейки запрещены.
• Это код-гольф, поэтому применяются все обычные правила игры в гольф, и выигрывает самый короткий код (в байтах).

Примеры

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

VB.NET, (.NET 4.5), 1238 1229 байт

-9 байт благодаря @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

Моделирование постановки задачи. Я начинаю с создания сетки, перебирая каждое новое число Фибоначчи, чтобы увеличить размер квадрата. Я храню индекс в каждой ячейке, чтобы на следующем шаге было легко определить, куда пойдут королевы.

Затем я нахожу каждую клетку, в которой должна быть королева, и помечаю каждую угрожаемую клетку нулем. Я пропускаю ячейки, где находятся королевы, чтобы мне не пришлось беспокоиться о возврате.

В конце я подсчитываю очищенные ячейки и ячейки с ферзями, а затем делю их на общее количество пробелов. Умножьте на 100, чтобы получить процент, и округлите до ближайших двух десятичных знаков.

Python 2 , 524 499 байт

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

Попробуйте онлайн!

Определение функции, которая принимает как размер nлиста и число квадрата Фибоначчи x. Процент выходных данных округленно округляется до двух знаков после запятой (в нижнем колонтитуле, где происходит весь вывод).

fявляется двумерным массивом, содержащим информацию о плате, инициируемой в 0. Затем вычисляется шахматная доска Фибоначчи и заполняется ферзями, где должны быть королевы. Эти королевы затем перемещаются в каждое место, где они могут быть перемещены; все позиции подсчитываются и печатаются в процентах от всей доски.

Mathematica 11,1, 336 байт, 1 на основе

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]

Использование: k[n, x]. Обратите внимание, что функция основана на 1. Округление достигаетсяRound[100x,0.01]

В основном, p[i]это функция определения положения каждого квадрата. А площадь рассчитывается верхнего уровня функции , такие как RegionIntersection, RegionUnion,RegionMeasure