1. 首頁 > 生活百科 > >

數學加減法編程 大整數加法c語言思路

生活經驗整數

我們知道，計算機內的數據表示只是一個有限字長的二進制序列，表達的十進制整數非常有限：
= 15 (十進制是個2位數，二進制是4位1)
= 255 (十進制是個3位數 ， 二進制是8位1)
= 65535 (十進制是個5位數，二進制是32位1)
= 4294967295 (十進制是個10位數 ， 二進制是32位1)
18446744073709551615 (十進制是個20位數，二進制是64位1)
可以看出 ， 通常一位十進制數需要3.2位二進制數來表示 。
相對于整型，數組或字符串可以表示更多的十進制位數，計算時做轉換即可 ?；蛘哝準酱鎯祿K（如一個數據塊存儲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 的鏈表表示 。
數學加減法編程 大整數加法c語言思路

文章插圖
按照此數據結構，可以從兩個表頭結點開始 ， 順序依次對應相加，求出所需要的進位后，代入下一個結點的運算 。
#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語言思路】當位數超過整數數據類型的兩個大數相乘時，大數可以使用字符串存儲，模擬手工做乘法的過程（不同的是，先從高位開始），將每一位相乘的結果先不做進位，累加到一個數組對應下標的元素中，最后做進位處理 。
以下是模擬過程：
數學加減法編程 大整數加法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的階乘，模擬過程如下：
數學加減法編程 大整數加法c語言思路

文章插圖
如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*/
數學加減法編程 大整數加法c語言思路

文章插圖
請輸入需要計算階乘的數：55500555!有1284位,=661408560927794670909833167124276990212353194561078966630610091508066518398462938708570165931453818774346806677937487622941296716409901122180791183381615199180133649323135568584492485536333258769584469786383591661922104266566863913614070698138881545530808522346156055053115762262612679476256481322688203567171111038254916285768948868390683387427561794062346854491689633073215348773710363218016157511181863057926134577070731221701301152592821760868454925199903505386017787199554004695300736714548162986647886019771379144075642172619449355885906311490931562018599832173006150698910081357711177369686310362939324425024584999311539904643730800189147272918915911770251276375152459026027462464002063813902395684537655374791000270699823191370607631655257869634515506590089013974314269381678319888713892407305906053693865079154285101747723299382026182512365914527438847783156831674629869733219475045947728356608604070725171727115599864469722301348700056888092787342824689113236014679770929700834913475709726807511726110607658874785711823552896770088837953463376048502815279955957922924689302538415337162205637471098765281762231617571867644711936978426265600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
數學加減法編程 大整數加法c語言思路

文章插圖
－End－