Diberikan bilangan bulat positif N , tugas Anda adalah mengembalikan jumlah langkah yang diperlukan oleh algoritma berikut untuk mencapai N :
Cari terkecil segitiga nomor T i sehingga T i ≥ N . Buat daftar yang sesuai L = [1, 2, ..., i] .
Sementara jumlah persyaratan L lebih besar dari N , hapus istilah pertama dari daftar.
Jika jumlah ketentuan L sekarang kurang dari N , tambahkan i dan tambahkan ke daftar. Lanjutkan dengan langkah # 2.
Kami berhenti segera setelah N tercapai. Hanya langkah pertama yang dilakukan secara sistematis. Langkah # 2 dan # 3 mungkin tidak diproses sama sekali.
Contohnya
Di bawah ini adalah contoh untuk N = 11 :
Jadi output yang diharapkan untuk N = 11 adalah 4 .
Contoh lain:
- N = 5 - Kita mulai dengan T 3 = 1 + 2 + 3 = 6 , diikuti oleh 2 + 3 = 5 . Output yang diharapkan: 2 .
- N = 10 - Hanya langkah pertama yang diperlukan karena 10 adalah angka segitiga: T 4 = 1 + 2 + 3 + 4 = 10 . Output yang diharapkan: 1 .
100 nilai pertama
Di bawah ini adalah hasil untuk 1 ≤ N ≤ 100 :
1, 2, 1, 4, 2, 1, 2, 10, 2, 1, 4, 2, 6, 2, 1, 22, 8, 2, 10, 2,
1, 2, 12, 6, 2, 4, 2, 1, 16, 2, 18, 50, 2, 6, 2, 1, 22, 6, 2, 4,
26, 2, 28, 2, 1, 8, 30, 16, 2, 6, 4, 2, 36, 2, 1, 2, 4, 12, 40, 2,
42, 14, 2,108, 2, 1, 46, 2, 6, 4, 50, 2, 52, 18, 2, 4, 2, 1, 56, 12,
2, 20, 60, 4, 2, 22, 10, 2, 66, 2, 1, 4, 10, 24, 2, 40, 72, 8, 2, 6
Aturan
- Anda dapat menulis program lengkap atau fungsi, yang mencetak atau mengembalikan hasilnya.
- Anda diharuskan memproses N ≤ 65536 dalam waktu kurang dari satu menit pada perangkat keras kelas menengah.
- Dengan waktu yang cukup, program / fungsi Anda secara teoritis harus bekerja untuk nilai N apa pun yang didukung secara asli oleh bahasa Anda. Jika tidak, mohon jelaskan mengapa dalam jawaban Anda.
- Ini adalah kode golf, jadi jawaban tersingkat dalam byte menang!
code-golf
math
integer-partitions
Arnauld
sumber
sumber
Jawaban:
Jelly ,
2931 byteTautan monadik yang mengembalikan hasilnya (N = 65536 membutuhkan waktu kurang dari dua detik).
Cobalah online!
Bagaimana?
Untuk penjelasan menyeluruh tentang algoritma, lihat posting fantastis oleh Martin Ender .
Implementasi program penuh 29 byte yang saya buat dari algoritma yang dijelaskan membutuhkan waktu 4 menit 30 untuk N = 65536 di laptop saya, jadi saya kira itu tidak masuk hitungan.
Menggunakan loop sementara untuk setiap langkah 3 dan menggunakannya kembali sebagai langkah 1 sama panjangnya dengan apa yang dapat saya kelola dengan menginisialisasi daftar karena tidak ada tanda centang pada langkah 3 berarti membuat daftar sampai tidak ada yang tersisa dan kemudian menemukan indeks pertama dari nilai:
sumber
Mathematica, 79 byte
Penjelasan
Saya tidak bisa diganggu untuk mengimplementasikan algoritma dalam tantangan, jadi saya ingin mencari jalan pintas ke solusinya. Walaupun saya menemukan satu, sayangnya itu tidak mengalahkan jawaban Mathematica yang mengimplementasikan algoritma. Yang mengatakan, saya yakin ini belum golf secara optimal, dan mungkin ada bahasa lain yang bisa mendapat manfaat dari pendekatan ini atau beberapa wawasan yang diperoleh dalam proses.
Jadi saya mengklaim bahwa urutan yang seharusnya kita hitung adalah:
f (n) = 2 * ( A212652 (n) - A002024 (n)) + 1 + A023532 (n-1)
Atau, itu f (n) = 1 jika n adalah bilangan segitiga dan f (n) = 2 * ( A212652 (n) - A002024 (n) + 1) sebaliknya.
Dalam ekspresi pertama, A023532 hanya menyandikan dua kasus yang berbeda ini. Dua urutan lainnya (plus 1) adalah perbedaan antara bilangan bulat terbesar k dalam dekomposisi terpanjang n menjadi bilangan bulat berurutan (k-i + 1) + (k-i + 2) + ... + k = n dan terbesar bilangan bulat j sehingga 1 + 2 + ... + j <n .
Dengan kata agak sederhana, di sini adalah bagaimana kita menemukan jawaban untuk nomor non-segitiga: pertama, menemukan terbesar nomor segitiga T j yang kurang dari n . Kemudian j adalah bilangan bulat kedua dari belakang yang ditambahkan selama langkah 1 (karena setelah menambahkan j + 1 kita akan melebihi n ). Kemudian dekomposisi n menjadi sebanyak (atau sekecil) bilangan bulat berturut-turut sebanyak mungkin dan panggil maksimum di antara angka-angka ini k . Hasilnya hanya 2 * (kj) . Alasan intuitif untuk ini adalah bahwa maksimum dalam dekomposisi bertambah 1 setiap langkah lainnya dan kita berhenti ketika kita mencapaik .
Kita perlu menunjukkan empat hal untuk membuktikan bahwa ini berhasil:
Kami telah menunjukkan mengapa (1) itu benar. Selanjutnya, kami membuktikan bahwa kami tidak dapat mengakhiri langkah penyisipan kecuali langkah awal (yang tidak terjadi untuk angka non-segitiga).
Misalkan kita berakhir pada langkah penyisipan, mencapai n setelah menambahkan nilai p ke jumlah. Itu berarti bahwa sebelum langkah penyisipan ini, nilainya adalah np ( atau kurang jika kami menambahkan beberapa nilai sekaligus). Tetapi langkah penyisipan ini didahului oleh langkah penghapusan (karena kami tidak bisa menekan n selama langkah 1). Nilai terakhir q yang kami hapus selama langkah penghapusan ini tentu kurang dari p karena cara kerja algoritma. Tetapi itu berarti sebelum kita menghapus q kita memiliki n-p + q ( atau kurang ) yang kurang dari n. Tapi itu kontradiksi, karena kita harus berhenti menghapus bilangan bulat ketika kita menekan n-p + q alih-alih menghapus q lain . Ini membuktikan poin (2) di atas. Jadi sekarang kita tahu bahwa kita selalu berakhir pada langkah penghapusan dan karena itu semua angka non-segitiga memiliki output yang sama.
Selanjutnya kita buktikan (3), bahwa setiap langkah penyisipan hanya dapat memasukkan satu nilai. Ini pada dasarnya adalah akibat wajar dari (2). Kami telah menunjukkan bahwa setelah menambahkan satu nilai, kami tidak dapat menekan n dengan tepat dan karena buktinya menggunakan ketidaksetaraan, kami juga tidak bisa berakhir di bawah n (sejak itu n-p + q masih akan lebih kecil dari n dan kami tidak seharusnya menghapus yang banyak nilai di tempat pertama). Jadi, setiap kali kita menambahkan nilai tunggal, kami dijamin melebihi n karena kami pergi di bawah n dengan menghapus nilai yang lebih kecil. Karenanya, kita tahu bahwa ujung atas dari jumlah itu bertambah 1 setiap langkah lainnya. Kita tahu nilai awal dari ujung atas ini (itu terkecil m sehinggaT m > n ). Sekarang kita hanya perlu mencari tahu ujung atas ini setelah kita mencapai jumlah akhir. Maka jumlah langkah hanyalah dua kali perbedaan (ditambah 1).
Untuk melakukan ini, kami membuktikan (4), bahwa jumlah akhir selalu merupakan dekomposisi dari n menjadi sebanyak mungkin bilangan bulat, atau dekomposisi di mana maksimum dalam dekomposisi itu minimal (yaitu dekomposisi paling awal yang mungkin). Kami akan lagi melakukan ini dengan kontradiksi (kata-kata di bagian ini bisa sedikit lebih keras, tapi saya sudah menghabiskan terlalu banyak waktu untuk ini ...)
Katakanlah dekomposisi paling awal / terpanjang dari n adalah beberapa a + (a + 1) + ... (b-1) + b , a ≤ b , dan katakanlah algoritma melewatkannya. Itu berarti pada saat b ditambahkan, a tidak boleh lagi menjadi bagian dari jumlah. Jika a adalah bagian dari jumlah s , maka kita akan memiliki n ≤ s pada saat itu. Jadi, penjumlahan hanya berisi nilai dari a ke b , yang sama dengan n dan kami berhenti (maka kami tidak melewatkan dekomposisi ini), atau setidaknya ada satu nilai kurang dari a dalam jumlah, menangkan kasus n <sdan nilai itu akan dihapus sampai kami mencapai jumlah yang tepat (sekali lagi, dekomposisi tidak dilewati). Jadi kita harus menyingkirkan sebuah sebelum menambahkan b . Tetapi itu berarti kita harus mencapai situasi di mana a adalah komponen terkecil dari jumlah, dan yang terbesar belum b . Namun, pada saat itu kami tidak dapat menghapus a , karena jumlahnya jelas kurang dari n (karena b tidak ada), jadi kami diharuskan untuk menambahkan nilai terlebih dahulu hingga kami menambahkan b dan menekan n dengan tepat. Ini membuktikan (4).
Jadi, kumpulkan semuanya ini: kita tahu bahwa pasangan langkah pertama memberi kita nilai maksimum A002024 (n) . Kita tahu bahwa nilai maksimum dekomposisi akhir adalah A212652 (n) . Dan kita tahu bahwa maksimum ini bertambah satu kali dalam setiap pasang langkah. Oleh karena itu, ekspresi terakhir adalah 2 * ( A212652 (n) - A002024 (n) + 1) . Rumus ini hampir berfungsi untuk bilangan segitiga, kecuali untuk itu kita hanya perlu 1 langkah alih-alih 2, itulah sebabnya kita mengoreksi hasilnya dengan fungsi indikator bilangan segitiga (atau kebalikannya, mana yang lebih nyaman).
Akhirnya, untuk implementasi. Untuk urutan sebelumnya, saya menggunakan rumus MIN (odd d | n; n / d + (d-1) / 2) dari OEIS. Ternyata untuk menghemat beberapa byte jika kita mengambil faktor 2 ke dalam ekspresi ini untuk mendapatkan MIN (odd d | n; 2n / d + d-1) , karena -1 kemudian dibatalkan dengan +1 di versi pertama saya dari f (n) yang secara langsung mengkodekan dua case untuk bilangan triangular dan non-triangular. Dalam kode, ini adalah:
Untuk urutan terakhir (
1, 2, 2, 3, 3, 3, ...
), kita dapat menggunakan formulir tertutup sederhana:Dan akhirnya, fungsi indikator terbalik dari angka segitiga adalah 0 setiap kali 8n + 1 adalah kuadrat sempurna. Ini dapat dinyatakan dalam Mathematica as
Ada banyak cara untuk mengekspresikan dua urutan terakhir ini dan untuk menggeser beberapa offset konstan di antara mereka, jadi saya yakin ini belum merupakan implementasi yang optimal, tetapi saya berharap ini dapat memberi orang lain titik awal untuk melihat ke dalam pendekatan baru di bahasa mereka sendiri.
Karena saya mengalami semua masalah ini, berikut adalah plot urutannya hingga n = 1000 (saya juga bisa menghitung 100k dalam beberapa detik, tetapi tidak benar-benar menunjukkan wawasan tambahan):
Mungkin menarik untuk melihat variasi tentang garis-garis yang sangat lurus itu, tetapi saya akan menyerahkannya kepada orang lain ...
sumber
Mathematica, 72 byte
Fungsi murni mengambil argumen integer.
Bagaimana itu bekerja
Satu
For
lingkaran.Inisialisasi; atur
l
(bawah),u
(atas),c
(penghitung), dank
(jumlah) ke 0.Kondisi; repeat sementara
k
tidak sama dengan input.Kenaikan; menambah konter
c
.Tubuh
Jika input lebih besar dari
k
:Sementara input lebih besar dari
k
, selisihu
dan selisihk
olehu
.Jika input tidak lebih besar dari
k
:Sementara input kurang dari
k
, penurunank
olehl
dan kenaikanl
.Kembali
c
setelah pengulangan.sumber
For[,...]
ketukanWhile[...]
.Python 2 , 104 byte
Cobalah online!
Berganti-ganti antara menambahkan istilah ke akhir daftar, dan menghapus istilah dari awal.
sumber
Haskell ,
70 63 6864 byteEDIT:
a
. Memperbaiki kesalahan satu per satu dalam penjelasan.a
danb
linier untuk mendapatkan syarat dalam rumus penjumlahan untuk dibatalkan.1#1
adalah fungsi anonim mengambil dan mengembalikan integer.Gunakan sebagai
(1#1) 100
.Cobalah online!
Bagaimana itu bekerja
(a#b)n
mewakili langkah perhitungan saat ini.a, b
adalah angka-angka1, 3, 5, ..
, sementaran
bisa positif atau negatif tergantung pada langkahnya.[(a+1)/2,(a+3)/2..(b-1)/2]
dan nomor tujuan-n
.[(b+1)/2,(b+3)/2..(a-1)/2]
dan nomor tujuann
.a, b
dan daftar adalah untuk dapat melakukan penjumlahan dengan ekspresi pendeks=a*a-b*b
.s= -8*sum[(a+1)/2..(b-1)/2]
.s=8*sum[(b+1)/2..(a-1)/2]
.s>8*n
, makab
bertambah 2 sebelum berulang.s<8*n
, maka rekursi mengubah langkah dengan menukara
danb
, dan meniadakann
, dan 1 ditambahkan ke hasilnya.s==8*n
, maka tidak satu pun dari kedua daftar pemahaman memberikan elemen apa pun, jadi jumlahnya adalah0
.(1#1) n
mewakili boneka "tahap 2" sebelum memulai, yang segera diubah ke langkah 1, membangun daftar dari[1..0]=[]
.sumber
PHP> = 7.0, 74 Bytes
gunakan operator pesawat ruang angkasa
Cobalah online!
Diperluas
sumber
$argn
?-R
lebih sedikitargv
atauargi
. Saya tahu argc dan argv tentu saja. Sangat menarik, terima kasih.C,
9491 byteCoba Online
sumber
return
), tetapi untuk yang melakukannya, jangan ragu untuk memasukkannya ke dalam jawaban Anda.JavaScript (ES6), 82 byte
Cuplikan Tes
Tampilkan cuplikan kode
sumber
dc , 61 byte
Cobalah online!
Penjelasan
Makro rekursif utama:
Makro ini:
S
mewakili angka saat ini dengan tepat. Keluar jika ada.S+N
(perkiraan berlebihan) atauS-N
(kurang perkiraan), pilihan berganti-ganti antara iterasi.Ketika keluar, jejak yang tersisa di tumpukan memberi tahu program utama berapa banyak iterasi yang dibutuhkan.
sumber
Python 3,
150138 byteChangelog:
sumber
else
ini perlu? Saya percayaelse
berjalan setiap saat, karena loop selalu berakhir dengan normal (tanpabreak
), dan tampaknya berfungsi dengan baik tanpa itu .A=l.append
bagian itu dan menggunakannyal+=[x]
.Batch, 126 byte
Penjelasan:
l
adalah nol jika langkah 2 tidak pernah dieksekusi. Ini memungkinkann
untuk melacak jumlah iterasi dari langkah 3. Karena algoritma tidak pernah berhenti pada langkah 3, oleh karena itu ia harus menjalankan langkah 1 sekali dan langkah 2n+1
kali untuk totaln+n+2
langkah. Namun jika parameternya adalah angka segitiga maka langkah 2 tidak pernah dijalankan sehingga kita perlu mengurangi satu langkah.sumber
Python 2,
8681 byteCobalah online!
Menghitung 65536 test case
0.183s
pada TIO.Versi rekursif ini pada 84 byte tidak dapat menghitung semua nilai hingga 65536:
Cobalah online!
sumber
Mathematica, 92 byte
Fungsi murni mengambil argumen integer dan mengembalikan integer.
Variabel
a
danb
singkatan dari angka awal dan akhir (terus berubah) dalam jumlah yang dipertimbangkan, sementaraq
singkatan total berjalan (dari angka daria+1
keb
);t
melacak semua nilai yangq
ditemui sejauh ini. Setelah menginisialisasi variabel-variabel ini,For
loop terus dijalankanIf[q<#,q+=++b,q-=++a]
, yang baik menambah nomor baru ke akhir atau mengurangi angka di depan seperti yang ditentukan oleh spesifikasi, sampaiq
sama dengan input.Sekarang kita hanya perlu mengekstrak jumlah langkah dari
t
, daftarq
nilai yang dijumpai di sepanjang jalan. Misalnya, ketika inputnya11
,For
loop keluar dengant
menyamakan{0,1,3,6,10,15,14,12,9,15,11}
. Cara terbaik yang saya temukan untuk menghitung jumlah langkah dari ini adalah menghitung berapa kali perbedaannya beralih dari naik ke turun; itulah yang dilakukan perintah verboseLength@Split@Sign@Differences@t
, tapi saya curiga itu bisa diperbaiki.sumber
C (tcc), 71 byte (61 + 10)
Argumen baris perintah (termasuk spasi):
Sumber:
Bagaimana itu bekerja:
c
menghitung jumlah langkah.m
danM
menyimpan batas minimum dan maksimum,s
jumlahnya. Awalnya, semuanya nol.Terus menerus,
c
meningkat, dans
dibandingkan dengann
. Selama mereka tidak setara:Jika
c
ganjil, maka selamas<n
, tambahkan bilangan bulat ke akhir rentang: meningkatM
satu, dans
olehM
.Jika
c
genap, maka selamas>n
, hapus bilangan bulat dari awal rentang: dikurangis
denganm
, dan tambahm
satu.Saat loop keluar,
c
telah meningkat satu kali terlalu banyak. Mengurangkannya menghasilkan hasil yang benar, dan kebetulan dihitung dalam register yang benar untuk bertindak sebagai nilai balik.Secara kebetulan terjadi untuk menggunakan nama variabel yang sama persis seperti jawaban C Khaled.K . Mereka tidak disalin.
sumber
Perl 6 , 114 byte
(Terinspirasi oleh implementasi Haskell sebelumnya )
Cobalah ini
berjalan dengan input 65536 dalam waktu kurang dari 45 detik di komputer saya, tetapi saya tidak dapat menjalankannya dalam waktu kurang dari 60 detik dengan TIO.run.
Saya memiliki Rakudo v2017.04 +, di mana ia memiliki v2017.01 .
Rakudo / NQP / MoarVM mendapatkan optimisasi hampir setiap hari, sehingga mungkin ada sejumlah dari mereka yang sementara dibutuhkan untuk mendapatkannya dalam waktu singkat.
Diperluas
Perhatikan bahwa Rakudo memiliki pengoptimalan
Range.sum
sehingga tidak perlu mengulangi semua nilai.sumber