17 高精度整数

N的阶乘

http://www.nowcoder.com/practice/f54d8e6de61e4efb8cce3eebfd0e0daa

理论说明

我们常用如下结构体保存一个高精度整数：

struct bigInteger {
	int digit[1000];
    int size;
};

其中digit数组用来保存大整数中每若干位的数字，这里我们暂且使用每4位为一个单位保存，size为digit数组中第一个我们没使用过的数组单元（即下一个我们可以使用的数组单元）。以整数123456789为例，当我们使用该数据结构体来保存该值时，其结果是这样的：digit[0]=6789;digit[1]=2345; digit[2]=1;size=3;

题目来源和说明

2010年华中科技大学计算机研究生机试真题

题目描述

实现一个加法器，使其能够输出a+b的值

输入说明

输入包括两个数a和b，其中a和b的位数不超过1000位

输出说明

输出可能有多组测试数据，对于每组数据，输出a+b的值。

样例展示

输入：
2 6
10000000000 10000000000000000
输出：
10000010000000000

C++代码

#include<iostream>
#include<string.h>
using namespace std;

struct bigInteger {
    int digit[1000];
    int size;
    void init() {
        for(int i=0;i<1000;i++)digit[0]=0; //所有位清零
        size=0; //下一个未使用数组单元未0
    }
    void set(char str[]) { //从字符串中提取整数
        init();
        int L=strlen(str);
        for(int i=L-1,j=0,t=0,c=1;i>=0;i--) {
            t+=(str[i]-'0')*c;
            j++;
            c=c*10;
            if(j==4 || i==0) {
                digit[size++]=t;
                j=0;
                t=0;
                c=1;
            }
        }
    }
    void output() { //将该高精度整数输出
        for(int i=size-1;i>=0;i--) {
            if(i!=size-1) printf("%04d",digit[i]);
            else printf("%d",digit[i]);
        }
        printf("\n");
    }
    bigInteger operator+(const bigInteger &A) const { //加法
        bigInteger ret;
        ret.init();
        int carry=0;
        for(int i=0;i<A.size || i<size;i++) {
            int temp=A.digit[i]+digit[i]+carry;
            carry=temp/10000;
            temp%=10000;
            ret.digit[ret.size++]=temp;
        }
        if(carry!=0) { //计算结束后若最高位有进位
            ret.digit[ret.size++]=carry;
        }
        return ret; //返回
    }
}a,b,c;

char str1[1002],str2[1002];

int main() {
    while(scanf("%s%s",str1,str2)!=EOF) { //输入
        a.set(str1);
        b.set(str2);
        c=a+b;
        c.output();
    }
    return 0;
}

C++代码

高校夏令营机试训练文章被收录于专栏

Leetcode题目太多，不知道如何准备高校夏令营？欢迎关注本专栏，和本小白一起准备夏令营吧！本专题的规划如下：截止到4月下旬：以王道考研为依托，提供夏令营机考的准备计划，打好基础截止到5月中旬：以剑指offer进一步加强本专题的内容如下： 1. 给出题目的在线测试链接，方面您检查代码的正确性 2. 给出题解