题目：
1. 给定一个整数N，nameN的阶乘N！结尾有多少个0呢？
2.求N！的二进制表示中最低位1的位置
1 #include <iostream> 2 3 4 // 遍历1~N，找到每一个5的倍数包含5这个因数的个数 5 // 比如 N=34，我们会找到 6 // 1. 数字5包含1个因数5（5=1*5）， 7 // 2. 数字10包含1个因数5（10=2*5） 8 // 3. 数字15包含1个因数5（15=3*5）， 9 // 4. 数字20包含1个因数5（20=4*5）， 10 // 5. 数字25包含2个因数5（25=2*5）， 11 // 5. 数字30包含1个因数5（30=2*3*5）， 12 // 一共找到1+1+1+1+2+1=7个5 13 int count0_way1( int N ) 14 { 15 int count = 0; 16 for ( int i = 1; i <= N; i++ ) { 17 int j = i; 18 while ( j % 5 == 0 ) { 19 count++; 20 j /= 5; 21 } 22 } 23 return count; 24 } 25 26 // 我们也可以直接在1~N中找到包含因数5的数的个数， 27 // 比如 N=34的数字中， 28 // 1. 包含1个因数5的数字有5，10，15，20，25，30，共6个（即34/5的结果) 29 // 2. 包含2个因数5的数字(即25)有25, 共1个，即34/25的结果， 30 // 3. 包含3个因数5的数字(即125)有0个，即34/125的结果， 31 // 4. ..... 32 // 一共找到34/5 + 34/25 = 6+1=7 个 33 int count0_way2( int N ) 34 { 35 int count = 0; 36 while ( N ) { 37 count += N / 5; 38 N = N / 5; 39 } 40 return count; 41 } 42 43 44 // 求N!结果中最低位置1的位置，等同于求N!的2的质因数的个数 45 // 我们可以观察到， 46 // 1. 任何奇数的二进制表示中，最后一位都是1 47 // 2. 任意多个奇数相乘的结果依然是奇数，也就是说，奇数相乘，其结果的最后一位1总是在最低位上 48 // 3. 任意一个数，都可以分解为质因数相乘，在所有的质数中，只有2是偶数，其余的都是奇数 49 // 4. 一个数乘以2，相当于其二进制表示左移一位, 即最低位的1的位置向左移动一位 50 // 5. 因此，我们把算式 N! = N*(N-1)*(N-2)*(N-3)....*1 分解质因式，其所有的因子中，只会存在2和奇数（因为质数中只有2是偶数） 51 // 根据2，奇数的乘积还是奇数，只有因数2才会改变最低位1的位置，每乘一次2(也即出现一个因子2）就会使得1的位置左移一次 52 // 得到我们的结论：求N!结果中最低位置1的位置，等同于求N!的2的质因数的个数, 53 // 求N！中质因数2的个数的方法可以参考Question1的方法2, 54 int OnePosition_way1(int N ) 55 { 56 int count = 0; 57 while ( N ) { 58 count += N / 2; 59 N = N >> 1; 60 } 61 return count + 1; 62 } 63 64 65 int main( int argc, char** argv ) 66 { 67 // Question1: 求N!的结果中，结尾0的个数。 68 // 求一个乘法算式结果的结尾0的个数，等同于求乘法算式中因子10的个数，而10=2*5，且在自然数的因子中，因子2的个数大于因子5的个数， 69 // 因此，求这个算式结果的结尾0的个数，等同于求这个算式中因子5的个数 70 int N = 34; 71 std::cout << " count 0 in " << N << std::endl; 72 std::cout << " way1: " << count0_way1( N ) << std::endl; 73 std::cout << " way2: " << count0_way2( N ) << std::endl; 74 std::cout << " DONE " << std::endl; 75 76 77 // Question2： 求N!结果的二进制表示中，最低位1的位置，比如 N=3, N!=3*2*1=6=0b(110), 其结尾最低位1的位置是2. 78 std::cout << " the positon of lowest 1 : in " << N << std::endl; 79 std::cout << " way1: " << OnePosition_way1( N ) << std::endl; 80 //std::cout << " way2: " << 1position_way2( N ) << std::endl; 81 std::cout << " DONE " << std::endl; 82 83 return 0; 84 }