任意数的阶乘

http://www.csdn.net/expert/Topic/63343.shtm http://www.csdn.net/expert/Topic/52263.shtm
// jiechen.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdlib.h>
// 000000000
// 000000000
#define WEISHU 10000
#define WEISHUBIT 4
#define MW ( WEISHU - 1 )
#define MAXLEN 100000
int num1[MAXLEN];
int num2[MAXLEN];
int num3[MAXLEN];
int resultTemp[MAXLEN];
int resultTempLen;
int mulTemp[MAXLEN];
int mulTempLen;
void showNum( int * num,int len )
{
for(int i=len-1;i>=0;i--)
{
printf("%04d",num );
}
}
int getweishu( int * num,int len )
{
int i;
for(i=len-1;i>=0;i--)
{
if ( i > 0 )
break;
}
if ( i == -1 )
return 1;
int r1 = i * WEISHUBIT;
int n2 = num;
if ( n2 == 0 )
return r1;
r1++;
while( n2 >= 10 )
{
r1++;
n2 /= 10;
}
return r1;
}
void showOpera( char * name1,int * num1,int len1 )
{
printf("%s = ",name1);
showNum( num1,len1 );
printf(""
}
void add( int * add1,int add1num,int *add2,int add2num,int *add3num )
{
// add1num >= add2num
int i;
//showOpera( "Add1",add1,add1num );
if ( add1num < add2num )
{
for(i=add1num;i<add2num;i++)
{
add1 = 0;
}
add1num = add2num;
}
int resultLen = add1num + 1;
int jinwei = 0;
for(i=0;i<add2num;i++)
{
add1 += add2 + jinwei;
if ( add1 > MW )
{
add1 -= WEISHU
jinwei = 1;
}
else
{
jinwei = 0;
}
}
if ( jinwei == 0 )
{
resultLen = add1num;
}
else
{
for(i=add2num;i<add1num;i++)
{
add1 ++;
if ( add1 > MW )
{
add1 = 0;
}
else
{
jinwei = 0;
break;
}
}
if ( jinwei == 0 )
{
resultLen = add1num;
}
else
{
add1[ add1num ] = 1;
}
}
*add3num = resultLen;
//showOpera("Add2",add2,add2num);
//showOpera("Add1 + Add2",add1,resultLen );
}
void mult( int * mul1,int mul1num,int *mul2,int mul2num,int *mul3,int *mul3num )
{
int i,j;
int result;
int jinwei = 0;
int kk;
resultTempLen = mul2num;
for(i=0;i<mul2num+mul1num+1;i++)
{
resultTemp = 0;
}
for(i=0;i<mul2num;i++)
{
jinwei = 0;
for(j=0;j<mul1num;j++)
{
result = mul2 * mul1[j] + jinwei;
if ( result > MW )
{
mulTemp[j] = result % WEISHU;
jinwei = result / WEISHU;
}
else
{
mulTemp[j] = result;
jinwei = 0;
}
}
if ( jinwei > 0 )
{
mulTempLen = mul1num+1;
mulTemp[mul1num] = jinwei;
}
else
{
mulTempLen = mul1num;
}
//showOpera("Mul1",mul1,mul1num);
//showOpera("Nul2",mul2+i,1);
//showOpera("Mul2 * Mul1",mulTemp,mulTempLen );
kk = resultTempLen;
add( resultTemp+i,kk-i,mulTemp,mulTempLen,&kk );
resultTempLen = kk + i;
}
*mul3num = resultTempLen;
for(i=0;i<resultTempLen;i++)
{
mul3 = resultTemp;
}
}
// 10! = 3628800
int ten( int num )
{
int re = 1;
for(int i=2;i<=num;i++)
re *= i;
return re;
}
void setNum( int num,int * n,int * len )
{
int i = 0;
while(num>0)
{
n = num % WEISHU;
num /= WEISHU;
i++;
}
*len = i;
}
void cal(int num)
{
int i,j;
if ( num <= 10 )
{
printf("%d! = %d",num, ten(num));
return;
}
int len1,len2,len3;
setNum( 3628800,num1,&len1);
for(i=11;i<=num;i++)
{
setNum( i,num2,&len2 );
mult( num1,len1,num2,len2,num3,&len3 );
for(j=0;j<len3;j++)
{
num1[j] = num3[j];
}
len1 = len3;
}
printf("%d! = ",num);
showNum( num3,len3 );
printf("= %d",getweishu(num3,len3));
}
void main(int argc, char* argv[])
{
if ( argc != 2 )
{
printf("Usage : Jiechen number"
return;
}
int num = atoi( argv[1] );
if ( num <= 0 )
{
printf("Arg %s is invalid!",argv[1]);
return;
}
cal(num);
}
*************
程序包含两个文件，
一个是执行窗体文件（包含组件：1个SpinEdit1，一个Edit，一个Button1，三个标签Label1，Label2，Label3），
另一个是类定义文件（Unit_factorial_class.pas），具体如下：
窗体定义文件：
unit Unit_Main;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls, Spin;
type
TForm1 = class(TForm)
Button1: TButton;
SpinEdit1: TSpinEdit;
Edit1: TEdit;
Label1: TLabel;
Label2: TLabel;
Label3: TLabel;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
{$R *.DFM}
uses
//使用类单元
Unit_factorial_class;
var
MyFactorial:TLQM_factorial_class;
procedure TForm1.Button1Click(Sender: TObject);
var
time1,time2:TTime;
begin
//创建对象
MyFactorial:=TLQM_factorial_class.Create;
label3.Caption:='Number: '+IntToStr(SpinEdit1.Value);
time1:=time;
//计算
Edit1.text:=string(MyFactorial.CaculateFactorial(SpinEdit1.Value));
time2:=time;
Label1.Caption:='Length: '+IntToStr(length(Edit1.text));
Label2.Caption:='Time: '+TimeToStr(time2-time1);
//销毁对象
MyFactorial.Free;
end;
end.
　
类定义文件（Unit_factorial_class.pas）内容为：
//-----------------------------------------------------------------------------
unit Unit_factorial_class;
interface
type
//数据结构-----------------------------------------------------
//-------------------------------------------------------------
//用于存储结果的每一个位(十进制位)的数据结构
TLQM_Factorial_Record_p=^TLQM_factorial_record;
TLQM_Factorial_Record=record
//只需用于保存0-9的数字,
//理论上的最大计算范围为[High(Integer)/10]的取值范围
//实际鉴于系统资源而定
Value:integer;
//指向高位的指针
HighPointer:TLQM_Factorial_Record_p;
end;
//类结构-------------------------------------------------------
//-------------------------------------------------------------
//用于实际计算的阶乘的类
TLQM_factorial_class=class(TObject)
//头节点指针
F_Head:TLQM_factorial_record_p;
private
//将指定值与链表中的值相乘（未进行值的标准处理）
//即：结果链表中的每个位都有可能是多位数
procedure Linklist_MultiplyValue_BlindMultiply(Value:integer);
//将最高位的值扩展到新加的高位字节（递归）
procedure Linklist_MultiplyValue_ExtendTopValue(
Top_p:TLQM_factorial_record_p);
//将链表中的值进行标准处理
//即：结果链表中的每个位只有一个个位数[0-9]
procedure Linklist_MultiplyValue_Fluency;
//将指定值与链表中的值相乘，生成标准的可输出值
//即：结果链表中的每个位只有一个个位数[0-9]
procedure Linklist_MultiplyValue(Value:integer);
//输出链表(注:由低位至高位,最高位的0不算)
function Linklist_OutputString:WideString;
public
//构造函数
constructor Create;
//计算阶乘的函数(当输入错误数[如:-1阶乘]时,返回字符串'-1')
function CaculateFactorial(UserValue:integer):WideString;
//析构函数
destructor Destroy;override;
end;
　
　
　
implementation
uses
Sysutils;
//构造函数
constructor TLQM_factorial_class.Create;
var
s:TLQM_factorial_record_p;
begin
//新建头节点-------------------------------------------------
new(s); s^.Value:=0; s^.HighPointer:=nil; F_Head:=s;
//创建并设置初始节点值为1------------------------------------
new(s); s^.Value:=1; s^.HighPointer:=nil; F_Head^.HighPointer:=s;
end;
//将指定值与链表中的值相乘（未进行值的标准处理）
//即：结果链表中的每个位都有可能是多位数
procedure TLQM_factorial_class.Linklist_MultiplyValue_BlindMultiply(Value:integer);
var
p:TLQM_factorial_record_p;
begin
p:=F_Head^.HighPointer;
while p<>nil do
begin
p^.Value:=p^.Value*Value;
p:=p^.HighPointer;
end;
end;
//将最高位的值扩展到新加的高位字节（递归）
procedure TLQM_factorial_class.Linklist_MultiplyValue_ExtendTopValue(
Top_p:TLQM_factorial_record_p);
var
s:TLQM_factorial_record_p;
begin
//若已经无高位，则退出
if (Top_p^.Value div 10)=0 then Exit;
//创建更高位-------------------------------------------------
new(s); Top_p^.HighPointer:=s; s^.HighPointer:=nil;
//将高位值存入s
s^.Value:=Top_p^.Value div 10;
//保留个位值
Top_p^.Value:=Top_p^.Value mod 10;
//继续扩展
Linklist_MultiplyValue_ExtendTopValue(s);
end;
//将链表中的值进行标准处理
//即：结果链表中的每个位只有一个个位数[0-9]
procedure TLQM_factorial_class.Linklist_MultiplyValue_Fluency;
var
s,p:TLQM_factorial_record_p;
begin
//一直循环到最高位（但最高位不在内）
p:=F_Head^.HighPointer;
//若不是最高位，则将本位的个位值保留，高位值进到高位
while p^.HighPointer<>nil do
begin
//s指向高一位
s:=p^.HighPointer;
s^.Value:=s^.Value+p^.Value div 10;
p^.Value:=p^.Value mod 10;
p:=p^.HighPointer;
end;
//将最高位的值分解到“另外扩展的”更高的位
//（注：当前指针已经指向最高位）
Linklist_MultiplyValue_ExtendTopValue(p);
end;
　
//将指定值与链表中的值相乘
procedure TLQM_factorial_class.Linklist_MultiplyValue(Value:integer);
begin
//将指定值与链表中的值相乘（未进行值的标准处理）
//即：结果链表中的每个位都有可能是多位数
Linklist_MultiplyValue_BlindMultiply(Value);
//将链表中的值进行标准处理
//即：结果链表中的每个位只有一个个位数[0-9]
Linklist_MultiplyValue_Fluency;
end;
//输出链表(注:由低位至高位)
function TLQM_factorial_class.Linklist_OutputString:WideString;
var
p:TLQM_factorial_record_p;
begin
Result:='';
p:=F_Head^.HighPointer;
while p<>nil do
begin
Result:=Result+IntToStr(p^.Value);
p:=p^.HighPointer;
end;
end;
//计算阶乘的函数
function TLQM_factorial_class.CaculateFactorial(UserValue:integer):WideString;
var
i:integer;
begin
//若为小于0的数的阶乘,返回字符串'-1'
if UserValue<0 then begin Result:='-1'; Exit; end;
//若为0或1的阶乘,返回字符串'1'
if (UserValue in [0,1]) then begin Result:='1'; Exit; end;
//计算函数的主体部分
for i:=UserValue downto 2 do
begin
Linklist_MultiplyValue(i);
end;
//输出链表(注:由低位至高位)
Result:=Linklist_OutputString;
end;
　
//析构函数
destructor TLQM_factorial_class.Destroy;
var
s,p:TLQM_factorial_record_p;
begin
//释放空间
p:=F_Head^.HighPointer;
while p<>nil do
begin
s:=p; p:=p^.HighPointer; Dispose(s);
end;
Dispose(F_Head);
inherited Destroy;
end;
end.