『壹』 誰知到高精度演算法（加減乘除）pascal的常規方法啊
所謂的高精度運算,是指參與運算的數(加數,減數,因子……）范圍大大超出了標准數據類型（整型，實型）能表示的范圍的運算。例如，求兩個200位的數的和。這時，就要用到高精度演算法了。在這里，我們先討論高精度加法。高精度運算主要解決以下三個問題：
一、加數、減數、運算結果的輸入和存儲
運算因子超出了整型、實型能表示的范圍，肯定不能直接用一個數的形式來表示。在Pascal中，能表示多個數的數據類型有兩種：數組和字元串。
數組：每個數組元素存儲1位（在優化時，這里是一個重點！），有多少位就需要多少個數組元素；用數組表示數的優點：每一位都是數的形式，可以直接加減；運算時非常方便。用數組表示數的缺點：數組不能直接輸入；輸入時每兩位數之間必須有分隔符，不符合數值的輸入習慣；
字元串：字元串的最大長度是255，可以表示255位。用字元串表示數的優點：能直接輸入輸出，輸入時，每兩位數之間不必分隔符，符合數值的輸入習慣；用字元串表示數的缺點：字元串中的每一位是一個字元，不能直接進行運算，必須先將它轉化為數值再進行運算；運算時非常不方便；
綜合以上所述，對上面兩種數據結構取長補短：用字元串讀入數據，用數組存儲數據：
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)-48;{將字元轉成數值}
k1:=k1-1;
end;
k1:=k1+1;
{————以上將s1中的字元一位一位地轉成數值並存在數組a中；低位在後（從第260位開始），高位在前（每存完一位，k1減1），完後，k1指向最高位}
對s2的轉化過程和上面一模一樣。
二、運算過程
在往下看之前，大家先列豎式計算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+b+y;
c:=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);
writeln;
例子：求兩個數的加法
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)-48;
k1:=k1-1;
end;
k1:=k1+1;
l:=length(s2);
k2:=260;
for I+:=l downto 1 do
begin
b[k2]:=ord(s2)-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+b+y;
c:=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);
writeln;
end.
四、優化：
以上的方法的有明顯的缺點：
（1）浪費空間：一個整型變數（-32768~32767）只存放一位（0~9）；
（2）浪費時間：一次加減只處理一位；
針對以上問題，我們做如下優化：一個數組元素存放四位數；（integer的最大范圍是32767，5位的話可能導致出界）。具體方法：
l:=length(s1);
k1:=260;
repeat {————有關字元串的知識}
s:=(s1,l-3,4);
val(s,a[k1],code);
k1:=k1-1;
s1:=(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,s: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:=(s1,l-3,4);
val(s,a[k1],code);
k1:=k1-1;
s1:=(s1,1,l-4);
l:=l-4;
until l<=0;
k1:=k1+1;
l:=length(s2);
k2:=260;
repeat
s:=(s2,l-3,4);
val(s,b[k2],code);
k2:=k2-1;
s2:=(s2,1,l-4);
l:=l-4;
until l<=0;
k2:=k2+1;
if k1<k2 then k:=k1 else k:=k2;
y:=0;
for i:=260 downto k do
begin
x:=a+b+y;
c:=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<1000 then write('0');
if c<100 then write('0');
if c<10 then write('0');
write(c);
end;
writeln;
end.
減法：和高精度加法相比，減法在差為負數時處理的細節更多一點：當被減數小於減數時，差為負數，差的絕對值是減數減去被減數；在程序實現上用一個變數來存儲符號位，用另一個數組存差的絕對值。
2、演算法流程：
（1）讀入被減數S1，S2（字元串）；
（2）置符號位：判斷被減數是否大於減數：大則將符號位置為空；小則將符號位置為「-」，交換減數與被減數；
（3）被減數與減數處理成數值，放在數組中；
（4）運算：
A、取數；
B、判斷是否需要借位；
C、減，將運算結果放到差數組相應位中；
D、判斷是否運算完成：是，轉5；不是，轉A；
（5）列印結果：符號位，第1位，循環處理第2到最後一位；
3、細節：
▲如何判斷被減數與減數的大小：字元串知識
（1）首先將兩個字元串的位數補成一樣(因為字元串的比較是從左邊對齊的；兩個字元串一樣長才能真正地比較出大小)：短的在左邊補0
k1:=length(s1);
k2:=length(s2);
if k1>k2 then for i:=1 to k1-k2 do s2:='0'+s2
else for i:=1 to k2-k1 do s1:='0'+s1;
（2）接著比較大小：直接比較字元串大小
fh:='';
if s1<s2 then begin fh:='-';s:=s1; s1:=s2; s2:=s; end;
{————s1存被減數，fh存符號}
▲將字元串處理成數值：
l:=length(s1);{求出s1的長度，也即s1的位數；有關字元串的知識。}
k1:=260;
for i:=l downto 1 do
begin
a[k1]:=ord(s1)-48;{將字元轉成數值}
k1:=k1-1;
end;
k1:=k1+1;
▲運算（減法跟加法比較，減法退位處理跟加法進位處理不一樣）：
a.處理退位；
跟加法一樣，在for語句外面先將退位清零，
用被減數再減去退位，
{注意：由於每一個數位不一定都得向前一位借位，所以這里退位得清零。例如，234-25，個位需借位，而十位不用}
接著，再判斷，當被減數某一位不夠減時，則需加上前一位退位過來的數。
{注意：由於這里採用優化方法，所以退一位，就等於後一位加上10000。）
最後，再拿一個數組來存儲兩個減數的差。
jw:=0;
for i:=260 downto k1 do
begin
a:=a-jw; {此處jw為下一位從I位的借位}
jw:=0; {此處jw為I 位準備向上一位的借位}
if a<b then
begin
jw:=1;
a:=a+10000;
end;
c:=a-b;
end;
▲列印結果：
先找到差的第一個非零數，如果差的所有位數都為零，就直接輸出零。
如果不是，就輸出符號位和差的第一位。
剩下部分，列印補足零:
因為優化後的高精度減法,是把每四個數位分成一段,而每一段則必須有四個
數,當有一段不足四個數時,就得用"0"補足.(如:第一位是'1',第二位是'34',第三位是'345',第四位是'8', 則應寫為'1003403450008').注意:第一位不用補零,(如:第一位為'3',則寫成'3').
while (c[k]=0) and (k<=260) do k:=k+1;
if k>260 then write('0')
else begin
write(fh,c[k]);{k是差的第1位；}
for i:=k+1 to 260 do
begin
if c<1000 then write('0');
if c<100 then write('0');
if c<10 then write('0');
write(c);
end;
end;
參考程序：
program Zfjianfa;
const n=25;
var s1,s2,s3,s4,s:string;
a,b,c:array[1..n] of integer;
i,k1,k2,l,code,jw:integer;
cq:char;
begin
readln(s1);
readln(s2);
k1:=length(s1);
k2:=length(s2);
if k1>k2 then for i:=1 to k1-k2 do s2:='0'+s2
else for i:=1 to k2-k1 do s1:='0'+s1;
cq:=' ';
if s1<s2 then begin cq:='-'; s:=s1; s1:=s2; s2:=s; end;
l:=length(s1);
k1:=n;
repeat
s3:=(s1,l-3,4);
val(s3,a[k1],code);
k1:=k1-1;
delete(s1,l-3,4);
l:=l-4;
until l<=0;
k1:=k1+1;
i:=length(s2);
k2:=n;
repeat
s4:=(s2,i-3,4);
val(s4,b[k2],code);
k2:=k2-1;
delete(s2,i-3,4);
i:=i-4;
until i<=0;
k2:=k2+1;
jw:=0;
for i:=n downto k1 do
begin
a:=a-jw;
jw:=0;
if a<b then begin
jw:=1;
a:=a+10000;
end;
c:=a-b;
end;
while (c[k1]=0) and (k1<=n) do
k1:=k1+1;
if k1>n then writeln('0')
else begin
write(cq,c[k1]);
for i:=k1+1 to n do
begin
if c<1000 then write('0');
if c<100 then write('0');
if c<10 then write('0');
write(c);
end;
end;
writeln;
end.
高精度乘法基本思想和加法一樣。其基本流程如下：
①讀入被乘數s1，乘數s2
②把s1、s2分成4位一段，轉成數值存在數組a,b中；記下a,b的長度k1,k2；
③i賦為b中的最低位；
④從b中取出第i位與a相乘，累加到另一數組c中；（注意：累加時錯開的位數應是多少位？）
⑤i:=i-1；檢測i值：小於k2則轉⑥,否則轉④
⑥列印結果
參考程序：
program chengfa;
const n=100;
type ar=array [1..n] of integer;
var a,b:ar; k1,k2,k:integer;
c:array [1..200] of integer;
s1,s2:string;
procere fenge(s:string;var d:ar; var kk:integer); {將s分割成四位一組存放在d中，返回的kk值指向d的最高位}
var ss:string;
i,code:integer;
begin
i:=length(s);
kk:=n;
repeat
ss:=(s,i-3,4);
val(ss,d[kk],code);
kk:=kk-1;
s:=(s,1,i-4);
i:=i-4;
until i<0;
kk:=kk+1;
end;
procere init;
var i:integer;
begin
for i:=1 to n do begin a:=0; b:=0; end;
for i:=1 to 2*n do c:=0;
write('input 2 numbers:');
readln(s1);
readln(s2);
fenge(s1,a,k1);
fenge(s2,b,k2);
end;
procere jisuan;
var i,j,m:integer; x,y,z,jw:longint;
begin
i:=n; k:=2*n;
repeat
x:=b; z:=0; m:=k; jw:=0;
for j:=n downto k1 do
begin
y:=a[j];
z:=c[m];
x:=x*y+z+jw;
jw:=x div 10000;
c[m]:=x mod 10000;
m:=m-1;
x:=b;
end;
if jw<>0 then c[m]:=jw else m:=m+1;
i:=i-1;
k:=k-1;
until i<k2;
k:=m;
end;
procere daying;
var i:integer;
begin
write(c[k]);
for i:=k+1 to 2*n do
begin
if c<1000 then write('0');
if c<100 then write('0');
if c<10 then write('0');
write(c);
end;
writeln;
end;
begin
init;
jisuan;
daying;
end.
教材「基礎編」P87高精乘法參考程序：
program ex3_1;
var
a,b,c:array[0..1000] of word;
procere init;
var
s:string;
ok,i,j:integer;
begin
readln(s);
a[0]:=length(s);
for i:=1 to a[0] do
val(s[a[0]-i+1],a,ok);
readln(s);
b[0]:=length(s);
b[0]:=length(s);
for i:=1 to b[0] do
val(s[b[0]-i+1],b,ok);
end;
procere highmul;
var i,j,k:integer;
begin
c[0]:=a[0]+b[0];
for i:=1 to b[0] do
for j:=1 to a[0]+1 do
begin
inc(c[i+j-1],a[j]*b mod 10);
c[i+j]:=c[i+j]+(a[j]*b div 10)+(c[i+j-1] div 10);
c[i+j-1]:=c[i+j-1] mod 10;
end;
end;
procere print;
var i:integer;
begin
while c[c[0]]=0 do dec(c[0]);
for i:=c[0] downto 1 do
write(c);
writeln;
end;
begin
init;
highmul;
print;
end.
高精度除法：
1）.高精度除以整型數據(integer);
程序如下:
program HighPrecision3_Multiply1;
const
fn_inp='hp5.inp';
fn_out='hp5.out';
maxlen=100; { max length of the number }
type
hp=record
len:integer; { length of the number }
s:array[1..maxlen] of integer
{ s[1] is the lowest position
s[len] is the highest position }
end;
var
x,y:hp;
z,w:integer;
procere PrintHP(const p:hp);
var i:integer;
begin
for i:=p.len downto 1 do write(p.s);
end;
procere init;
var
st:string;
i:integer;
begin
assign(input,fn_inp);
reset(input);
readln(st);
x.len:=length(st);
for i:=1 to x.len do { change string to HP }
x.s:=ord(st[x.len+1-i])-ord('0');
readln(z);
close(input);
end;
procere Divide(a:hp;b:integer;var c:hp;var d:integer);
{ c:=a div b ; d:=a mod b }
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
len:=a.len;
d:=0;
for i:=len downto 1 do { from high to low }
begin
d:=d*10+a.s;
c.s:=d div b;
d:=d mod b;
end;
while(len>1) and (c.s[len]=0) do dec(len);
c.len:=len;
end;
procere main;
begin
Divide(x,z,y,w);
end;
procere out;
begin
assign(output,fn_out);
rewrite(output);
PrintHP(y);
writeln;
writeln(w);
close(output);
end;
begin
init;
main;
out;
end.
2）.高精度除以高精度
程序如下:
program HighPrecision4_Multiply2;
const
fn_inp='hp6.inp';
fn_out='hp6.out';
maxlen=100; { max length of the number }
type
hp=record
len:integer; { length of the number }
s:array[1..maxlen] of integer
{ s[1] is the lowest position
s[len] is the highest position }
end;
var
x:array[1..2] of hp;
y,w:hp; { x:input ; y:output }
procere PrintHP(const p:hp);
var i:integer;
begin
for i:=p.len downto 1 do write(p.s);
end;
procere init;
var
st:string;
j,i:integer;
begin
assign(input,fn_inp);
reset(input);
for j:=1 to 2 do
begin
readln(st);
x[j].len:=length(st);
for i:=1 to x[j].len do { change string to HP }
x[j].s:=ord(st[x[j].len+1-i])-ord('0');
end;
close(input);
end;
procere Subtract(a,b:hp;var c:hp); { c:=a-b, suppose a>=b }
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
if a.len>b.len then len:=a.len { get the bigger length of a,b }
else len:=b.len;
for i:=1 to len do { subtract from low to high }
begin
inc(c.s,a.s-b.s);
if c.s<0 then
begin
inc(c.s,10);
dec(c.s[i+1]); { add 1 to a higher position }
end;
end;
while(len>1) and (c.s[len]=0) do dec(len);
c.len:=len;
end;
function Compare(const a,b:hp):integer;
{
1 if a>b
0 if a=b
-1 if a < b
}
var len:integer;
begin
if a.len>b.len then len:=a.len { get the bigger length of a,b }
else len:=b.len;
while(len>0) and (a.s[len]=b.s[len]) do dec(len);
{ find a position which have a different digit }
if len=0 then compare:=0 { no difference }
else compare:=a.s[len]-b.s[len];
end;
procere Multiply10(var a:hp); { a:=a*10 }
var i:Integer;
begin
for i:=a.len downto 1 do
a.s[i+1]:=a.s;
a.s[1]:=0;
inc(a.len);
while(a.len>1) and (a.s[a.len]=0) do dec(a.len);
end;
procere Divide(a,b:hp;var c,d:hp); { c:=a div b ; d:=a mod b }
var i,j,len:integer;
begin
fillchar(c,sizeof(c),0);
len:=a.len;
fillchar(d,sizeof(d),0);
d.len:=1;
for i:=len downto 1 do
begin
Multiply10(d);
d.s[1]:=a.s; { d:=d*10+a.s }
{ c.s:=d div b ; d:=d mod b; }
{ while(d>=b) do begin d:=d-b;inc(c.s) end }
while(compare(d,b)>=0) do
begin
Subtract(d,b,d);
inc(c.s);
end;
end;
while(len>1)and(c.s[len]=0) do dec(len);
c.len:=len;
end;
procere main;
begin
Divide(x[1],x[2],y,w);
end;
procere out;
begin
assign(output,fn_out);
rewrite(output);
PrintHP(y);
writeln;
PrintHP(w);
writeln;
close(output);
end;
begin
init;
main;
out;
end.