大数计算常用函数-白红宇

#include<stdio.h>

#include<string.h>

#include<memory.h>

#define MAX 10002

void reverse(char *p)

{//逆序存放

int i=(int)strlen(p),j;

char temp;

for(j=0;j<i/2;j++)

{

temp=p[j];

p[j]=p[i-j-1];

p[i-j-1]=temp;

}

int compare(char *a,char *b)

{//比较两正数大小

if(strlen(a)>strlen(b))return 1;

if(strlen(a)<strlen(b)) return -1;

if(strcmp(a,b)>0)return 1;

if(strcmp(a,b)<0)return -1;

return 0;

}

void cutzero(char *temp)

{//去首零

int i=0;

int flag=0;

if(temp[0]=='+'||temp[0]=='-')

{

i++;

flag=1;

}

while(temp[i]=='0')

i++;

int j=0;

if(flag)

temp[j++]=temp[0];

int len=(int)strlen(temp);

for(;i<=len;i++,j++)

{

temp[j]=temp[i];

}

if(temp[0]=='\0')

{

temp[0]='0';

temp[1]='\0';

}

void add(char *c,char *a,char *b)

{//a加b结果放入c中 a,b都为正数

char A[MAX],B[MAX];

if(strlen(a)<strlen(b))

{

strcpy(A,b); strcpy(B,a);

}

else

{

strcpy(A,a); strcpy(B,b);

}

reverse(A);

reverse(B);

int carry=0;//进位

int i=0,temp;

int flag=1;

while(A[i])

{

if(flag) temp=A[i]+B[i]-96;

else temp=A[i]-48;

c[i]=(temp+carry)%10+'0';

carry=(temp+carry)/10;

i++;

if(flag&&!B[i]) flag=0;

}

if(carry==0)

c[i]='\0';

else

{

c[i]=carry+'0';

c[i+1]='\0';

}

reverse(c);

}

void mul(char *c,char *a,char *b)

{//a乘b结果放入c中 a,b都为正数

char A[MAX],B[MAX];

if(a[0]=='0'||b[0]=='0')

{

c[0]='0'; c[1]='\0'; return;

}

memset(c,'0',MAX);

strcpy(A,a);

strcpy(B,b);

reverse(A);

reverse(B);

int carry;//进位

int i=0,j,temp1,temp2;

while(B[i])

{

j=0;

carry=0;

while(A[j])

{

temp1=(A[j]-48)*(B[i]-48);

temp2=c[i+j]-'0';

c[i+j]=(temp1+temp2+carry)%10+'0';

carry=(temp1+temp2+carry)/10;

j++;

}

if(carry!=0)

c[i+j]=carry+'0';

i++;

}

if(c[i+j-1]=='0')

c[i+j-1]='\0';

else

c[i+j]='\0';

reverse(c);

}

void sub(char *c,char *a,char *b)

{//a减b结果放入c中 a,b都为正数

char A[MAX],B[MAX];

int flag=1;

if(compare(a,b)<0) flag=0;

if(flag==0)

{

strcpy(A,b);strcpy(B,a);

}

else

{

strcpy(A,a);strcpy(B,b);

}

reverse(A);

reverse(B);

int carry=0;//借位

int i=0,temp;

int mark=1;

while(A[i])

{

if(mark)

temp=A[i]-B[i]-carry;

else

temp=A[i]-carry-48;

if(temp<0)

{

carry=1;temp+=10;

}

else

carry=0;

c[i++]=temp%10+'0';

if(mark&&!B[i])

mark=0;

}

if(c[i-1]=='0')

{

if(flag==0)

{

c[i-1]='-';

c[i]='\0';

}

else

c[i-1]='\0';

}

else

{

if(flag==0)

{

c[i]='-';c[i+1]='\0';

}

else

c[i]='\0';

}

reverse(c);

cutzero(c);

}

void div(char *d,char *m,char *a,char *b)

{// a/b 商d 余数m

//调用add sub mul

if(compare(a,b)<0)

{

d[0]='0';d[1]='\0';

strcpy(m,a);

return;

}

char A[MAX],B[MAX];

strcpy(A,a); strcpy(B,b);

char temp[MAX+1],havetry[MAX],tryd[2];

memset(temp,'\0',MAX+1);

int ina=strlen(B),ind=0,i,flag;

int len_A=(int)strlen(A);

strncpy(temp,A,ina);

while(ina<len_A+1)

{

flag=0;

while(compare(temp,B)<0)

{

if(ina==len_A)

{

flag=1;

d[ind++]='0';

break;

}

i=(int)strlen(temp);

temp[i++]=A[ina++];

temp[i]='\0';

cutzero(temp);

d[ind++]='0';

}

if(flag==1)

break;

if(strlen(temp)==strlen(B))

i=(temp[0]-'0')/(B[0]-'0'+1);

else

i=((temp[0]-'0')*10+temp[1]-'0')/(B[0]-'0'+1);

if(i<=1) i=2;

while(1)

{

tryd[0]=i+'0';

tryd[1]='\0';

mul(havetry,B,tryd);

if(compare(havetry,temp)>0) break;

i++;

}

i--;

d[ind++]=i+'0';

add(temp,temp,B);

sub(temp,temp,havetry);

i=strlen(temp);

temp[i++]=A[ina++];

temp[i]='\0';

cutzero(temp);

}

cutzero(temp);

strcpy(m,temp);

if(m[0]=='\0')

{

m[0]='0';m[1]='\0';

}

d[ind]='\0';

cutzero(d);

}

void transfer(char result[MAX],int n)

{//整数n->字符串reuslt

if(n==0)

{

result[0]='0';

result[1]='\0';

return;

}

int i=0,temp=n;

while(temp>0)

{

result[i++]=temp%10+'0';

temp=temp/10;

}

result[i--]='\0';

int length=(i+1)/2;

int j;

for(j=0;j<length;j++,i--)

{

temp=result[i];

result[i]=result[j];

result[j]=temp;

}

int re_transfer(char result[MAX])

{//字符串result->整数n

int count=0;

int i;

for(i=0;result[i];i++)

count=count*10+result[i]-'0';

return count;

}

void JieC(char result[MAX],int m)

{//计算m! ->result

strcpy(result,"1");

int i=2;

char temp1[MAX],temp2[MAX];

while(i<=m)

{

transfer(temp1,i);

mul(temp2,result,temp1);

strcpy(result,temp2);

i++;

}

void Cmn(char result[MAX],int m,int n)

{//计算C(m,n) (m>=n)

if(n>m/2) n=m-n;

strcpy(result,"1");

int i,j;

char temp1[MAX],temp2[MAX],temp3[MAX];

for(i=m,j=1;i>=m-n+1;i--,j++)

{

transfer(temp1,i);

mul(temp2,result,temp1);

transfer(temp1,j);

div(result,temp3,temp2,temp1);

}

int mod(char ch[],int n)

{

int i;

int len;

int result;

len=strlen(ch);

result=0;

for(i=0;i<len;i++)

result=(result*10+ch[i]-'0')%n;

return result;

}

char a[MAX],b[MAX];

char c[MAX];

int main()

{

int cas;

int r=1;

scanf("%d",&cas);

getchar();

while(cas--)

{

scanf("%s%s",a,b);

getchar();

add(c,a,b);

printf("Case %d:\n",r++);

printf("%s + %s = %s\n",a,b,c);

if(cas)

printf("\n");

}

return 1;

}

本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2007/03/09/669042.html，如需转载请自行联系原作者