Tugas
Diberikan bilangan bulat positif masukan n
(dari 1 hingga batas bahasa Anda, secara inklusif), kembalikan atau hasilkan jumlah maksimum bilangan bulat positif berbeda yang dijumlahkan n
.
Uji Kasus
Mari f
tentukan fungsi yang valid sesuai dengan tugas:
Urutan untuk f
, mulai dari 1:
1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, ...
Sebagai test case yang lebih besar:
>>> f(1000000000) // Might not be feasible with brute-forcers
44720
Kode Uji
Untuk setiap kasus uji yang tidak diberikan secara eksplisit, output kode Anda harus cocok dengan hasil dari yang berikut:
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
System.out.println((int) Math.floor(Math.sqrt(2*x + 1./4) - 1./2));
}
}
code-golf
math
number-theory
integer
integer-partitions
Addison Crump
sumber
sumber
Jawaban:
05AB1E , 4 byte
Cobalah online!
Alat yang sempurna untuk pekerjaan itu.
ÅT
menghasilkan daftar nomor Å ll T riangular hingga dan termasuk N (sayangnya termasuk 0 juga, jika tidak akan menjadi 3 byte),g<
dapatkan len g th dan kurangi.sumber
Jelly ,
65 byteCobalah online!
Agak efisien. Urutan ini bertambah pada angka segitiga, jadi ini hanya menghitung berapa banyak angka segitiga lebih kecil dari n .
Penjelasan:
sumber
Haskell , 26 byte
-2 byte terima kasih kepada H.PWiz.
Cobalah online!
Ini mengembalikan elemen ke - n dari seluruh bilangan di mana masing-masing i direplikasi i + 1 kali.
sumber
succ
singkatansuccessor
.Brain-Flak , 36 byte
Cobalah online!
Ini menggunakan struktur yang sama dengan algoritma pembagian standar, kecuali bahwa "pembagi" bertambah setiap kali dibaca.
sumber
Pari / GP , 19 byte
Cobalah online!
sumber
Brain-Flak , 82 byte
Whitespace ditambahkan untuk "Keterbacaan"
Cobalah online!
sumber
Jelly , 7 byte
Cobalah online!
Jelly , 9 byte
Cobalah online!
Ini lebih lama dari
Dennisdan DJ, tapi kali ini sengaja . Sangat, sangat efisien .sumber
M
.R , 28 byte
Cobalah online!
Menciptakan vektor
1
berulang2
kali,2
berulang3
kali, ...,n
berulangn+1
kali dan mengambilnth
elemen. Ini akan kesalahan memori karena1:n
terlalu besar atau karena daftar yang diulang dengann*(n+1)/2 - 1
elemen terlalu besar.R , 29 byte
Cobalah online!
Menghitung nilai secara langsung, menggunakan rumus yang ditemukan dalam jawaban alephalpha . Ini harus dijalankan tanpa masalah, selain dari ketepatan angka mungkin
R , 30 byte
Cobalah online!
Menghitung angka segitiga kurang dari atau sama dengan
n
. Ini mungkin kesalahan memori jika1:n
cukup besar - misalnya, saat1e9
melemparError: cannot allocate vector of size 3.7 Gb
.sumber
APL (Dyalog) , 8 byte
Cobalah online!
sumber
TI-Basic, 12 byte
sumber
JavaScript (Node.js) , 18 byte
Cobalah online!
sumber
floor((sqrt(8x+4)-1)/2)
(rumus Anda) danfloor((sqrt(8x+1)-1)/2)
(rumus yang benar) memberikan hasil yang sama untuk setiapx
.Japt , 8 byte
Solusi formula tertutup.
Cobalah
Penjelasan
Kalikan dengan 8, tambahkan 1 (
Ä
), dapatkan akar kuadrat (¬
), kurangi 1 (É
) dan bagilah hasilnya dengan 2 (z
).Alternatif, 8 byte
Pelabuhan solusi Jelly DJMcMayhem .
Cobalah
Hasilkan array bilangan bulat (
õ
) dari 1 ke input, secara kumulatif mengurangi (å
) dengan menambahkan (+
) dan menghitung (è
) elemen yang kurang dari atau sama dengan (§
) input (U
).sumber
Befunge,
3220 byteCobalah online!
sumber
Brain-Flak ,
705648 byteCobalah online!
Penjelasan
Bagian utama dari ini adalah cuplikan berikut yang saya tulis:
Ini tidak akan melakukan apa-apa jika KL positif dan akan beralih tumpukan. Hal ini yang super tumpukan haram tetapi bekerja. Sekarang bagian utama dari program mengurangi jumlah yang semakin besar dari input sampai inputnya tidak positif. Kami memulai akumulator pada 1 setiap kali mengurangi 1 lebih dari akumulator dari input.
Kita bisa memasukkannya di dalam cuplikan di atas
Itu dimasukkan ke dalam loop sehingga dijalankan sampai kita berganti tumpukan. Setelah loop selesai, kami mengambil akumulator dengan menukar tumpukan dan menghapus sampah.
sumber
Pyth , 7 byte
Cobalah online!
Filter-menjaga partisi integer yang
I
berbeda atas deduplikasi, ambilh
ead dan dapatkanl
ength.Bukti validitas
Tidak terlalu ketat dan tidak beralasan.
Mari A = a 1 + a 2 + ... + a n dan B = b 1 + b 2 + ... + b m menjadi dua partisi yang berbeda dari integer yang sama N . Kami akan menganggap bahwa A adalah partisi unik terpanjang . Setelah kami menghapus duplikat B , yaitu, menggantikan beberapa kejadian integer yang sama dengan hanya satu dari mereka, kita tahu bahwa jumlah B kurang dari N . Tetapi kita juga tahu bahwa hasil fungsi meningkat (tidak ketat), sehingga kita dapat menyimpulkan bahwa partisi unik terpanjang A selalu memiliki setidaknya jumlah elemen yang sama dengan jumlah item unik di partisi lain.
sumber
Triangularity , 49 byte
Cobalah online!
Bagaimana itu bekerja
Triangularity memerlukan kode untuk memiliki distribusi titik-titik. Artinya, panjang setiap baris harus sama dengan jumlah baris dikalikan 2 dan dikurangi, dan setiap baris harus memiliki (di setiap sisi) sejumlah titik yang sama dengan posisinya dalam program (baris bawah adalah baris 0, yang di atasnya adalah baris 1 dan seterusnya). Hanya ada beberapa perintah, dan karakter apa pun selain yang terdaftar di halaman 'Wiki / Perintah' diperlakukan sebagai no-op (titik-titik asing tidak mempengaruhi program dengan cara apa pun, selama bentuk keseluruhan program tetap persegi panjang).
Perhatikan bahwa untuk perintah dua argumen, saya telah menggunakan a dan b di seluruh penjelasan. Ingatlah itu, mari kita lihat apa yang sebenarnya dilakukan program, setelah menghapus semua karakter asing yang membentuk padding:
Solusi alternatif, dan lebih pendek jika padding tidak diperlukan:
Cobalah online!
sumber
PowerShell 3.0, 45 byte
Panggilan matematika itu menyakitkan dan pembulatan bankir PS adalah iblis yang sebenarnya (karenanya perlu regex untuk memotong untuk menyimpan byte) tetapi ini tampaknya cukup baik-baik saja.
sumber
Java (JDK) , 28 byte
Cobalah online!
Karena contohnya benar-benar tidak golf dengan baik: p
Kredit
sumber
Jelly , 7 byte
Berjalan kira-kira masuk O (2 n ) .
Cobalah online!
Bagaimana itu bekerja
sumber
JavaScript (ES7),
2219 byte-3 byte terima kasih untuk ETHproductions.
Cobalah
Penjelasan
Lipat gandakan input dengan 8 dan tambahkan 1, naikkan ke pangkat .5, beri kami akar kuadrat, kurangi 1 dan bithift hasilnya tepat dengan 1.
sumber
n=>(8*n+1)**.5-1>>1
menyimpan 3 byte? (belum diuji)Python 2/3, 32 byte
Implementasi python dari formula form tertutup
//2
Putaran bilangan bulat mengarah ke nol, jadi tidakfloor( )
diperlukansumber
from math import sqrt
bekerja? Jika demikian, itu harus dimasukkan dalam bytecount. (Dalam hallambda n:int((math.sqrt(1+8*n)-1)//2) import math
ini sedikit lebih pendek. )Haskell , 28 byte
Agak membosankan, tetapi ini
cukup pendek daripada solusi Haskell lainnya danmemiliki ekspresi pointfree yang sangat bagus. Sayangnya saya tidak bisa mendapatkannya lebih pendek tanpa sistem jenis menghalangi:Cobalah online!
Pointfree, 33 byte
Atau, 33 byte
Panjangnya sama dengan versi pointfree, tetapi jauh lebih menarik.
sumber
Bimasakti , 12 byte
Penjelasan
sumber
Pyt ,
75 bytePenjelasan:
Lebih cepat, tapi jauh
Pyt ,
119 bytePenjelasan:
Cara alternatif - port jawaban Shaggy
Pyt ,
87 bytesumber
J , 11 byte
Cobalah online!
sumber
*
menghasilkan 1Ruang putih , 111 byte
Huruf
S
(spasi),T
(tab), danN
(baris baru) ditambahkan hanya sebagai penyorotan.[..._some_action]
ditambahkan sebagai penjelasan saja.Cobalah online (dengan spasi, tab, dan hanya baris baru).
Penjelasan dalam pseudo-code:
Gunakan rumus:
CATATAN: Ruang kosong tidak memiliki built-root kuadrat, jadi kita harus melakukan ini secara manual.
sumber
Vitsy , 16 byte
Cobalah online!
Mungkin juga menambah kontribusi saya sendiri ke dalam campuran. Ini lebih pendek daripada solusi iterasi partisi di Vitsy.
sumber
Oasis , 14 byte
Cobalah online!
Bagaimana?
Ini adalah solusi rekursif yang meningkatkan hasil ketika bertemu indeks segitiga, dimulai dengan 0 untuk input 0.
sumber
Perl 5
-p
, 19 (++) byteCobalah online!
sumber
Rubi , 27 byte
Tiga untuk harga satu. Saya kecewa karena saya tidak bisa lebih pendek.
Cobalah online! (untuk memilih fungsi, tambahkan f = di depannya)
sumber