如何知道分数中的重复小数？
我已经知道一个分数是重复小数。 这是function。
public bool IsRepeatingDecimal { get { if (Numerator % Denominator == 0) return false; var primes = MathAlgorithms.Primes(Denominator); foreach (int n in primes) { if (n != 2 && n != 5) return true; } return false; } } 现在，我正试图获得重复的数字。 我正在查看这个网站： http ： //en.wikipedia.org/wiki/Repeating_decimal
public decimal RepeatingDecimal() { if (!IsRepeatingDecimal) throw new InvalidOperationException("The fraction is not producing repeating decimals"); int digitsToTake; switch (Denominator) { case 3: case 9: digitsToTake = 1; break; case 11: digitsToTake = 2; break; case 13: digitsToTake = 6; break; default: digitsToTake = Denominator - 1; break; } return MathExtensions.TruncateAt((decimal)Numerator / Denominator, digitsToTake); }
但我真的意识到，有些数字有一个部分小数有限，后来有无数。 例如：1/28
你知道更好的方法吗？ 还是一个算法？
一个非常简单的算法是：实现长除法。 记录您所做的每个中级部门。 一旦你看到一个与你之前完成的部门相同的部门，就会有重复的部分。
示例：7/13。
1. 13 goes into 7 0 times with remainder 7; bring down a 0. 2. 13 goes into 70 5 times with remainder 5; bring down a 0. 3. 13 goes into 50 3 times with remainder 11; bring down a 0. 4. 13 goes into 110 8 times with remainder 6; bring down a 0. 5. 13 goes into 60 4 times with remainder 8; bring down a 0. 6. 13 goes into 80 6 times with remainder 2; bring down a 0. 7. 13 goes into 20 1 time with remainder 7; bring down a 0. 8. We have already seen 13/70 on line 2; so lines 2-7 have the repeating part
算法给出了538461作为重复部分。 我的计算器说7/13是0.538461538。 看起来对我来说！ 剩下的就是实现细节，或者找到更好的算法！
如果你有一个（正）减少的分数numerator / denominator ，当且仅当denominator没有除2或5之外的素因子时，分数的十进制展开终止。如果它有任何其他素因子，则十进制展开将是周期性的。 但是，分母可以被2和5中的至少一个整除，并且不会产生略微不同的行为。 我们有三种情况：
-
denominator = 2^a * 5^b，则十进制扩展终止小数点后的max {a, b}位数。 -
denominator = 2^a * 5^b * m其中m > 1不能被2或5整除，那么小数展开的小数部分由两部分组成，长度为max {a, b}的前期和期间，其长度由m决定，与分子无关。 -
denominator > 1不能被2或5整除，则十进制扩展纯粹是周期性的，这意味着句点在小数点后立即开始。
案例1.和2.的处理有一个共同的部分，让c = max {a, b} ，然后
numerator / denominator = (numerator * 2^(ca) * 5^(cb)) / (10^c * m)
对于情况1， m = 1 1。注意，我们乘以分子的因子2^(ca)和5^(cb)是1.然后通过扩展得到十进制扩展
(numerator * 2^(ca) * 5^(cb)) / m
并将小数点c位置向左移动。 在第一种情况下（ m = 1 ），该部分是微不足道的。
病例2.和3的处理也有一个共同的部分，计算一个分数
n / m
其中n和m没有共同的素因子（并且m > 1 ）。 我们可以写出n = q*m + r其中0 <= r < m （除以除法， r = n % m ），q是该分数的整数部分，而且相当无趣。
由于假设分数减小，我们r > 0 ，所以我们想要找到分数r / m的扩展，其中0 < r < m且m不能被2或5整除。如上所述，这样的扩展纯粹是周期性的，所以找到这个时期意味着找到完全的扩张。
让我们开始寻找启发期。 因此， k为（最短）周期的长度， p = d_1d1_2...d_k周期。 所以
r / m = 0.d_1d_2...d_kd_1d_2...d_kd_1... = (d_1d_2...d_k)/(10^k) + (d_1d_2...d_k)/(10^(2k)) + (d_1d_2...d_k)/(10^(3k)) + ... = p/(10^k) * (1 + 1/(10^k) + 1/(10^(2k)) + 1/(10^(3k)) + ...)
最后一项是几何级数， 1 + q + q^2 + q^3 + ...对于|q| < 1 |q| < 1的总和为1/(1-q) 。 在我们的情况下， 0 < q = 1/(10^k) < 1 ，因此总和是1 / (1 - 1/(10^k)) = 10^k / (10^k-1) 。 因此我们已经看到了
r / m = p / (10^k-1)
由于r和m没有共同因子，这意味着存在一个具有10^k - 1 = s*m和p = s*r 。 如果我们知道周期的长度k ，我们可以通过计算简单地找到周期的数字
p = ((10^k - 1)/m) * r
并用前导零填充，直到我们有k位数。 （注意：只有当k足够小或大整数类型可用时才这么简单。要计算例如标准固定宽度整数类型的17/983的周期，请使用@Patrick87所解释的长除法。）
所以仍然需要找到这个时期的长度。 我们可以恢复上面的推理，并发现如果m除以10^u - 1 ，那么我们就可以写了
r / m = t/(10^u - 1) = t/(10^u) + t/(10^(2u)) + t/(10^(3u)) + ... = 0.t_1t_2...t_ut_1t_2...t_ut_1...
和r/m有一段长度u 。 因此，最短周期的长度是最小正u ，使得m除以10^u - 1 ，或换句话说，最小正u ，使得10^u % m == 1 。
我们可以在O（m）时间内找到它
u = 0; a = 1; do { ++u; a = (10*a) % m; while(a != 1);
现在，找到那段时间的长度并不比找到周期的数字和长度以及长除法更有效，并且对于足够小的m这是最有效的方法。
int[] long_division(int numerator, int denominator) { if (numerator < 1 || numerator >= denominator) throw new IllegalArgumentException("Bad call"); // now we know 0 < numerator < denominator if (denominator % 2 == 0 || denominator % 5 == 0) throw new IllegalArgumentException("Bad denominator"); // now we know we get a purely periodic expansion int[] digits = new int[denominator]; int k = 0, n = numerator; do { n *= 10; digits[k++] = n / denominator; n = n % denominator; }while(n != numerator); int[] period = new int[k]; for(n = 0; n < k; ++n) { period[n] = digits[n]; } return period; }
只要10*(denominator - 1)没有溢出就行，当然int可以根据需要是32位或64位整数。
但是对于大分母来说，这是低效率的，通过考虑分母的素因子化，可以找到周期长度和周期。 关于期间长度，
- 如果分母是素数幂，
m = p^k，则r/m的周期长度是(p-1) * p^(k-1)的除数 - 如果
a和b是互质且m = a * b，则r/m的周期长度是周期长度1/a和1/b最小公倍数。
总之， r/m的周期长度是λ(m)的除数，其中λ是Carmichael函数 。
因此，为了找到r/m的周期长度，找到r/m的素因子分解，并且对于所有素数幂因子p^k ，找到1/(p^k)的周期 - 等效地，10模数p^k的乘法阶数，已知是(p-1) * p^(k-1)的除数。 由于这些数字的除数不是很多，所以很快就会完成。 然后找到所有这些中最不常见的倍数。
对于周期本身（数字），如果有大整数类型且周期不是太长，则为公式
p = (10^k - 1)/m * r
是一种快速计算方法。 如果周期太长或者没有大整数类型可用，那么有效地计算数字会更加混乱，而且我不记得究竟是怎么做到的。
一种方法是重复手工分割的方式，并记下每个阶段的余数。 当剩余部分重复时，其余过程也必须重复。 例如，1.0 / 7的数字是0.1余数3然后0.14剩余2然后0.142剩余6然后0.1428余数4然后0.14285余数5然后0.142857余数1这是1再次启动它amd所以你得到0.1428571余数3并且它重复再次从那里。
长除法算法非常好，所以我没有任何补充。
但请注意，您的算法IsRepeatingDecimal可能无法正常工作且无效。
如果你的分数不是不可约的，那么它将不起作用，即如果存在一个大于1的整数，它将你的分子和分母分开。 例如，如果您提供7/14，那么当算法返回false时，您的算法将返回true。
要减少分数，找到分子和分母之间的gcd，并用这个gcd除。
如果你认为分数是不可简化的，那么你的测试
if (Numerator % Denominator == 0)
可以简单地替换为
if (Denominator == 1)
但这仍然是不必要的，因为如果Denominator为1，那么你的列表’primes’将是空的，你的算法无论如何都会返回false。
最后，调用MathAlgorithms.Primes（Denominator）对于大数字来说将是昂贵的并且可以避免。 实际上，你需要做的就是将你的分母除以5（分别为2），直到它不再被5整除（相应的2）。 如果最终结果为1，则返回false，否则返回true。