Bài toán chia kẹo là một dạng toán điển hình, bài toán này có phương pháp giải đặc biệt, tư tưởng của nó có thể được áp dụng để giải cho rất nhiều bài toán khác trong Tin học . Nó còn có tên gọi là Number Partitioning, không có thuật toán tối ưu để giải. Sau đây là những thuật toán từ đơn giản đến khó để giải quyết bài tập này .
Nhắc lại bài toán chia kẹo
Có N gói kẹo, gói thứ i có Aicái kẹo. Không được bóc bất kỳ một gói kẹo nào, cần chia N gói kẹo thành hai phần sao cho độ chênh lệch số kẹo giữa hai gói là ít nhất.
Dữ liệu vào trong file “chiakeo.inp” có dạng :
– Dòng đầu tiên là số N[NL2 Then Max:=L1 Else Max:=L2; For i:=L1+1 to Max do s1:='0'+s1; For i:=L2+1 to Max do s2:='0'+s2; nho:=0; h:=''; For i:=Max downto 1 do Begin val[s1[i],a,code]; val[s2[i],b,code]; tam:=a+b+nho; if tam>=10 Then nho:=1 Else nho:=0; str[tam Mod 10,h1]; h:=h1+h; End; if nho=1 Then h:='1'+h; cong:=h; End; Begin write['nhap so thu nhat']; readln[st1]; write['nhap so thu hai']; readln[st2]; writeln['ket qua la', cong[st1,st2]]; readln; End.
Nhận xét: - Chương trình trên thực hiện việc cộng hai số được nhập từ bàn phím. - Trong chương trình có sử dụng chương trình con Cong[s1,s2:String]: String để tính kết quả phép cộng hai xâu s1, s2. - Kết quả phép cộng được hiện lên trên màn hình. - Ta có thể thay đổi chương trình bằng cách sử dụng tệp để đọc dữ liệu vào và ghi kết quả ra.
* Bây giờ chúng ta tìm hiểu giải thuật kinh điển cho dạng toán này như sau: - Giả sử hai số được cho bởi chuổi s1,s2 - Thêm kí tự ‘0’ vào bên trái số có chiều dài ngắn để 2 chuổi s1,s2 có chiều dài bằng nhau và giả sử chiều dài lúc đó là Max. - Kết quả được đưa vào mảng C. - Tính c[i]=a[i]+b[i] với mọi i[i=1..Max] Ví dụ: a=986 b=927 Thì c[1]=18; c[2]=10; c[3]=13; - Để C là mảng số kết quả cần biến đổi một chút nữa như sau: - Duyệt mảng C từ phải qua trái, mỗi c[i] chỉ giữ lại phần dư còn phần nguyên thì cộng thêm cho phần tử c[i-1] như sau: For i:=Max downto 1 do Begin c[i-1]:=c[i-1] + c[i] Div 10; c[i]:=c[i] Mod 10; End; Chương trình kết quả đưa vào mảng.
USES CRT; Procedure cong; Var s1,s2:String; a,b,i,L1,L2,code:word; max:longint; c:Array[0..255] of byte; Begin Write['Nhap so thu nhat']; Readln[s1]; Write['Nhap so thu hai']; Readln[s2]; L1:=length[s1]; L2:=length[s2]; if L1>L2 Then Max:=L1 Else Max:=L2; For i:=L2+1 to Max do s2:='0'+s2; For i:=L1+1 to Max do s1:='0'+s1; For i:=0 to 255 do C[i]:=0; For i:=0 to Max do Begin val[s1[i],A,code]; val[s2[i],B,code]; c[i]:=a+b; End; For i:=Max downto 1 do Begin c[i-1]:=c[i-1] + c[i] Div 10; c[i]:=c[i] Mod 10; End; For i:=0 to Max do Write[c[i]]; End; BEGIN cong; readln; END.
Nhận xét: - Chương trình trên thực hiện việc cộng hai số nguyên lớn được nhập từ bàn phím. Kết quả của phép cộng được hiển thị trên màn hình. - Ngoài ra ta có thể sử dụng tệp để đọc các số nguyên lớn vào và ghi kết quả ra
Bài toán 2: Chương trình trừ 2 số tự nhiên lớn
* Ý tưởng: - Hai số được lưu dưới dạng xâu. Các số có thể đọc ra từ tệp lưu vào biến kiểu xâu hoặc các số có thể được nhập từ màn hình lưu vào biến kiểu xâu. - So sánh độ dài hai xâu, tìm độ dài xâu lớn nhất - Thêm kí tự '0' vào xâu có độ dài ngắn hơn để hai xâu bằng nhau. - So sánh hai xâu có độ dài bằng nhau. + Nếu xâu lưu số bị trừ lớn hơn xâu lưu số trừ. Thực hiện phép trừ hai xâu từ cuối lên đầu [tương tự như phép trừ trong toán học]. Sử dụng thủ tục chuyển đổi xâu thành số trong quá trình tính toán. + Nếu xâu lưu số bị trừ bé hơn xâu lưu số trừ thực hiện đặt dấu trừ [-] vào phần đầu kết quả, đồng thời thực hiện hoán đổi hai xâu cho nhau và thực hiện phép trừ tương tự như ở trên. * Các bước thực hiện: - Nhập hai số từ bàn phím lưu vào hai biến xâu st1, st2. - So sánh hai xâu st1 và st2. Thêm kí tự ‘0’ vào xâu ngắn hơn để hai xâu có độ dài bằng nhau. - So sánh hai xâu st1, st2 độ dài bằng nhau. + Nếu xâu lưu số bị trừ lớn hơn xâu lưu số trừ. Thực hiện phép trừ hai xâu từ cuối lên đầu [tương tự như phép trừ trong toán học]. Sử dụng thủ tục chuyển đổi xâu thành số trong quá trình tính toán. + Nếu xâu lưu số bị trừ bé hơn xâu lưu số trừ thực hiện đặt dấu trừ [-] vào phần đầu kết quả, đồng thời thực hiện hoán đổi hai xâu cho nhau và thực hiện phép trừ tương tự như ở trên. - Phép trừ được thực hiện như sau: Các kí tự sâu St1 được chuyển thành số và lưu vào mảng h1. Các kí tự sâu St2 được chuyển thành số và lưu vào mảng h2. Thực hiện phép trừ hai mảng h1 và h2 [lưu ý trương hợp số bị trừ bé hơn số trừ] Nếu h1[i]=h2[i] thì c[i]:=h1[i]-h2[i]; - Mảng C thu được chính là kết quả.
Chương trình:
program tru_so_lon; var st1,st2:string; Procedure tru[s1,s2:string]; Var s:String; h1,h2:Array[1..255] of byte; C:Array[1..255] of byte; dau:Char; code,l1,l2,Max,i:word; Begin L1:=length[s1]; L2:=length[s2]; if L1>L2 Then Max:=L1 Else Max:=L2; For i:=L2+1 to Max do s2:='0'+s2; For i:=L1+1 to Max do s1:='0'+s1; dau:=' '; IF s2>s1 Then Begin dau:='-'; s:=s2; s2:=s1; s1:=s; End; For i:=1 to 255 do C[i]:=0; For i:=1 to Max do Begin val[s1[i],h1[i],code]; val[s2[i],h2[i],code]; End; For i:=Max downto 1 do IF h1[i]