大数运算-(加、减、乘)

大数其实和一般数字的区别在于大数的存储。一般数字可以用已有类型表示,如int。但是大数动不动100位,这样的话大数用什么存储已然是个问题。我仔细查找了下,大多数要么用char数组,要么用string表示。有大数了,那么它的计算怎么写?和普通四则运算一致。

1.加法

以十进制计算符合我们的日常习惯。同时暂且不考虑正负数的问题。那么就以两个正的大数相加为例,类比普通十进制的加法,就是从个位依次相加,和超过10就进位。看起来也不难,无非就是个位相加,超十进一。那么问题的重点就在于我们从低位相加没问题,什么时候停止相加,结果保存在哪,进位怎么处理?

当然以两个数的最小长度为相加终止条件,进位用一个变量表示即可。下面是参考代码:

注意数的低位高位保存的顺序自己要约定好。

//0的ASCII码是48
void Add(char a[],char b[],char d[])
{
   char c[10001];
   int lena=strlen(a),lenb=strlen(b);
   int i,j,len;
   len=max(lena,lenb);
   len++;
   c[0]='\0';
   for(i=1;i<=len;i++)c[i]='0';
   for(i=1;i<=lena;i++)c[i]+=a[lena-i]-48;
   for(i=1;i<=lenb;i++)c[i]+=b[lenb-i]-48;
   for(i=0;i<=len;i++)
   if(c[i]>57)
   {
     c[i]-=10;
     c[i+1]++;
    }

    for(i=len;i>1;i--)
      if(c[i]==48)len--;
      else break;
    for(i=0;i<=len;i++)
        d[i]=c[len-i];
 }

那么符号问题怎么解决呢?联系我们平常的运算,如果两个数符号相同,那么忽略符号进行两数相加,结果的符号相同。两数符号不同时,可以等效于做减法。

2.减法

同样的类比,我们是从个位相减,不够减向高位借一当十。这里我多说一句,看见很多人搞混。被减数是第一个数,键鼠是第二个数。是以“-”号运算符分开的。我们通常选取两个数中较长的数作为被减数。从低位向高位按位相减。

<span style="font-size:18px;">//假设d2的长度大于d1
void dec(char *d1, char *d2, char *out)
{
    int len_min = strlen(d1);
    int len_max = strlen(d2);
    int last_j = 0;     //最关键的错位
    while(len_min > 0)
    {
        int dd1 = d1[len_min - 1] - '0';
        int dd2 = d2[len_max - 1] - '0';
        if (last_j) dd2 = dd2 - 1;
        last_j = dd2 >= dd1 ? 0 : 1;
        dd2 = dd2 >= dd1 ? dd2 : dd2 + 10;
        out[len_max] = (dd2 - dd1) + '0';
        len_max -- ;
        len_min -- ;
    }
    while(len_max > 0)
    {
        int dd2 = (d2[len_max -1] - '0');
        if (last_j) dd2 = dd2 - 1;
        last_j = dd2 >= 0 ? 0 : 1;
        dd2 = dd2 >= 0 ? dd2 : dd2 + 10;
        out[len_max] = dd2 + '0';
        len_max --;
    }
    if (last_j)
          out[0] ='1';
    else
          out[0] ='0';
}</span>

最后是设置标志位,负数为1,正数为0。

3.乘法

乘法是这样的,如12*21。个位乘个位,个位乘十位相加求和。如果将大数从个位开始标注索引0,1,2,3....n。只要两数的索引和相同就相加到第i+j位,和超过10则进位。如下:

void Mul(char a[],char b[],char c[])//大数乘法
{
    int i,j;
    int alen=strlen(a),blen=strlen(b);
	int Len=max(alen,blen);
    for(i=0; i<Len; i++) c[i]=0;
    for(i=0; i<alen; i++)
        for(j=0; j<blen; j++) //处理进位
        {
            c[i+j]+=a[i]*b[j];
            if(c[i+j]>=10)
            {
                c[i+j+1]+=c[i+j]/10;
                c[i+j]%=10;
            }
        }
}

总之,我写的比较简单,但思想是这样的。

时间: 08-03

大数运算-(加、减、乘)的相关文章

opencv学习之路(8)、基本图像运算——加减与或

一.图像加法 1 #include<opencv2/opencv.hpp> 2 #include<iostream> 3 using namespace cv; 4 using namespace std; 5 6 void main(){ 7 Mat img1=imread("E://1.jpg"); 8 Mat img2=imread("E://2.jpg"); 9 Mat dst;//存储结果 10 imshow("img1&

常用数据结构算法 : 大数的加减

package wellhold.algorithm.bigInteger; public class BigDataPlus { public static void main(String[] args) { System.out.println(Plus("92321231", "12345123123")); } public static String Plus(String num1,String num2) { num1=new StringBuffe

大数加减乘法

大数的相关计算问题一直是编程比赛常考的题目,在蓝桥杯比赛之前又把大数的加减乘法做了一遍.大数除法比较难,还没有去尝试实现,以后有机会了再继续补全好了. 算法分析:三种方法相似,都是按位操作,动态存储.处理好输入数据后,对每一位的逐个操作,很容易得到答案. 大数加法 #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #define MAX 1010 using n

字符串大数加减运算问题

这里自己利用STL模板中的容器和链表实现字符串大数加减运算. 1 #include<iostream> 2 #include<vector> 3 #include<list> 4 using namespace std; 5 6 list<char> Input_Number(list<char> ilist)//输入链表字符串,以‘#’作为结束符 7 { 8 cout<<"please Input string ,end

POJ 2756 Autumn is a Genius 使用string的大数加减

本题就是说一个小神童,能计算加减法. 不过题目知识说这个小神童,到底有多神,要我们自己发现. 因为最后给出的数据非常非常巨大,听说接近50k就是超过50000个数位相加,可想而知他多神. 看来题目也是考IQ啊! 如果以为是超级水题,按照一般加减法做,肯定是WA了. 这里给出使用string的加减法运算,因为string是长度可增可减的,所以不管是多少位,只要内存支持,那么本算法都可以支持了.也可以使用vector这些容器.不过string应该更加省点内存. 注意: POJ比较讨厌的就是不支持C+

【算法】大数加减

超长的整型加减法可以用数组int来存储,每个单元可以存储1~9位数字,然后模拟手算过程 大数乘除法,稍复杂,(挖坑)续更.. ====================分割线==================== 1 /************************************************* 2 Copyright: CheerM 3 Author: CheerM 4 Date: 2016-11-02 5 Description: 实现超长int型的加减运算.输入任意长

大数加减1——将两个数均前后倒置,以对齐最低位

#include <stdio.h> //将读入的数据存储到num[1]~num[x]中,num[0]表示存入数据的长度. void read(int num[]) { int i; char ch; for (i = 0; i<500; i++) num[i] = 0; i = 1; while ((ch = getchar()) != '\n') { num[i] = ch - '0'; i++; num[0]++; } } //将数据num[]中的数翻转,以便计算 void rev

常见的编程问题(一)少大数加减

存储区的概念 常见的存储区域可分为: 栈 由编译器在需要的时候分配,在不需要的时候自动清除的变量的存储区.里面的变量通常是局部变量.函数参数等. 堆 由new分配的内存块,他们的释放编译器不去管,由我们的应用程序去控制,一般一个new就要对应一个delete.如果程序员没有释放掉,程序会一直占用内存,导致内存泄漏,在程序结束后,操作系统会自动回收. 由malloc等分配的内存块,它和堆是十分相似的,不过它是用free来释放分配的内存. 全局/静态存储区 全局变量和静态变量被分配到同一块内存中,在

大数加减乘模板

大数加法: 1 #include <stdio.h> 2 3 #include <string.h> 4 5 #define M 100 //定义了数量M是100作为数组初始化的数量 6 7 8 9 int main() 10 11 { 12 13 int i, j, len_s1, len_s2; // len_s1是字符数组s1的长度, len_s2是字符数组s2的长度, 14 15 char s1[M], s2[M]; 16 17 int num1[M] = {0}; //

转:JS日期加减,日期运算

原文 出处http://hi.baidu.com/tonlywang/item/685fba8933a2a756e73d1950 一.日期减去天数等于第二个日期 function cc(dd,dadd) ...{ //可以加上错误处理 var a = new Date(dd) a = a.valueOf() a = a - dadd * 24 * 60 * 60 * 1000 a = new Date(a) alert(a.getFullYear() + "年" + (a.getMon