阶乘相关的算法及其C++实现 |
|
有关阶乘的算法，不外乎两个方面：一是高精度计算；二是与数论 有关 。 一、 高精度计算阶乘 这实际上是最没有技术含量的问题，然而又会 时常用到，所以还是得编写，优化它的计算 。 首先看小于等于12的阶乘计算(计算 后果不会超出32位 规模)： int factorial(int n) { if (n == 1 || n == 0) return 1; return factorial(n-1)*n; } 这个递归程序 方便明了，十分直观，然而一旦n > 12，则超过32位int型的 规模浮现 舛误 后果，所以上面这个递归程序仅 合适n <= 12的阶乘计算，为了计算较大n的阶乘，需求将高精度乘法算法纳入到阶乘计算中来，高精度乘法过程 可以如下 方便的 形容：(其中A * B = C，A[0], B[0], C[0]分别存储长度) for (i = 1; i <= A[0]; i++) for (j = 1; j <= B[0]; j++) { C[i+j-1] += A[i]*B[j]; // 目前i+j-1位对应项 + A[i] * B[j] C[i+j] += C[i+j-1]/10; // 它的后一位 + 它的商(进位) C[i+j-1] %= 10; // 它再取余即可 } C[0] = A[0] + B[0]; while (C[0] > 1 && C[C[0]] == 0) C[0]--; // 去头0， 获得实际C的长度 有了这个高精度乘法之后，计算阶乘就 可以 方便的迭代进行： for (i = 2; i <= n; i++) { 将i转换成字符数组； 执行高精度乘法：将上一次 后果乘上i } 二、 与数论有关 由于阶乘到后面越来越大， 奇妙的利用数论求得一些 乏味的数字(数值)等成为阶乘算法的设计点，下面给出几道 有关的问题与 综合： (1) 计算阶乘末尾第一个非0数字： 这是一个 比较经典的问题， 比较复杂的算法是利用一个困难的数学公式，惋惜我不会，从网上的 材料学习中， 整顿出下面这个 方便易懂的算法： 视察n!， 可以发现在乘的过程中，关于任意 n > 1，n!的末尾第一个非0数字都是偶数 。我们 惟独保留最终一位非零数 。当要乘的数中含有因数5时，我们 可以把全部的因数5都当作8来乘 。这是由于： …x2*5=…10(舍)或…60，最终一位非零数为6 。而恰好2*8=16，末位为6 。 …x4*5=…70(舍)或…20，最终一位非零数为2 。而恰好4*8=32，末位为2 。 …x6*5=…30(舍)或…80，最终一位非零数为8 。而恰好6*8=48，末位为8 。 …x8*5=…90(舍)或…40，最终一位非零数为4 。而恰好8*8=64，末位为4 。 (关于n > 1时，最终一位不会浮现 1, 7, 3, 9，而永远是2, 4, 6, 8的循环浮现) 因此，在迭代作乘法时，重要便是计算因子5的数量，同时可见因子5的个数以4为循环节(即 惟独求取它的数量对4取模) 。那么关于不同状况下的因子5的数量， 可以通过res[5][4] = {{0,0,0,0}, {2,6,8,4}, {4,2,6,8}, {6,8,4,2}, {8,4,2,6}}来得到， 使用nonzero[i] 示意i的阶乘的最终一位，那么： 假如t是偶数，则直接乘：nonzero[i] = (nonzero[i-1]*t)%10 。 不然nonzero[i] = res[((nonzero[i-1]*t)%10)/2][five]; 其中t是除掉全部因子5的 后果，five为因子5数量对4的模 。 (2) 。 阶乘末尾有多少个0 综合发现，实际上 构成末尾0，便是因子5的数量，而计算1'n中间包括一个因子i的个数的 方便算法便是： cnt = 0; while (n) { n /= i; cnt += n; } 因此，直接将i换成5，就 可以得到因子5的数量，也即n!末尾0的数量 。 (3) 。 返回阶乘左边的第二个数字 方便算法：用实数乘，超过100就除以10，最终取个位即可 。由于整数 部分的个位便是阶乘 后果左边的第二个数字 。 有关题目： (4) 。 推断数值 m 是不是 可以整除 n! 算法： 使用素因子推断法 A. 首先直接输出两种特别状况： m == 0 则 0 确定不会整除n!； n >= m 则 m 确定 可以整除n!; B. 那么就只剩最终一种状况：m > n，我们从m的最小素因子取起，设素因子为i那么 可以 求得m的素因子i的个数 nums1；再 审查闭区间 i ' n 中间的数，一共包括多少个素因子i，就 可以 方便的利用上面(2)中所介绍的数学公式进行计算得到nums2 。假如nums2 < nums1，就 示意1 ' n中包括素因子的数量 < 除数m包括素因子i的数量，那么m必定不能整除n!，置ok = false 。 C. 最终：假如 !ok or m > n or m == 0 则不能整除；不然 可以整除 (5) 。数字N 是不是 示意成若干个不 雷同的阶乘的和： 这里 可以 取舍的阶乘为：0! ' 9!，实际上这一题与数论无关，与搜索有关 。 综合，由于可供 取舍的阶乘数量较少，直接 可以利用DFS搜索来做： A. 首先将0 ' 9的阶乘作一个表A[10]；再设置一个 可以构成“和”的数组ans[N] 。 B. 深度优先搜索 步骤： search(n) { for(i = n; i <= 9; i++) { sum += A[i]; //求和 假如sum在ans数组中不存在，则将sum插入到ans[]数组中 search(n+1)； sum -= A[i]; //回溯 } } C. 最终关于输入n，就在ans数组中搜索是不是存在n，假如存在，则 示意n 可以 示意成不同的阶乘和，不然不行 。 |
