冬令營(yíng)講義李學(xué)武附錄

1、附錄 5.用分治法求兩個(gè)高精度正純小數(shù)的乘法program multi01; uses crt;const limit=258;type arr2=array 0.limit of long str=string255; 數(shù)組 ARR2 存放高精度純小數(shù), 每一位存放 1 位小數(shù).第零位存放整數(shù)部分(=0) var aa,bb,cc,wk1:arr2;dd:array 1.60 ofeger; 用于打印,每行 60 個(gè)數(shù)字i,n,n2,n4,t,k1,k2:longstr1,str2:str;procedure frmt (var f:arr2;n1,n:long); No.1 n1:star

2、ing place, var fj,fj1,j,n2:long beginn2:=n1; if n1=10) thenn:end place ;n2:=1;begin fj1:=fj div 10;fj-1:=fj-1+fj1;fj:=fj-(fj1*10)end;end;end;procedure wrt(var cc:arr2;n:long;lin1:byte); No.2 PrResult var i,j,j2,j4,kk,n2,ccj:long beginkk:=n div 60; n2:=n;gotoxy(4,lin1+1);write(cc0:1,.); for i:=1 to k

3、k+1 dobeginj2:=60; if j2n2 then j2:=n2;for j:=1 to j2 do ddj:=cc(i-1)*60+j; n2:=n2-60;lin1:=lin1+1; gotoxy(6,lin1);for j:=1 to j2 do write(ddj:1);wriend;n;end;procedure plus5(var d,e,f:arr2;n:long No.3 dn+en=fn );var i:begineger;for i:=0 to n do fi:=ei+di; frmt(f,1,n);end;procedure minus5(var d,e,f:

4、arr2;n:eger); No.4 dn-en=fn , wk2n:working array 本子程序不作符號(hào)處理,故必須保證 d=e,d=0,e=0 var j,ej:long;beginfor j:=0 to n do wk1j:=dj; for j:=n downto 1 dobeginej:=ej;if (wk1jccn*2, 分治法, n 必須是 2 的整數(shù)次冪(n=2k)var n2,n4,i:long;a2,b2,wk3:arr2; arrs1,arrs2:word; pa,pb:eger;begin1cc0:=0; pa:=aa0; pb:=bb0;aa1:=aa1+pa*

5、10; aa0:=0; 處理為純小數(shù)bb1:=bb1+pb*10; bb0:=0; if n=1 thenbegincc2:=aa1*bb1; cc1:=0; frmt(cc,1,2); exitend; n4:=n*2;arrs1:=n*sizeof(long)+1;arrs2:=(n*sizeof(long) div 2)+1;getmem(a2,arrs2); getmem(b2,arrs2); getmem(wk3,arrs1);n2:=n div 2;for i:=1 to n2 dobegin a2i:=aai+n2; b2i:=bbi+n2; end; a20:=0; b20:=

6、0;mult5(aa,bb,wk3,n2);if wk300 then wk31:=wk31+10*wk30; for i:=1 to n do cci:=wk3i; mult5(a2,b2,wk3,n2);if wk300 then wk31:=wk31+10*wk30;for i:=1 to n doccn+i:=wk3i;plus5(aa,a2,wk3,n2); plus5(bb,b2,aa,n2); mult5(wk3,aa,bb,n2);for i:=1 to n do wk3i:=cci+ccn+i;wk30:=0;frmt(wk3,1,n);minus5(bb,wk3,aa,n)

7、;for i:=0 to n do ccn2+i:=ccn2+i+aai; frmt(cc,1,n4);freemem(a2,arrs2); freemem(b2,arrs2); freemem(wk3,arrs1);end;1procedure mult3(var d,e,f:arr2;var m,n,p:long); No.5 d(m)*e(n)=f(p), p:=m+n, 普通乘法,用于對(duì)照結(jié)果var j,j1,k,dj,fk,fk1:long beginp:=m+n;for k:=0 to p for j:=1 to mbegindj:=dj; if (dj0)do fk:=0;dot

8、henfor k:=j+1 to n+j do if (j mod 30)=0) thenend; frmt(f,1,p)end;fk:=fk+dj*ek-j;frmt(f,j,n+j) ;procedure trans(var str3:str; var dd:arr2;var k:long);var i,j:begineger;if (str31=0)and(str32=.) then delete(str3,1,2); i:=1;repeatif not (str3i in 0.9) then delete(str3,i,1) else inc(i);until ilength(str3

9、);k:=length(str3);for i:=1 to k doddi:=ord(str3i)-48; end;begainclrscr;gotoxy(10,4);wrin(Input thenumber(255 pla):);gotoxy(10,5); readln(str1); trans(str1,aa,k1);gotoxy(10,10);wrin(Input the second number(n then n:=k2;t:=1;n:=t;while tn do t:=t*2;for i:=k1+1 to n do aai:=0; for i:=k2+1 to n do bbi:=0 ; n4:=n*2;aa0:=0; bb0:=0;mult5(a