Напишите функцию, которая принимает одно положительное целое число n и возвращает период десятичного представления 1 / n .

Тестовые случаи:

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

Это код-гольф . Встроенные модули или библиотеки, которые возвращают период напрямую, не допускаются. Числа до 100000 должны работать в течение разумного времени (не более нескольких минут).

APL, 19 символов / байт *

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

Нарс2000 . Предыдущая версия была неправильной на некоторых числах, это должно быть правильно. Я проверял это вручную на всех номерах до 50.

Опять же, кредит идет к Бен Рейху за идею взглянуть на период10^i (mod x)

В разобранном виде

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

Примеры

      {(↑⍳⍨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 может быть записан в своей собственной (устаревшей) однобайтовой кодировке, которая отображает символы APL в верхние 128-байтовые значения. Следовательно, для целей оценки программа из N символов, в которой используются только символы ASCII и символы APL, может рассматриваться как длина N байтов.}

GolfScript ( 42 27)

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

Время теста: 5 секунд. Код бенчмаркинга:

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

Благодарим Бен Райха за основную идею взглянуть на период 10^i (mod x).

объяснение

Период pопределяется как наименьшее положительное целое число такое, что для всех достаточно больших iу нас есть frac(10^i * 1/x) = frac(10^(i+p) * 1/x). Мы можем немного упростить это до frac(10^i / x) = frac(10^(i+p) / x). Теперь, frac(a / x) = frac(b / x)тогда и только тогда a == b (mod x), поэтому мы ищем наименьшее натуральное число такое , что для всех достаточно больших i: 10^i == 10^(i+p) (mod x).

Пусть 10^i == 10^(i+p) (mod x). Тогда 10^(i+1) == 10 * 10^i == 10 * 10^(i+p) == 10^(i+p+1) (mod x); поэтому, когда мы получаем повторение, мы находимся в неразрывном цикле.

Существуют только xразличные значения (mod x), поэтому по принципу «голубиных отверстий» мы должны получить повторение первых x + 1значений 10^i (mod x).

Так что код выше, это вычислить x + 2значения 10^i (mod x)*. Тогда последний гарантированно будет повторением, и, переворачивая список и ища его, я могу найти самое последнее вхождение. Более того, потому что я делаю только один поиск, это псевдолинейное время.

* Дополнительный один должен обрабатывать особый случай x = 1, потому что я не уменьшаю , 10^0 (mod x)и поэтому я бы ищу 0дюйм [1].

Golfscript - 26 байт

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

Редактировать: обновляется для вывода, 1если заканчивается десятичное число, а не длина десятичного представления.

Довольно эффективная версия. Значение 67890 выполняется примерно за 10 секунд, а 99991 - около 20 секунд. Это немного медленнее, чем было раньше (примерно вдвое быстрее), потому что диапазон, который повторяется, был удвоен, первая половина которого игнорируется.

Альтернатива, также 26 байтов

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

Это работает путем перебора строки "\n"*(2*i+1), где iнаходится значение, переданное функции. Значение, передаваемое в блок каждый раз, является порядковым значением "\n", равным 10 .

Это )^^немного обходной путь. Когда вы отключаете символ от строки, результатом является порядковый номер удаленного символа, как упомянуто выше. Однако добавление этого значения обратно добавит строковое представление этого числа, а не символа - довольно несимметричное поведение и, на мой взгляд, недостаток дизайна. Если вы на самом деле хотите это сделать, строковое преобразование будет стоить всего один байт.

Дополнительная копия окончательного значения уже находится в стеке, поэтому я снова )удаляю окончательное значение , записываю его в строку и затем снова записываю в него, так что все символы, которые были добавлены или удалены первым xor, будут восстановлены. Если бы int op stringобрабатывались как символ, а не его строковое представление, )^^можно было бы заменить на |.

Обратите внимание, что хотя строки (которые в Golfscript хранятся в виде массива целых чисел) будут отображать значение каждого символа мод 256 , сами значения каждого символа могут выходить за пределы этого диапазона. При проверке уникальности (через операции набора) или автономности (через ?) сравнивается фактическое значение, а не отображаемое значение.

Файл патча для текущего интерпретатора Golfscript :

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

Вышеуказанное повлияет только на поведение string op int(и наоборот), где opодин из
+-|&^. Все остальное остается неизменным, включая поведение Gint`.

Следующее 24-байтовое решение станет действительным:

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

И это также исправляет много других действительно уродливых обходных путей .

Python - 48 байт

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

Не самое эффективное решение, но разумное для значений менее 100000 .

FWIW, основной элемент идентичен моему решению для Генерации циклических чисел в десятичном виде .

Более эффективная версия того же кода ( 70 байт ):

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

Значение 99991 занимает меньше секунды.

GolfScript, 48 47 46

Спасибо @PeterTaylor за то, что отрубили два символа.

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

Я пытался использовать J, но это продолжало давать мне всевозможные странные результаты.

Тест онлайн

Это в основном делит 2 и 5 из числа (2 и 5 - простые множители 10, и их взаимные значения заканчиваются, и заполняют алгоритм), тогда самое низкое целое число n такое, что результирующее число делит 10 ^ n - 1: Период.

Perl, 52 символа

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

Это несложная реализация прямого подхода. (К счастью, прямой подход также довольно эффективен: благодаря арифметике по модулю математике никогда не приходится иметь дело с числом, более чем в 10 раз превышающим входное значение.)

Так как в задании была указана функция, я был вынужден (повторно) инициализировать мои переменные, что я бы не стал делать для полной программы. Аналогично, ~~в заключительном утверждении нет необходимости, если функция может быть уверена, что она будет вызываться в скалярном контексте.

Clojure, 102, 117, 115106

unformated:

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

отформатирован:

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

Время работы весов с периодом. Почти мгновенно на моем компьютере для выборочных значений.

В основном, это вычисляет результат вычитания после каждого шага в длинном делении. Цикл обнаруживается, если в любой точке это число совпадает с тем, которое было вычислено до него.

(не конкурирующий) Pyth

fq.^;yTQ.^;TQ

Использует алгоритм черепахи и зайца ( дополнительная информация ).

Смотреть это пройти каждый тест.