“Konvergensi” yang Harmonis

16

The Alternating Harmonic Series adalah seri konvergen yang terkenal.

1/1 - 1/2 + 1/3 - 1/4 + 1/5 - 1/6 + ...

"Jelas", jelas bahwa ia menyatu dengan log natural 2. Atau apakah itu?

Karena seri ini tidak sepenuhnya konvergen , dengan hanya menata ulang persyaratan, saya dapat membuatnya mendekati apa pun yang saya inginkan. Misalkan saya ingin seri konvergen ke e . Yang harus saya lakukan adalah ini:

1/1 + 1/3 + ... + 1/65 - 1/2 + 1/67 + ... + 1/175 - 1/4

Jika Anda tidak menangkap polanya, tidak ada yang jelas. Begini cara kerjanya:

  1. Pertimbangkan ketentuan deret harmonik bolak-balik dari segi positif dan negatif.
  2. Tambahkan bersama cukup istilah positif untuk melampaui target kami (e). (alias sum > target)
  3. Kurangi istilah negatif berikutnya.
  4. Kembali ke 2.

Perhatikan bahwa pada langkah 2, jika kami sum == target, Anda harus menambahkan istilah positif lain.

Dari sini kita dapat menentukan urutan yang terkait dengan setiap angka sebagai berikut:

  • Ikuti algoritma di atas
  • Untuk setiap istilah positif, output 1.
  • Untuk setiap istilah negatif, hasilkan 0.

Sebut urutan ini sebagai "Pola Bit yang Harmonis" dari sebuah angka. Misalnya, HBP e dimulai sebagai:

1, 1, 1, 1, <32 times>, 0, 1, 1, <54 times>, 0, 1, 1, ...

Tantangan Anda:

Anda akan diberikan:

  • target input rasional dalam kisaran [-10, 10] (catatan: bahkan mencapai 10 melalui seri harmonik membutuhkan jutaan istilah). Ini mungkin desimal (alias 1.1) atau Anda dapat mengambil rasional langsung (alias 12/100)
  • suatu input int n positif , yang menentukan jumlah syarat dari Pola Bit Harmonis untuk output.

Anda diharapkan untuk menghasilkan Pola Bit Harmonis yang tepat dari target ke jumlah syarat yang ditentukan. Anda dapat menampilkan nilai ruang yang dipisahkan, dipisahkan oleh koma, tanpa pemisahan, dll; sepanjang pola 0s dan 1s terlihat jelas dan dibaca dari kiri ke kanan dengan pemisahan yang konsisten.

Uji Kasus

>>> 0, 1
1
>>> 0, 2
10
>>> 0, 7
1000010
>>> 1, 10
1101011011
>>> 1.01, 3
110
>>> 1.01, 24
110101101101101101101101
>>> 2.71, 32
11111111111111111111111111111111
>>> 2.71, 144
111111111111111111111111111111110111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111
>>> -9.8, 100
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Perhatikan bahwa karena -9.8sangat besar, yang pertama 1adalah output di sekitar 149496620istilah th (yang dihitung melalui float, jadi nilainya mungkin tidak tepat).

code-golf sequence Justin
sumber

Jawaban:

3

Perl, 69 byte

use bigrat;$s+=.5/($s>$ARGV[$_=0]?-++$n:++$p-++$_/2),print for 1..pop

Mengambil input sebagai argumen baris perintah.

Penjelasan : bigratmemungkinkan pecahan di mana saja untuk perhitungan yang akurat. $sadalah jumlah istilah saat ini, $ARGV[0]adalah nilai target, pop(sama dengan $ARGV[1]) mewakili jumlah istilah, $pdan $nmewakili jumlah istilah positif dan negatif. $_adalah salah satu 1atau 0tergantung pada apakah istilah positif atau negatif ditambahkan.

svsd
sumber
3

Haskell, 92 91 90 byte

import Data.Ratio
f=(.h 0 1 2).take
h a p q z|a>z=0:h(a-1%q)p(q+2)z|1<2=1:h(a+1%p)(p+2)q z

Contoh penggunaan: f 24 1.01->[1,1,0,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1] .

hmembangun pola bit tak terbatas dengan membawa empat parameter di sekitar: aadalah jumlah saat ini. padalah penyebut dari istilah positif berikutnya, quntuk istilah negatif. zadalah nomor target. fmemulai semuanya dan memotong hasilnya menjadi panjangn .

Sunting: @Zgarb menemukan byte untuk disimpan. Terima kasih!

nimi
sumber
Mendefinisikan h a p qbukannya h p q amenyimpan byte.
Zgarb
Harus dicatat bahwa 7 byte dihabiskan untuk hanya memotong daftar hasil tanpa batas ke salah satu dari panjang n . Sebenarnya akan jauh lebih baik untuk hanya memberikan daftar yang tidak terbatas sebagai hasilnya.
lagi mengaktifkan counterclock
1

Python 3, 128 124 byte

from fractions import*
F=Fraction
*c,s=2,1,0
t=F(input())
for i in'x'*int(input()):w=s<=t;s+=F(w*2-1,c[w]);c[w]+=2;print(+w)

Ini memanfaatkan Fractionkelas Python .

from fractions import* 
F=Fraction
*c,s=2,1,0                # c = [2, 1]. s = 0
                          # c is my positive/negative term counter, s is the sum
t=F(input())              # input a fraction
for i in'x'*int(input()): # Do this for for the chosen number of terms, as per the spec
  w=s<=t;                 # "w" or which one do we choose? Positive or negative?
  s+=F(w*2-1,c[w]);       # w*2-1 gives 1 if w else -1. Gives 1 if we need to add, else -1
  c[w]+=2;                # Increment the coefficient we chose
  print(+w)               # Output that. The +w coerces the bool to an int.
Justin
sumber
1
'x'*int(input())?
FryAmTheEggman