Nhân hai số nguyên lớn với Giải thuật chia để trị
Phạm Thế Anh
Với bài toán đặt ra: Tính tíchhai số nguyên lớn nhập từ bàn phímnhư các bạn đã biết trong
các số báotrước đã nêu ra nhiều cách giải và nhiều cách xử lý khác nhau, sau đây tôi cómột
ý tưởng cho kết quả rất nhanh.
Xét ví dụ phép nhân 2 số: S1=1234 và S2=5678
Ta tách S1 thành 2 phần : a=12 ; b=34 suy raS1 =12*10
2
+34 = a*10
2
+b
và tách S2 thành 2 phần : c=56 ; d=78, vì vậy S2 = 56*10
2
+78 = c*10
2
+d
Khi đó: S1*S2 =(a*10
2
+b)*( c*10
2
+d) = a*c*10
4
+ a*d*10
2
+ b*c*10
2
+b*d
Theo ý tưởng đó ta viết hàm nhân hai số (mỗi số là mộtString) như sau:
Function Nhan(S1,S2:string):string;
1. Nếu độ dài S1 và S2 đều nhỏ hơn 5 ( số S1 và S2 có tối đa 4 chữ số ) ta chuyểnS1 và S2
thành số rồi tiến hành nhân hai số longint, kết quả chuyển thành chuỗitrả về giá trị cho hàm

c:=copy(s2,1,x); { c la nua dau cua s2 }
d:=copy(s2,x+1,length(s1)-x); { dla nua sau cua s2 }
sac:=<b>nhan(a,c); {Tinh a*c roi nhan cho 10
2(L-x)
}
for i:=1 to (length(s1)-x)*2 dosac:=sac+'0';
sad:=<b>nhan(a,d); { Tinh a*d roi nhan cho 10
L-x
}
for i:=1 to length(s1)-x dosad:=sad+'0';
sbc:=<b>nhan(b,c); {Tinh b*c roi nhan cho 10
L-x
}
for i:=1 to length(s1)-x dosbc:=sbc+'0';
sbd:=<b>nhan(b,d); {Tinh b*d }
nhan:=cong(cong(sac,sad),cong(sbc,sbd));
end;
end;
Chương trình có sử dùng các hàmphụ:
{chuyển chuỗi St thành số nguyên dương }
function tonum(s:string):longint;
var l:longint;
code:integer;
begin
val(s,l,code);
tonum:=l;
end;
{chuyển số nguyên dương n thành chuỗi }
Function toST(l:longint):string;
var s:string;