大数运算——加法减法
|
http://www.cnblogs.com/leader/archive/2013/01/28/2880643.html 第一篇博文有点小鸡冻。在哈工程寒假集训中第一次模拟中唯一一道对我有价值的题就是大数加法，随后的几次模拟中大数运算不断，可见这是我们必须掌握的技能，本人智商较低，先讲解下大数加法减法，乘除阶乘或者结合其他知识的大数运算日后定会奉上。 究竟为什么要用大数加法呢。我们来看下数据： bool型为布尔型，占1个字节，取值0或1。 BOOL型为int型，一般认为占4个字节，取值TRUE/FALSE/ERROR。 sbyte型为有符号8位整数，占1个字节，取值范围在128~127之间。 bytet型为无符号16位整数，占2个字节，取值范围在0~255之间。 short型为有符号16位整数，占2个字节，取值范围在-32,768~32,767之间。 ushort型为无符号16位整数，占2个字节，取值范围在0~65,535之间。 int型为有符号32位整数，占4个字节，取值范围在-2,147,483,648~2,647之间。 uint型为无符号32位整数，占4个字节，取值范围在0~4,294,967,295之间。 long型为64位有符号整数，占8个字节，取值范围在9,223,372,036,854,775,808~9,807之间。 ulong型为64位无符号整数，占8个字节，取值范围在0~18,446,744,073,709,551,615之间。 float型为32位单精度实数，占4个字节，取值范围3.4E+10的负38次方~3.4E+10的38次方之间。 double型为64位实数，占8个字节，取值范围1.7E+10的负308次方~1.7E+10的正308次方。 ? ? ? ??所以999999999999999999999999999999999999999+888888888888888888888888888888888888888888888=？ ? ? ? ? ? ? ? ? ?? 大数加法 ? ? ? ?基本思想：数组要多长有多长啊，随便定义个a[1000000],不就OK啦！ ? ? ? ? ? ?我都能写出来，当然代码是非常简单了啦，我说下要注意的几个问题： 1.? ? ?判断最后数组的长度 ? ? 2. ? ? 去掉前导零 ?
1 void Add(char s1[],char s2[]) //需要两个字符串参数&&无返回值 2 { 3 int num1[M],nm2[M]; 4 int i,j; 5 len1=strlen(s1); 6 len2=strlen(s2); 7 for(i=len1-1,j=0;i>=0;i--)//num[0]保存的是低位 8 num1[j++]=s1[i]-'0'; 9 for(i=len2-1,j=0;i>=0;i--) 10 num2[j++]=s2[i]-'0'; 11 for(i=0;i<M;i++) 12 { 13 num1[i]+=num2[i]; 14 if(num1[i]>9) 15 { 16 num1[i]-=10; 17 num1[i+1]++; 18 } 19 } 20 21 for(i=M;(i>=0)&&(num1[i]==0);i--)//找到第一个不是零的数 22 { 23 if(i>=0) 24 for(;i>=0;i--) 25 printf("%d",num1[i]); 26 else 27 printf("0n") 28 }
? ?当然方法不止一种。如果说上面这个清晰的话，那下面这个应该是省了点内存。 1 void Add(char a[],char b[],char d[]) 2 { 3 char c[10001]; 4 int lena=strlen(a),lenb=strlen(b); 5 int i,j,len; 6 len=lena>lenb?lena:lenb; 7 len++; 8 c[0]=' '; 9 for(i=1;i<=len;i++)c[i]='0'; 10 for(i=1;i<=lena;i++)c[i]+=a[lena-i]-48; 11 for(i=1;i<=lenb;i++)c[i]+=b[lenb-i]-48; 12 for(i=0;i<=len;i++) 13 if(c[i]>57) 14 { 15 c[i]-=10; 16 c[i+1]++; 17 } 18 19 for(i=len;i>1;i--) 20 if(c[i]==48)len--; 21 else break; 22 for(i=0;i<=len;i++) 23 d[i]=c[len-i]; 24 } 好吧，这个代码还有个好处就是让我记住了‘0’和‘9’的ASCII码是48和57。? ? ? ? ? ? ? ? ? ? ? ? ? 大数减法 ?减法的算法也是从低位开始减，先要判断减数和被减数那一个位数长，减数位数长是正常减；被减数位数长，则被减数减减数，最后还要加上负号；两个位数长度相等时，最好比较那一个数字大，否则负号会处理的很繁琐；处理每一项时，如果前一位相减有错位，就先减上一位的错位，无则不减，再去判断是否能够减开被减数，如果减不开，就要借位后再去减，同时错位为1，否则置错位为0. 1 //d2 > d1，如果需要比较大小自己加一个不麻烦。 2 void dec(char *d1,char *d2,char *out) 3 { 4 int len_min = strlen(d1); 5 int len_max = strlen(d2); 6 int last_j = 0; //最关键的错位 7 while(len_min > 0) 8 { 9 int dd1 = d1[len_min - 1] - '0'; 10 int dd2 = d2[len_max - 1] - '0'; 11 if (last_j) dd2 = dd2 - 1; 12 last_j = dd2 >= dd1 ? 0 : 1; 13 dd2 = dd2 >= dd1 ? dd2 : dd2 + 10; 14 out[len_max] = (dd2 - dd1) + '0'； 15 len_max -- ; 16 len_min -- ; 17 } 18 while(len_max > 0) 19 { 20 int dd2 = (d2[len_max -1] - '0'); 21 if (last_j) dd2 = dd2 - 1; 22 last_j = dd2 >= 0 ? 0 : 1; 23 dd2 = dd2 >= 0 ? dd2 : dd2 + 10; 24 out[len_max] = dd2 + '0'; 25 len_max --; 26 } 27 if (last_j) 28 out[0] ='1'; 29 else 30 out[0] ='0'; 31 } 哦了。就这么多了。大数乘法除法神马的敬请期待！ （编辑：源码网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
