Thuật toán chia kẹo

Chia sẻ: Kieu Chi Hieu | Ngày: | Loại File: DOC | Số trang:10

Thêm vào BST

Báo xấu

1.107
lượt xem 150
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Một bài toán được gọi là một bàitoán hay nếu nó là một bài toán khó và có lời giải độc đáo. Bài toán "Chia kẹo" là một minh chứng cho điềuđó. 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 ápdụng để giải cho rất nhiều bài toán khác trong Tin học.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Thuật toán chia kẹo

Thuật toán chia kẹo Nguyễn Ngọc Thắng Một bài toán được gọi là một bàitoán hay nếu nó là một bài toán khó và có lời giải độc đáo. Bài toán "Chia kẹo" là một minh chứng cho điềuđó. 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 ápdụng để giải cho rất nhiều bài toán khác trong Tin học. Các bạn có thể thamkhảo bài viết "Thuật toán chia kẹo và ứng dụng giải lớp bài toán chianhóm" của tác giả Lã Thành Công trên số báo tháng 1/2001. Sauđây tôi xin trình bày phương pháp giải bài toán này và ứng dụng thuật toántrong việc giải các bài toán tin khác. 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 haiphầ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(N
Chương trình thể hiện thuật toántrên. {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+,Y+} {$M 16384,0,655360} Program chia_keo; uses crt; const max = 100; fi ='chiakeo.inp'; fo ='chiakeo.out'; var a,s : array[1..max]of integer; d1,d2,tr : array[0..max*max]of integer; n,m,sum : integer; Procedure docf; var f: text; k : integer; begin assign(f,fi); reset(f); readln(f,n); sum:=0; for k:=1 to n do begin read(f,a[k]); sum:=sum+a[k]; end;
close(f); end; Procedure lam; var i,j : integer; Begin fillchar(d1,sizeof(d1),0); fillchar(tr,sizeof(tr),0); d1[0]:=1;d2:=d1; for i:=1 to n do begin for j:=0 to sum-a[i] do if (d1[j]=1)and(d2[j+a[i]]=0) then begin d2[j+a[i]]:=1; tr[j+a[i]]:=i; end; d1:=d2; end; end; Procedure ghif; var m,k : integer; f :text; Begin
fillchar(s,sizeof(s),0); m:=sum div 2; while d2[m]=0 do dec(m); assign(f,fo); rewrite(f); writeln(f,sum-2*m); while tr[m]>0 do begin s[tr[m]]:=1; m:=m-a[tr[m]]; end; for k:=1 to n do write(f,k+1,#32); close(f); end; BEGIN {main} docf; lam; ghif; END. Nhận xét:Chương trình trên đây cài đặt rất "thô", song dễ hiểu. Chương trình có thể cảitiến lại để có thể chạy được số liệu lớn hơn, nhanh hơn. Ví dụ: bạn có cần để ýđến các tổng >sum/2 không? Có thể tích hợp cả ba mảng D1, D2 và TR làm mộtmảng không? Bạn đọc hãy chỉnh lại để chương trình chạy tốt hơn. Sau đây là các lớp bài toán ápdụng thuật toán chia kẹo. Bài nào đơn giản tôi chỉ đưa thuật toán để các bạntham khảo. Còn chương trình bạn đọc tự cài đặt.
Bài toán mua bán hàng Có một người đi mua hàng, anhta có N đồng tiền d1, d2,.., dN. Người bánhàng có M đồng tiền b1, b2,.., bm. Anh tamuốn mua một mặt hàng với giá trị W. Hỏi cuộc mua bán có thể diễn ra đượckhông? Giới hạn: M, N
+ Các dòng tiếp theo là các phần tử của mảng A. Kết quả ra file: "MONEY.OUT" gồmmột dòng duy nhất là số cách trả tiền (Số cách trả tiền < Maxlongint) Ví dụ: Thuật toán: Bài toán này khác với bài toán chia kẹo, nhưngđể giải ta vẫn áp dụng tư tưởng chia kẹo. Nó không đơn thuần là tìm được mộtcách trả tiền, mà là tìm số cách trả tiền. Với bài này ta cũng sinh ra tất cảcác tổng, song mảng D (mảng đánh dấu) không đơn thuần là bằng 1 hay bằng 0 mànó có ỹ nghĩa là số cách tạo ra tổng đó. Chương trình thể hiện thuật toán: {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+,Y+} {$M 16384,0,655360} Program tra_tien; uses crt; const max = 100; limit = 1000; fi = 'money.inp'; fo = 'meney.out'; var D : array[0..limit]of longint; a : array[1..max]ofinteger; n, m : longint; Procedure docf; var f : text; k :integer;
Begin assign(f,fi); reset(f); readln(f,n,m); for k:=1 to n do read(f,a[k]); close(f); end; Procedure lam; var i,j :integer; Begin fillchar(D,sizeof(D),0); D[0]:=1; for i:=1 to n do for j:=m-a[i] downto 0 do inc(D[j+a[i]],D[j]); end; Procedure ghif; Var f :text; Begin assign(f,fo); rewrite(f); write(f,D[m]); close(f); End; BEGIN {main} docf; lam; ghif; END.
Bài toán dãy có tổng chia hết chok (đề thi toàn Quốc) Cho một dãy số nguyên A1,A2,.., AN và một số k. Hãy tìm một dãy con (không nhấtthiết phải liên tiếp nhau) dài nhất có tổng các số chia hết cho số k. Dữ liệu vào trong file "dayso.inp" có dạng: + Dòng 1 gồm 2 số N và k(N
const maxK = 100; fi ='dayso.inp'; fo ='dayso.out'; var L1,L2 :array[0..maxK]of longint; n,k,p : longint; Procedure lam; var f : text; i,j,x : longint; Begin fillchar(L1,sizeof(L1),0); L2:=L1; assign(f,fi); reset(f); readln(f,n,k); p:=0; for i:=1 to n do begin read(f,x); x:=x mod k+k; p:=(p+x)mod k; for j:=0 to k-1 do if (L1[j]>0) then if (L2[(x+j)mod k]=0)or(L2[(x+j)mod k]>L1[j]+1) then L2[(x+j)modk]:=L1[j]+1; L2[x mod k]:=1;
end; close(f); end; Procedure ghif; var f :text; Begin assign(f,fo); rewrite(f); write(f,n-L2[p]); close(f); End; BEGIN {main} lam; ghif; END. Nếu bạn muốn tìm dãy con này thìđây là một công việc khác phức tạp. Trước tiên bạn phải tìm ra các phần tử cầnloại bỏ. Sau đó đọc lại file một lần nữa. Nhưng việc tìm ra các số cần loại bỏkhông đơn giản. Nguyên nhân gây ra việc khó khăn này là mảng trước bị ghi đè.Song không phải là không giải được. Tôi có một cách làm nhưng cách làm đó khádài dòng, chưa tốt. Bạn nào có cách làm tốt, hay có thắc mắc gì xin liên hệ vớitoà soạn.