Bài toán nhân hai số nguyên tố

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*102+34 = a*102+b

và tách S2 thành 2 phần : c=56 ; d=78, vì vậy S2 = 56*102+78 = c*102+d

Khi đó: S1*S2 =(a*102+b)*( c*102+d) = a*c*104

+ a*d*102

+ b*c*102 +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

Nhan và thoát.

2. Nếu độ dài S1 không bằng S2 thì thêm các số 0 vào trước S1 hoặc S2 để chúng códộ dài

bằng nhau.

3. Tiến hành tách S1,S2 thành các số a, b, c, d như sau:

Lấy x=length(s1) div 2 ;L=length(s1)

a:=copy(s1,1,x); { a là nửa đầu của s1 }

b:=copy(s1,x+1,length(s1)-x); { blà nửa sau của s1 }

c:=copy(s2,1,x); { c là nửa đầu của s2 }

d:=copy(s2,x+1,length(s2)-x); { dlà nửa sau của s2 }

Kết quả: Nhan:= nhan(a,c)*102(L-x)+ nhan(a,d)*10L-x + nhan (b,c)*10L-x + nhan(b,d);

Chương trình:

{$m65520,0,0}