TỦ SÁch tri thức duy tân nguyễn xuân huy sáng tạo trong thuật toán và LẬp trìNH
tải về 2.51 Mb.
|
3.2 DominoCho lưới đơn vị gồm n dòng và m cột. Các ô trong lưới được gán mã số 1, 2, ... , nm theo trật tự từ dòng trên xuống dòng dưới, trên mỗi dòng tính từ trái qua phải. Người ta đặt v vách ngăn giữa hai ô kề cạnh nhau. Hãy tìm cách đặt nhiều nhất k quân domino, mỗi quân gồm hai ô kề cạnh nhau trên lưới và không có vách ngăn ở giữa.
Thuật toán Bài này có hai điểm khác với dạng bài cặp ghép truyền thống. Thứ nhất là ghép cặp được thực hiện từ một tập A với chính nó: f: A A. Thứ hai, mỗi số trong tập A chỉ có thể ghép tối đa với 4 số trong các ô kề cạnh nó mà ta tạm gọi là số kề. Thí dụ, 8 có 4 số kề theo thứ tự trái, phải và trên, dưới là 7, 9 và 3, 13. Các số ngoài rià và các số có vách ngăn còn có ít bạn hơn. Thí dụ, 20 có đúng 1 bạn.Khi đọc dữ liệu ta xác định ngay cho mỗi số i trong bảng bốn số kề và ghi vào mảng ke với ý nghĩa như sau ke[i][j] = 1 khi và chỉ khi i có số kề tại vị trí j; j = 1, 2, 3, 4. Nếu i có vách ngăn phải thì i sẽ mất bạn kề phải. Tương tự, nếu i có vách ngăn dưới thì i sẽ mất bạn kề dưới. Ngoài ra, dễ hiểu rằng các số trên dòng 1 thì không có số kề trên, các số trên dòng n thì không có số kề dưới. Tương tự, các số trên cột 1 thì không có số kề trái, các số trên cột m thì không có số kề phải.Nhắc lại rằng ta chỉ cần sử dụng một mảng a với ý nghĩa a[i] = j, đồng thời a[j] = i cho biết số i chọn số kề j để ghép thành 1 quân domino. Nói cách khác nếu ta xếp được f(i) = j thì ta phải gán a[i] = j và a[j] = i. Tiếp đến ta thực hiện thủ tục Xep(i) cho mọi số chưa được ghép cặp (a[i] = 0) và chưa là bạn của bất kì số nào (b[i] = 0). Khi ghi kết quả ra file ta lưu ý là hai cặp (i , a[i] = j) và (j, a[j] = i) thực ra chỉ tạo thành một quân domino duy nhất, do đó ta chỉ cần ghi một trong hai cặp đó. Ta chọn cặp i < a[i] để tránh trường hợp không xếp được cho số i, vì khi đó a[i] = 0 tức là i > a[i]. (* Domino.pas *) uses crt; const maxmn = 201; fn = 'domino.inp'; gn = 'domino.out'; bl = #32; nl = #13#10; phai = 1; trai = 2; tren = 3; duoi = 4; type mi1 = array[0..maxmn] of integer; var n: integer; { so dong } m: integer; { so cot } nm: integer;{ nm = n.m } f,g: text; ke: array[0..maxmn,phai..duoi] of Boolean; st: mi1; { stack } p: integer; { ngon st } a, t: mi1; procedure Doc; var i, j, k, v, t: integer; begin fillchar(ke,sizeof(ke),true); assign(f,fn); reset(f); readln(f,n,m,v); { v - so vach ngan } nm := n*m; { dong 1 va dong n } k := (n-1)*m; for j := 1 to m do begin ke[j, tren] := false; ke[j+k, duoi] := false; end; j := 1; { cot 1 va cot m } for i := 1 to n do begin ke[j , trai] := false; j := j + m; ke[j-1, phai] := false; end; for k := 1 to v do begin readln(f,i,j); if i > j then begin t := i; i := j; j := t end; { i < j } if i = j-1 then ke[i,phai] := false else ke[i,duoi] := false; end; close(f); end; procedure Update(i,j: integer); var q: integer; begin repeat q := a[i]; { i bo so q } a[i] := j; a[j] := i; { de nhan so j } j := q; i := t[i]; { chuyen qua so truoc } until q = 0; end; function Xep(i: integer): integer; var j, k: integer; begin Xep := 1; p := 0; inc(p); st[p] := i; { nap st } fillchar(t, sizeof(t),0); t[i] := i; while p > 0 do begin i := st[p]; dec(p); { Lay ngon st } for k := 1 to 4 do if ke[i,k] then { i co o ke } begin case k of tren: j := i - m; duoi: j := i + m; phai: j := i + 1; trai: j := i - 1; end; if a[j] = 0 then { j chua bi chiem } begin Update(i,j); exit end else if t[a[j]] = 0 { a[j] chua co trong st } then begin inc(p); st[p] := a[j]; t[a[j]] := i end; end; end; Xep := 0; end; function Par: integer; var i, v: integer; begin fillchar(a,sizeof(a),0); v := 0; for i := 1 to nm do if a[i] = 0 then v := v + Xep(i); par := v; end; procedure Ghi(k: integer); var i: integer; begin assign(g,gn); rewrite(g); writeln(g, k); for i := 1 to nm do if i < a[i] then writeln(g,i,bl,a[i]); close(g); end; procedure Run; var k: integer; begin Doc; k := Par; Ghi(k); end; BEGIN Run; writeln(nl,' Fini'); readln; END. // DevC++: Domino.cpp #include #include using namespace std; // D A T A A N D V A R I A B L E S const char * fn = "domino.inp"; const char * gn = "domino.out"; const int Maxmn = 201; // tich max n.m const int phai = 0; const int duoi = 1; const int tren = 2; const int trai = 3; int a[Maxmn]; // a[i] = j, a[j] = i: i chon j int t[Maxmn]; // t[j] = i : j nhuong cho i bool ke[Maxmn][4]; // moi so co toi da 4 so ke int n; // so dong int m; // so cot int nm; int st[Maxmn]; // stack int p; // con tro stack // P R O T O T Y P E S int main(); void Doc(); int Par(); int Xep(int); void Update(int, int); void Ghi(int); // I M P L E M E N T A T I O N int main() { Doc(); int k = Par(); Ghi(k); cout << endl; system("PAUSE"); return EXIT_SUCCESS; } void Ghi(int k) { ofstream g(gn); g << k << endl; for (int i = 1; i <= nm; ++i) if (i < a[i]) g << i << " " << a[i] << endl; g.close(); } void Update(int i, int j){ int c; do { c = a[i]; // i bo c xuong a[i] = j; a[j] = i; // i nhan so moi j i = t[i]; j = c; // chuyen qua so khac } while (c > 0); } int Xep(int i) { // tim so ghep voi i memset(t, 0, sizeof(t)); int j, k; p = 0; st[++p] = i; t[i] = i; while(p > 0) { i = st[p--]; // lay ngon stack for (j = 0; j < 4; ++j) { // duyet cac o ke if (ke[i][j] > 0) { // co o ke switch(j) { case tren: k = i-m; break; case duoi: k = i+m; break; case phai: k = i+1; break; case trai: k = i-1; break; } if (a[k] == 0) { // o k chua bi chiem Update(i,k); return 1; } if (t[a[k]] == 0) { // a[k] chua co trong danh sach st[++p] = a[k]; t[a[k]] = i; // nap } } } } return 0; // Khong chon duoc cap ghep cho i } int Par(){ // Cap ghep int v = 0, i; memset(a,0,sizeof(a)); for (i = 1; i <= nm; ++i) if (a[i]==0) v += Xep(i); return v; } void Doc(){ int i, j, k, r, v; // so vach ngan int n1, m1,ij; ifstream f(fn); f >> n >> m >> v; nm = n*m; n1 = n-1; m1 = m-1; memset(ke,1, sizeof(ke)); // duyet cac o trong for (j = (n-1)*m, i = 1; i <= m; ++i) ke[i][tren] = ke[i+j][duoi] = 0; for (j = m-1, i = m; i <= nm; i += m) ke[i-j][trai] = ke[i][phai] = 0; for (i = 0; i < v; ++i) { f >> k >> r; if (k > r) { j = k; k = r; r = j; } // k < r if (r == k+1) ke[k][phai] = ke[r][trai] = 0; else ke[k][duoi] = ke[r][tren] = 0; } f.close(); } 3.3 Thám hiểmTrường A và trường B đều cử n học sinh (HS) tham gia trò chơi Thám hiểm Cung Trăng với n xe tự hành, mỗi xe chở được 2 người có nhiệm vụ khảo cứu một đề tài khoa học và hoạt động tại một vùng riêng trên Cung Trăng với một chủ đề cụ thể ghi trên xe đó. Sau khi xem bản hướng dẫn và trình diễn thử của các xe tự hành, mỗi HS chọn một số xe. Ban tổ chức (BTC) cần chia các em thành các nhóm, mỗi nhóm 2 bạn sẽ làm việc trên một xe, một bạn của trường A, một bạn của trường B sao cho 2 bạn trên cùng một xe thì cùng quan tâm đên chủ đề chung. Hãy giúp BTC sắp xếp sao cho nhiều chủ đề nhất được thực hiện.Dữ liêụ vào: Text file Discover.inp.Dòng đầu tiên: số tự nhiên nDòng thứ i trong số n dòng tiếp theo có dạng: k c1 c2 ... ck trong đó k là số lượng xe HS i của trường A chọn, các số tiếp theo là mã số của các xe đồng thời là mã số của đề tài mà bạn đó chọn.Dòng thứ i trong số n dòng tiếp theo là thông tin của trường B có cấu trúc tương tự như của trường A.Dữ liệu ra: Text file Discover.out gồm n dòng, mỗi dòng 2 học sinh: i của trường A, j của trường B cho biết i và j tạo thành một nhóm do cùng chọn một xe. Dữ liệu trên cùng dòng cách nhau qua dấu cách. Bài toán luôn luôn có nghiệm.
Thuật toán Ta thực hiện hai lần ghép cặp Xe-Trường A và Xe-Trường B. Sau lần ghép thứ nhất ta thu được kết quả ghi trong mảng a[1..n] trong đó a[i] = j cho biết xe i sẽ chở bạn j của trường A. Sau lần ghép thứ hai ta lại thu được kết quả ghi trong mảng b[1..n] trong đó b[i] = k cho biết xe i sẽ chở bạn k của trường B. Tổng hợp lại ta có mỗi xe i sẽ chở 2 bạn, bạn a[i] của trường A và bạn b[i] của trường B, i = 1..n. Khung chương trình khi đó sẽ như sau: 1. Mở file input f "Discover.inp"; 2. Đọc số n;
3. Đọc dữ liệu của trường A vào mảng 2 chiều c, c[i][j] = 1 khi và chỉ khi xe i được HS j của trường A chọn; 4. Gọi thủ tục Par(a) để ghép cặp Xe – A cho HS trường A. Kết quả a[i] = j cho biết xe i sẽ chở HS i của trường A, i = 1..n; 5. Đọc tiếp dữ liệu của trường B vào mảng 2 chiều c, c[i][k] = 1 khi và chỉ khi xe i được HS k của trường B chọn; 6. Gọi thủ tục Par(b) để ghép cặp Xe – B cho HS trường B. Kết quả b[i] = k cho biết xe i sẽ chở HS k của trường B, i = 1..n; 7. Ghi các cặp a[i], b[i], i = 1..n vào file output; 8. Đóng các files input và output. Bạn lưu ý, với thí dụ đã cho, sau khi đọc n dòng dữ liệu của trường A bạn phải thu được kết quả trong mảng c như mảnh A trong bảng. Tương tự, sau khi đọc tiếp n dòng dữ liệu của trường B bạn phải thu được kết quả trong mảng c như mảnh B trong bảng. (* Pas: Discover *) uses crt; const fn = 'Discover.inp'; gn = 'Discover.out'; mn = 201; bl = #32; nl = #13#10; type mi1 = array[0..mn] of integer; mb2 = array[0..mn,0..mn] of byte; var f,g: text; n: integer; { so HS = so xe = so de tai } c: mb2; { c[i,j] = 1 khi va chi khi hs j chon xe i } a, b: mi1; { xep xe truong a, b } t, x: mi1; { t - tro truoc } st: mi1; { stack } p: integer; { ngon st } procedure XemC; var i,j: integer; begin write(nl,n); for i := 1 to n do begin writeln; for j := 1 to n do write(c[i,j]); end; end; { xep lien hoan, xe i, hs j } procedure Update(var a: mi1; i, j: integer); var c: integer; begin repeat c := a[i]; { hs c roi xe i } a[i] := j; x[j] := i; { hs j len xe i } j := c; i := t[i]; { xet hs tiep } until c = 0; end; function XepXe(var a: mi1; i: integer): integer; { xep xe i } var j: integer; begin XepXe := 1; p := 1; st[p] := i; fillchar(t, sizeof(t),0); t[i] := i; while (p > 0) do begin i := st[p]; dec(p); { xe i } for j := 1 to n do { hs j } if (c[i,j] = 1) then { hs j chon xe i } begin if x[j] = 0 { hs j chua len xe } then begin Update(a,i,j); exit end; { xep duoc xe i } { Nap x[j] vao st } if t[x[j]] = 0 { x[j] chua duoc nap } then begin inc(p); st[p] := x[j]; t[x[j]] := i end; end; end; XepXe := 0; { kho xep duoc xe i } end; function Par(var a: mi1): integer; var i, k: integer; begin k := 0; { so xe da xep duoc } fillchar(a, sizeof(a),0); x := a; for i := 1 to n do k := k + XepXe(a,i); Par := k; end; procedure Doc; var soxe, hs, xe, j: integer; begin fillchar(c,sizeof(c),0); for hs := 1 to n do begin read(f,soxe); for j := 1 to soxe do { Hs chon xe } begin read(f,xe); c[xe,hs] := 1 end; end; end; procedure Ghi; var i: integer; begin assign(g,gn); rewrite(g); for i := 1 to n do writeln(g,a[i],bl,b[i]); close(g); close(f); end; procedure Run; var i: integer; begin assign(f,fn); reset(f); readln(f,n); Doc; Par(a); Doc; Par(b); Ghi; end; BEGIN Run; write(nl,nl,' Fini'); readln; END. // DevC++: Discover.cpp #include #include using namespace std; // D A T A A N D V A R I A B L E S const char * fn = "Discover.inp"; const char * gn = "Discover.out"; const int mn = 501; int a[mn]; // a[i] – xe i cho HS truong A int b[mn]; // b[i] – xe i cho HS truong B int x[mn]; int t[mn]; int c[mn][mn]; // c[i][j] = 1 – xe i duoc HS j chon int n; // so hoc sinh cua moi truong A, B; so xe int st[mn]; // stack int p; // ngon stack ifstream f(fn); // mo san input file // P R O T O T Y P E S int main(); void Doc(); void Print(); int Par(int []); int Xep(int [], int); void Update(int [], int, int); void PrintArray(int [], int , int ); void Ghi(); // I M P L E M E N T A T I O N int main() { f >> n; Doc(); Print(); Par(a); cout << endl << " Xep xong truong A: "; PrintArray(a,1,n); Doc(); f.close(); Par(b); cout << endl << " Xep xong truong B: "; PrintArray(b,1,n); Ghi(); cout << endl << " Fini "; cinget(); return 0; } void Ghi() { ofstream g(gn); for (int xe = 1; xe <= n; ++xe) g << a[xe] << " " << b[xe] << endl; g.close(); } void PrintArray(int a[], int d, int c) { // hien thi mang a[d..c] int i; cout << endl; for (i = d; i <= c; ++i) cout << a[i] << " "; } void Update(int a[], int i, int j){ int xe; do { xe = a[i]; // HS i roi xe a[i] = j; x[j] = i; // vao xe j i = t[i]; j = xe; } while (xe > 0); } int Xep(int a[], int i) { // xep HS vao xe i memset(t, 0, sizeof(t)); int j; p = 0; st[++p] = i; t[i] = i; while(p > 0){ i = st[p--]; // lay ngon st, xe i for (j = 1; j <= n; ++j) { // duyet cac HS j if ((c[i][j] == 1)) { // xe i co the xep HS j if (x[j] == 0) { // HS j chua duoc xep Update(a,i,j); return 1; } if (t[x[j]] == 0) { // xe x[j] chua nap st[++p] = x[j]; t[x[j]] = i; } } // if } // for } // while return 0; // Khong xep duoc cho HS i } int Par(int a[]) { int d = 0, i; memset(a,0,sizeof(a)); memset(x,0,sizeof(b)); for (i = 1; i <= n; ++i) d += Xep(a,i); return d; } void Print(){ cout << endl << n << endl; int i,j; for (i = 1; i <= n; ++i) { for (j = 1; j <= n; ++j) cout << c[i][j] << " "; cout << endl; } } void Doc() { memset(c,0,sizeof(c)); int hs, xe, soxe, r; for (hs = 1; hs <= n; ++hs) { // truong A f >> soxe; for (r = 1; r <= soxe; ++r) { f >> xe ; c[xe][hs] = 1; } } } 3.4 ShowNhóm n học sinh (HS) tham gia trình diễn phần mềm. Mỗi em được trình bày riêng sản phẩm của mình trước Ban giám khảo (BGK) trong thời hạn 30 phút. BGK làm việc trong m ngày, ngày thứ i có thể nhận vi HS. Trong bản đăng ký mỗi HS ghi khả năng có thể trình diễn phần mềm của mình vào những ngày nào. Hãy sắp lịch để các HS được trình diễn theo đúng nguyện vọng. Dữ liệu vào: Text file show.inp Dòng đầu tiên: hai số n m. Dòng thứ hai: các giá trị v1 v2 … vm Dòng thứ i trong số n dòng tiếp theo: k u1 u2 … uk trong đó k là số ngày HS i chọn, các uj là những ngày cụ thể HS i chọn. Dữ liệu ra: Text file show.out gồm m dòng, dòng thứ i cho biết ngày thứ i BGK duyệt trình diễn của những HS nào. Dữ liệu trên cùng dòng cách nhau qua dấu cách
Thuật toán Bài này khá dễ giải nếu ta biết cách biến đổi ngày thành phiên theo ý tưởng như sau. Ta hiểu mỗi lượt trình diễn của một HS là một phiên.
Khi đọc dữ liệu ta ghi vào mảng s, s[i] cho biết số hiệu phiên của cuối mỗi ngày. Với thí dụ trên, sa khi đọc dữ liệu bạn phải tính được số phiên sp = 5 và s[0..3] = (0,2,4,5). Ngày thứ nhất kết thúc tại phiên 2; ngày thứ hai két thúc tại phiên 4 và ngày cuối cùng, ngày thứ m = 3 kết thúc tại phiên 5. Sau đó bạn tổ chức mảng 2 chiều c, c[i,j] cho biết HS i thích trình diễn tại phiên j. Chú ý rằng HS đăng kí 1 ngày có thể sinh ra nhiều phiên tùy thuộc vào ngày hôm đó có mấy phiên. Phiên chính là số HS được BGK cho phép trình diễn trong ngày đó. Sau khi thực hiện thủ tục cặp ghép như các bài trước, bạn cần duyệt lại kết quả để đổi phiên thành ngày. (* Show.pas *) uses crt; (* D A T A A N D V A R I A B L E S *) const fn = 'show.inp'; gn = 'show.out'; mn = 101; bl = #32; nl = #13#10; type mi1 = array[0..mn] of integer; mb2 = array[0..mn,0..mn] of byte; var n, m: integer; { n - so hs; m - so ngay } s: mi1; { s[i] - phien cuoi cua ngay i } a,b: mi1; c: mb2; { c[i,j] = 1 khi va chi khi hs i chon phien j } t, st: mi1; { stack st } p: integer; { ngon st } sp: integer; { so phien lam viec cua BGK } f,g: text; (* I M P L E M E N T A T I O N *) function ToNgay(p: integer): integer; { Doi Phien p -> ngay } var ng: integer; begin ng := 1; while (p > s[ng]) do inc(ng); ToNgay := ng end; procedure Ghi; var i,j,ng: integer; begin fillchar(c,sizeof(c),0); for i := 1 to n do if (a[i] > 0) then begin ng := ToNgay(a[i]); c[ng,i] := 1; end; { Xep ngay cho hs i } assign(g,gn); rewrite(g); for i := 1 to m do { Duyet c theo ngay i } begin for j := 1 to n do { Hs j } if (c[i,j] > 0) then write(g,j,bl); writeln(g); end; close(g); end; procedure Update(i,j: integer); var c: integer; begin repeat c := a[i]; a[i] := j; b[j] := i; i := t[i]; j := c; until c = 0; end; function XepHs(i: integer): integer; var j: integer; begin XepHs := 1; fillchar(t,sizeof(t),0); p := 1 ; st[p] := i; t[i] := i; while(p > 0) do begin i := st[p]; dec(p); { Lay ngon st, xep phien cho hs i } for j := 1 to sp do { duyet cac phien } if c[i,j] = 1 then { hs i chon phien j } begin if b[j] = 0 then { Phien j con roi } begin Update(i,j); exit end; if (t[b[j]] = 0) then { hs b[j] chua nap } begin inc(p); st[p] := b[j]; t[b[j]] := i; end; end; end; XepHs := 0; { Ko xep duoc phien cho hs i } end; function Par: integer; var i, d: integer; begin fillchar(a, sizeof(a),0); b := a; d := 0; for i := 1 to n do d := d + XepHs(i); Par := d; end; procedure Doc; var i,j,k,r,q: integer; begin fillchar(c,sizeof(c),0); assign(f,fn); reset(f); readln(f, n, m); s[0] := 0; for i := 1 to m do { m ngay lam viec } begin read(f,r); { so phien trong ngay i } s[i] := s[i-1] + r; { s[i] - phien cuoi cua ngay i } end; sp := s[m]; { Tong so phien } for i := 1 to n do { xet nguyen vong cua hs i } begin read(f,k); { so ngay hs i chon } for r := 1 to k do begin read(f,j); { cac phien trong ngay j } for q := s[j-1]+1 to s[j] do c[i][q] := 1; { hs i chon phien q } end end; close(f); end; procedure PA(var a: mi1; d,c: integer); { Print array a[d..c] } var i: integer; begin for i := d to c do write(a[i],bl); end; procedure Xem; var i,j: integer; begin write(nl,n,bl,m,nl); for i := 1 to n do begin writeln; for j := 1 to sp do write(c[i,j]); end; end; BEGIN Doc; Xem; writeln(nl,' Xep duoc: ',Par); Ghi; write(nl,' Fini '); readln; END. // DevC++: Show.cpp #include #include using namespace std; // D A T A A N D V A R I A B L E const char * fn = "show.inp"; const char * gn = "show.out"; const int mn = 101; int a[mn]; int b[mn]; int t[mn]; int c[mn][mn];// c[i][j] = 1 khi va chi khi HS i dang ki phien j int n; // so hoc sinh int m; // so ngay lam viêc cua BGK int sp; // so phien lam viec cua BGK int s[mn]; // s[i] - ma so phien cuoi cua ngay i int st[mn]; // stack int p; // ngon stack // P R O T O T Y P E S int main(); void Doc(); int Par(); int Xep(int); void Update(int, int); void Ghi(); int ToNgay(int); // I M P L E M E N T A T I O N int main() { Doc(); Par(); Ghi(); cout << endl << " fini "; cin.get(); return 0; } int ToNgay(int p) { // Phien -> ngay int ng = 1; while (p > s[ng]) ng++; return ng; } void Ghi() { int i,j; memset(c,0,sizeof(c)); for (i = 1; i <= n; ++i) // hs i if (a[i] > 0) c[ToNgay(a[i])][i] = 1; // c[j][i] = 1 neu hs i duoc xep cho ngay j ofstream g(gn); for (int i = 1; i <= m; ++i){ // ngay i for (j = 1; j <= n; ++j) // hs j if (c[i][j] > 0) g << j << " "; g << endl; } g.close(); } void Update(int i, int j){ int c; do { c = a[i]; a[i] = j; b[j] = i; i = t[i]; j = c; } while (c > 0); } int Xep(int i) { // xep cho HS i memset(t, 0, sizeof(t)); int j; p = 0; st[++p] = i; t[i] = i; while(p > 0){ i = st[p--]; for (j = 1; j <= sp; ++j) { // duyet cac buoi if (c[i][j] > 0) { // i chon j if (b[j] == 0) { // j con roi Update(i,j); return 1; } if (t[b[j]] == 0) { // b[j] chua nap st[++p] = b[j]; t[b[j]] = i; } }// if } // for } // while return 0; // Khong xep duoc cho HS i } int Par(){ int d = 0, i; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for (i = 1; i <= n; ++i) d += Xep(i); return d; } void Doc(){ memset(c,0,sizeof(c)); ifstream f(fn); f >> n >> m; // n - so hs; m - so ngay int i,j,k,r,q; s[0] = 0; for (i = 1; i <= m; ++i) { f >> r; // so phien trong ngay i s[i] = s[i-1] + r; // s[i] - phien cuoi cua ngay i } sp = s[m]; for (i = 1; i <= n; ++i){ // nguyen vong cua hs i f >> k; // so ngay hs i chon for (r = 1; r <= k; ++r){ f >> j ; // HS i chon ngay j for (q = s[j-1]+1; q <= s[j]; ++q) // duyet theo phien c[i][q] = 1; } } f.close(); } 3.5 Cặp ghép cực đại: Chị Hằng 2Nội dung giống bài cặp ghép với một thay đổi như sau: c[i][j] = v cho biết em i yêu thích món quà j với mức độ vi, 0 vi 10. Yêu cầu ghép cặp sao cho tổng độ yêu thích đạt max.
Thuật toán Ta quản lí một giá trị dmax là giá trị gia tăng nhiều nhất trong các phương án xếp quà cho em i. Thí dụ, sau khi đã xếp quà cho i1 em đầu tiên ta chuyển qua xếp quà cho em i. Giả sử ta có 2 phương án xếp quà cho em i. Phương án thứ nhất có thể tăng giá trị dmax lên thêm v1 đơn vị, phương án thứ hai có thể tăng giá trị dmax lên thêm v2 > v1 đơn vị. Ta sẽ chọn phương án thứ hai. Để thực hiện điều này ta cần lưu ý mấy giá trị sau đây.
Khác với phương pháp ghép cặp không phân biệt mức độ yêu thích trước kia, mỗi khi tìm được một dãy liên hoàn em t1 nhận quà từ em t2, t2 nhận quà từ em t3, ..., tk sẽ nhận món quà q chưa chia i = t1 t2 … tk1 tk = j (*) thì ta đánh giá xem nếu quyết định kết thúc thủ tục Xep(i) bằng cách thực hiện dãy liên hoàn (*) thì giá trị gia tăng dmax của phương án này là bao nhiêu và cập nhật giá trị đó. Gọi d là giá trị gia tăng của phương án chia quà. Mỗi khi em j nhường quà a[j] của mình cho bạn i để nhận quà mới q thì giá trị của phương án sẽ thay đổi như sau:
Tổng hợp lại, giá trị gia tăng của việc em j nhường quà cho em i để nhận quà mới q sẽ là c[j,q] + c[i,a[j]] – c[i,a[j]]. Ta có d := d + c[j,q] + c[i,a[j]] – c[i,a[j]]. Kí hiệu d(j) là giá trị gia tăng của phương án khi em j được đưa vào danh sách nhường quà. Phương án này bắt đầu bằng việc tìm quà cho em i, do đó d(i) = 0. Mỗi khi đưa j vào danh sách nhường quà cho k ta tính được d(j) = d(k) + c[k,a[j]] – c[k,a[j]]. Giả sử ta quyết định kết thúc việc tìm quà cho em i, tức là kết thúc thủ tục xét tại dãy (*). Khi đó do em j cuối cùng trong dãy nhận quà mới là q thì giá trị gia tăng của phương án sẽ được cộng thêm một lượng c[j,q] và bằng d(j) + c[j,q]. Ta so sánh đại lượng này với dmax để ghi nhận tình huống tối ưu. (* Autum2.pas *) uses crt; const fn = 'autum2.inp'; gn = 'autum2.out'; mn = 201; { so nguoi va so qua toi da } bl = #32; nl = #13#10; type mi1 = array[0..mn] of integer; mb2 = array[0..mn,0..mn] of byte; var a: mi1; { a[i] = j: em i nhan qua j } b: mi1; { b[j] = i: qua j trong tay em i } t: mi1; { t[j] = i : em j nhuong qua cho ban i } c: mb2; { c[i][j] = 1: i thich qua j } d: mi1; { d[j]: gia tri gia tang tich luy den em j } n: integer; { so em nho } m: integer; { so qua } st: mi1; { stack } p: integer; { tro ngon st } imax, jmax, dmax: integer; procedure Ghi(v: integer); var vmax, i: integer; g: text; begin vmax := 0; for i := 1 to n do if (a[i] > 0) then vmax := vmax + c[i,a[i]]; assign(g,gn); rewrite(g); writeln(g,vmax); for i := 1 to n do if (a[i] > 0) then writeln(g,i,bl,a[i]); close(g); end; procedure PrintArray(var a: mi1; d,c: integer); { Hien thi mang a[d..c] } var i: integer; begin for i := d to c do write(a[i],bl); end; procedure Update(i,j: integer); var c: integer; begin repeat c := a[i]; { i bo qua c } a[i] := j; b[j] := i; { i nhan qua moi j } i := t[i]; j := c; { chuyen qua nguoi khac } until c = 0; end; procedure Mark(i,j: integer); { ghi nhan phuong an i nhan qua j } var sum: integer; begin sum := d[i] + c[i,j]; { neu i nhan qua moi j } if (sum > dmax) then { ghi nhan phuong an tot hon } begin dmax := sum; imax := i; jmax := j; end end; procedure Nap(i,j: integer); { Nap em j vao danh sach nhuong qua cho em i } begin if (t[j] > 0) then exit; { j da co trong st } inc(p); st[p] := j; t[j] := i; { j se nhuong qua cho i } { dieu chinh gia tri tich luy } d[j] := d[i] + c[i,a[j]] - c[j,a[j]] ; end; function Xep(i: integer): integer; { tim qua cho em i } var j: integer; begin fillchar(t,sizeof(t),0); d := t; { d[j] - do gia tang tich luy den em j } dmax := 0; p := 0; Nap(i,i); while (p > 0) do begin i := st[p]; dec(p); { lay ngon stack } for j := 1 to m do { duyet cac mon qua } if (b[j] = 0) then Mark(i,j) { qua j chua chia } else Nap(i,j); { danh sach nhuong qua } end; Xep := 0; if (dmax = 0) then exit; Update(imax, jmax); Xep := 1; { Xep duoc qua cho em i } end; function Par: integer; { Ghep cap } var i, v: integer; begin v := 0; fillchar(a,sizeof(a),0); b := a; for i := 1 to n do v := v + Xep(i); Par := v; end; procedure Print; { Hien thi ma tran c } var i,j: integer; begin writeln(nl,' Input: '); for i := 1 to n do begin writeln; for j := 1 to m do write(c[i,j],bl); end; end; procedure Doc; var f: text; i,j,k,r: integer; begin fillchar(c,sizeof(c),0); assign(f,fn); reset(f); readln(f,n,m); for i := 1 to n do for j := 1 to m do read(f,c[i,j]); close(f); end; procedure Run; var v: integer; begin Doc; Print; v := Par; Ghi(v); writeln(nl, ' ket qua: '); PrintArray(a,1,n); end; BEGIN Run; writeln(nl,' Fini'); readln; END. // Dev-C++: Autum2 #include #include using namespace std; // D A T A A N D V A R I A B L E S const char * fn = "autum2.inp"; const char * gn = "autum2.out"; const int mn = 201; // so nguoi va so qua toi da int a[mn]; // a[i] = j: em i nhan qua j int b[mn]; // b[j] = i: qua j trong tay em i int t[mn]; // t[j] = i : em j nhuong qua cho ban i int c[mn][mn]; // c[i][j] = 1: i thich qua j int d[mn]; // d[j] khi j nhuong qua cho i int n; // so em nho int m; // so qua int st[mn]; // stack int p; // con tro stack int imax, jmax, dmax; // P R O T O T Y P E S int main(); void Doc(); void Print(); int Par(); int Xep(int); void Update(int, int); void PrintArray(int [], int , int ); void Ghi(int); void Nap(int, int); void Mark(int, int); // I M P L E M E N T A T I O N int main() { Doc(); Print(); int v = Par(); Ghi(v); cout << endl << " Ket qua: "; PrintArray(a,1,n); cout << endl; system("PAUSE"); return EXIT_SUCCESS; } void Ghi(int v) { int vmax = 0; for (int i = 1; i <= n; ++i) if (a[i] > 0) vmax += c[i][a[i]]; ofstream g(gn); g << vmax << endl; for (int i = 1; i <= n; ++i) if (a[i] > 0) g << i << " " << a[i] << endl; g.close(); } void PrintArray(int a[], int d, int c) { int i; for (i = d; i <= c; ++i) cout << a[i] << " "; } void Update(int i, int j){ int c; do { c = a[i]; // i bo qua c a[i] = j; b[j] = i; // i nhan qua moi j i = t[i]; j = c; // chuyen qua nguoi khac } while (c > 0); } void Mark(int i, int j) { int sum = d[i]+c[i][j];// neu i nhan qua moi j if (sum > dmax) { // ghi nhan phuong an tot hon dmax = sum; imax = i; jmax = j; } } void Nap(int i, int j) { // Nap j vao st // em j se nhuong qua a[j] cho em i // em i bo qua a[i] de lay a[j] if (t[j]>0) return; // j da co st[++p] = j; t[j] = i; d[j] = d[i] + c[i][a[j]] - c[j][a[j]] ;// do lech } int Xep(int i) { // tim qua cho em i memset(t, 0, sizeof(t)); memset(d, 0, sizeof(d)); // d[i] - do lech neu i nhuong qua int j; dmax = 0; p = 0; Nap(i,i); while(p > 0) { i = st[p--]; // lay ngon stack for (j = 1; j <= m; ++j) // duyet cac mon qua if (b[j] == 0) Mark(i,j); // qua j chua chia else Nap(i,j);// danh sach nhuong qua } // while if (dmax = 0) return 0; Update(imax, jmax); return 1; // Xep duoc qua cho em i } int Par(){ // Cap ghep int v = 0, i; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for (i = 1; i <= n; ++i) v += Xep(i); return v; } void Print() { // Hien thi ma tran c cout << endl << " input: "; cout << endl << n << " " << m << endl; int i,j; for (i = 1; i <= n; ++i){ for (j = 1; j <= m; ++j) cout << c[i][j] << " "; cout << endl; } } void Doc(){ memset(c,0,sizeof(c)); ifstream f(fn); f >> n >> m; int i,j; for (i = 1; i <= n; ++i) for (j = 1; j <= m; ++j) f >> c[i][j]; f.close(); } Каталог: tailieu tailieu -> MỘt số thủ thuật khi sử DỤng phần mềm adobe presenter tạo bài giảng e-learning tailieu -> Trung tâM ĐÀo tạo mạng máy tính nhất nghệ 105 Bà Huyện Thanh Quan – 205 Võ Thị Sáu, Q3, tp. Hcm tailieu -> Céng hßa x· héi chñ nghÜa viÖt nam Độc lập tự do hạnh phúc tailieu -> Lê Xuân Biểu giao thông vận tảI ĐẮk lắK 110 NĂm xây dựng và phát triểN (1904 2014) nhà xuất bảN giao thông vận tảI tailieu -> ĐỀ thi học sinh giỏi tỉnh hải dưƠng môn Toán lớp 9 (2003 2004) (Thời gian : 150 phút) Bài 1 tailieu -> A. ĐẠi số TỔ HỢp I. Kiến thức cơ bản quy tắc cộng tailieu -> Wikipedia luôn có mặt mỗi khi bạn cần giờ đây Wikipedia cần bạn giúp tailieu -> CHÍnh phủ CỘng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh phúc tailieu -> VĂn phòng cộng hoà XÃ HỘi chủ nghĩa việt nam tải về 2.51 Mb. Chia sẻ với bạn bè của bạn:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||