Tulis fungsi yang mengambil bilangan bulat positif tunggal n dan mengembalikan periode representasi desimal 1 / n .

Kasus uji:

1 -> 1               # 1/1 = 1.0000...... = 1._0
2 -> 1               # 1/2 = 0.5000...... = 0.5_0
3 -> 1               # 1/3 = 0.3333...... = 0._3
7 -> 6               # 1/7 = 0.14285714.. = 0._142857
13 -> 6
14 -> 6
123 -> 5
345 -> 22
654 -> 108
12345 -> 822
67890 -> 120

Ini adalah kode-golf . Built-in atau perpustakaan yang mengembalikan periode secara langsung tidak diizinkan. Jumlah hingga setidaknya 100.000 harus berfungsi dalam waktu yang wajar (paling tidak beberapa menit).

APL, 19 karakter / byte *

{(↑⍳⍨1∘↓)⌽⍵|10x*⍳⍵}

Nars2000 . Versi sebelumnya salah pada beberapa angka, ini seharusnya benar. Saya memeriksanya secara manual pada semua nomor hingga 50.

Sekali lagi, kredit pergi ke Ben Reich untuk gagasan melihat periode10^i (mod x)

Tampilan meledak

{                     ⍳⍵}   generate all naturals up to the argument ⍵
                 10x*       raise 10 to each of them, with unlimited precision
              ⍵|            compute the respective remainders mod ⍵
            ⌽               reverse the list
 (  ⍳⍨    )                 (fork) find the position of the first occurrence
  ↑                         of the fist element of the list
       1∘↓                  in the remainder of the list

Contohnya

      {(↑⍳⍨1∘↓)⌽⍵|10x*⍳⍵}¨1 2 3 7 13 14 123 345 654 12345 67890
1 1 1 6 6 6 5 22 108 822 120

⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
^{*: APL dapat ditulis dalam charset byte tunggal (lama) yang memetakan simbol APL ke nilai 128 byte atas. Oleh karena itu, untuk tujuan penilaian, program karakter N yang hanya menggunakan karakter ASCII dan simbol APL dapat dianggap sebagai panjang N byte.}

GolfScript ( 42 27)

{:x)1\[{.10*x%}*]-1%(?)}:P;

Waktu benchmark: 5 detik. Kode pembandingan:

'"The time is #{Time.now#1
}"'~ puts
[1 2 3 7 13 14 123 345 654 12345 67890 99991]{[P]p}%
'"The time is #{Time.now#2
}"'~ puts

Penghargaan untuk Ben Reich untuk ide inti melihat periode 10^i (mod x).

Penjelasan

Periode pdidefinisikan sebagai bilangan bulat positif terkecil sehingga untuk semua yang cukup besar yang ikita miliki frac(10^i * 1/x) = frac(10^(i+p) * 1/x). Kita bisa menyederhanakannya menjadi sedikit frac(10^i / x) = frac(10^(i+p) / x). Sekarang, frac(a / x) = frac(b / x)jika dan hanya jika a == b (mod x), jadi kami sedang mencari bilangan bulat positif terkecil sehingga untuk semua cukup besar i: 10^i == 10^(i+p) (mod x).

Misalkan 10^i == 10^(i+p) (mod x). Lalu 10^(i+1) == 10 * 10^i == 10 * 10^(i+p) == 10^(i+p+1) (mod x); jadi begitu kita mendapatkan pengulangan, kita berada dalam siklus yang tidak bisa dipecahkan.

Hanya ada xnilai-nilai yang berbeda (mod x), sehingga dengan prinsip mengesampingkan kita harus mendapatkan pengulangan pertama x + 1nilai-nilai 10^i (mod x).

Jadi yang dilakukan oleh kode di atas adalah menghitung x + 2nilai 10^i (mod x)*. Kemudian yang terakhir dijamin akan menjadi pengulangan, dan dengan membalik daftar dan mencarinya, saya dapat menemukan kejadian terbaru. Selain itu, karena saya hanya melakukan pencarian satu kali ini adalah waktu pseudolinear.

* Yang ekstra adalah menangani kasus khusus x = 1, karena saya tidak mengurangi 10^0 (mod x)dan jadi saya akan mencari 0di [1].

Golfscript - 26 byte

{:i.)+.,{;10*i%.}%i>|,}:f;

Sunting: diperbarui ke keluaran 1jika desimal berakhir, daripada panjang representasi desimal.

Versi yang cukup efisien. Nilai 67890 berjalan dalam waktu sekitar 10 detik, dan 99991 sekitar 20 detik. Ini sedikit lebih lambat daripada sebelumnya (kira-kira setengah lebih cepat), karena rentang yang diulang telah dua kali lipat, setengah pertama diabaikan.

Alternatif, juga 26 byte

{:i.)+.n*{*i%.}%i>)^^,}:f;

Yang ini bekerja dengan mengulangi string "\n"*(2*i+1), di mana inilai dilewatkan ke fungsi. Nilai yang diteruskan ke blok setiap kali adalah nilai ordinal "\n", yaitu 10 .

Ini )^^adalah sedikit masalah. Saat Anda membuka karakter dari string, hasilnya adalah nilai ordinal karakter yang dihapus, seperti yang disebutkan di atas. Namun, menambahkan nilai itu kembali akan menambahkan representasi string angka itu, daripada karakter - perilaku yang cukup tidak simetris, dan menurut saya cacat desain. Jika Anda benar-benar ingin melakukan itu, pengerasan terlebih dahulu hanya membutuhkan biaya satu byte.

Salinan tambahan dari nilai akhir sudah ada di tumpukan, jadi saya menghapus nilai akhir lagi ), xor dengan string, dan kemudian xor lagi, sehingga setiap karakter yang ditambahkan atau dihapus oleh xor pertama dikembalikan. Jika int op stringdiperlakukan sebagai karakter, bukan representasi stringnya, )^^bisa diganti dengan |.

Perhatikan bahwa sementara string (yang dalam Golfscript disimpan sebagai array int) akan menampilkan nilai setiap karakter mod 256 , nilai-nilai masing-masing karakter itu sendiri mungkin berada di luar kisaran ini. Saat menguji keunikan (melalui operasi yang ditetapkan) atau isi (melalui ?), itu adalah nilai aktual yang dibandingkan, bukan nilai tampilan.

File tambalan untuk penerjemah Golfscript saat ini :

61c61
<       to_gs
---
>       Gstring.new([self])

Di atas hanya akan mempengaruhi perilaku string op int(dan sebaliknya), di mana opsalah satunya
+-|&^. Segala sesuatu yang lain tetap tidak terpengaruh, termasuk perilaku Gint`.

Solusi 24 byte berikut akan menjadi valid:

{:i.)+.n*{*i%.}%i>|,}:f;

Dan ini juga memperbaiki banyak cara kerja yang benar - benar jelek .

Python - 48 byte

f=lambda n:len(set(10**-~i%n for i in range(n)))

Bukan solusi yang paling efisien, tetapi masuk akal untuk nilai di bawah 100000 .

FWIW, elemen inti identik dengan solusi saya untuk Menghasilkan angka siklik dalam desimal .

Versi kode yang sama ( 70 byte ) yang lebih efisien :

 def f(n):
  a=[];i=10%n
  while i not in a:a+=i,;i=i*10%n
  return len(a)

Nilai 99991 membutuhkan waktu kurang dari satu detik.

GolfScript, 48 47 46

Terima kasih kepada @PeterTaylor karena telah memangkas dua karakter.

{2{1$1$%!{.@\/\d}*}:d~;5d;9{2$%}{10*9+}/+,}:f;

Saya mencoba menggunakan J, tetapi terus memberi saya segala macam hasil yang aneh.

Tes online

Ini pada dasarnya membagi 2 dan 5 dari angka (2 dan 5 adalah faktor utama 10, dan timbal baliknya berakhir, dan mengisi algoritma), maka bilangan bulat terendah n sehingga jumlah yang dihasilkan membagi 10 ^ n - 1 adalah periode.

Perl, 52 karakter

sub f{($p,%r)=1;1until$r{$p=$p*10%$_[0]}++;~~keys%r}

Ini adalah implementasi langsung dari pendekatan yang tidak rumit. (Untungnya pendekatan langsung juga cukup efisien: berkat modulo aritmatika, matematika tidak harus berurusan dengan angka lebih dari 10 kali nilai input.)

Karena tantangan menentukan fungsi, saya merasa harus (menginisialisasi) variabel saya, sesuatu yang saya tidak mau lakukan untuk program yang lengkap. Demikian juga, ~~dalam pernyataan akhir tidak perlu jika fungsi dapat dipastikan akan dipanggil dalam konteks skalar.

Clojure, 102, 117, 115, 106

belum dibentuk:

(defn r([n](r{}(iterate #(mod(* % 10)n)10)0))([a[f & s]i](if(a f)(- i(a f))(recur(assoc a f i)s(inc i)))))

diformat:

(defn r
  ([n] (r {} (iterate #(mod (* % 10) n) 10) 0))
  ([a [f & s] i]
    (if (a f)
      (- i (a f))
      (recur
        (assoc a f i)
        s
        (inc i)))))

Menjalankan skala waktu dengan periode. Hampir seketika di komputer saya untuk nilai sampel.

Pada dasarnya, ini menghitung hasil pengurangan setelah setiap langkah dalam pembagian panjang. Siklus terdeteksi jika pada titik mana pun jumlah itu sama dengan yang telah dihitung sebelumnya.

(Non-bersaing) Pyth

fq.^;yTQ.^;TQ

Menggunakan algoritme penyu dan kelinci ( informasi lebih lanjut ).

Saksikan lulus setiap tes.