当前位置:编程学习 > C/C++ >>

杭电1042—— N!(大数乘法的应用!)


Problem Description
Given an integer N(0 ≤ N ≤ 10000), your task is to calculate N!
 

Input
One N in one line, process to the end of file.
 

Output
For each N, output N! in one line.
 

Sample Input
1
2
3
 

Sample Output
1
2
6
 
这道题目有一些东西特别要注意:

1.0的阶乘是存在的!0!=1,我当初提交这道题目是在这一点上吃了不少的亏!我开始是是写的while(cin>>n && n>0);交上去的时候老是报错!但是我就纳闷了,没错啊!后来才发现,这句应该写成while(cin>>n && n>=0);或者while(scanf("%d",&n)!=EOF);

2.10000的阶乘是在是太大了!我的数组开4000居然还是错,开8000还错!后来索性开个10000,居然对了!太吃惊!


[cpp] 
//首先需要肯定,程序是正确的  
//这算是大数乘除法!记住他们是如何处理的!由于数据很大,用基本数据类型根本无法满足要求,只能用数组来表示! 
//大数乘法!10000!的阶乘是在太大!几次数组开小了都报错误! 
#include <iostream> 
#include<cstdio> 
#include<memory.h> 
using namespace std; 
#define MAX 10000 
#define BASE 100000//base只是一个基度,对最终取值并没有影响,相反,base取值愈大,计算量愈小 
//base发生改变的时候,下面的输出也要相应地做出调整,否则也会输出错误答案!除非当base取10! 
int h[MAX]; 
//这是我第二次接触大数的乘法!现在复习一下吧!很好的算法! 
 
int main() 

    int i,j,k,carry; 
    int n; 
     
    while(scanf("%d",&n)!=EOF) 
    {   
        memset(h,0,MAX*sizeof(int));//赋值,每一个都置为0  
        for(i=1,h[MAX-1]=1;i<=n;++i)//运用递归,并且h[1]=1;  
        for(k=MAX-1,carry=0;k>=0;--k)//从最后一位开始相乘,依次向前与每一位相乘  
        {  
            carry+=i*h[k]; 
            h[k]=carry%BASE; 
            carry/=BASE;//carry表示进位 
        }        
        for(j=0;j<MAX && h[j]==0;++j);//从0位开始搜索,找到不为0的第一个数  
        printf("%d",h[j++]);//像是这个输出,就很妙了,第一位可能不足五位,就地输出! 
        for(;j<MAX;++j) 
        printf("%05d",h[j]);//处在中间的值也可能没有五位,这时候要注意了,往左边加0,凑足5位,不然答案会出错!     
        printf("\n"); 
    } 
    //system("pause"); 
     
    return 0; 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,