一点一点前进...

0%

计算循环节长度

发表于 分类于 ， Disqus：

对于有理数，分成有限小数和无限循环小数。比如1/3 = 0.33333…
对于无限循环小数，循环节表示后续循环的部分。比如1/6 = 0.166666…，循环节是6，长度是1。1/7 = 0.1428571428571428…，循环节是142857，长度是6。

欧拉项目的第二十六题很有意思。基于以上知识，对于任意d < 1000，找到分数1/d循环节最长的那个d。

如何计算循环节长度呢？
想想我们手算，如果余数比除数小，我们会在后面补0然后再除。也就是说补零之后的数是下一次的被除数。如果被除数重复出现，除数确定的，那么商和余数也就是一样的。这时，循环节就出现了。
下面的函数分为两部分，

  1. 补零操作
  2. 查找有没有同样的被除数存在，如果有，就找到了循环节，计算循环节长度并返回。在没有找到的前提下，把当前被除数记录下来，并得到余数作为下一次的被除数。
    这里需要注意，如果某一次出现了除尽的情况，说明该分数是有限小数，循环节长度是0。
    下面是函数代码： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    // n/m
    static int GetRecurringCycle(int n, int m)
    {
        List<int> dividends = new List<int>();
        while (true)
        {
            while (n < m)
            {
                n *= 10;
            }
            // search pattern.
            int index = dividends.IndexOf(n);
            if (index >= 0)
            {
                return dividends.Count - index;
            }
            dividends.Add(n);
            n %= m;
            // n is divisible by m.
            if (n == 0)
            {
                return 0;
            }
        }
    }

能够计算循环节长度，得到循环节最长的那个d就易如反掌了。