11 = (1 + 2 + 3 + 4 + 5) - (1 + 2 + 3) + (6) - (4)

35

Diberikan bilangan bulat positif N , tugas Anda adalah mengembalikan jumlah langkah yang diperlukan oleh algoritma berikut untuk mencapai N :

  1. Cari terkecil segitiga nomor T i sehingga T i  ≥ N . Buat daftar yang sesuai L = [1, 2, ..., i] .

  2. Sementara jumlah persyaratan L lebih besar dari N , hapus istilah pertama dari daftar.

  3. 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 :

Contoh

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!
Arnauld
sumber
Terkait (Saya curiga Anda sudah tahu tentang ini, tetapi hanya mempostingnya untuk anak cucu)
ETHproduksi
Berapa nilai maksimum N yang perlu kita tangani?
Luke
@ Lukas Silakan lihat aturan yang diperbarui.
Arnauld

Jawaban:

4

Jelly , 29 31 byte

ÆDµ’H+Ṛ%1$ÐḟṂ
>TḢ_@Ç}‘Ḥ
R+\ðċȯç

Tautan 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 .

ÆDµ’H+Ṛ%1$ÐḟṂ - Link 1, smallest natural number, M, that satisfies the below*, N
              - * N = T(M) - T(i) for some non-negative integer i <= M
ÆD            - divisors of N
  µ           - monadic chain separation, call that d
   ’          - increment d (vectorises)
    H         - halve (vectorises
      Ṛ       - reverse d
     +        - add (vectorises)
          Ðḟ  - filter discard if:
       %1$    -   modulo one is truthy (those which are the result of even divisors)
            Ṃ - minimum

>TḢ_@Ç}‘Ḥ - Link 2, evaluate result for non-triangular: list of T(1) to T(N), N
>         - T(i) > N
 T        - truthy indexes
  Ḣ       - head (yields the first i for which T(i) > N)
     Ç}   - call last link (1) as a monad converted to a dyad using the right argument
   _@     - subtract with reverse @rguments
       ‘  - increment
        Ḥ - double 

R+\ðċȯç - Main link: N
R       - range -> [1,2,...,N]
 +\     - reduce with addition -> [1,3,6,10,...T(N)]
   ð    - dyadic chain separation, call that t
    ċ   - count occurrences of N in t (1 if N is triangular else 0)
      ç - call last link (2) as a dyad(t, N)
     ȯ  - or

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.

Ṁ‘ṭµS<³µ¿
ḊµS>³µ¿
0®Ḃ‘©¤ĿÐĿL’

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:

ḊµS>³µ¿
Ṁ‘ṭ
Ḥ½_.ĊR®Ḃ‘©¤ĿÐĿS€i
Jonathan Allan
sumber
25

Mathematica, 79 byte

Min[2#/(d=Divisors@#~Cases~_?OddQ)+d]-2⌊(2#)^.5+.5⌋+⌈Sqrt[8#+1]~Mod~1⌉&

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:

  1. f (n) = 1 untuk bilangan segitiga. Ini sepele kasusnya, karena langkah pertama hanya iterates melalui semua angka segitiga. Jika kita menekan dan persis selama proses ini kita selesai dan hanya ada satu langkah untuk menghitung.
  2. Untuk semua angka lainnya, kami selalu berakhir setelah langkah penghapusan, tidak pernah setelah langkah penyisipan. Itu berarti semua f (n) lainnya adalah genap.
  3. Di setiap langkah penyisipan setelah yang pertama, kami hanya menambahkan satu nomor. Jaminan bahwa kita akan mencapai dekomposisi termasuk k setelah kj pasang langkah.
  4. Dekomposisi akhir dari n yang kita peroleh selalu merupakan dekomposisi terpanjang yang mungkin dari n menjadi bilangan bulat berurutan, atau dengan kata lain, itu selalu merupakan dekomposisi dari n dengan maksimum terendah di antara jumlah yang dijumlahkan. Dengan kata lain, angka terakhir yang kita tambahkan ke penjumlahan selalu A212652 (n) .

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:

Min[2#/(d=Divisors@#~Cases~_?OddQ)+d]

Untuk urutan terakhir ( 1, 2, 2, 3, 3, 3, ...), kita dapat menggunakan formulir tertutup sederhana:

⌊(2#)^.5+.5⌋

Dan akhirnya, fungsi indikator terbalik dari angka segitiga adalah 0 setiap kali 8n + 1 adalah kuadrat sempurna. Ini dapat dinyatakan dalam Mathematica as

⌈Sqrt[8#+1]~Mod~1⌉

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):

masukkan deskripsi gambar di sini

Mungkin menarik untuk melihat variasi tentang garis-garis yang sangat lurus itu, tetapi saya akan menyerahkannya kepada orang lain ...

Martin Ender
sumber
Saya akhirnya meluangkan waktu untuk membaca jawaban Anda secara menyeluruh. Ini brilian. Perhatikan bahwa (3) sudah diasumsikan dalam algoritma (langkah # 3 adalah jika , tidak sementara ), tetapi buktinya - tentu saja - disambut dengan baik.
Arnauld
@Arnauld Terima kasih. :) Saya harus mengabaikan / salah mengerti bagian if / while. Untung itu tidak membuat perbedaan kalau begitu.
Martin Ender
7

Mathematica, 72 byte

(For[l=u=c=k=0,k!=#,c++,If[#>k,While[#>k,k+=++u],While[#<k,k-=l++]]];c)&

Fungsi murni mengambil argumen integer.

Bagaimana itu bekerja

For[ ... ]

Satu Forlingkaran.

l=u=c=k=0

Inisialisasi; atur l(bawah), u(atas), c(penghitung), dan k(jumlah) ke 0.

k!=#

Kondisi; repeat sementara ktidak sama dengan input.

c++

Kenaikan; menambah konter c.

If[#>k,For[,#>k,,k+=++u],For[,#<k,,k-=l++]]

Tubuh

If[#>k, ... ]

Jika input lebih besar dari k:

While[#>k,k+=++u]

Sementara input lebih besar dari k, selisih udan selisih koleh u.

Jika input tidak lebih besar dari k:

While[#<k,k-=l++]

Sementara input kurang dari k, penurunan koleh ldan kenaikan l.

( ... ;c)

Kembali csetelah pengulangan.

JungHwan Min
sumber
1
For[,...]ketukan While[...].
Martin Ender
5

Python 2 , 104 byte

N=input();i=s=0;l=()
while N!=sum(l):exec'while sum(l)'+['<N:i+=1;l+=i,','>N:l=l[1:]'][s%2];s+=1
print s

Cobalah online!

Berganti-ganti antara menambahkan istilah ke akhir daftar, dan menghapus istilah dari awal.

mathmandan
sumber
5

Haskell , 70 63 68 64 byte

EDIT:

  • -7 byte: Menghilangkan spasi, dua tanda, dan beberapa tanda kurung dengan meniadakan arti a. Memperbaiki kesalahan satu per satu dalam penjelasan.
  • 5 byte: Argh, benar-benar merindukan itu 65536 persyaratan, dan ternyata (1) kekuatan dari 2 sangat mahal, karena mereka hanya mendapatkan hit ketika Anda mendapatkan ke nomor itu sendiri (2) begitu juga menjumlahkan rentang panjang (yang membungkus di sekitar nol) sepanjang waktu. Mengganti jumlah dengan rumus matematika.
  • -4 byte: Disesuaikan adan blinier untuk mendapatkan syarat dalam rumus penjumlahan untuk dibatalkan.

1#1 adalah fungsi anonim mengambil dan mengembalikan integer.

Gunakan sebagai (1#1) 100.

1#1
(a#b)n|s<-a*a-b*b=sum$[a#(b+2)$n|s>8*n]++[(b#a)(-n)+1|s<8*n]

Cobalah online!

Bagaimana itu bekerja

  • (a#b)nmewakili langkah perhitungan saat ini. a, badalah angka-angka 1, 3, 5, .., sementara nbisa positif atau negatif tergantung pada langkahnya.
    • Ketika pada langkah 1 atau 3, itu mewakili daftar [(a+1)/2,(a+3)/2..(b-1)/2]dan nomor tujuan -n.
    • Ketika pada langkah 2, itu mewakili daftar [(b+1)/2,(b+3)/2..(a-1)/2]dan nomor tujuan n.
  • Korespondensi aneh antara a, bdan daftar adalah untuk dapat melakukan penjumlahan dengan ekspresi pendek s=a*a-b*b.
    • Pada langkah 1 dan 3, ini sama dengan s= -8*sum[(a+1)/2..(b-1)/2].
    • Pada langkah 2, ini sama dengan s=8*sum[(b+1)/2..(a-1)/2].
  • Percabangan dilakukan dengan memiliki daftar pemahaman yang menghasilkan elemen hanya dalam satu kasus masing-masing, dan menjumlahkan hasilnya.
    • Jika s>8*n, maka bbertambah 2 sebelum berulang.
      • Di langkah 1 dan 3, ini menumbuhkan daftar, sementara di langkah 2, ini menyusut itu.
    • Jika s<8*n, maka rekursi mengubah langkah dengan menukar adan b, dan meniadakan n, dan 1 ditambahkan ke hasilnya.
    • Jika s==8*n, maka tidak satu pun dari kedua daftar pemahaman memberikan elemen apa pun, jadi jumlahnya adalah 0.
  • (1#1) nmewakili boneka "tahap 2" sebelum memulai, yang segera diubah ke langkah 1, membangun daftar dari [1..0]=[].
Ørjan Johansen
sumber
4

PHP> = 7.0, 74 Bytes

while($i=$r<=>$argn)for($s++;($r<=>$argn)==$i;)$r+=$i+1?-++$y:++$x;echo$s;

gunakan operator pesawat ruang angkasa

Cobalah online!

Diperluas

while($i=$r<=>$argn) # if input is not equal sum of array
  for($s++;  # raise count steps
  ($r<=>$argn)==$i;)
  # so long as value compare to input has not change to lower/higher to higher/lower or equal  
    $r+=$i+1
      ?-++$y # if $i was higher remove the first integer
      :++$x;} # if $i was lower add the next highest integer     
echo$s; # Output steps
Jörg Hülsermann
sumber
Apa $argn ?
chx
@chx Variabel yang tersedia saat Anda menggunakan PHP dari baris perintah dengan Opsi -R php.net/manual/en/features.commandline.options.php
Jörg Hülsermann
Wow. Saya tidak pernah mendengar -Rlebih sedikit argvatau argi. Saya tahu argc dan argv tentu saja. Sangat menarik, terima kasih.
chx
4

C, 94 91 byte

Coba Online

c;s;m;M;f(n){while(s-n){while(s<n)s+=++M;c++;if(s==n)break;while(s>n)s-=++m;c++;}return c;}
Khaled.K
sumber
Penggunaan luas pada variabel yang tidak diinisialisasi oO
YSC
@YSC dalam C, bilangan bulat yang dinyatakan diinisialisasi secara global disetel ke nol pada waktu kompilasi. baca selengkapnya
Khaled.K
Lupa tentang ini. Terima kasih atas pengingat ini.
YSC
FYI, saya diposting C jawaban lain . Setidaknya salah satu trik yang saya gunakan tidak akan bekerja dengan kompiler lain (yang hilang return), tetapi untuk yang melakukannya, jangan ragu untuk memasukkannya ke dalam jawaban Anda.
hvd
3

JavaScript (ES6), 82 byte

D=(o,a=0,b=1,d=1,c=0)=>a<o?D(o,a+=b,b+1,d,c+(a>=o)):a>o?D(o,a-=d,b,d+1,c+(a<=o)):c

Cuplikan Tes

R. Kap
sumber
Maaf mengatakan ini, tetapi masing-masing ↄ dihitung sebagai 3 byte. Saya kira itu tidak masalah karena ini dapat diganti nama secara sepele.
Ørjan Johansen
@ ØrjanJohansen Terima kasih telah mengingatkan saya. Saya benar-benar harus ingat untuk mencetak kode saya dengan byte daripada panjang. Saya tidak berpikir ada konsensus komunitas tentang "variabel [nama] yang bisa diganti nama" jadi saya mengedit posting. Baiklah.
R. Kap
3
Cuplikan gagal dengan “Terlalu banyak rekursi” di 6553. 6553 bekerja di Node (6.9.1) secara lokal, tetapi 65536 tidak (“Ukuran tumpukan panggilan maksimum terlampaui”).
eush77
3

dc , 61 byte

dsN[ddd9k4*d2*1+dv-0k2/-d1+*2/-d[q]s.0=.-lN-0lN-sNlFx]dsFxz2-

Cobalah online!

Penjelasan

Makro rekursif utama:

ddd9k4*d2*1+dv-0k2/-d1+*2/-d[q]s.0=.-lN-0lN-sNlFx
   9k4*d2*1+dv-0k2/-                              # Compute triangular root
                    d1+*2/                        # Compute triangular number
  d                       -d[q]s.0=.              # Check if sum is exact
 d                                  -lN-          # Compute S-N or S+N
                                        0lN-sN    # Update N := -N
d                                             lFx # Leave the trail and recurse

Makro ini:

  1. Menemukan nomor segitiga minimum yang melebihi angka saat ini di tumpukan (menggunakan yang dimodifikasi rumus akar segitiga yang ).
  2. Cek apakah jumlah segitiga S mewakili angka saat ini dengan tepat. Keluar jika ada.
  3. Lanjutkan ke langkah 1 dengan salah 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.

eush77
sumber
3

Python 3, 150 138 byte

n=int(input())
S=sum
l=[1]
i=s=1
while S(l)<n:i+=1;l+=[i]
while S(l)!=n:
 while S(l)>n:l.pop(0)
 s+=1
 if S(l)<n:i+=1;l+=[i];s+=1
print(s)

Changelog:

  • Berubah tambahkan ke + =, dihapus yang lain (terima kasih musicman523, Loovjo; -12 byte)
L3viathan
sumber
1
Langkah # 2 dapat menghapus satu atau beberapa istilah sekaligus dari daftar (seperti 1, 2 dan 3 pada contoh untuk N = 11) tetapi dihitung sebagai satu langkah dengan cara apa pun.
Arnauld
@Arnauld mengabaikan hal itu; tetap.
L3viathan
1
Bisakah Anda menjelaskan mengapa elseini perlu? Saya percaya elseberjalan setiap saat, karena loop selalu berakhir dengan normal (tanpa break), dan tampaknya berfungsi dengan baik tanpa itu .
musicman523
Anda dapat melewati A=l.appendbagian itu dan menggunakannya l+=[x].
Loovjo
3

Batch, 126 byte

@echo off
set/an=s=l=u=0
:l
if %s% lss %1 set/as+=u+=1,n+=!!l&goto l
if %s% gtr %1 set/as-=l+=1&goto l
cmd/cset/an+n+2-!l

Penjelasan: ladalah nol jika langkah 2 tidak pernah dieksekusi. Ini memungkinkan nuntuk 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 2 n+1kali untuk total n+n+2langkah. Namun jika parameternya adalah angka segitiga maka langkah 2 tidak pernah dijalankan sehingga kita perlu mengurangi satu langkah.

Neil
sumber
3

Python 2, 86 81 byte

n=input()
l=u=i=s=0
while n:k=n>0;i+=k^s;s=k;l+=k;n-=l*k;u+=k^1;n+=u*-~-k
print i

Cobalah online!

Menghitung 65536 test case 0.183spada TIO.


Versi rekursif ini pada 84 byte tidak dapat menghitung semua nilai hingga 65536:

def f(n,l=[0],m=1):k=n>sum(l);return n==sum(l)or f(n,[l[1:],l+[l[-1]+1]][k],k)+(m^k)

Cobalah online!

ovs
sumber
2

Mathematica, 92 byte

(For[q=a=b=0;t={},t~AppendTo~q;q!=#,If[q<#,q+=++b,q-=++a]];Length@Split@Sign@Differences@t)&

Fungsi murni mengambil argumen integer dan mengembalikan integer.

Variabel adan bsingkatan dari angka awal dan akhir (terus berubah) dalam jumlah yang dipertimbangkan, sementara qsingkatan total berjalan (dari angka dari a+1ke b); tmelacak semua nilai yang qditemui sejauh ini. Setelah menginisialisasi variabel-variabel ini, Forloop 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, daftar qnilai yang dijumpai di sepanjang jalan. Misalnya, ketika inputnya 11, Forloop keluar dengan tmenyamakan {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 verbose Length@Split@Sign@Differences@t, tapi saya curiga itu bisa diperbaiki.

Greg Martin
sumber
2

C (tcc), 71 byte (61 + 10)

Argumen baris perintah (termasuk spasi):

-Dw=while

Sumber:

c,m,M,s;f(n){w(++c,s-n){w(c&s<n)s+=++M;w(~c&s>n)s-=m++;}--c;}

Bagaimana itu bekerja:

cmenghitung jumlah langkah. mdan Mmenyimpan batas minimum dan maksimum,s jumlahnya. Awalnya, semuanya nol.

Terus menerus, cmeningkat, dan sdibandingkan dengan n. Selama mereka tidak setara:

  • Jika cganjil, maka selama s<n, tambahkan bilangan bulat ke akhir rentang: meningkat Msatu, dan soleh M.

  • Jika cgenap, maka selama s>n, hapus bilangan bulat dari awal rentang: dikurangi sdengan m, dan tambah msatu.

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.

hvd
sumber
1

Perl 6 , 114 byte

{((0,0,1),->(\a,\b,\c){b,(a..*).first(->\d{(d,b).minmax.sum*c>=$_*c}),-c}...->(\a,\b,\c){(a,b).minmax.sum==$_})-1}

(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

{
  (

    # generate a sequence

    (0,0,1),           # initial value 

    -> (\a,\b,\c) {
      b,               # swap the first two values

      (a..*)
      .first(          # find the first number that brings us to or past the input

        -> \d {
          (d,b).minmax # get a Range object regardless of which is larger
          .sum * c     # sum it, and negate it every other time

          >=           # is it equal to or greater than

          $_ * c       # negate the original input every other time
        }

      ),

      -c               # invert for next round
    }

    ...                # keep doing that until

    -> (\a,\b,\c) {
     (a,b).minmax.sum == $_ # it finally reaches the input
    }

  ) - 1 # count the number of elements in the sequence
        # and subtract one for the initializer
}

Perhatikan bahwa Rakudo memiliki pengoptimalan Range.sumsehingga tidak perlu mengulangi semua nilai.

Brad Gilbert b2gills
sumber