Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# - Tập 3 - Chương 5: Luyện tập từ các đề thi

[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 Robots 
Mộ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.INP 
Dò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.OUT 
Dò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. 
ROBOTS.INP ROBOTS.OUT Giải thích Khoảng cách AB = 1; AC = 3 trên đường thẳng 
ABC; 
robot R cần 3, B cần 1 và G cần 2 đơn vị năng lượng để di 
chuyển 1 đơn vị khoảng cách; 
Phòng A có 2 robot R, 1 robot B và 2 robot G; 
Phòng B có 1 robot R, 4 robot B và 3 robot G; 
Phòng C có 2 robot R, 2 robot B và 1 robot G. 
Kết quả: Nếu tập hợp các robot mũ đỏ R về phòng A, các 
robot mũ xanh lá G về phòng B và các robot mũ xanh B về 
phòng C thì chi phí năng lượng là tối thiểu và bằng 40. 
1 3 
3 1 2 
2 1 2 
1 4 3 
2 2 1 
40 
RGB 
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