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.
|
5.17 GameBulgariaĐây là trò chơi một người tạm gọi là bạn Vova với hai dãy số nguyên dương: a gồm n > 1 phần tử và b gồm m > 1 phần tử. Vova phải thực hiện các thao tác sau đây:
trong đóci = (siui)(tivi), i = 1, 2, …, k;si là tổng các phần tử của nhóm i trong dãy a;ui là số phần tử của nhóm i trong dãy a;ti là tổng các phần tử của nhóm i trong dãy b;vi là số phần tử của nhóm i trong dãy b;Hãy cho biết giá trị min của c.
Giải thíchVới thí dụ trên, Vova xét các phương án sau: Phương án 1: Chọn k = 1. Khi đó mỗi dãy tự thạo thành một nhóm: a = (3,7,4); b = (5,2). Thao tác trên dãy a: s1 = 3+7+4 = 14; u1 = 3; Thao tác trên dãy b: t1 = 5+2 = 7; v1 = 2; c = c1 = (s1 u1)(t1v1) = (143)(72) = 115 = 55. Phương án 2: Chọn k = 2. Khi đó mỗi dãy có đúng 2 nhóm: a = (3)(7,4); b = (5)(2) hoặc a = (3,7)(4); b = (5)(2) . Ta xét lần lươt từng phương án con 2.1 và 2.2. Phương án 2.1: a = (3)(7,4); b = (5)(2) Thao tác trên dãy a: s1 = 3; u1 = 1; s2 = 7+4 = 11; u2 = 2; Thao tác trên dãy b: t1 = 5; v1 = 1; t2 = 2; v2= 1; c1 = (s1 u1)(t1v1) = (31)(51) = 24 = 8; c2 = (s2 u2)(t2v2) = (112)(21) = 91 = 9; c = c1 + c2 = 8 + 9 = 17. Phương án 2.2: a = (3,7)(4); b = (5)(2) Thao tác trên dãy a: s1 = 3+7 = 10; u1 = 2; s2 = 4; u2 = 1; Thao tác trên dãy b: t1 = 5; v1 = 1; t2 = 2; v2= 1; c1 = (s1 u1)(t1v1) = (102)(51) = 84 = 32; c2 = (s2 u2)(t2v2) = (41)(21) = 31 = 3; c = c1 + c2 = 32 + 3 = 35. Vậy cmin = min(55, 17, 35) = 17.
Thật vậy, gỉa sử hai nhóm cuối của dãy a và b, nhóm thứ k, đều chứa hơn 1 phần tử. Ta gọi phương án này là P1. Ta xây dựng phương án P2 gồm k+1 nhóm như sau. Tách hai nhóm cuối của a và b thành hai nhóm nhỏ và gọi tổng của các nhóm đó lần lượt là A+B cho nhóm của dãy a và C+D cho nhóm của dãy b. Khi đó (A+B)(C+D) = AC + AD + BC + BD > AC + BD. Từ đây suy ra phương án phân nhóm P2 với k+1 nhóm sẽ cho kết quả nhỏ hơn phương án phân nhóm P1 thành k nhóm như trong bảng dưới đây:
Như vậy, để đạt trị cmin, nhóm thứ k của một trong 2 dãy a hoặc b phải chứa đúng 1 phần từ. Ta kí hiệu cho các tình huống này là:
hoặc
Kí hiệu c(n,m) là giá trị cmin của bài toán với hai dãy a(1..n) và b(1..m). Với tình huống 1:1 ta có hai nhóm cuối là (an) và (bm), do đó c(n,m) = c(n1,m1) + anbm Với tình huống 1:N ta giả sử có hai nhóm cuối là (an) và (bi ,bi+1, ... ,bm-1,bm), i < m. Ta có an(bi + bi+1+ ... +bm-1+bm) = an(bi + bi+1+ ... +bm-1) + anbm , do đó c(n,m) = c(n,m1) + anbm Với tình huống N:1 ta giả sử có hai nhóm cuối là (aj ,aj+1, ... ,an-1,an), j < n và (bm) . Xét tương tự như tình huống 1:N ta thu được c(n,m) = c(n1,m) + anbm Vậy c(n,m) = min { c(n1,m1) + anbm, c(n,m1) + anbm , c(n1,m) + anbm }, hay c(n,m) = min { c(n1,m1) , c(n,m1) , c(n1,m) } + anbm Khi n = 1, với mọi m 1, mỗi dãy tạo thành đúng 1 nhóm nên ta cóc(n,m) = a1(b1 + b2+ ... +bm-1+bm).Tương tự, khi m = 1, với mọi n 1, mỗi dãy tạo thành đúng 1 nhóm nên ta cóc(n,m) = (a1 + a2+ ... +an-1+an)b1.Để cài đặt ta dùng 2 mảng 1 chiều c và d.Khi đọc dữ liệu bạn nhớ giảm đồng loạt 1 đơn vị cho các số trong hai dãy a và b.Mảng c lúc đầu được khởi trị với n = 1, c[j] = a[1]*(b[1] + ... + b[j]), j = 1..m với ý nghiã dãy a có đúng 1 phần tử a[1] do đó lúc đầu chỉ có 2 nhóm (a[1]) và (b[1..j]).Sau đó ta lặp n1 lần mỗi lần lặp thứ i ta tính trị cho hàm c(i,j), j = 1..m và ghi vào mảng d vớid[1] = c[1] +a[i]*b[1]d[j] = min { c[j1], c[j], d[j1] } + a[i]*b[j], j = 2..m(* Game.pas *) uses crt; const mn = 201; fn = 'vova.inp'; gn = 'vova.out'; bl = #32; nl = #13#10; type mi1 = array[0..mn] of integer; var a,b,c,d: mi1; n, m: integer; function Min(a, b, c: integer): integer; begin if a > b then a := b; if a < c then Min := a else Min := c; end; function Cmin: integer; var i,j: integer; begin fillchar(c,sizeof(c),0); d := c; { Khoi tri: 2 day a[1] , b[1..m] } for j := 1 to m do c[j] := c[j-1] + a[1]*b[j]; for i := 2 to n do begin d[1] := c[1] + a[i]*b[1]; for j := 2 to m do d[j] := Min(c[j-1], c[j],d[j-1]) + a[i]*b[j]; c := d; end; Cmin := d[m]; end; procedure Doc; var i: integer; f: text; begin assign(f,fn); reset(f); read(f,n,m); writeln(nl,n, bl, m); for i := 1 to n do begin read(f,a[i]); dec(a[i]); write(a[i],bl); end; writeln; for i := 1 to m do begin read(f,b[i]); dec(b[i]); write(b[i],bl); end; close(f); end; procedure Ghi(v: integer); var g: text; begin assign(g,gn); rewrite(g); writeln(g,v); close(g); end; BEGIN Doc; Ghi(Cmin); writeln(nl,' Fini'); readln; END. // DevC++: game.cpp #include #include #include using namespace std; const int mn = 201; const char * fn = "vova.inp"; const char * fn = "vova.out"; int a[mn], b[mn], c[mn], d[mn]; int n, m; void Doc(); int Cmin(); int Min(int, int, int); void Ghi(int); main() { Doc(); Ghi(Cmin()); cout << endl << " Fini "; cin.get(); return 0; } int Min(int x, int y, int z) { if (x > y) x = y; return (x < z) ? x : z; } int Cmin() { int i,j; memset(c,0,sizeof(c)); memset(d,0,sizeof(d)); for (j = 1; j <= m; ++j) c[j] = c[j-1] + a[1]*b[j]; for (i = 2; i <= n; ++i) { d[1] = c[1] + a[i]*b[1]; for (j = 2; j <= m; ++j) d[j] = Min(c[j-1], c[j],d[j-1]) + a[i]*b[j]; memcpy(c,d,sizeof(d)); } return d[m]; } void Doc() { ifstream f(fn); f >> n >> m; cout << endl << n << " " << m << endl; int i; for (i = 1; i <= n; ++i) { f >> a[i]; --a[i]; cout << a[i] << " "; } cout << endl; for (i = 1; i <= m; ++i) { f >> b[i]; --b[i]; cout << b[i] << " "; } f.close(); } void Ghi(int v) { ofstream g(gn); g << v; g.close(); } 5.18 RobotsMột khu nghiên cứu Robot có 3 phòng thí nghiệm là A, B và C bố trí trên một tuyến đường thẳng theo thứ tự đã nêu. Mỗi phòng đều có thể có 3 loại robot thông minh là robot mũ đỏ R, robot mũ xanh B và robot mũ xanh lá G. Người ta ra lệnh cho các robot phải tự bàn nhau để thực hiện nhiệm vụ sau đây: di chuyển về các phòng sao cho mỗi phòng chỉ có một loại robot và năng lượng chi phí cho việc di chuyển là ít nhất.Hãy cùng bàn với các robot để chọn một phương án tối ưu.Dữ liệu vào: text file ROBOTS.INPDòng thứ nhất: hai số nguyên dương biểu thị khoảng cách AB và AC;Dòng thứ hai: ba số nguyên dương r b g cho biết chi phí năng lượng của mỗi loại robot R, B và G để di chuyển 1 đơn vị khoảng cách;Dòng thứ ba: ba số nguyên không âm cho biết số lượng robot mỗi loại R, B và G trong phòng A;Dòng thứ tư: tương tự như dòng thứ ba, chứa thông tin về phòng B;Dòng thứ năm: tương tự như dòng thứ ba, chứa thông tin về phòng C.Dữ liệu ra: text file ROBOTS.OUTDòng thứ nhất: tổng chi phí năng lượng tối thiểu cho các robot di chuyển;Dòng thứ hai: một hoán vị của ba chữ cái R, B, G viết liền nhau cho biết phương án tối ưu bố trí các robot vào các phòng.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 vì chỉ đòi hỏi khoàng vài chục lần tính toán đơn giản. Kí hiệu XYZ là một phương án bố trí robot loại X vào phòng A, loại Y vào phòng B và loại Z vào phòng C. Ta có tất cả 6 phương án là RBG, RGB, BRG, BGR, GRB và GBR. Ta tính chi phí cho mỗi phương án rồi chọn phương án với chi phí min. Ta sử dụng các hàm hỗ trợ sau đây: Move(r, i, j) chi phí di chuyển toàn bộ robot loại r hiện có trong phòng i sang phòng j ≠ i, i, j = A, B, C . PhuongAn(r1, r2, r3) – chi phí cho phương án đưa các robot loại r1 về phòng A, loại r2 về phòng B và robot loại r3 về phòng C. (* ROBOTS.PAS *) uses crt; const fn = 'ROBOTS.INP'; gn = 'ROBOTS.OUT'; bl = #32; nl = #13#10; NN = 3; A = 1; B = 2; C = 3; { cac phong } RR = 1; RB = 2; RG = 3; { mau mu cua robots } type mi1 = array[0..NN] of integer; mi2 = array[0..NN] of mi1; var AB,AC: integer; { Khoảng cách } energy: mi1; { energy[i] - chi phí năng lượng của robot loại i } number: mi2; { number[i,j] - so luong robot loai j trong phong i } procedure Doc; var i,j: integer; f: text; begin assign(f,fn); reset(f); read(f,AB,AC); write(nl,' Khoang cach: ',AB,bl,AC); write(nl,' Nang luong: '); for i := 1 to NN do begin read(f,energy[i]); write(energy[i],bl); end; writeln(nl, ' Phan bo: '); for i := 1 to NN do begin writeln; for j := 1 to NN do begin read(f,number[i,j]); write(number[i,j],bl) end; end; close(f); end; (* Chi phi chuyen robot loai r tu phong i sang phong j *) function Move(r, i, j: integer): integer; var e: integer; begin e := energy[r]*number[i][r]; case i of A: if (j = B) then e := e*AB else if (j = C) then e := e*AC else e := 0; B: if (j = A) then e := e*AB else if (j = C) then e := e*(AC-AB) else e := 0; C: if (j = A) then e := e*AC else if (j = B) then e := e*(AC-AB) else e := 0; end; Move := e; end; function PhuongAn(r1, r2, r3: integer): integer; begin PhuongAn := Move(r1,B,A) + Move(r1,C,A)+ Move(r2,A,B) + Move(r2,C,B)+ Move(r3,A,C) + Move(r3,B,C); end; procedure XuLi; var i, imin, p: integer; pa: array[1..6] of integer; g: text; begin p := 1; { phuong an 1: RBG } pa[p] := PhuongAn(RR,RB,RG); inc(p); { phuong an 2: RGB } pa[p] := PhuongAn(RR,RG,RB); inc(p); { phuong an 3: BRG } pa[p] := PhuongAn(RB,RR,RG); inc(p); { phuong an 4: BGR } pa[p] := PhuongAn(RB,RG,RR); inc(p); { phuong an 5: GRB } pa[p] := PhuongAn(RG,RR,RB); inc(p); { phuong an 6: GBR } pa[p] := PhuongAn(RG,RB,RR); imin := 1; for i := 1 to 6 do if (pa[i] < pa[imin]) then imin := i; assign(g,gn); rewrite(g); writeln(g,pa[imin]); case imin of 1: write(g,'RBG'); 2: write(g,'RGB'); 3: write(g,'BRG'); 4: write(g,'BGR'); 5: write(g,'GRB'); 6: write(g,'GBR'); end; close(g); end; BEGIN Doc; XuLi; writeln(nl,' Fini'); readln; END. // DecC++: Robots.cpp #include #include #include using namespace std; const int A = 0; // Phong 0: A const int B = 1; // Phong 1: B const int C = 2; // Phong 2: C const int RR = 0; // Red Robot const int RB = 1; // Blue Robot const int RG = 2; // Green Robot const int NN = 3; // So loai Robot = 3 const char * fn = "robots.inp"; const char * gn = "robots.out"; const char bl = 32; int energy[NN]; // chi phi nag luong int number[NN][NN]; // numer[i][j] - so luong robot loai j trong phong i int AB, AC; // Khoang cach AB, AC int pa[6]; // cac phuong an void Doc() { int i, j; ifstream f(fn); f >> AB >> AC; cout << endl << "Khoang cach: " << AB << bl << AC; cout << endl << " Nang luong: "; for (i = 0; i < NN; ++i) { f >> energy[i]; cout << energy[i] << bl; } cout << endl << " Phan bo: "; for (i = 0; i < NN; ++i) { cout << endl; for (j = 0; j < NN; ++j) { f >> number[i][j]; cout << number[i][j] << bl; } } f.close(); } int Move(int r, int from, int to) { // chi phoi chuyen robot r tu phong i sang phong j int e = energy[r]*number[from][r]; switch(from) { case A: if (to == B) return e*AB; else if (to == C) return e*AC; case B: if (to == A) return e*AB; else if (to == C) return e*(AC-AB); case C: if (to == A) return e*AC; else if (to == B) return e*(AC-AB); } } int PhuongAn(int r1, int r2, int r3) { return (Move(r1,B,A)+Move(r1,C,A)+ Move(r2,A,B)+Move(r2,C,B)+ Move(r3,A,C)+Move(r3,B,C)); } void XuLi() { int p, i, imin; p = 0; // phuong an 0: RBG pa[p] = PhuongAn(RR,RB,RG); cout << endl << "RBG: " << pa[p]; ++p; // phuong an 1: RGB pa[p] = PhuongAn(RR,RG,RB); cout << endl << "RGB: " << pa[p]; ++p; // phuong an 2: BRG pa[p] = PhuongAn(RB,RR,RG); cout << endl << "BRG: " << pa[p]; ++p; // phuong an 3: BGR pa[p] = PhuongAn(RB,RG,RR); cout << endl << "BGR: " << pa[p]; ++p; // phuong an 4: GRB pa[p] = PhuongAn(RG,RR,RB); cout << endl << "GRB: " << pa[p]; ++p; // phuong an 5: GBR pa[p] = PhuongAn(RG,RB,RR); cout << endl << "GBR: " << pa[p]; imin = 0; for (i = 1; i < 6; ++i) if (pa[i] < pa[imin]) imin = i; ofstream g(gn); g << pa[imin] << endl; switch (imin) { case 0: g << "RBG"; break; case 1: g << "RGB"; break; case 2: g << "BRG"; break; case 3: g << "BGR"; break; case 4: g << "GRB"; break; case 5: g << "GBR"; break; } g.close(); } main(){ Doc(); XuLi(); cout << endl << " Fini"; cin.get(); return 0; } - Giao thừa 2010 Каталог: 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:
| |||||||||||||||||||||||||||