手指算法教程10以内加法（趣味数学与编程）

我们知道，计算机内的数据表示只是一个有限字长的二进制序列，表达的十进制整数非常有限：

= 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 10000 typedef 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=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; // total000的结果 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 大数相乘

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

以下是模拟过程：

使用双重循环得出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]逐次迭代。

直接看代码和注释：

#include <iostream> using namespace std; #define N 10000 long 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; } /* 请输入需要计算阶乘的数：12 479001600 479001600 12!有9位,= 479001600 请输入需要计算阶乘的数：22 -522715136 -522715136 22!有22位,= 1124000727777607680000 */

请输入需要计算阶乘的数：555 0 0 555!有1284位,= 66140856092779467090983316712427699021235319456107896663061009150806651839846293 87085701659314538187743468066779374876229412967164099011221807911833816151991801 33649323135568584492485536333258769584469786383591661922104266566863913614070698 13888154553080852234615605505311576226261267947625648132268820356717111103825491 62857689488683906833874275617940623468544916896330732153487737103632180161575111 81863057926134577070731221701301152592821760868454925199903505386017787199554004 69530073671454816298664788601977137914407564217261944935588590631149093156201859 98321730061506989100813577111773696863103629393244250245849993115399046437308001 89147272918915911770251276375152459026027462464002063813902395684537655374791000 27069982319137060763165525786963451550659008901397431426938167831988871389240730 59060536938650791542851017477232993820261825123659145274388477831568316746298697 33219475045947728356608604070725171727115599864469722301348700056888092787342824 68911323601467977092970083491347570972680751172611060765887478571182355289677008 88379534633760485028152799559579229246893025384153371622056374710987652817622316 17571867644711936978426265600000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000 0000

－End－

,