Latar Belakang
Pertimbangkan urutan yang didefinisikan sebagai berikut:
- Elemen pertama adalah 0;
- Elemen kedua adalah 4;
- Dari elemen ketiga dan seterusnya, nilainya dapat dihitung dengan:
- Mengambil himpunan bilangan bulat dari 0 hingga elemen sebelumnya dari urutan (inklusif atau eksklusif, itu tidak masalah);
- Menghapus semua bilangan bulat yang sudah muncul sebelumnya dalam urutan dari set;
- Menambahkan elemen sisa set; itulah nilai yang Anda inginkan.
Menariknya, urutan ini tampaknya belum berada di OEIS .
Tugas
Tulis program atau fungsi yang mengambil integer n sebagai input, dan output elemen ke- n dari urutan.
Uji kasus
Beberapa elemen pertama dari urutan adalah:
- 0
- 4
- 6 (1 + 2 + 3)
- 11 (1 + 2 + 3 + 5)
- 45 (1 + 2 + 3 + 5 + 7 + 8 + 9 + 10)
- 969 (1 + 2 + 3 + 5 + 7 ... 10 + 12 ... 44)
- 468930 (1 + 2 + 3 + 5 + 7 ... 10 + 12 ... 44 + 46 ... 968)
Klarifikasi
- Secara teori, program Anda dapat menangani n sembarang jika dijalankan pada varian bahasa Anda yang memiliki bilangan bulat besar tanpa batas dan akses ke jumlah memori yang tidak terbatas. (Bahasa tanpa bignum tidak mungkin bisa mendapatkan lebih dari 468930, tapi itu bukan alasan untuk menuliskan kode jawaban).
- Anda dapat memilih pengindeksan berbasis-0 atau berbasis-1 untuk urutan (misalnya terserah Anda apakah n = 1 mengembalikan elemen pertama, n = 2 elemen kedua, dan seterusnya; atau apakah n = 0 mengembalikan elemen pertama , n = 1 elemen kedua, dan seterusnya).
- Tidak ada persyaratan pada algoritma yang Anda gunakan, atau pada efisiensinya; Anda dapat mengimplementasikan definisi urutan secara langsung (meskipun itu benar-benar tidak efisien), dan Anda juga dapat menerapkan algoritma berbeda yang mengarah ke hasil yang sama.
Kondisi kemenangan
Ini adalah kode-golf , sehingga program terpendek yang benar, diukur dalam byte, menang.
Jawaban:
Jelly ,
13129 byteMenggunakan pengindeksan berbasis 0.
Cobalah online!
Bagaimana itu bekerja
sumber
Python,
6660 byteTerima kasih kepada @Dennis karena mencukur 6 byte!
Ini bukan potongan kode golf yang pernah ada, tetapi menggunakan rumus yang saya buat:
Di mana
x
di sisi kanan adalahf(n - 1)
, dany
inif(n - 2)
.Penjelasan:
Jumlah bilangan bulat berkelanjutan dari
a
hinggab
(inklusif) dapat dijelaskan dengan rumus ini:Di mana
amount
(jumlah angka) digambarkan seperti ini:Dan
average
(rata-rata semua angka) dijelaskan seperti ini:Jadi rumus lengkapnya sekarang:
Cara kita menerapkan formula ini ke dalam rumus akhir ini adalah untuk menggantikan
a
untukf(n - 1)
,b
untukf(n - 2)
, yang pada dasarnya menghitung jumlah dari semua syarat baru, dan tambahkan lagif(n - 1)
(yang sekaranga
) pada, yang merupakan jumlah dari semua istilah sebelumnya.Menggabungkannya bersama-sama, kita dapatkan:
Ganti
a
denganx
danb
dengany
, dan hai presto, Anda harus rumus di atas.sumber
Python 2 ,
585450 byteCobalah online!
sumber
Mathematica,
4948 byteMenggunakan pengodean CP-1252. Menentukan fungsi
PlusMinus (±)
. 1-diindeks.Penjelasan
sumber
Oasis , 11 byte
Kode:
Penjelasan:
Untuk memvisualisasikan hubungan f n , mari kita ambil contoh f 5 . Untuk menghitung f 5 , mari kita lihat jumlah berikut:
1 + 2 + 3 + 5 + 7 + 8 + 9 + 10
Bagian tebal sama dengan f 4 . Bagian 7 + 8 + 9 + 10 adalah kisaran [f n-2 + 1, f n-1 - 1] . Itu membuat rumus f n-1 + Σ [f n-2 + 1 ... f n-1 - 1] ( tautan Wolfram ):
f n = 0,5 × (f n-1 2 - f n-2 2 + f n-1 - f n-2 )
Yang dapat ditulis ulang untuk:
f n = 0,5 × ((f n-1 - f n-2 ) (f n-1 + f n-2 ) + (f n-1 - f n-2 ))
f n = 0,5 × ((f n-1 - f n-2 ) (f n-1 + f n-2 + 1))
Rumus yang mana yang akan kita gunakan dalam kode:
Penjelasan kode
Bagian
640
memberi kita kasus dasar:Kode yang akan dieksekusi (yang mendefinisikan a (n) ):
Cobalah online!
sumber
Julia,
393332 byteBerbasis 0.
Berkat @ Dennis, disimpan 6 byte.
Berkat @ GlenO, tersimpan satu byte.
Cobalah online!
Jawaban sebelumnya 1- berdasarkan:
Cobalah online!
Berbasis 1 jawaban ungolfed sebelumnya:
Cobalah online!
sumber
n<3?5n-n^2:
bukann<4?2(n>1)n:
- perhatikan bahwa ia beralih menggunakan pengindeksan berbasis 0.JavaScript (ES6), 47 byte
Menggunakan relasi perulangan
f(n) = sum(range(f(n-2) + 1, f(n-1) + 1))
untuk n> 2.sumber
PowerShell ,
84898887 byteCobalah online!
Penjelasan
Pengindeksan berbasis 0. Hanya bekerja melalui
n = 6
(pada mesin Windows saya crash dengan stack overflow untukn = 7
).Menggunakan metode yang sama dengan jawaban JungHwan Min (jumlah kisaran minus jumlah istilah sebelumnya).
Menjumlahkan rentang / array di PowerShell panjang, jadi saya menggunakan trik bergabung dengan array
+
untuk membuat ekspresi panjang (seperti1+2+3+4...etc
) dan kemudian mengirimkannya melaluiiex
(Invoke-Expression
).Karena saya perlu melakukannya dua kali, daripada menggunakan
-join
saya mengatur variabel khusus$OFS
, yang merupakan pemisah bidang keluaran. Saat Anda merangkaikan array, ini adalah karakter yang digunakan untuk menggabungkan elemen; itu default ke spasi. Jadi dengan mengaturnya ke+
(sekali), saya bisa mengganti sesuatu$a-join'+'|iex
dengan"$a"|iex
.Sebuah
for
loop sederhana terus berjalan hingga jumlah urutan kurang dari atau sama dengan integer input, lalu saya mengembalikan$n
elemen th.sumber
;
diperlukan setelahfor
loop. Tidak pernah menyadari itu sebelumnya.MATL ,
1716 byte1
pengindeksan berbasis digunakan. Kode ini sangat tidak efisien. Untukn = 6
itu sudah melebihi batas memori kompiler online.Cobalah online!
Bagaimana itu bekerja
Selama 20 byte , versi berikut ini menghindari batasan memori. Tetapi masih ada batasan tipe data (
double
tipe hanya dapat menjamin bahwa integer terwakili secara akurat hingga2^53
), sehingga hasilnya hanya valid hinggan = 8
.Coba juga online !
sumber
Haskell , 42 byte
Cobalah online!
Hal ini secara langsung mengimplementasikan kekambuhan bahwa untuk
n>2
,f(n)
samaf(n-1)
ditambah jumlah interval terbuka darif(n-2)
kef(n-1)
mana lagi adalah sama dengan jumlah dari interval setengah terbuka darif(n-2)
kef(n-1)
inklusif.sumber
Haskell, 31 byte
Contoh penggunaan:
((0:4#6)!!) 6
->468930
. Cobalah online! .Rekursi sederhana, yang melacak elemen maksimum
m
sejauh ini dan nilai selanjutnyas
.sumber
JavaScript,
123119 byteCobalah online! Solusi ini berbasis 1
f(1) => 0
,.sumber
Perl 6 ,
52 49 4435 byteCobalah
Cobalah
Cobalah
Cobalah
Diperluas:
sumber
PowerShell ,
7773 byteCobalah online!
Menerapkan algoritma seperti yang didefinisikan, dan diindeks 0. Input
6
terlalu banyak untuk ditangani oleh TIO.Setel
$a
menjadi array[0,4]
. Loop dari1
hingga input$n
. Dalam loop, kami mengambil rentang angka dari0
hingga jumlah terbesar yang kami miliki$a[-1]
, dan menggunakanWhere-Object
klausa|?{...}
untuk menarik hanya angka-angka yang belum ada. Array angka itu-join
diedit bersama dengan+
s, lalu diumpankan keiex
(kependekan dariInvoke-Expression
dan mirip denganeval
) Nilai itu kemudian array-concatenated ke akhir$a
. Akhirnya, kita keluar dari loop kita, dan mengambil$n
nomor ke dalam array kita. Angka itu ditinggalkan di jalur pipa, dan hasilnya tersirat.sumber
Python 2 , 85 byte
Cobalah online!
sumber
Batch, 108 byte
Port jawaban JavaScript saya.
sumber
dc , 47 byte
Bekerja dengan bilangan bulat sebesar yang Anda inginkan, hingga kapasitas memori komputer.
Cobalah online!
Pengindeksan berbasis 0, input pada stdin, output pada stdout. (Ada juga output pada stderr, yang harus diabaikan.)
Sampel berjalan:
Ini menggunakan algoritma yang sama dengan solusi berikut dalam bash, yang (sedikit) lebih mudah dibaca:
Bash murni, 60 byte
Tetapi program bash hanya bekerja untuk input hingga 7, karena itu melebihi bilangan bulat integer di luar itu.
sumber
Pyth - 15 byte
Test Suite .
sumber
C # - 74 byte
Tidak Terkumpul:
Mungkin ada cara untuk mengonversikan ini ke lambda untuk menyimpan lebih banyak lagi, atau sesuatu menggunakan .Aggregate Function. Meskipun saat ini saya tidak memiliki impor, jadi mungkin itu sama?
sumber
> <> , 43 + 3 = 46 byte
Manfaatkan formula yang disajikan dalam jawaban Adnan dan Qwerp-Derp .
Mengharapkan input akan ada di stack, jadi +3 byte untuk
-v
flag.Cobalah online!
sumber