jc.cpp

大数相乘、计算时间、josep问题、计算JC、分形图形

//PIII900，不到2秒钟，算5000！ 


// Factorial.cpp : 高精度阶乘算法，算n!，n<5000 
// Author:Goodfire 
// Date:2003-7-4 
// PIII900，不到2秒钟，算5000?
#include <stdio.h> 

#define N  18000 
#define RADIX 100000 
#define MAX_NUM 5000 

FILE *gfpin=stdin; 
FILE *gfpout=stdout; 

unsigned long ga[N]={0}; 
unsigned long glen=0; 

int seqlen() 
{ 
     return glen; 
} 

void HPCarry(int off) 
{ 
     if(ga[off]<=RADIX-1) return ; 
     int a=ga[off]; 
     ga[off]=a%RADIX; 
     ga[off+1]+=a/RADIX;  // off+1 是更高一位 
     if(off==glen-1) glen++; 
} 

void HPMulti(int k) 
{// 高精度按位乘法，被乘数总是不大于5000 
    int i, len=seqlen() ; 
    for(i=0;i<len;i++) ga[i]=ga[i]*k; 
    for(i=0;i<len+5;i++) { // 检查每一位是否需要进位。因为最大乘数可能为5000， 
          // 所以要向后检查4位 
        if(ga[i]>RADIX-1) { 
        HPCarry(i); 
        } 
    } 
} 

void Print() 
{// 打印高精度数 
    int i=seqlen()-1; 
    while(i>=0) {fprintf(gfpout, "%d", ga[i]); i--;}; // 倒序打印 
    fprintf(gfpout, "\n"); 
} 

void Fact(int n) 
{// 计算n! 
    int i, n2=n; 
    ga[0]=1; // 初始化高精度数为1 
    glen=1; 
    if(n>1) { 
        for(i=2;i<=n;i++) {// 计算1*2*3*4... 
        HPMulti(i); 
        } 
    } 
    Print(); // 打印结果 
} 

int main(void) 
{ 
    int n; 
    fscanf(gfpin, "%d", &n); 
    Fact(n); 
    return 0; 
}