简介

• 任意的无限循环小数都可以用两个有理数组成的分数表示;
• 无限循环小数也是有理数

算法

由于需求只是求出循环周期，因此不关心其小数形式。利用小学三年级计算除法的步骤。当除得的余数重复出现时，两次步骤之间的间隔数目即为小数但循环周期。

ps: 函数传入参数为两个u64.

code

code1

fn cycle(m:u64,n:u64) -> Option
    
     {    use std::collections::HashMap;    let mut residues = HashMap::new();    let mut residue = m%n;    let mut count:u64 = 0;    residues.insert(residue, count);    loop{        count +=1;        residue = (residue*10)%n;        if residue == 0{            return None;        }        if let Some(res) = residues.get(&residue){            return Some(count-res);        }        residues.insert(residue, count);    }}#[test]fn test() {    //1.42857 142857 142857 ...    assert!(Some(6) == cycle(10,7));}
    

code2

用HashMap的好处是，hash查找的时间复杂度为O(1)，每次查询所消耗的的时间固定。但缺点是每次查询都需要计算一次hash值，遇到hash碰撞还会使得性能下降。总的来说比较适合循环周期较长的情况。

代码中，hash表记录的值是这个余数出现的序数。可以用vec代替，则余数出现但序数就是该数在数组中的索引。“呆？！看代码。。。”

fn cycle(m:u64,n:u64) -> Option
    
     {    let mut residues = vec![];    let mut residue = m%n;    residues.push(residue);    loop{        residue = (residue*10)%n;        if residue == 0{            return None;        }        if let Some(res) = residues.iter().position(|&item|item==residue){            return Some((residues.len() -res) as u64);        }        residues.push(residue);    }}