Napisz funkcję, która przyjmuje pojedynczą dodatnią liczbę całkowitą n i zwraca okres dziesiętnej reprezentacji 1 / n .

Przypadki testowe:

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

To jest golf golfowy . Wbudowane biblioteki lub biblioteki zwracające okres bezpośrednio nie są dozwolone. Liczby do co najmniej 100000 powinny działać w rozsądnym czasie (maksymalnie kilka minut).

APL, 19 znaków / bajtów *

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

Nars2000 . Poprzednia wersja była błędna w przypadku niektórych liczb, powinna być poprawna. Sprawdziłem go ręcznie dla wszystkich numerów do 50.

Ponownie, uznanie należy się Benowi Reichowi za pomysł spojrzenia na okres10^i (mod x)

Widok rozstrzelony

{                     ⍳⍵}   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

Przykłady

      {(↑⍳⍨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 może być zapisany we własnym (starszym) jednobajtowym zestawie znaków, który odwzorowuje symbole APL na górne 128 bajtów. Dlatego do celów oceniania program N znaków, który używa tylko znaków ASCII i symboli APL, można uznać za N-bajtowy.}

GolfScript ( 42 27)

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

Czas testu: 5 sekund. Kod porównawczy:

'"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

Podziękowania dla Bena Reicha za podstawową ideę spojrzenia na okres 10^i (mod x).

Wyjaśnienie

Okres pjest definiowany jako najmniejsza dodatnia liczba całkowita taka, że ​​dla wszystkich wystarczająco dużych imamy frac(10^i * 1/x) = frac(10^(i+p) * 1/x). Możemy to nieco uprościć frac(10^i / x) = frac(10^(i+p) / x). Teraz, frac(a / x) = frac(b / x)IFF a == b (mod x), więc szukamy najmniejszej liczby całkowitej dodatniej takie, że dla wszystkich wystarczająco duża i: 10^i == 10^(i+p) (mod x).

Załóżmy 10^i == 10^(i+p) (mod x). Wtedy 10^(i+1) == 10 * 10^i == 10 * 10^(i+p) == 10^(i+p+1) (mod x); więc kiedy otrzymamy powtórzenie, jesteśmy w niezniszczalnym cyklu.

Istnieją tylko xodrębne wartości (mod x), więc zgodnie z zasadą szufladki musimy uzyskać powtórzenie w pierwszych x + 1wartościach 10^i (mod x).

Tak więc powyższy kod oblicza x + 2wartości 10^i (mod x)*. Wtedy na pewno będzie to powtórzenie, a odwracając listę i szukając jej, mogę znaleźć ostatnie wystąpienie. Ponadto, ponieważ wykonuję tylko jedno wyszukiwanie, jest to czas pseudoliniowy.

* Dodatkowym jest załatwienie specjalnego przypadku x = 1, ponieważ nie zmniejszam, 10^0 (mod x)więc szukałbym 0w [1].

Golfscript - 26 bajtów

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

Edycja: zaktualizowane, aby wyświetlało dane wyjściowe, 1jeśli liczba dziesiętna zakończy się, a nie długość reprezentacji dziesiętnej.

Dość wydajna wersja. Wartość 67890 działa w około 10 sekund, a 99991 około 20 sekund. Jest nieco wolniejszy niż wcześniej (mniej więcej o połowę szybciej), ponieważ iterowany zasięg został podwojony, z czego pierwsza połowa jest ignorowana.

Alternatywnie, również 26 bajtów

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

Ten działa poprzez iterowanie ciągu "\n"*(2*i+1), gdzie ijest wartość przekazywana do funkcji. Wartość przekazana w każdym bloku jest numerem porządkowym wartość "\n", która jest 10 .

To )^^jest trochę obejścia. Kiedy odczytujesz znak z ciągu, wynikiem jest wartość porządkowa usuniętego znaku, jak wspomniano powyżej. Jednak ponowne dołączenie tej wartości spowoduje dodanie reprezentacji ciągu tej liczby zamiast znaku - dość niesymetryczne zachowanie, a moim zdaniem wada projektowa. Jeśli tak naprawdę chciałbyś to zrobić, najpierw strajkowanie kosztowałoby tylko jeden bajt.

Dodatkowa kopia wartości końcowej znajduje się już na stosie, więc ponownie )usuwam wartość końcową , xor ją za pomocą łańcucha, a następnie xor ponownie, aby przywrócić wszystkie znaki, które zostały dodane lub usunięte przez pierwszy xor. Gdyby int op stringbył traktowany jako znak, a nie jego ciąg znaków, )^^mógłby zostać zastąpiony przez |.

Zauważ, że chociaż ciągi znaków (które w Golfscript są przechowywane jako tablica liczb całkowitych) będą wyświetlać wartość każdego znaku mod 256 , wartości każdego znaku mogą być poza tym zakresem. Podczas testowania niepowtarzalności (za pomocą operacji ustawiania) lub ograniczania (za pośrednictwem ?) porównywana jest rzeczywista wartość, a nie wartość wyświetlana.

Plik łatki dla bieżącego interpretera Golfscript :

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

Powyższe wpłynie tylko na zachowanie string op int(i odwrotnie), gdzie opjest jedno z
+-|&^. Wszystko inne pozostaje nienaruszone, w tym zachowanie Gint`.

Następujące 24-bajtowe rozwiązanie stałoby się wtedy prawidłowe:

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

To naprawia również wiele innych naprawdę brzydkich obejść .

Python - 48 bajtów

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

Nie jest to najbardziej wydajne rozwiązanie, ale rozsądne w przypadku wartości mniejszych niż 100000 .

FWIW, rdzeń jest identyczny z moim rozwiązaniem generowania liczb cyklicznych w systemie dziesiętnym .

Bardziej wydajna wersja tego samego kodu ( 70 bajtów ):

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

Wartość 99991 zajmuje mniej niż sekundę.

GolfScript, 48 47 46

Dzięki @PeterTaylor za odcięcie dwóch znaków.

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

Próbowałem użyć J, ale ciągle dawało mi to różnego rodzaju dziwne wyniki.

Przetestuj online

To zasadniczo dzieli 2 i 5 z liczby (2 i 5 są pierwszymi czynnikami 10, a ich wzajemności kończą się i upychają algorytm), a następnie najniższa liczba całkowita n taka, że ​​wynikowa liczba dzieli 10 ^ n - 1 wynosi okres.

Perl, 52 znaki

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

Jest to nieskomplikowana implementacja bezpośredniego podejścia. (Na szczęście bezpośrednie podejście jest również dość wydajne: dzięki arytmetyki modulo matematyka nigdy nie musi radzić sobie z liczbą większą niż 10-krotność wartości wejściowej.)

Ponieważ wyzwanie określiło funkcję, czułem się zmuszony (ponownie) zainicjować moje zmienne, czego nie zawracałbym sobie głowy tworzeniem kompletnego programu. Podobnie, ~~w końcowej instrukcji nie jest konieczne, jeśli funkcja może być pewna, że ​​zostanie wywołana w kontekście skalarnym.

Clojure, 102, 117, 115, 106

nieformowane:

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

sformatowany:

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

Czas pracy jest skalowany wraz z okresem. Niemal natychmiastowe na moim komputerze dla przykładowych wartości.

Zasadniczo oblicza to wynik odejmowania po każdym kroku w długim podziale. Cykl jest wykrywany, jeśli w dowolnym momencie liczba ta jest taka sama jak ta, która została obliczona przed nim.

(niekonkurencyjny) Pyth

fq.^;yTQ.^;TQ

Wykorzystuje algorytm żółwia i zająca ( więcej informacji ).

Zobacz, jak przechodzi każdy test.