数学加减法编程大整数加法c语言思路 _整数

我们知道，计算机内的数据表示只是一个有限字长的二进制序列，表达的十进制整数非常有限：
= 15 (十进制是个2位数，二进制是4位1)
= 255 (十进制是个3位数，二进制是8位1)
= 65535 (十进制是个5位数，二进制是32位1)
= 4294967295 (十进制是个10位数，二进制是32位1)
18446744073709551615 (十进制是个20位数，二进制是64位1)
可以看出，通常一位十进制数需要3.2位二进制数来表示。
相对于整型，数组或字符串可以表示更多的十进制位数，计算时做转换即可。或者链式存储数据块（如一个数据块存储4位数）。
对于浮点数，可以表示更大的数字，但精度有限。

浮点数的位数分为三部分：符号位、阶码、尾码；阶码决定值域，尾码决定精度。
float： 1bit（符号位） 8bits（指数位） 23bits（尾数位）
double： 1bit（符号位） 11bits（指数位） 52bits（尾数位）
于是，float的指数范围为-127~+128，而double的指数范围为-1023~+1024，并且指数位是按补码的形式来划分的。
其中负指数决定了浮点数所能表达的绝对值最小的非零数；而正指数决定了浮点数所能表达的绝对值最大的数，也即决定了浮点数的取值范围。

float和double的精度是由尾数的位数来决定的。浮点数在内存中是按科学计数法来存储的，其整数部分始终是一个隐含着的“1” ，由于它是不变的，故不能对精度造成影响。
float：2^23 = 8388608，一共七位，这意味着最多能有7位有效数字，但绝对能保证的为6位，也即float的精度为6~7位有效数字；
double：2^52 = 4503599627370496，一共16位，同理，double的精度为15~16位。（52/3.2≈16）

1 利用链式存储数据块来模拟大整数加数
首先采用一个带有表头结点的环形链来表示一个非负的超大整数，如果从低位开始为每个数字编号，则第1~4 位、第5~8 位……的每4 位组成的数字，依次放在链表的第1 个、第2 个……第n 结点中，不足4 位的最高位存放在链表的最后一个结点中，表头结点的值规定为-1 。例如：大整数“587890987654321”可用如下的带表头结点head 的链表表示。

文章插图
按照此数据结构，可以从两个表头结点开始，顺序依次对应相加，求出所需要的进位后，代入下一个结点的运算。

#include<stdio.h>#include<stdlib.h>#define HUNTHOU 10000typedef struct node{ int data; struct node *next;}NODE; /*定义链表结构*/NODE *insert_after(NODE *u,int num); /*在u结点后插入一个新的NODE，其值为num*/NODE *addint(NODE *p,NODE *q); /*完成加法操作返回指向*p+*q结果的指针*/void printint(NODE *s);NODE *inputint(void);void main(){ NODE *s1,*s2,*s; NODE *inputint(), *addint(), *insert_after(); puts("*********************************************************"); puts("* This program is to calculate *"); puts("* the addition of king sized positive integer. *"); puts("*********************************************************"); printf(" >> Input S1= "); s1=inputint(); /*输入被加数*/ printf(" >> Input S2= "); s2=inputint(); /*输入加数*/ printf(" >> The addition result is as follows.\n\n"); printf(" S1= "); printint(s1); putchar('\n'); /*显示被加数*/ printf(" S2= "); printint(s2); putchar('\n'); /*显示加数*/ s=addint(s1,s2); /*求和*/ printf(" S1+S2="); printint(s); putchar('\n'); /*输出结果*/ printf("\n\n Press any key to quit..."); getch();}NODE *insert_after(NODE *u,int num){ NODE *v; v=(NODE *)malloc(sizeof(NODE)); /*申请一个NODE*/ v->data=http://www.baifabohui.com/smjk/num; /*赋值*/ u->next=v; /*在u结点后插入一个NODE*/ return v;}NODE *addint(NODE *p,NODE *q) /*完成加法操作返回指向*p+*q结果的指针*/{ NODE *pp,*qq,*r,*s,*t; int total; // 两数相加的和 int remain; // total%10000的结果 int carry; // total/10000的结果 pp=p->next; qq=q->next; s=(NODE *)malloc(sizeof(NODE)); /*建立存放和的链表表头*/ s->data=-1; t=s; carry=0; /*carry:进位*/ while(pp->data!=-1&&qq->data!=-1) /*均不是表头*/ { total=pp->data+qq->data+carry; /*对应位与前次的进位求和*/ remain=total%HUNTHOU; /*求出存入链中部分的数值 */ carry=total/HUNTHOU; /*算出进位*/ t=insert_after(t,remain); /*将部分和存入s向的链中*/ pp=pp->next; /*分别取后面的加数*/ qq=qq->next; } r=(pp->data!=-1)?pp:qq; /*取尚未自理完毕的链指针*/ while(r->data!=-1) /*处理加数中较大的数*/ { total=r->data+carry; /*与进位相加*/ remain=total%HUNTHOU; /*求出存入链中部分的数值*/ carry=total/HUNTHOU; /*算出进位*/ t=insert_after(t,remain); /*将部分和存入s指向的链中*/ r=r->next; /*取后面的值*/ } if(carry) t=insert_after(t,1); /*处理最后一次进位*/ t->next=s; /*完成和的链表*/ return s; /*返回指向和的结构指针*/}NODE *inputint(void) /*输入超长正整数*/{ NODE *s,*ps,*qs; struct remain { int num; struct remain *np; }*p,*q; int i,j,k; long sum; char c; p=NULL; /*指向输入的整数 ， 链道为整数的最低的个位 ， 链尾为整数的最高位*/ while((c=getchar())!='\n') /*输入整数 ， 按字符接收数字*/ if(c>='0'&&c<='9') /*若为数字则存入*/ { q=(struct remain *)malloc(sizeof(struct remain)); /*申请空间*/ q->num=c-'0'; /*存入一位整数*/ q->np=p; /*建立指针*/ p=q; } s=(NODE *)malloc(sizeof(NODE)); s->data=-1; /*建立表求超长正整数的链头*/ ps=s; while(p!=NULL) /*将接收的临时数据链中的数据转换为所要求的标准形式*/ { sum=0;i=0;k=1; while(i<4&&p!=NULL) /*取出低四位*/ { sum=sum+k*(p->num); i++; p=p->np; k=k*10; } qs=(NODE *)malloc(sizeof(NODE));/*申请空间*/ qs->data=sum; /*赋值，建立链表*/ ps->next=qs; ps=qs; } ps->next=s; return s;}void printint(NODE *s){ if(s->next->data!=-1) /*若不是表头，则输出*/ { printint(s->next); /*递归输出*/ if(s->next->next->data==-1) printf("%d",s->next->data); else{ int i,k=HUNTHOU; for(i=1;i<=4;i++,k/=10) putchar('0'+s->next->data%(k)/(k/10)); } }}/*********************************************************** This program is to calculate ** the addition of king sized positive integer. ********************************************************** >> Input S1= 1234567890 >> Input S2= 987654321123456789 >> The addition result is as follows. S1= 1234567890 S2= 987654321123456789 S1+S2=987654322358024679 Press any key to quit... */

2 大数相乘
【数学加减法编程大整数加法c语言思路】当位数超过整数数据类型的两个大数相乘时，大数可以使用字符串存储，模拟手工做乘法的过程（不同的是，先从高位开始），将每一位相乘的结果先不做进位，累加到一个数组对应下标的元素中，最后做进位处理。
以下是模拟过程：

文章插图
使用双重循环得出TempResult[1]＝10 ， TempResult[2]＝32，TempResult[3]＝24
数组逐元素逆序迭代处理进位和求余：

 for (i = alen + blen; i >=0; i--) // 处理进位、各数求10的模数，//TempResult[alen + blen]是结果的最低位，逆序处理 { if (TempResult[i] >= 10) { TempResult[i - 1] += TempResult[i] / 10; // i-1位是i位的高位 TempResult[i] %= 10; } }

然后将整数数组逐项赋值给字符数组即可。
code:

#include<stdio.h> #include<stdlib.h>#include<string.h>// 因为大数过长，所以采用字符串存储， 故要将字符串中字符转化为数字char *BigDataMutliply(char *DataA, char *DataB){ int alen = strlen(DataA); int blen = strlen(DataB); size_t size = sizeof(int)*(alen + blen); int *TempResult = (int *)malloc(size); // 动态数组存储两数各个位相乘的结果 char *Result = (char *)malloc(sizeof(char)*(alen + blen + 1)); memset(TempResult, 0, size); for (int i=0 ; i<alen; i++) // 从高位开始，迭代出各个位的值存储到数组对应的位 { for (int j=0; j<blen; j++) TempResult[i+j+1] += (DataA[i] - '0')*(DataB[j] - '0');// 最高位留出一位，待进位 } for (i = alen + blen; i >=0; i--) // 处理进位、各数求10的模数 { if (TempResult[i] >= 10) { TempResult[i - 1] += TempResult[i] / 10; TempResult[i] %= 10; } } i=0; while (TempResult[i] == 0) // 计算数组不包括前导0的位数 i++; int j; for(j=0; i < alen + blen + 1; j++, i++)// 将整数数组转换到字符数组 { Result[j] = TempResult[i] + '0'; } Result[j-1] = '\0'; // 最后位置\0 return Result;}int main(){ char *A = "111111111"; char *B = "111111111"; char *res = BigDataMutliply(A, B); printf("res = %s\n",res); // 12345678987654321 system("pause"); return 0;}

3 大数阶乘
对于一个较小的数的阶乘，较容易通过循环和递归去实现。
对于一个较大的数的阶乘，其结果因为位数较多，基本数据类型无法存储。可以考虑用一个数组a来保存结果的每一位。如计算7的阶乘，模拟过程如下：

文章插图

如8!=8*7!=8*5040
a[0] =8*0 = 0
a[1] = 8*a[1]+a[0]/10 = 32
a[0] %= 10 = 0
a[2] = 8*a[2]+a[1]/10 = 3
a[1] %= 10 = 2
a[3] = 8*a[3]+a[2]/10 = 40
a[2] %/10 = 3
a[4] = 8*a[4]+a[3]/10 = 4
a[3] %= 10 = 0
a[4] = 4
// 40320

以a[0]为基准，a[i] = n*a[i] + a[i-1]/10，a[i-1] = a[i-1]%10逐次迭代。
直接看代码和注释：

#include <iostream>using namespace std;#define N 10000long facLoop(int n) // 循环实现小整数的阶乘{ long sum=1; for(int i=2; i<=n; i++) sum*=i; return sum;}long facRecur(int n) // 递归实现小整数的阶乘{ if(n==0) return 1; else return n*facRecur(n-1);}void facBig(int m){ /* 大整数阶乘，使用数组来存储每一位： 1 初始值a[0]=1； 2 i=1,2,…,m循环； 3 j从1开始循环 。逐位乘i并加上前一位的进位，并将前一位只保留个位数； */ int a[N]={1}; // a[0]=1，其余各位全为0 for(int i=2; i<=m; i++) // 阶乘数的循环，如32的阶乘，会连续乘32次 { a[0] *= i; // 个位做为基准位 for(int j=1; j<N; j++) // 整数数组从低位(第2位)开始循环如6!=6*5!=6*120 { a[j] = a[j]*i +a[j-1]/10; // 逐位乘i并加上前一位的进位 a[j-1] %=10; // 前一位只保留个位数 } } int n = N-1; while(a[n]==0) n--; // 从最高位找到第一个非零数 cout<<m<<"!有"<<n+1<<"位,"<<"=\n"; for(;n>=0; n--) cout<<a[n]; cout<<""<<endl;}int main(){ int m; // 需要计算阶乘的数 cout<<"请输入需要计算阶乘的数："; cin>>m; cout<<facLoop(m)<<endl; cout<<facRecur(m)<<endl; facBig(m); getchar();getchar(); return 0;}/*请输入需要计算阶乘的数：1247900160047900160012!有9位,=479001600 请输入需要计算阶乘的数：22 -522715136 -522715136 22!有22位,= 1124000727777607680000*/

文章插图

请输入需要计算阶乘的数：55500555!有1284位,=661408560927794670909833167124276990212353194561078966630610091508066518398462938708570165931453818774346806677937487622941296716409901122180791183381615199180133649323135568584492485536333258769584469786383591661922104266566863913614070698138881545530808522346156055053115762262612679476256481322688203567171111038254916285768948868390683387427561794062346854491689633073215348773710363218016157511181863057926134577070731221701301152592821760868454925199903505386017787199554004695300736714548162986647886019771379144075642172619449355885906311490931562018599832173006150698910081357711177369686310362939324425024584999311539904643730800189147272918915911770251276375152459026027462464002063813902395684537655374791000270699823191370607631655257869634515506590089013974314269381678319888713892407305906053693865079154285101747723299382026182512365914527438847783156831674629869733219475045947728356608604070725171727115599864469722301348700056888092787342824689113236014679770929700834913475709726807511726110607658874785711823552896770088837953463376048502815279955957922924689302538415337162205637471098765281762231617571867644711936978426265600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

文章插图
－End－

数学加减法编程 大整数加法c语言思路

数学加减法编程大整数加法c语言思路