Алгоритм обнаружения повторяющихся десятичных знаков?

Чтобы найти повторяющийся шаблон, просто следите за значениями, которые вы используете в строке:

1/5 = 1/101:

1 < 101 => 0
(decimal separator here)
10 < 101 => 0
100 < 101 => 0
1000 >= 101 => 1

  1000 - 101 = 11

110 >= 101 => 1

  110 - 101 = 1

10 -> match

Когда вы достигнете того же значения, что и во втором бите, процесс будет просто повторяться с этой точки, создавая один и тот же битовый шаблон снова и снова. У вас есть шаблон «0011», повторяющийся со второго бита (первый после десятичного разделителя).

Если вы хотите, чтобы шаблон начинался с «1», вы можете просто повернуть его, пока он не будет соответствовать этому условию:

"0011" from the second bit
"0110" from the third bit
"1100" from the fourth bit

Изменить:
Пример на C#:

void FindPattern(int n1, int n2) {
   int digit = -1;
   while (n1 >= n2) {
      n2 <<= 1;
      digit++;
   }
   Dictionary<int, int> states = new Dictionary<int, int>();
   bool found = false;
   while (n1 > 0 || digit >= 0) {
      if (digit == -1) Console.Write('.');
      n1 <<= 1;
      if (states.ContainsKey(n1)) {
         Console.WriteLine(digit >= 0 ? new String('0', digit + 1) : String.Empty);
         Console.WriteLine("Repeat from digit {0} length {1}.", states[n1], states[n1] - digit);
         found = true;
         break;
      }
      states.Add(n1, digit);
      if (n1 < n2) {
         Console.Write('0');
      } else {
         Console.Write('1');
         n1 -= n2;
      }
      digit--;
   }
   if (!found) {
      Console.WriteLine();
      Console.WriteLine("No repeat.");
   }
}

Вызывается с вашими примерами, он выводит:

.1
No repeat.
.01
Repeat from digit -1 length 2.
.10
Repeat from digit -1 length 2.
1.0
Repeat from digit 0 length 2.
.0011
Repeat from digit -1 length 4.

1. если делитель не является степенью числа 2 (как правило, содержит простые множители, не являющиеся общими с базой представления)
2. длина повторяющегося цикла будет зависеть от наибольшего простого множителя делимого (но не связана с длиной представления этого множителя — см. 1/7 в десятичном виде), но длина первого цикла может отличаться от единицы повторения (например, 11/28 = 1/4+1/7 в десятичном виде).
3. фактический цикл будет зависеть от числителя.

Я могу дать подсказку: повторяющиеся десятичные дроби в основании десять являются дробями со знаменателем, имеющим по крайней мере один простой множитель, отличный от двух и пяти. Если знаменатель не содержит простых множителей два или пять, их всегда можно представить со знаменателем, состоящим из всех девяток. Тогда числитель — это повторяющаяся часть, а количество девяток — длина повторяющейся части.

3     _
- = 0.3
9

1   142857     ______
- = ------ = 0.142857
7   999999

Если в знаменателе есть простые множители два или пять, повторяющаяся часть начинается не с первой позиции.

17    17        ______
-- = ----- = 0.4857142
35   5 * 7

Но я не могу вспомнить, как получить неповторяющуюся часть и ее длину.

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

1/2 =   1/10   = 0.1
1/4 =   1/100  = 0.01
3/4 =  11/100  = 0.11
5/8 = 101/1000 = 0.101

Все дроби с нечетными знаменателями должны быть повторяющимися, а образец и его длину можно получить, представив дробь со знаменателем в виде 2^n-1.

                                                     __
 1/3            =  1/(2^2-1) =        1/11       = 0.01
                                                     __
 2/3            =  2/(2^2-1) =       10/11       = 0.10
                       __
 4/3  => 1 + 1/3 =>  1.01
                       __
10/3  => 3 + 1/3 => 11.01
                                                     ____
 1/5  =   3/15  =  3/(2^4-1) =       11/1111     = 0.0011
                                                     ________
11/17 = 165/255 = 11/(2^8-1) = 10100101/11111111 = 0.10100101

Что касается основания десять, я не могу сказать, как обращаться со знаменателями, содержащими, но не являющимися степенью двойки, например, 12 = 3 * 2^2.

Во-первых, один из ваших примеров неверен. Повторяющаяся часть 1/5 — это 0011, а не 1100, и она начинается в самом начале дробной части.

Повторяющееся десятичное число выглядит примерно так:

a/b = c + d(2-n + 2-n-k + 2-n-2k + ...)
    = c + 2-n * d / (1 - 2-k)

в котором n и d - это то, что вы хотите.

Например,

1/10(dec) = 1/1010(bin) = 0.0001100110011... // 1 = true, 2 = -1, 3 = 0011

можно представить формулой с

a = 1, b = 10(dec), c = 0, d = 0.0011(bin), n = 1, k = 4;
(1 - 2-k) = 0.1111

Поэтому 1/10 = 0.1 * 0.0011/0.1111. Ключевая часть повторяющегося десятичного представления генерируется путем деления на (2n - 1) или на любое его число, кратное 2. Таким образом, вы можете либо найти способ выразить свой знаменатель как таковой (например, построить постоянные таблицы), либо выполнить деление больших чисел (что относительно медленно) и найдите петлю. Нет быстрого способа сделать это.

Ознакомьтесь с десятичным расширением и особенно о периоде дроби.

Вы можете выполнить полное деление, отмечая остатки. Структура остатков даст вам структуру любого рационального десятичного числа:

1. последний остаток равен нулю: это десятичная дробь без повторяющейся части
2. первый и последний остаток равны: десятичная дробь повторяется сразу после точки
3. расстояние между первым и первым остатком равно последнему - неповторяющиеся цифры, остаток - повторяющаяся часть

В общем, расстояния дадут вам количество цифр для каждой части.

Вы можете увидеть этот алгоритм в кодировке C++ в методе decompose() здесь.

Попробуйте 228142/62265, у него есть период 1776 цифр!