求NOIP的高精度加法计算

计算高精度加法~

把输入的数字看成是字符，再用小学学的加法的规则来实行一步一步的加法运算，最后输出的也是字符，这样占用的空间又少算起来又快，而且不论多长都可以算
#include
#include
#define MAX_LEN 80
int an1[MAX_LEN+10];
int an2[MAX_LEN+10];
char szLine1[MAX_LEN+10];
char szLine2[MAX_LEN+10];
int main()
{
scanf("%s",szLine1);
scanf("%s",szLine2);
int i,j;
memset(an1,0,sizeof(an1));
memset(an2,0,sizeof(an2));
int nLen1=strlen(szLine1);
j=0;
for(i=nLen1-1;i>=0;i--)
an1[j++]=szLine1[i]-'0';
int nLen2=strlen(szLine2);
j=0;
for(i=nLen2-1;i>=0;i--)
an2[j++]=szLine2[i]-'0';
for(i=0;i<MAX_LEN;i++){
an1[i]+=an2[i];//逐位相加
if(an1[i]>=10){//判断是否要进位
an1[i]-=10;
an1[i+1]++;//进位
}
}
bool bStartOutput =false;//此变量用于跳过多余的0
for(i=MAX_LEN;i>=0;i--){
if(bStartOutput)
printf("%d",an1[i]);
else if(an1[i]){
printf("%d",an1[i]);
bStartOutput=true;
}
}
ptintf("
");
return 0;
}

if(n==1)
有点问题，因为你没有给n赋初值，所以n的值不确定，也就是说可能为1，那该if语句就失效了。
另外，其实根本就没必要事先比较s1和s2的长度，模仿递增向量的合并方法，先计算长度相同的部分，之后计算剩余部分。
我用c++的string字符串写了一个，你参考下。
#include
#include
using
namespace
std;
void
Reverse(string
&
str);
void
AddInt(string
&
c,
string
a,
string
b);
int
main()
{
string
a,
b,
c;
cin
>>
a
>>
b;
AddInt(c,
a,
b);
cout
<<
a
<<
"
+
";
cout
<<
b
<<
"
=
"
<<
endl;
cout
<<
c
<<
endl;
system("pause");
return
0;
}
void
Reverse(string
&
str)
{
int
left,
right;
left
=
0;
right
=
str.size()-1;
while
(left
<
right)
{
char
ch
=
str[left];
str[left]
=
str[right];
str[right]
=
ch;
left++;
right--;
}
}
void
AddInt(string
&
c,
string
a,
string
b)//模仿递增向量的合并方法
{
c.resize(0);
Reverse(a);
Reverse(b);
//逆序计算a+b，则从低位开始计算
int
i,
carry;
i
=
carry
=
0;
while
(i
<
a.size()
&&
i
<
b.size())
{
c
+=
(a[i]-'0'
+
b[i]-'0'
+
carry)
%
10
+
'0';
carry
=
(a[i]-'0'
+
b[i]-'0'
+
carry)
/
10;
i++;
}
while
(i
<
a.size())
{
c
+=
(a[i]-'0'
+
carry)
%
10
+
'0';
carry
=
(a[i]-'0'
+
carry)
/
10;
i++;
}
while
(i
<
b.size())
{
c
+=
(b[i]-'0'
+
carry)
%
10
+
'0';
carry
=
(b[i]-'0'
+
carry)
/
10;
i++;
}
while
(carry
>
0)//计算进位部分
{
c
+=
carry
%
10
+
'0';
carry
/=
10;
}
i
=
c.size()
-
1;
while
(c[i]
==
'0')//消除多余的高位0
{
i--;
}
c
=
c.substr(0,
i+1);
Reverse(c);
}

var a,b:array[1..256] of integer;
s1,s2:string;
c,i,j,k:integer;
begin
readln(s1);
readln(s2);
for i:=1 to length(s1) do
a[length(s1)-i+1]:=ord(s1[i])-ord('0');
for i:=1 to length(s2) do
b[length(s2)-i+1]:=ord(s2[i])-ord('0');
if length(s1)<length(s2) then k:=length(s2) or k:=length(s1);
for i:=1 to k do begin
a[i]:=a[i]+b[i]+j;
j:=a[i] div 10;
a[i]:=a[i] mod 10;
end;
while j>0 do begin
inc(i);
a[i]:=j mod 10;
j:=j div 10;
end;
for j:=i downto 1 do write(a[j]);
writeln;
end.

可能有错......不过应该是对的

输入两个长整数（十位以上），输出它们的和。

var st:string;
x,y:array[0..101]of integer;
i,j,l1,l2:integer;
begin
write('x='); readln(st);
l1:=length(st);
for i:=0 to 101 do x[i]:=0;
for i:=l1 downto 1 do
x[l1-i]:=ord(st[i])-ord('0');
write('y='); readln(st);
l2:=length(st);
for i:=0 to 101 do y[i]:=0;
for i:=l2 downto 1 do
y[l2-i]:=ord(st[i])-ord('0');
if l1<l2 then l1:=l2;
for i:=0 to l1 do
begin
x[i]:=x[i]+y[i];
x[i+1]:=x[i+1]+x[i] div 10;
x[i]:=x[i] mod 10;
end;
write('x+y=');
j:=101;
while x[j]=0 do j:=j-1;
for i:=j downto 0 do write(x[i]);
readln;
end.

例七 输入两个长整数（十位以上），输出它们的积。

var st1,st2:string;
x,y:array[1..200]of integer;
z: array[1..401]of integer; i,j,l1,l2,a,b,c,d:integer;
begin
write('x='); readln(st1);
l1:=length(st1);
for i:=1 to 200 do x[i]:=0;
for i:=l1 downto 1 do
x[l1+1-i]:=ord(st1[i])-ord('0');
write('y='); readln(st2);
l2:=length(st2);
for i:=1 to 200 do y[i]:=0;
for i:=l2 downto 1 do
y[l2+1-i]:=ord(st2[i])-ord('0');
for i:=1 to l1 do
for j:=1 to l2 do
begin
a:=x[i]*y[j];
b:=a div 10;
c:=a mod 10;
d:=i+j-1;{积z数组的元素号}
z[d]:=z[d]+c;
z[d+1]:=z[d+1]+z[d] div 10 + b;{进位}
z[d]:=z[d] mod 10;
end;
a:=l1+l2;;
while z[a]=0 do a:=a-1;
write(st1,’*’,st2,’=‘);
for i:=a downto 1 do write(z[i]);
writeln;
readln;
end.

例六 输入两个长整数（十位以上），输出它们的差。

var st,st1,st2:string;
x,y,z:array[0..200]of byte;
i,k,s1,s2,code:integer;
begin
write('x='); readln(st1);
s1:=length(st1);
write('y='); readln(st2);
s2:=length(st2);
write(st1,’-’,st2,’=‘);
if (s1<s2)or((s1=s2)and(st1<st2)) then
begin
write(‘-’);
st:=st1;st1:=st2;st2:=st;
k:=s1;s1:=s2;s2:=k;
end;
fillchar(x,sizeof(x),0);
fillchar(y,sizeof(y),0);
fillchar(z,sizeof(z),0);
for i:=1 to s1 do val(st1[i],x[s1+1-i],code);
for i:=1 to s2 do val(st2[i],y[s2+1-i],code); for i:= 1 to s1 do
begin
if x[i]-y[i]<0 then{不够减，借位}
begin
x[i+1]:=x[i+1]-1;
x[i]:=x[i] + 10;
end;
z[i]:=x[i]-y[i];
end;
k:=s1;
while z[k]=0 do k:=k-1;
for i:=k downto 1 do write(z[i]);
writeln;
readln;
end.

就是把数字的每一位存在数组里，假设113+222,那么存113的数组就是:
a[3]=1; a[2]=1; a[3]=1;
这样存好后把两个数组加起来就可以了，部分代码：
maxl表示a，b中的最高位的较大的加1，也就是和可能的最大长度。
for i:=1 to maxl do
begin
inc(c[i],a[i]+b[i]); //不能c[i]:=a[i]+b[i]; 因为c[i]可能已经从前面的进位过了而不为0；
if c[i]>=10 then //进位
begin
c[i+1]:=c[i] div 10; c[i]:=c[i] mod 10;
end;
end;

高精度加法
所谓的高精度运算,是指参与运算的数(加数,减数,因子……）范围大大超出了标准数据类型（整型，实型）能表示的范围的运算。例如，求两个200位的数的和。这时，就要用到高精度算法了。在这里，我们先讨论高精度加法。高精度运算主要解决以下三个问题：
基本方法
1、加数、减数、运算结果的输入和存储
运算因子超出了整型、实型能表示的范围，肯定不能直接用一个数的形式来表示。在Pascal中，能表示多个数的数据类型有两种：数组和字符串。
（1）数组：每个数组元素存储1位（在优化时，这里是一个重点！），有多少位就需要多少个数组元素；
用数组表示数的优点：每一位都是数的形式，可以直接加减；运算时非常方便
用数组表示数的缺点：数组不能直接输入；输入时每两位数之间必须有分隔符，不符合数值的输入习惯；
（2）字符串：字符串的最大长度是255，可以表示255位。
用字符串表示数的优点：能直接输入输出，输入时，每两位数之间不必分隔符，符合数值的输入习惯；
用字符串表示数的缺点：字符串中的每一位是一个字符，不能直接进行运算，必须先将它转化为数值再进行运算；运算时非常不方便；
（3）因此，综合以上所述，对上面两种数据结构取长补短：用字符串读入数据，用数组存储数据：
var s1,s2:string;
a,b,c:array [1..260] of integer;
i,l,k1,k2:integer;
begin
write('input s1:');readln(s1);
write('input s2:');readln(s2);
{————读入两个数s1，s2，都是字符串类型}
l:=length(s1);{求出s1的长度，也即s1的位数；有关字符串的知识。}
k1:=260;
for i:=l downto 1 do
begin
a[k1]:=ord(s1[i])-48;{将字符转成数值}
k1:=k1-1;
end;
k1:=k1+1;
{————以上将s1中的字符一位一位地转成数值并存在数组a中；低位在后（从第260位开始），高位在前（每存完一位，k1减1）}
对s2的转化过程和上面一模一样。
2、运算过程
在往下看之前，大家先列竖式计算35+86。
注意的问题：
（1）运算顺序：两个数靠右对齐；从低位向高位运算；先计算低位再计算高位；
（2）运算规则：同一位的两个数相加再加上从低位来的进位，成为该位的和；这个和去掉向高位的进位就成为该位的值；如上例：3+8+1=12，向前一位进1，本位的值是2；可借助MOD、DIV运算完成这一步；
（3）最后一位的进位：如果完成两个数的相加后，进位位值不为0，则应添加一位；
（4）如果两个加数位数不一样多，则按位数多的一个进行计算；
if k1>k2 then k:=k1 else k:=k2;
y:=0;
for i:=260 downto k do
begin
x:=a[i]+b[i]+y;
c[i]:=x mod 10;
y:=x div 10;
end;
if y<>0 then begin k:=k-1;c[k]:=y; end;
3、结果的输出（这也是优化的一个重点）
按运算结果的实际位数输出
for i:=k to 260 do write(c[i]);
writeln;
4、例子：求两个数的加法
program sum;
var s,s1,s2:string;
a,b,c:array [1..260] of integer;
i,l,k1,k2:integer;
begin
write('input s1:');readln(s1);
write('input s2:');readln(s2);
l:=length(s1);
k1:=260;
for i:=l downto 1 do
begin
a[k1]:=ord(s1[i])-48;
k1:=k1-1;
end;
k1:=k1+1;
l:=length(s2);
k2:=260;
for i:=l downto 1 do
begin
b[k2]:=ord(s2[i])-48;
k2:=k2-1;
end;
k2:=k2+1;
if k1>k2 then k:=k2 else k:=k1;
y:=0;
for i:=260 downto k do
begin
x:=a[i]+b[i]+y;
c[i]:=x mod 10;
y:=x div 10;
end;
if y<>0 then begin k:=k-1;c[k]:=y;
end;
for i:=k to 260 do write(c[i]);
writeln;
end.
优化：
以上的方法的有明显的缺点：
（1）浪费空间：一个整型变量（-32768~32767）只存放一位（0~9）；
（2）浪费时间：一次加减只处理一位；
针对以上问题，我们做如下优化：一个数组元素存放四位数；（integer的最大范围是32767，5位的话可能导致出界）。具体方法：
l:=length(s1);
k1:=260;
repeat {————有关字符串的知识}
s:=copy(s1,l-3,4);
val(s,a[k1],code);
k1:=k1-1;
s1:=copy(s1,1,l-4);
l:=l-4;
until l<=0;
k1:=k1+1;
而因为这个改进，算法要相应改变：
（1）运算时：不再逢十进位，而是逢万进位（mod 10000; div 10000);
（2）输出时：最高位直接输出，其余各位，要判断是否足够4位，不足部分要补0；例如：1，23，2345这样三段的数，输出时，应该是100232345而不是1234567。
改进后的算法：
program sum;
var s1,s2:string;
a,b,c:array [1..260] of integer;
i,l,k1,k2,code:integer;
begin
write('input s1:');readln(s1);
write('input s2:');readln(s2);
l:=length(s1);
k1:=260;
repeat {————有关字符串的知识}
s:=copy(s1,l-3,4);
val(s,a[k1],code);
k1:=k1-1;
s1:=copy(s1,1,l-4);
l:=l-4;
until l<=0;
k1:=k1+1;
l:=length(s2);
k2:=260;
repeat
s:=copy(s2,l-3,4);
val(s,b[k2],code);
k2:=k2-1;
s2:=copy(s2,1,l-4);
l:=l-4;
until l<=0;
k2:=k2+1;
if k1 y:=0;
for i:=260 downto k do
begin
x:=a[i]+b[i]+y;
c[i]:=x mod 10000;
y:=x div 10000;
end;
if y<>0 then begin k:=k-1;c[k]:=y;end;
write(c[k]);
for i:=k+1 to 260 do
begin
----if c[i]<1000 then write('0');
----if c[i]<100 then write('0');
----if c[i]<10 then write('0');
----write(c[i]);
end;
writeln;
end.
高精度加法(优化)
1.和普通高精度加法比较,这里多了几个优点:
1)普通高精度加法,每次计算只能用一个数组.如果用到1000个数组,那么
就超界了,不能执行.而优化后的高精度加法,则多了四倍的空间,容纳得
下更多的数组.
2)计算方面.普通高精度加法,一次只能一个数位一个数位地加,而优化后的
高精度加法,一次可以同时四个数位一起加.
2.算法流程:
1)读入两个加数(s1,s2)(字符串);
2)求两个字符串长度.把他们分成没四个数位一段(由最后一位起),
复制s1,s2中从w开始的k位.(如:s1:='1234567',x:=copy(s1,4,4)既('4567')
将字符串转为数值,存在一个变量中.删除从第w位开始的k个字符(如:s1:='123456789',
delete(s1,5,5)[即删除'56789']);
3)运算(以下说的是简便方法):
<1>先判断两个加数.把大的一个放前面,小的一个放后面,赋给一个变量.
用if语句.(如:if k1>k2 then k:=k2 else k:=k1;)
<2>处理进位(jw):
注意:89+17,最终答案为106,而此时,k的位置在0,而不在1,则写成06,这时,
就得用if语句判断.
(if jw<>0 then begin )
k:=k-1;
c[k]:=jw;
end;
这样,最终答案才是106.
4)打印补足零:
因为优化后的高精度加法,是把每四个数位分成一段,而每一段则必须有四个
数,当有一段不足四个数时,就得用"0"补足.
(如:第一位是'1',第二位是'34',第三位是'345',第四位是'8',
则应写为'1003403450008')
注意:第一位不用补零,(如:第一位为'3',则写成'3').
program ZFLCQ;
var s1,s2,s3,s4:string;
a,b,c:array[1..200] of integer;
i,l,k1,k2,k,cq,x,jw:integer;
begin
readln(s1);
readln(s2);
l:=length(s1);
k1:=200;
repeat
s3:=copy(s1,l-3,4);
val(s3,a[k1],cq);
k1:=k1-1;
delete(s1,l-3,4);
l:=l-4;
until l<=0;
k1:=k1+1;
i:=length(s2);
k2:=200;
repeat
s4:=copy(s2,i-3,4);
val(s4,b[k2],cq);
k2:=k2-1;
delete(s2,i-3,4);
i:=i-4;
until i<=0;
k2:=k2+1;
if k1>k2 then k:=k2
else k:=k1;
jw:=0;
for i:=200 downto k do
begin
x:=a[i]+b[i]+jw;
c[i]:=x mod 10000;
jw:=x div 10000;
end;
if jw<>0 then begin
k:=k-1;
c[k]:=jw;
end;
write(c[k]);
for i:=k+1 to 200 do
begin
if c[i]<1000 then write('0');
if c[i]<100 then write('0');
if c[i]<10 then write('0');
write(c[i]);
end;
end.

高精度加法PASCAL代码：（位压缩）
var s1,s2:ansistring;
function zhuan(x:string):string;
begin
for k:=1 to 4-length(x) do x:='0'+x;
exit(x);
end;
function add(x,y:ansistring):ansistring;
var g,t,jw,l,r,tp:longint;
num1,num2:array[1..1000] of longint;
mid,s:ansistring;
begin
if x='0' then exit(y);
if y='0' then exit(x);
fillchar(num1,sizeof(num1),0);
fillchar(num2,sizeof(num2),0);
l:=length(x);r:=length(y);
for g:=1 to l do
num1[g]:=ord(x[l-g+1])-48;
for g:=1 to r do
num2[g]:=ord(y[r-g+1])-48;
if r>l then l:=r;
jw:=0;
for g:=1 to l+1 do
begin
t:=num1[g]+num2[g]+jw;
num2[g]:=t mod 10;
jw:=t div 10;
end;
s:='';
for g:=1 to l do
begin
str(num2[g],mid);
s:=mid+s;
end;
if s[1]='0' then delete(s,1,1);
exit(s);
end;
begin
readln(s1);
readln(s2);
writeln(add(s1,s2));
end.

---

高邮市15599066975： 矩阵取数游戏(2007NOIP)求处理思路 - ？
骆婕潘多： 我们可以注意到,每一行都是独立的,即我们可以把每一行都分别算完后最后将各行结果相加,有数据规模看,需要用到高精度运算. 由样例1的解释看,固守本分的一路作下去,最大会出现1000*2^80,需要编写高精度乘法,提高了程序的空...

高邮市15599066975： noip 高精度算法 pascal - ？
骆婕潘多： 我也要去复赛,志同道合啊~~~~绝对标准的模块化实现高精度系列(High Precision) by tenshi HP1 高精度 1 : 加法 HP2 高精度 2 : 减法 HP3 高精度 3 : 乘法 1 : 高精度数 x 单精度数 HP4 高精度 4 : 乘法 2 : 高精度数 x 高精度数 HP5 ...

高邮市15599066975： 求NOIP提高组考试需掌握的算法(大纲) - ？
骆婕潘多： 1、排序算法(快排、选择、冒泡、堆排序、二叉排序树、桶排序)2、DFS/BFS 也就是搜索算法,剪枝务必要学! 学宽搜的时候学一下哈希表!3、树 ①遍历 ②二叉树 ③二叉排序树(查找、生成、删除) ④堆(二叉堆、左偏树、堆排序) ⑤...

高邮市15599066975： 要想在NOIP复赛中获得200左右的分 - ？
骆婕潘多： 先谈谈基本算法吧.下面是从OIBH上摘来的,我加了点注释.一、 排序 //这个不用说了,必须十分熟练的过关,特别是快速排序.要能够达到立刻默出来的效果,并要适当学会灵活应用.堆排序也稍微注意一下,毕竟速度比较稳定.1. 快速排...

高邮市15599066975： 求求求:NOIP2000第二题怎么做? - ？
骆婕潘多： 用动态规划的方法做..不过还需要实现高精度的乘法.转移方程为s[i][j] = i...k * s[k+1][j-1],枚举k从i到n-j-1 从后面往前算,s[i][j]表示从i到末尾分成j个数的最优解.初始化全为0,s[n][1] = char[n].

高邮市15599066975： NOIP提高组,要用到哪些算法 pascal - ？
骆婕潘多： NOIP提高组的你暂时不用学,但如果你想知道的话就告诉你一下吧: 算法:贪心、DP、搜索(重点学优化和判重)、分治、图论、博弈、二分、二分图匹配、网络流、KMP. 数据结构:并查集、二叉堆、队列、hash、二叉查找树、双向链表...

高邮市15599066975： noip初赛题求解? - ？
骆婕潘多： 1 V 是或运算∧ 是与运算运算级 是先与后或 b...........00001111 c...........01011100 B∧C........00001100 a...........11001110 A V B∧C....110011102 这个就是 输入 key 对应的返回 key/13的余数如本题用线性 就是发现有冲突以后(地址相同) 地址+1直到有空地址 在 (2、8、31、20、19、18、53、27) 里面的元素/%13后 地址有2 8 5 7 6 9(5+1+1+1+1) 1 3(2+1)

高邮市15599066975： 参加noip需要哪些知识 - ？
骆婕潘多： 初赛考的知识点,大纲如是说:计算机基本常识/基本操作和程序设计基本知识.选择题考查的是知识,而填空/问题解决题更加重视能力的考查.一般说来,选择题是不需要单独准备的 -- 也无从准备.只要多用心积累就可以了.到是问题解决题...

高邮市15599066975： 高精度计算的高精度加法 - ？
骆婕潘多： 高精度运算主要解决以下三个问题:一、加数、减数、运算结果的输入和存储 运算因子超出了整型、实型能表示的范围,肯定不能直接用一个数的形式来表示.在Pascal中,能表示多个数的数据类型有两种:数组和字符串.数组:每个数组元素...

高邮市15599066975： 输入两串数字字符(一行一串,不超过80位)两数求和 - ？
骆婕潘多： /*高精度加法*/#include <stdio.h>#include <string.h>#include <stdlib.h> void fanzhuan(char *x); char *jiafa(char *x, char *y); int main(void) { char num1[81] = {0}; char num2[81] = {0}; gets(num1); gets(num2); printf(＂%s\n＂, jiafa(num1, num2)); return ...