关于算法:编程之美22-不要被阶乘吓倒

题目：

1. 给定一个整数N，nameN的阶乘N！结尾有多少个0呢？
2. 求N！的二进制示意中最低位1的地位

#include <iostream>


// 遍历1~N，找到每一个5的倍数蕴含5这个因数的个数
// 比方 N=34，咱们会找到
//      1. 数字5蕴含1个因数5（5=1*5），
//      2. 数字10蕴含1个因数5（10=2*5）
//      3. 数字15蕴含1个因数5（15=3*5），
//      4. 数字20蕴含1个因数5（20=4*5），
//      5. 数字25蕴含2个因数5（25=5*5），
//      5. 数字30蕴含1个因数5（30=2*3*5），
//      一共找到1+1+1+1+2+1=7个5
int count0_way1( int N )
{
    int count = 0;
    for ( int i = 1; i <= N; i++ ) {
        int j = i;
        while ( j % 5 == 0 ) {
            count++;
            j /= 5;
        }
    }
    return count;
}

// 咱们也能够间接在1~N中找到蕴含因数5的数的个数，
// 比方 N=34的数字中，
//      1. 蕴含1个因数5的数字有5，10，15，20，25，30，共6个（即34/5的后果)
//      2. 蕴含2个因数5的数字(即25)有25, 共1个，即34/25的后果，
//      3. 蕴含3个因数5的数字(即125)有0个，即34/125的后果，
//      4. .....
//      一共找到34/5 + 34/25 = 6+1=7 个
int count0_way2( int N )
{
    int count = 0;
    while ( N ) {
        count += N / 5;
        N = N / 5;
    }
    return count;
}


// 求N!后果中最低地位1的地位，等同于求N!的2的质因数的个数
// 咱们能够察看到，
//     1. 任何奇数的二进制示意中，最初一位都是1
//     2. 任意多个奇数相乘的后果仍然是奇数，也就是说，奇数相乘，其后果的最初一位1总是在最低位上
//     3. 任意一个数，都能够合成为质因数相乘，在所有的质数中，只有2是偶数，其余的都是奇数
//     4. 一个数乘以2，相当于其二进制示意左移一位, 即最低位的1的地位向左挪动一位
//     5. 因而，咱们把算式 N! = N*(N-1)*(N-2)*(N-3)....*1 合成质因式，其所有的因子中，只会存在2和奇数（因为质数中只有2是偶数）
//        依据2，奇数的乘积还是奇数，只有因数2才会扭转最低位1的地位，每乘一次2(也即呈现一个因子2）就会使得1的地位左移一次
//     失去咱们的论断：求N!后果中最低地位1的地位，等同于求N!的2的质因数的个数,
//     求N！中质因数2的个数的办法能够参考Question1的办法2,
int OnePosition_way1(int N )
{
    int count = 0;
    while ( N ) {
        count += N / 2;
        N = N >> 1;
    }
    return count + 1;
}


int main( int argc, char** argv )
{
    // Question1: 求N!的后果中，结尾0的个数。
    // 求一个乘法算式后果的结尾0的个数，等同于求乘法算式中因子10的个数，而10=2*5，且在自然数的因子中，因子2的个数大于因子5的个数，
    // 因而，求这个算式后果的结尾0的个数，等同于求这个算式中因子5的个数
    int N = 34;
    std::cout << " count 0 in " << N << std::endl;
    std::cout << " way1: " << count0_way1( N ) << std::endl;
    std::cout << " way2: " << count0_way2( N ) << std::endl;
    std::cout << " DONE " << std::endl;


    // Question2： 求N!后果的二进制示意中，最低位1的地位，比方 N=3, N!=3*2*1=6=0b(110), 其结尾最低位1的地位是2.
    std::cout << " the positon of lowest 1 : in " << N << std::endl;
    std::cout << " way1: " << OnePosition_way1( N ) << std::endl;
    //std::cout << " way2: " << 1position_way2( N ) << std::endl;
    std::cout << " DONE " << std::endl;

    return 0;
}