Sep 28

n!的相关总结 不指定

Posted by ringsd at 18:01 | ACM | 评论(7) | 阅读(1386) | 转自 本站原创 | |
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);
    }
  }
}


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;
}

相关题目: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);
}

相关题目: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;
}

因此,直接将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];         //回溯
     }
}

C. 最后对于输入n,就在ans数组中查找是否存在n,如果存在,则表示n可以表示成不同的阶乘和,否则不行。

---前面的四条都有具体的实现,后面的三个暂时没有具体的实现。
浩子 Homepage
2009/10/25 21:37
看不懂……囧
sakula.
2009/10/11 22:06
呃 很久不来 一来就看到了神之一手 加油哈 还有我的校园卡类 嘿嘿grinshy
仁心博客 Email Homepage
2009/10/07 20:31
向你学习中
lee Homepage
2009/10/03 19:59
grin中秋快乐
风吟! Homepage
2009/10/03 19:55
虽然是谬论!但是祝贺博主中秋快乐。
lee Homepage
2009/09/29 21:51
grin我已经忘记这些东西了
261762586 回复于 2009/09/29 21:54
哈哈  给你复习一下!!
csuft1
2009/09/29 20:26
呵呵..写的很好啊..顶一下..
261762586 回复于 2009/09/29 21:53
呵呵!!
分页: 1/1 第一页 1 最后页