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

Ответ 1

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

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

Edit:
Пример в С#:

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.

Ответ 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.

Ответ 4

Прежде всего, один из ваших примеров неверен. Повторяющаяся часть 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. Таким образом, вы можете либо найти способ выразить свой знаменатель как таковой (например, строить таблицы констант), либо сделать большое числовое деление ( который относительно медленный) и найти петлю. Нет быстрого способа сделать это.

Ответ 5

Откажитесь от десятичного расширения, а конкретно о периоде доли.

Ответ 6

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

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

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

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

Попробовать 228142/62265, он имеет период 1776 цифр!