Sep
28
n的阶乘有很多相关的算法,这里总结了几个常用的算法:
1.高精度求解N!
2.计算阶乘末尾第一个非0数字
相关题目:http://acm.hdu.edu.cn/showproblem.php?pid=1066
3.斯特林公式快速求解N!和N!的位数
斯特林公式:

注意这里的斯特林公式求解出来的是一个近似值,所以不能用来求解需要准确值
斯特林公式求解N!的位数:

对N!取以10为底的对数
可以得到以下公式
相关题目:http://acm.hdu.edu.cn/showproblem.php?pid=1018
4.阶乘末尾有多少个0
分析发现,实际上形成末尾0,就是因子5的数量,而计算1~n之间包含一个因子i的个数的简单算法就是:
因此,直接将i换成5,就可以得到因子5的数量,也即n!末尾0的数量。
http://acm.hdu.edu.cn/showproblem.php?pid=1124
5.返回阶乘左边的第二个数字
简单算法:用实数乘,超过100就除以10,最后取个位即可。因为整数部分的个位就是阶乘结果左边的第二个数字。
6.判断数值 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 则不能整除;否则可以整除
7.数字N能否表示成若干个不相同的阶乘的和
这里可以选择的阶乘为:0! ~ 9!,实际上这一题与数论无关,与搜索有关。相关题目:http://acm.zju.edu.cn 的2358题。
分析,由于可供选择的阶乘数量较少,直接可以利用DFS搜索来做:
A. 首先将0 ~ 9的阶乘作一个表A[10];再设置一个可以组成“和”的数组ans[N]。
B. 深度优先搜索方法:
C. 最后对于输入n,就在ans数组中查找是否存在n,如果存在,则表示n可以表示成不同的阶乘和,否则不行。
---前面的四条都有具体的实现,后面的三个暂时没有具体的实现。
1.高精度求解N!
//以下为使用Java的大数类实现
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args)
{
BigInteger inc = new BigInteger("1");
BigInteger n = null;
Scanner sc = new Scanner(System.in);
while(sc.hasNext())
{
n = sc.nextBigInteger();
BigInteger ans = new BigInteger("1");
BigInteger i = new BigInteger("1");
for(; i.compareTo(n) != 1; i = i.add(inc))
{
ans = ans.multiply(i);
}
System.out.println(ans);
}
}
}
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args)
{
BigInteger inc = new BigInteger("1");
BigInteger n = null;
Scanner sc = new Scanner(System.in);
while(sc.hasNext())
{
n = sc.nextBigInteger();
BigInteger ans = new BigInteger("1");
BigInteger i = new BigInteger("1");
for(; i.compareTo(n) != 1; i = i.add(inc))
{
ans = ans.multiply(i);
}
System.out.println(ans);
}
}
}
2.计算阶乘末尾第一个非0数字
//快速求解N!末尾第一个非0数字,时间复杂度为O(n^2),n为 N的位数
//输入的N为字符串读入
int lastdigit(char*buf)
{
int mod[20]={1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2};
int len=strlen(buf),a[maxn],i,c,ret=1;
if(len==1)
return mod[buf[0]-'0'];
for(i=0;i<len;i++)
a[i]=buf[len-1-i]-'0';
for(;len;len-=!a[len-1])
{
ret=ret*mod[a[1]%2*10+a[0]]%5;
for(c=0,i=len-1;i>=0;i--)
c=c*10+a[i],a[i]=c/5,c%=5;
}
return ret+ret%2*5;
}
//输入的N为字符串读入
int lastdigit(char*buf)
{
int mod[20]={1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2};
int len=strlen(buf),a[maxn],i,c,ret=1;
if(len==1)
return mod[buf[0]-'0'];
for(i=0;i<len;i++)
a[i]=buf[len-1-i]-'0';
for(;len;len-=!a[len-1])
{
ret=ret*mod[a[1]%2*10+a[0]]%5;
for(c=0,i=len-1;i>=0;i--)
c=c*10+a[i],a[i]=c/5,c%=5;
}
return ret+ret%2*5;
}
相关题目:http://acm.hdu.edu.cn/showproblem.php?pid=1066
3.斯特林公式快速求解N!和N!的位数
斯特林公式:
注意这里的斯特林公式求解出来的是一个近似值,所以不能用来求解需要准确值
斯特林公式求解N!的位数:
对N!取以10为底的对数
可以得到以下公式
//快速求解N!的位数,输入的n即为N!中的最大的那个N
int strilingToDigit (int n)
{
double ans;
ans = 0.5*log10(2*pi)+(0.5+n)*log10(n)-n/log(10.0)+1.0;
return int(ans);
}
int strilingToDigit (int n)
{
double ans;
ans = 0.5*log10(2*pi)+(0.5+n)*log10(n)-n/log(10.0)+1.0;
return int(ans);
}
相关题目:http://acm.hdu.edu.cn/showproblem.php?pid=1018
4.阶乘末尾有多少个0
分析发现,实际上形成末尾0,就是因子5的数量,而计算1~n之间包含一个因子i的个数的简单算法就是:
int factorNum(int i, int n)
{
int cnt = 0;
while(n)
{
n /= i;
cnt += n;
}
return cnt;
}
{
int cnt = 0;
while(n)
{
n /= i;
cnt += n;
}
return cnt;
}
因此,直接将i换成5,就可以得到因子5的数量,也即n!末尾0的数量。
http://acm.hdu.edu.cn/showproblem.php?pid=1124
5.返回阶乘左边的第二个数字
简单算法:用实数乘,超过100就除以10,最后取个位即可。因为整数部分的个位就是阶乘结果左边的第二个数字。
6.判断数值 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 则不能整除;否则可以整除
7.数字N能否表示成若干个不相同的阶乘的和
这里可以选择的阶乘为:0! ~ 9!,实际上这一题与数论无关,与搜索有关。相关题目:http://acm.zju.edu.cn 的2358题。
分析,由于可供选择的阶乘数量较少,直接可以利用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]; //回溯
}
}
for(i = n; i <= 9; i++) {
sum += A[i]; //求和
如果sum在ans数组中不存在,则将sum插入到ans[]数组中
search(n+1);
sum -= A[i]; //回溯
}
}
C. 最后对于输入n,就在ans数组中查找是否存在n,如果存在,则表示n可以表示成不同的阶乘和,否则不行。
---前面的四条都有具体的实现,后面的三个暂时没有具体的实现。
浩子
2009/10/25 21:37
看不懂……囧
sakula.
2009/10/11 22:06
呃 很久不来 一来就看到了神之一手 加油哈 还有我的校园卡类 嘿嘿

仁心博客
2009/10/07 20:31
向你学习中
lee
2009/10/03 19:59
中秋快乐
风吟!
2009/10/03 19:55
虽然是谬论!但是祝贺博主中秋快乐。
lee
2009/09/29 21:51
我已经忘记这些东西了
261762586 回复于 2009/09/29 21:54
哈哈 给你复习一下!!
csuft1
2009/09/29 20:26
呵呵..写的很好啊..顶一下..
261762586 回复于 2009/09/29 21:53
呵呵!!
分页: 1/1
1
1



卡题真难受
流水一篇
