关于算法:编程之美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;
}