Алгоритм для обнаружения периодических десятичных дробей?
Поблочное тестирование работает на парней QA или Ваших менеджеров, не на Вас; таким образом, это определенно не стоит того.
необходимо сфокусироваться на написании правильного кода (независимо от того, что это означает), не тестовые сценарии. Позвольте другим парням волноваться о тех.
5 ответов
Чтобы найти повторяющийся шаблон, просто отслеживайте значения, которые вы используете вдоль линии:
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/7 в десятичном виде), но длина первого цикла может отличаться от единицы повторения (например, 11/28 = 1/4 + 1/7 в десятичном ).
- фактический цикл будет зависеть от числителя.
Во-первых, один из ваших примеров неверен. Повторяющаяся часть 1/5 равна 0011 , а не 1100 , и начинается в самом начале дробной части.
Повторяющаяся десятичная дробь - это что-то вроде:
a / b = c + d (2 -n + 2 -nk + 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 . Ключевая часть повторяющегося десятичного представления генерируется путем деления на (2 n - 1) или его любое кратное 2. Таким образом, вы можете найти способ выразить свой знаменатель как такие (например, создание таблиц констант) или деление большого числа (что относительно медленно) и поиск цикла. Нет быстрого способа сделать это.
Я могу дать подсказку - повторение десятичных знаков в базе десять - это дроби, в знаменателе которых есть хотя бы один простой делитель, кроме двух и пяти. Если знаменатель не содержит простых множителей два или пять, они всегда могут быть представлены знаменателем всех девяток. Тогда номинатор - это повторяющаяся часть, а количество девяток - это длина повторяющейся части.
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/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/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 .
Обратите внимание на десятичное представление и, в частности, о периоде дроби.