Dada a entrada de um único número inteiro positivo, imprima a "soma alternada cruzada" que corresponde a esse número inteiro.
Veja o exemplo da entrada n=5
. Para encontrar a soma alternada cruzada, primeiro crie uma grade quadrada de largura e altura n
que, lendo da esquerda para a direita e de cima para baixo, inicie 1
e aumente em uma cada posição:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
Em seguida, pegue as somas da grade que formam uma "cruz" (ou seja, as duas diagonais combinadas):
1 5
7 9
13
17 19
21 25
1 5 7 9 13 17 19 21 25
Por fim, pegue a soma alternada desta sequência:
1+5-7+9-13+17-19+21-25
-11
Outro exemplo, para n=6
(apenas para mostrar como é a cruz para números pares n
):
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30
31 32 33 34 35 36
1 6
8 11
15 16
21 22
26 29
31 36
1+6-8+11-15+16-21+22-26+29-31+36
20
Como esse é o código-golfe , o código mais curto em bytes será vencedor.
Aqui estão as saídas corretas para n=1
to n=100
, que você pode usar como casos de teste:
1
4
-3
10
-11
20
-23
34
-39
52
-59
74
-83
100
-111
130
-143
164
-179
202
-219
244
-263
290
-311
340
-363
394
-419
452
-479
514
-543
580
-611
650
-683
724
-759
802
-839
884
-923
970
-1011
1060
-1103
1154
-1199
1252
-1299
1354
-1403
1460
-1511
1570
-1623
1684
-1739
1802
-1859
1924
-1983
2050
-2111
2180
-2243
2314
-2379
2452
-2519
2594
-2663
2740
-2811
2890
-2963
3044
-3119
3202
-3279
3364
-3443
3530
-3611
3700
-3783
3874
-3959
4052
-4139
4234
-4323
4420
-4511
4610
-4703
4804
-4899
5002
Respostas:
Geléia,
211911107 bytesExperimente online!
Idéia
Suponha por um segundo que o primeiro termo da soma final seja subtraído em vez de adicionado.
Seja n um número inteiro positivo.
Caso uniforme
As diferenças entre os elementos diagonais na metade inferior das linhas são os primeiros n ÷ 2 números naturais ímpares. Como 1 + 3 + 5 +… + (2k + 1) = k 2 , eles somam (n ÷ 2) 2 = n 2 ÷ 4 .
Neste exemplo
Assim, a soma é 2 × n 2 ÷ 4 = n 2 ÷ 2 .
Caso estranho
As diferenças entre os elementos diagonais nas linhas correspondentes de cima e de baixo (
1
e5
, e21
e25
;7
e9
, e17
e19
) são as mesmas, portanto, elas serão canceladas na soma alternada.Neste exemplo
Tudo o que resta é o negativo do elemento central, que é a média aritmética do primeiro e do último número, para que possa ser calculado como - (n 2 + 1) ÷ 2 .
Caso Geral
Como ~ x = - (x + 1) para números inteiros de complemento de dois ( ~ denota NOT bit a bit), a fórmula do caso ímpar pode ser reescrita como ~ n 2 ÷ 2 .
Além disso, como o primeiro termo ( 1 ) da soma original é adicionado em vez de subtraído, as fórmulas acima deixam um erro 2 , que deve ser corrigido.
Portanto, a nésima soma de cruzada alternativa é n 2 ÷ 2 + 2 se n for par e ~ n 2 ÷ 2 + 2 se for ímpar.
Finalmente, NOT bit a bit é uma involução, ou seja, ~~ x = x para todos os x . Dessa forma, ~~~ x = ~ x , ~~~~ x = x e, em geral, ~ n x (significando que ~ é aplicado n vezes) é x se n for par e ~ x se for ímpar.
Assim, podemos reescrever nossa fórmula geral como ~ n n 2 ÷ 2 + 2 para todos os números inteiros positivos n .
Código
fonte
JavaScript,
403822 bytesUsar essa solução sofisticada e cheia de estilo, cheia de fanfarras, é toda a raiva!
Graças à ThomasKwa, posso eliminar minha função recursiva dispendiosa.
fonte
(n%2?3-n*n:4+n*n)/2
Gelatina, 12 bytes
Experimente aqui .
fonte
CJam, 13
15bytesDois bytes de desconto, graças a Dennis.
Experimente online!
fonte
2%{~}&
por{~}*
salva dois bytes.Número 0.15 ,
261513 bytesUsando o algoritmo insano de Dennis, jogou mais dois bytes graças a ele. Esse cara é responsável pela metade da contagem de bytes!
Experimente aqui!
Explicação
Veja a resposta de Dennis para a explicação de por que isso funciona. Em um comentário sobre essa resposta, ele sugeriu outra melhoria que funciona porque
:
é a divisão inteira, para que eu possa negar o topo da pilha e não me preocupar com o +1 de fazer o complemento binário. Além disso, n e n ^ 2 têm a mesma paridade, o que elimina a necessidade de uma troca.fonte
GolfScript, 12 bytes
Isso usa o algoritmo da minha resposta Jelly . Experimente online!
Como funciona
fonte
ES7, 17 bytes
Porta simples da resposta Python 2 de @ Dennis.
Enquanto escrevia esta resposta, também consegui rodar minha porta ES6 com 17 bytes!
fonte
MATL , 13
27bytesUsando as incríveis fórmulas de Dennis:
Experimente online!
Abordagem direta ( 27 bytes ):
fonte
Pure Bash, 28
Bem, agora que o @Dennis nos mostrou tudo como fazer isso, isso precisa ser atualizado:
Resposta anterior:
Utilitários Bash + GNU, 77
Aqui está um começo:
N é passado como um parâmetro de linha de comando.
paste
é realmente útil aqui para produzir a soma alternada. A-d
opção permite uma lista de caracteres separadores, que são usados ciclicamente.fonte
$[-1**$1*$1*$1+4>>1]
é ainda mais curto.Julia,
4140251916 bytesEsta é uma função anônima que aceita um número inteiro e retorna um número inteiro. Para chamá-lo, atribua-o a uma variável.
A abordagem aqui, elaborada por Dennis, é a seguinte. Primeiro obtemos a paridade de n , ou seja, n (mod 2) e a negamos. Isso nos dá 0 para entradas pares e -1 para ímpares. Em seguida, bit a bit XOR com n 2 . Quando n é par, isso é apenas n 2 porque XOR com 0 é apenas o número. Quando n é ímpar, XOR com -1 é igual à negação bit a bit. Então, neste ponto, ou temos n 2 ou NÃO bit a bit de n 2 . Nós inteiro dividimos isso por 2 e adicionamos 2 para obter o resultado.
Salvou um byte graças ao Sp3000 em uma versão anterior e salvou 9 graças ao Dennis nesta versão!
fonte
Jolf, 13 bytes
Experimente aqui!
fonte
Python 2, 24 bytes
Isso usa o algoritmo da minha resposta Jelly , com uma pequena modificação:
Em vez de aplicar
~
n vezes, aplicamos-
n vezes (multiplicando por (-1) n ). Isso é equivalente porque ~ x = -x - 1 e pisos de divisão inteira em Python, então ~ x / 2 = (-x - 1) / 2 = -x / 2 .fonte
Pitão, 11 bytes
Experimente online no Pyth Compiler .
Como funciona
Isso usa o algoritmo da minha resposta Jelly , com uma pequena modificação:
Em vez de aplicar
~
n vezes, aplicamos-
n vezes (multiplicando por (-1) n ). Isso é equivalente porque ~ x = -x - 1 e pisos de divisão inteira em Pyth, então ~ x / 2 = (-x - 1) / 2 = -x / 2 .fonte
dc, 17
Usando a mesma fórmula testada e comprovada de Dennis:
Experimente onlineOh, por que a sandbox Ideone bash não incluidc
?Teste de linha de comando:
fonte
?2^1+2~2*1-*2+p
salva dois bytes.GS2, 9 bytes
Isso usa o algoritmo da minha resposta Jelly . Experimente online!
é igualmente curto, mas notavelmente não contém caracteres não ASCII.
Como funciona
fonte
J, 16 bytes
Isso usa o mesmo algoritmo da minha resposta Jelly. Testá-lo com J.js .
fonte
Lua, 33 bytes ( Experimente online )
Como funciona:
fonte
Dyalog APL, 13 bytes
Isso usa o mesmo algoritmo da minha resposta Jelly. Teste-o no TryAPL .
fonte