MySQL中实现阶乘函数的方法与相关探讨

我们今天要讨论的问题大意是&＃xff1a;给定一个数n&＃xff0c;判断是否存在一个数m&＃xff0c;使得&＃xff1a;n &＃61;&＃61; ∑i!(这里共m个不同整数)。(n≤1000000)

说白了其实就是&＃xff1a;给定一个数n&＃xff0c;看看这个数能不能表示成从m个不同整数阶乘的和。

刚拿到题目可能没有思路。仔细考虑可以注意到&＃xff0c;n的最大值为1000000&＃xff0c;小于32位机器上的int型的最大值(2^31-1)&＃xff0c;最先可能想到的是枚举法&＃xff0c;由于10!>1000000&＃xff0c;所以可能出现的0-9这几个数&＃xff0c;每个数都有出现或者不出现两种情况&＃xff0c;如果枚举将会有2^10共1024种情况&＃xff0c;这个数量也不小。这就意味着需要换个思路来考虑。

注意到&＃xff0c;对于一个整数k(k>1)&＃xff0c;0! &＃43; 1! &＃43; ... &＃43; (k-1)! n&＃xff0c;那么n分解成阶乘和的数中必定包含j!&＃xff0c;用反证法证明&＃xff0c;假设不包含&＃xff0c;由之前的结论&＃xff0c;小于j的所有数的阶乘和都小于j!&＃xff0c;当然也必小于n。因此&＃xff0c;当n &＃61; n - j!后&＃xff0c;再判断n是否等于新的j!&＃xff0c;等于证明分解成功&＃xff1b;否则就减去新的j!&＃xff0c;并循环判断。

于是&＃xff0c;我们很容易得出以下代码。

public final static int count &＃61; 10;

public static int[] Facs(){

int temp &＃61; 1;

int[] facs &＃61; new int[count];

for(int i&＃61;0; i

if(i !&＃61; 0)

temp &＃61; temp * i;

facs[i] &＃61; temp;

}

return facs;

}

public static boolean facsSum(int n){

int rest &＃61; n;

int current &＃61; count - 1;

int[] facs &＃61; Facs();

while(rest >&＃61; 0 && current >&＃61; 0){

if(rest >&＃61; facs[current]){

rest -&＃61; facs[current];

}

current--;

}

if(rest &＃61;&＃61; 0)

return true;

return false;

}

这里有个技巧&＃xff0c;在上面的代码中&＃xff0c;Facs函数把0到9的阶乘储存在一个数组当中。这里有的同学可能会这么写代码。

private static int factorials(int n){

if(n<&＃61;1)

return 1;

return factorials(n-1)*n;

}

private static int[] Facs(){

int[] retFacs &＃61; new int[count];

for(int i&＃61;0; i

retFacs[i] &＃61; factorials(i);

}

return retFacs;

}

注意到差别没有&＃xff0c;其实我们上一次用到的阶乘存放在临时数中&＃xff0c;下轮就可以直接拿来使用。第二种方法更直观&＃xff0c;但是重复的运算、加上递归的使用&＃xff0c;使代码的效率低了许多。

因此&＃xff0c;大家可以试试只用一个循环来计算1到100阶乘的和。