(inspirado na resposta de Helka ao meu pareamento aleatório das tags "xadrez" e "Fibonacci" no bate-papo)
Fibonacci
Os números de Fibonacci são uma das seqüências mais conhecidas da matemática, onde cada número é composto adicionando os dois números anteriores. Abaixo está uma definição da sequência indexada a zero:
f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)
Isso resulta na sequência 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
( link OEIS ). Neste desafio, focaremos apenas os valores estritamente positivos (so 1, 1, 2, 3, ...
), e você pode escolher a indexação zero ou a indexação única, mas indique qual em seu envio.
Os números de Fibonacci podem ser usados para um mosaico do plano, usando quadrados de f(n)
tamanho sucessivo e alinhando suas arestas. A lado a lado é feita no sentido anti-horário, colocando quadrados no padrão "direita-cima-esquerda-baixo" a partir do quadrado atual. Um exemplo desse ladrilho parcial para f(8)=21
, com o quadrado inicial destacado em azul, é o seguinte:
Você pode ver f(1)=1
como o quadrado inicial (destacado em azul), o f(2)=1
quadrado colocado à direita dele, o f(3)=2
quadrado colocado a partir daí, o f(4)=3
quadrado colocado à esquerda e assim por diante. O próximo quadrado seria f(9)=21+13=34
e seria colocado no fundo. Esse é o método de ladrilhos parciais que usaremos neste desafio.
As rainhas
No jogo de xadrez , a peça mais poderosa é a rainha, porque ela pode mover qualquer número de espaços na horizontal, na vertical ou na diagonal. No diagrama abaixo, os quadrados com um círculo preto mostram onde a rainha pode se mover:
Definiremos o termo cobertura como
A porcentagem de quadrados para os quais a rainha pode se mover em relação ao número total de quadrados, dada a posição específica da rainha em um tabuleiro vazio e incluindo a posição inicial da rainha.
Para o exemplo acima, a cobertura da rainha é 28/64 = 43.75%
. Se a rainha estivesse no h8
quadrado superior direito , a cobertura seria 22/64 = 34.375%
. Se a rainha estivesse e7
, a cobertura seria 24/64 = 37.5%
.
O desafio
Vamos usar o ladrilho de Fibonacci demonstrado acima como nosso tabuleiro de xadrez para esse desafio. Você receberá dois números inteiros positivos como entrada n
e x
:
- O
n
representa o tamanho da peça. O exemplo lado a lado acima, com o21
quadrado à esquerda, é uma placa de tamanhon = 8
desdef(8) = 21
(quando indexada a zero). - O
x
representa qual dos quadrados de Fibonacci é usado para a colocação das rainhas, para o cálculo da cobertura. As rainhas são colocadas uma de cada vez em cada quadrado naquele bloco quadrado de Fibonacci específico, e a cobertura total é o somatório da cobertura individual (única).
Por exemplo, aqui está uma imagem de n = 8
(o mesmo lado a lado acima) e x = 4
(correspondente ao f(4) = 3
quadrado, sombreado em azul). Ao colocar uma rainha uma de cada vez em cada um dos nove quadrados azuis, as rainhas podem (combinadas) cobrir todos os quadrados sombreados em laranja. A cobertura total neste exemplo é, portanto 309/714 = 43.28%
.
Obviamente, a qualquer momento n = x
, a cobertura será 100%
(por exemplo, com n=8
e x=8
, você pode ver que todos os quadrados de todo o quadro serão cobertos pelo menos uma vez). Por outro lado, com um tamanho adequadamente grande n
e x=1
ou x=2
, a cobertura se aproximará (mas nunca alcançará) 0%
(por exemplo, com n=8
e x=1
, a cobertura é insignificante 88/714 = 12.32%
).
Dados dois desses números de entrada, você deve gerar a porcentagem de cobertura, com precisão de duas casas decimais. Especifique como o seu código lida com o arredondamento.
Regras
- A entrada e a saída podem ser fornecidas em qualquer formato conveniente , mas devem ter precisão de duas casas decimais. Especifique como o seu código lida com o arredondamento.
- Suponha que não haja outras peças no tabuleiro ou interfira nos movimentos.
- Um programa completo ou uma função são aceitáveis. Se uma função, você pode retornar a saída em vez de imprimi-la.
- Se possível, inclua um link para um ambiente de teste on-line para que outras pessoas possam experimentar seu código!
- As brechas padrão são proibidas.
- Isso é código-golfe, portanto todas as regras usuais de golfe se aplicam e o código mais curto (em bytes) vence.
Exemplos
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
Respostas:
VB.NET, (.NET 4.5),
12381229 bytes-9 bytes graças a @totallyhuman
Simulação da declaração do problema. Começo criando a grade, percorrendo cada novo número de fibonacci para aumentar o tamanho do quadrado. Eu armazeno o índice em cada célula, para que seja fácil descobrir para onde as rainhas irão na próxima etapa.
Então, encontro todas as células que devem ter uma rainha e marque cada quadrado ameaçado com um zero. Eu pulo as células onde estão as rainhas para não precisar me preocupar em voltar atrás.
No final, conto as células que são limpas e as células com rainhas e depois as divido pelo número total de espaços. Multiplique por 100 para obter a porcentagem e arredondar para as duas casas decimais mais próximas.
fonte
hits
para um nome de variável mais curto? Não conheço o VB.NET, mas presumo que seja uma variável.Python 2 ,
524499 bytesExperimente online!
Definir uma função que considere o tamanho da peça
n
e o número quadrado de fibonacci da rainhax
. A porcentagem de saída é arredondada porperly para duas casas decimais (no rodapé, onde toda a saída está ocorrendo).f
é uma matriz bidimensional que contém as informações da placa que estão sendo iniciadas0
. Então, o tabuleiro de xadrez de Fibonacci é calculado e preenchido com rainhas onde as rainhas devem estar. Essas rainhas são então movidas para todos os lugares em que podem ser movidas; todas as posições são contadas e impressas como uma porcentagem de todo o quadro.fonte
Mathematica 11.1, 336 bytes, com base em 1
Uso:
k[n, x]
. Preste atenção que a função é baseada em 1. O arredondamento é obtido porRound[100x,0.01]
Basicamente,
p[i]
é uma função da determinação da posição de cada quadrado. E a área é calculada pelo nível superior funções comoRegionIntersection
,RegionUnion
,RegionMeasure
fonte