洛谷1601 A+B Problem(高精)
本题地址:http://www.luogu.org/problem/show?pid=1601
题目背景
无
题目描述
高精度加法,x相当于a+b problem,不用考虑负数
输入输出格式
输入格式:
分两行输入a,b<=10^500
输出格式:
输出只有一行,代表A+B的值
输入输出样例
输入样例#1:
1
1
输出样例#1:
2
题解
高精度
题目非常简单,但数据规模却非常大,显然是常规数据类型无法承受的,因此不能用普通做法来完成这道题。
我们可以借助高精度。高精度运算实际上是运用了模拟的思想,对现实数学竖式运算的过程进行了模拟。
因此,我们可以用数组来存储一个大规模数据,并对其运算,数组的运算规则如同算术的竖式运算(注意相加进位),步骤如下:
1.求出和的最小可能位数。
2.从低位到高位,逐位相加。
3.从低位到高位处理进位,满十进一。
4.处理最高位的进位。
5.输出结果。
下面附上代码。
代码
- var i,l1,l2:longint;
- a,b,c:array [1..502] of longint;
- ch:array [1..502] of char;
- begin
- repeat
- inc(l1);
- read(ch[l1]);
- until eoln;
- for i:=1 to l1 do a[i]:=ord(ch[l1-i+1])-48;
- readln;
- repeat
- inc(l2);
- read(ch[l2]);
- until eoln;
- for i:=1 to l2 do b[i]:=ord(ch[l2-i+1])-48;
- if l1<l2 then l1:=l2;//加法运算要进行max(l1,l2)次,这里用l1保存运算次数
- for i:=1 to l1 do
- begin
- inc(c[i],a[i]+b[i]);//还要加上可能有的从低位进上来的值
- if c[i]>=10 then//进位
- begin
- dec(c[i],10);
- inc(c[i+1]);
- end;
- end;
- if c[l1+1]>0 then inc(l1);//检测最高位是否进位
- for i:=l1 downto 1 do write(c[i]);
- end.
(本文系笔者原创,未经允许不得转载)