Temukan jumlah lintas-alternatif n

17

Diberikan input dari integer positif tunggal, output "jumlah lintas-alternatif" yang sesuai dengan integer itu.

Ambil contoh input n=5. Untuk menemukan jumlah lintas-alternatif, pertama-tama buat kisi persegi lebar dan tinggi nyang, membaca dari kiri ke kanan dan atas ke bawah, dimulai dari 1dan bertambah dengan satu posisi masing-masing:

 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

Kemudian, ambil jumlah dari kisi-kisi yang membentuk "salib" (yaitu, kedua diagonal digabungkan):

 1           5
    7     9
      13
   17    19
21          25

1 5 7 9 13 17 19 21 25

Akhirnya, ambil jumlah bolak-balik dari urutan ini:

1+5-7+9-13+17-19+21-25

-11

Contoh lain, untuk n=6(hanya untuk menunjukkan seperti apa bentuk salib untuk nomor genap 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

Karena ini adalah kode-golf , kode terpendek dalam byte akan menang.

Berikut adalah output yang benar untuk n=1ke n=100, yang dapat Anda gunakan sebagai uji kasus:

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
code-golf sequence Gagang pintu
sumber
8
Nit pick: Itu bukan jumlah yang bolak-balik. Anda menambahkan dua istilah pertama.
Dennis

Jawaban:

26

Jelly, 21 19 11 10 7 byte

²~³¡H+2

Cobalah online!

Ide

Asumsikan untuk sesaat bahwa istilah pertama dari jumlah akhir dikurangi daripada ditambahkan.

Biarkan n menjadi bilangan bulat positif.

Bahkan kasus

 1              6
    8       11
      15 16
      21 22
   26       29
31             36

Perbedaan antara elemen-elemen diagonal pada bagian bawah dari baris adalah bilangan asli ganjil n ÷ 2 . Karena 1 + 3 + 5 +… + (2k + 1) = k 2 , mereka berjumlah (n ÷ 2) 2 = n 2 ÷ 4 .

Dalam contoh ini

- 1 + 6 - 8 + 11 - 15 + 16 - 21 + 22 - 26 + 29 - 31 + 36  =
-(1 - 6)-(8 - 11)-(15 - 16)-(21 - 22)-(26 - 29)-(31 - 36) =
(    5   +   3    +    1  )+(   1    +    3    +    5   ) =
             9             +              9               = 18

Jadi, jumlahnya adalah 2 × n 2 ÷ 4 = n 2 ÷ 2 .

Kasus aneh

 1           5
    7     9
      13
   17    19
21          25

Perbedaan antara elemen diagonal pada baris yang sesuai dari atas dan bawah ( 1dan 5, dan 21dan 25; 7dan 9, 17dan 19) adalah sama, sehingga mereka akan membatalkan dalam jumlah bolak-balik.

Dalam contoh ini

- 1 + 5 - 7 + 9 - 13 + 17 - 19 + 21 - 25  =
-(1 - 5)-(7 - 9)- 13 +(17 - 19)+(21 - 25) =
    4   +   2   - 13 -    2    -    4     = -13

Yang tersisa adalah negatif dari elemen pusat, yang merupakan rata-rata aritmatika dari angka pertama dan terakhir, sehingga dapat dihitung sebagai - (n 2 + 1) ÷ 2 .

Kasus umum

Karena ~ x = - (x + 1) untuk integer komplemen dua ( ~ menunjukkan bitwise TIDAK), rumus untuk kasus aneh dapat ditulis ulang sebagai ~ n 2 ÷ 2 .

Juga, karena suku pertama ( 1 ) dari jumlah asli ditambahkan bukannya dikurangi, rumus di atas meninggalkan kesalahan 2 , yang harus diperbaiki.

Oleh karena itu, penjumlahan silang ke - n adalah n 2 ÷ 2 + 2 jika n adalah genap, dan ~ n 2 ÷ 2 + 2 jika ganjil.

Akhirnya, bitwise TIDAK adalah involusi, yaitu, ~~ x = x untuk semua x . Dengan cara ini ~~~ x = ~ x , ~~~~ x = x , dan, secara umum, ~ n x (artinya ~ diterapkan n kali) adalah x jika n adalah genap dan ~ x jika ganjil.

Dengan demikian, kita dapat menulis ulang rumus umum kita sebagai ~ n n 2 ÷ 2 + 2 untuk semua bilangan bulat positif n .

Kode

²~³¡H+2    Main link. Input: n

²          Yield n².
 ~         Apply bitwise NOT to n²...
  ³¡           n times.
    H      Halve the result.
     +2    Add 2.
Dennis
sumber
1
Saya tahu ada semacam formula sederhana, tetapi penjelasan dan eksekusi Anda sangat menakjubkan. +1
ETHproduk
5

JavaScript, 40 38 22 byte

Menggunakan solusi bentuk tertutup baru-ketinggalan jaman, mewah itu saja kemarahan!

n=>(n%2?3-n*n:4+n*n)/2

Berkat ThomasKwa, saya bisa menghilangkan fungsi rekursif saya yang mahal.

Conor O'Brien
sumber
Anda hanya perlu bitwise TIDAK sekali jika n% 2. Sebenarnya, saya pikir di JS mungkin lebih pendek untuk dilakukan(n%2?3-n*n:4+n*n)/2
lirtosiast
4

Jelly, 12 byte

RṖµ²+‘×-*$SC

Coba di sini .

lirtosiast
sumber
4

CJam, 13 15 byte

ri2#_{~}*2/2+

Dua byte off berkat Dennis.

Cobalah online!

Luis Mendo
sumber
3
Jawaban CJam pertamaku!
Luis Mendo
1
Mengganti 2%{~}&dengan {~}*menghemat dua byte.
Dennis
@ Dennis Bagus sekali! Terima kasih!
Luis Mendo
3

Minkolang 0,15 , 26 15 13 byte

Menggunakan algoritma gila Dennis, dan bermain golf dua byte lagi berkat dia. Orang itu bertanggung jawab untuk mengurangi separuh jumlah byte!

n2;d[~]4+2:N.

Coba di sini!

Penjelasan

@VoteToClose n^ 2, terapkan bitwise NOT nkali, tambahkan empat, belah dua. - Thomas Kwa 7 menit yang lalu

Lihat jawaban Dennis untuk penjelasan mengapa itu berhasil. Dalam komentar pada jawaban ini, ia menyarankan perbaikan lain yang berfungsi karena :adalah divisi integer, jadi saya bisa meniadakan bagian atas tumpukan dan tidak khawatir tentang +1 dari melakukan komplemen biner. Selanjutnya, n dan n ^ 2 memiliki paritas yang sama, yang menghilangkan kebutuhan untuk swap.

n                Take number from input - n
 2;              n**2
   d             Duplicates top of stack
    [~]          For loop that negates the top of stack n times
       4+        Add 4
         2:      Divide by 2
           N.    Output as number and stop.
El'endia Starman
sumber
2

GolfScript, 12 byte

~2?.{~}*2/2+

Ini menggunakan algoritma dari jawaban Jelly saya . Cobalah online!

Bagaimana itu bekerja

~            # Evaluate the input.
 2?          # Square it.
   .         # Push a copy of the square.
    {~}      # Push a code block that applies bitwise NOT.
       *     # Execute it n² times. Since n² and n have the same parity,
             # this is equivalent to executing in only n times.
        2/   # Halve the result.
          2+ # Add 2.
Dennis
sumber
2

ES7, 17 byte

n=>-1**n*n*n+4>>1

Port sederhana jawaban @ Dennis's Python 2.

Saat menulis jawaban ini saya berhasil golf port ES6 saya hingga 17 byte juga!

n=>(n*n^-n%2)/2+2
Neil
sumber
2

MATL , 13 27 byte

Menggunakan formula luar biasa Dennis:

2^t2\?Q_]2/2+

Cobalah online!

Pendekatan langsung ( 27 byte ):

2^:GtetXdwPXdhutn:-1w^!*s2+
Luis Mendo
sumber
2

Pure Bash, 28

Nah, sekarang @Dennis telah menunjukkan kepada kita semua cara melakukan ini, ini perlu diperbarui:

echo $[-1**$1*($1*$1+1)/2+2]

Jawaban sebelumnya:

Utilitas Bash + GNU, 77

Inilah awalnya:

a=$1
(seq 1 $[a+1] $[a*a]
seq $1 $[a>1?a-1:1] $[a*a])|sort -un|paste -sd+-|bc

N dilewatkan sebagai parameter baris perintah.

pastesangat berguna di sini untuk menghasilkan jumlah bolak-balik. The -dpilihan memungkinkan daftar karakter pemisah, yang digunakan siklis.

Trauma Digital
sumber
$[-1**$1*$1*$1+4>>1] bahkan lebih pendek.
Neil
2

Julia, 41 40 25 19 16 byte

n->-n%2$n^2÷2+2

Ini adalah fungsi anonim yang menerima integer dan mengembalikan integer. Untuk menyebutnya, tetapkan ke variabel.

Pendekatan di sini, dirancang oleh Dennis, adalah sebagai berikut. Pertama kita mendapatkan paritas n , yaitu n (mod 2), dan meniadakannya. Ini memberi kita 0 untuk input genap dan -1 untuk ganjil. Kami kemudian bitwise XOR dengan n 2 . Ketika n adalah genap, ini hanya n 2 karena XOR dengan 0 hanyalah angka. Ketika n ganjil, XOR dengan -1 sama dengan negasi bitwise. Jadi pada titik ini kita memiliki n 2 atau bitwise BUKAN dari n 2 . Kami integer membagi ini dengan 2 dan menambahkan 2 untuk mendapatkan hasilnya.

Menyimpan satu byte berkat Sp3000 pada versi sebelumnya, dan menyimpan 9 berkat Dennis yang satu ini!

Alex A.
sumber
1

Jolf, 13 byte

Coba di sini!

½?mρj-3Qj+4Qj
 ?mρj         if parity of j
     -3Qj     return 3 - j*j
         +4Qj else return 4 + j*j
½             (and halve the result)
Conor O'Brien
sumber
1

Python 2, 24 byte

lambda n:(-1)**n*n*n/2+2

Ini menggunakan algoritma dari jawaban Jelly saya , dengan sedikit modifikasi:

Alih-alih menerapkan ~ n kali, kami menerapkan - n kali (dengan mengalikan dengan (-1) n ). Ini setara karena ~ x = -x - 1 dan lantai pembagian bilangan bulat dengan Python, jadi ~ x / 2 = (-x - 1) / 2 = -x / 2 .

Dennis
sumber
1

Pyth, 11 byte

+2/u_GQ*QQ2

Cobalah online di Pyth Compiler .

Bagaimana itu bekerja

Ini menggunakan algoritma dari jawaban Jelly saya , dengan sedikit modifikasi:

Alih-alih menerapkan ~ n kali, kami menerapkan - n kali (dengan mengalikan dengan (-1) n ). Ini setara karena ~ x = -x - 1 dan lantai pembagian bilangan bulat di Pyth, jadi ~ x / 2 = (-x - 1) / 2 = -x / 2 .

+2/u_GQ*QQ2  Evaluated input: Q

       *QQ   Yield Q².
   u  Q      Set G = Q². For each non-negative integer below Q:
    _G         Set G = -G.
             Return G.
  /       2  Halve the result.
+2           Add 2.
Dennis
sumber
1

dc, 17

Menggunakan rumus yang sama dicoba dan diuji dari Dennis:

?dd*1+r_1r^*2/2+p

Cobalah online Oh, mengapa kotak pasir Ideone bash tidak termasuk dc?

Tes baris perintah:

for i in {1..100}; do echo $i | dc -e '?dd*1+r_1r^*2/2+p'; done
Trauma Digital
sumber
?2^1+2~2*1-*2+pmenghemat dua byte.
Dennis
1

GS2, 9 byte

V,@!α2+''

Ini menggunakan algoritma dari jawaban Jelly saya . Cobalah online!

V,@e 7+''

sama pendeknya, tetapi terutama tidak mengandung karakter non-ASCII.

Bagaimana itu bekerja

V          Parse the input as an integer n.
 ,         Compute n².
  @        Push a copy of n².
   !       Bitwise NOT.
    α      Make a block of the previous instruction.
     2     Execute the block n² times. Since n² and n have the same parity,
           this is equivalent to executing in only n times.
      +    Halve the result.
       ''  Increment twice.
Dennis
sumber
1

J, 16 byte

[:<.2%~4+*:*_1^]

Ini menggunakan algoritma yang sama dengan jawaban Jelly saya. Mengujinya dengan J.js .

Dennis
sumber
0

Lua, 33 byte ( Coba online )

i=(...)print((-1)^i*i*i/2-.5*i%2)

Bagaimana itu bekerja:

i=(...)print((-1)^i*i*i/2-.5*i%2)
i=(...)                           Take input and store to i
       print(
             (-1)^i               Raise (-1) to the i-th power: -1 if odd, 1 if even
                   *i*i/2         Multiply by i squared and halved.
                         -.5*i%2  i%2 is the remainder when i is divided by 2
                                  if i is odd, then i%2 will be 1, and this expression
                                  will evaluate to -0.5
                                  but if i is even, then i%2 will be 0, which makes
                                  this expression evaluate to 0
                                )
Biarawati Bocor
sumber
0

Dyalog APL, 13 byte

⌊2+.5××⍨ׯ1*⊢

Ini menggunakan algoritma yang sama dengan jawaban Jelly saya. Uji di TryAPL .

Dennis
sumber