OJ练习33——T172 Factorial Trailing Zeroes

求n！末尾有多少个0.

【思路】

1.发现规律

2*5会产生1个0,4*25会产生2个0,8*125会产生3个0,……

又偶数都包含因子2，所以只要有5,25,125(5^i)出现，就会有配套的2^i出现，

所以最终算法是，看n中包含多少个5的次幂。

2.笨办法，先算出n!，再循环除以10，计算次数。

【other code】

int trailingZeroes(int n) {
        int ret = 0;
        while(n)
        {
            ret += n/5;
            n /= 5;
        }
        return ret;
    }

【my code】测试版

int main()
{
    int n=10;
    int re=1;
    int count=0;
    for(int i=1; i<=n; i++)
        re*=i;
    cout<<re<<endl;
    while(re>0){
        if(re%10==0){
            count++;
            re/=10;
        }
        else break;
    }
    cout<<count<<endl;
    system("pause");
    return 0;
}

【结果】

自己测试了几个用例，结果是对的，但是忘记了！能表示的n!是有限的，比如n=30时，输出0，正确结果应该是7.溢出了。

发现规律的时候要耐心，差点就能挖掘出这个规律了！