Sáng tạo trong Thuật toán và Lập trình với ngôn ngữ Pascal và C # - Tập 2

161 trang phuongnguyen 5070

Download

Bạn đang xem 20 trang mẫu của tài liệu "Sáng tạo trong Thuật toán và Lập trình với ngôn ngữ Pascal và C # - Tập 2", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

sangtao2_v5_10_6853_372925.pdf

Nội dung text: Sáng tạo trong Thuật toán và Lập trình với ngôn ngữ Pascal và C # - Tập 2

T Ủ SÁCH TRI THỨC DUY TÂN NGUYỄN XUÂN HUY S Á N G T Ạ O TRONG THUẬT TOÁN V À L Ậ P T R Ì N H với ngôn ngữ Pascal và C # T ậ p 2 Tuyển các bài toán Tin nâng cao cho học sinh và sinh viên giỏi 1
MỤC LỤC . Chương 1 Các bài toán về đoạn thẳng 4 Bài 1.1 Đoạn rời 1 4 Bài 1.2 Đoạn gối 1 8 Bài 1.3 Đoạn gối 2 11 Bài 1.4 Đoạn gối 3 13 Bài 1.5 Đoạn bao nhau 1 16 Bài 1.6 Đoạn bao nhau 2 19 Bài 1.7 Phủ đoạn 1 21 Bài 1.8 Xanh đỏ tím vàng 1 24 Bài 1.9 Xanh đỏ tím vàng 2 27 Bài 1.10 Phủ đoạn 2 30 Bài 1.11 Đoạn rời 2 34 Bài 1.12 Ghép hình chữ nhật 35 Bài 1.13 Xanh đỏ 37 Bài 1.14 Xếp đoạn 39 Bài 1.15 Các hình chữ nhật 41 Bài 1.16 Các tam giác vuông cân 46 Chương 2 Các hàm Next 52 Bài 2.1 Số sát sau cùng độ cao 52 Bài 2.2 Số sát sau cùng chữ số 54 Bài 2.3 Các hoán vị 55 Bài 2.4 Tổ hợp 58 Bài 2.5 Số Kapreka 61 Bài 2.6 Khóa vòng 66 Bài 2.7 Trả tiền 69 Bài 2.8 Dãy Farey 72 Bài 2.9 Qúy Mùi 77 Bài 2.10 Tổng đoạn 79 Bài 2.11 Đoạn không giảm dài nhất 82 Bài 2.12 Đoạn đơn điệu dài nhất 84 Bài 2.13 Lũy thừa 2, 3 và 5 87 Chương 3 Trò chơi 89 Bài 3.1. Bốc sỏi A 90 Bài 3.2. Bốc sỏi B 92 Bài 3.3. Bốc sỏi C 94 Bài 3.4. Chia đoạn 97 Bài 3.5. Bốc sỏi D 97 Bài 3.6. Bốc sỏi E 99 Bài 3.7. Bốc sỏi F 100 Bài 3.8. Chia Hình chữ nhật 102 Bài 3.9. Bốc sỏi G 103 Bài 3.10. Chia Hình hộp 103 2
Bài 3.11. Trò chơi NIM 104 Bài 3.12. Cờ bảng 106 Bài 3.13. Cờ đẩy 113 Bài 3.14. Bốc sỏi H 114 Chương 4 Các thuật toán sắp đặt 115 4.1 Cờ tam tài 115 4.2 Lưới tam giác đều 117 4.3 Dạng biểu diễn của giai thừa 121 4.4 Xếp sỏi 127 4.5 Dãy các hoán vị 130 4.6 Bộ bài 134 4.7 Thuận thế 141 4.8 Các nhà khoa học 144 4.9 Chín chiếc đồng hồ 152 4.10 Số duy nhất 159 3
Chương 1 Các bài toán về đoạn thẳng Bạn cần chú ý đọc kĩ đề bài. Có những bài mới xem ta thấy từa tựa như nhau nhưng kết quả là khác nhau. Điển hình là những bài tối ưu hóa, tức là những bài tìm max hay min của một hàm. Các ràng buộc chỉ khác nhau đôi chút nhưng độ khó sẽ thì lại khác xa nhau. Bài 1.1 Đoạn rời 1 Cho N đoạn thẳng với các điểm đầu ai và điểm cuối bi là những số nguyên trong khoảng 1000 1000, ai r thì lấy đoạn j đưa vào kết quả và chỉnh r là đầu phải của đoạn j, r := bj. Độ phức tạp: cỡ NlogN chi phí cho quick sort. 4
(* Pascal *) (*=== Doan roi 1: Liet ke toi da cac doan thang khong giao nhau ===*) program DoanRoi1; uses crt; const mn = 1001; bl = #32 {Dấu cách}; nl = #13#10 {Xuống dòng}; fn = 'doan.inp'; gn = 'doan.out'; type { Mô tả một đoạn } KieuDoan = record a,b: integer; id: integer; { Chỉ số đoạn } end; md1 = array[0 mn] of KieuDoan; mi1 = array[0 mn] of integer; var n,m,r: integer; { n – số lượng đoạn } { m – số lượng đoạn được chọn } { r – đầu phải đang duyệt } d: md1; { các đoạn d[1 n] } f,g: text; c: mi1; { mảng chứa kết qủa } procedure Doc; var i: integer; begin assign(f,fn); reset(f); readln(f,n); for i := 1 to n do begin read(f,d[i].a,d[i].b); d[i].id := i; end; close(f); end; (* Sắp tăng các đoạn d[t p] theo đầu phải b. *) procedure Qsort(t,p: integer); var i,j,m: integer; x: KieuDoan; begin i := t; j := p; m := d[(i + j) div 2].b; while (i <= j) do begin while (d[i].b < m) do i := i + 1; while (m < d[j].b) do j := j - 1; if (i <= j) then begin x := d[i]; d[i] := d[j]; d[j] := x; i := i + 1; j := j - 1; end; end; if (t < j) then Qsort(t,j); if (i < p) then Qsort(i,p); end; procedure XuLi; var i: integer; 5
begin m := 1; c[m] := 1; { Đưa đoạn 1 vào kết quả } r := d[m].b; { đầu phải của đoạn cuối trong kết quả } for i := 2 to n do if (r (int.Parse)); n = a[0]; // so doan d = new Doan[n]; int j = 1; for (int i = 0; i < n; ++i, j += 2) // đọc đoạn i d[i] = new Doan(a[j], a[j + 1], i + 1); } // Doc static public void XuLi() { m = 0; 6
c = new int[n]; c[m++] = 0; // chọn đoạn 0 int r = d[0].b; // thiết lập giới hạn phải for (int i = 1; i m) j; if (i <= j) { Doan x = d[i]; d[i] = d[j]; d[j] = x; ++i; j; } } if (t < j) QSortB(d, t, j); if (i < p) QSortB(d, i, p); } static public void Ghi() { StreamWriter g = File.CreateText(gn); g.WriteLine(m); for (int i = 0; i < m; ++i) g.WriteLine(d[c[i]].id); g.Close(); } // Hiển thị lại các files input, output để kiểm tra static public void XemKetQua() { Console.WriteLine("\n Input " + fn); Console.WriteLine(File.ReadAllText(fn)); Console.WriteLine("\n Output " + gn); Console.WriteLine(File.ReadAllText(gn)); } }// DoanRoi1 public struct Doan { // Mô tả một đoạn public int a, b, id; public Doan(int x1,int x2,int z) // Tạo đoạn mới { a = x1; b = x2; id = z; } } // Doan } // SangTao2 Giải thích chương trình C# 1. Khai báo file text f, mở file tên fn = “doan.inp” để đọc toàn bộ dữ liệu vào biến string s rồi đóng file lại. StreamReader f = File.OpenText(fn); string s = f.ReadToEnd(); f.Close(); 2. Tách string s thành mảng các string ss[i] theo các dấu ngăn cách khai báo trong new char [], loại bỏ các string rỗng. Trong một dòng văn bản thường chứa các dấu ngăn cách sau đây (gọi là các dấu trắng) ' ' - dấu cách '\n' - dấu hết dòng (dấu xuống dòng) '\r' - dấu về đầu dòng (dấu ENTER/RETURN) '\t' - dấu tab 7
string[] ss = s.Split(new char [] { ' ', '\n', '\r', '\t' }, StringSplitOptions.RemoveEmptyEntries); 3. Chuyển đổi mỗi string ss[i] thành số nguyên và ghi trong mảng nguyên a int[] a = Array.ConvertAll(ss, new Converter (int.Parse)); Sau bước 3 dữ liệu trong file “doan.inp” được đọc vào mảng a[0 n-1]. 4. Lấy số lượng đoạn : n = a[0]; 5. Xin cấp phát n con trỏ kiểu Doan : d = new Doan[n]; 6. Cấp phát và khởi trị cho mỗi đoạn i = 0 n-1. Đoạn i có chỉ số là i+1: int j = 1; for (int i = 0; i < n; ++i, j += 2) // doc doan i { d[i] = new Doan(a[j], a[j + 1], i + 1); } Có nhiều phương thức đọc/ghi các text file. Bạn cần lựa chọn và ghi nhớ một phương thức mà bạn cảm thấy tiện lợi nhất. 7. Bạn có thể tổ chức dữ liệu Doan theo dạng struct (bản ghi) hoặc dạng class (lớp). Điểm khác nhau căn bản giữa hai cấu trúc này là, theo qui ước ngầm định struct được truyền theo trị (by val) còn class được truyền theo chỉ dẫn (by ref). public struct Doan { public int a, b; // diểm đầu và điểm cuối đoạn public int id; // chỉ số đoạn // phương thức tạo đoạn public Doan(int x1, int x2, int z) { a = x1; b = x2; id = z; } } Bài 1.2 Đoạn gối 1 Cho N đoạn thẳng trên trục số với các điểm đầu ai và điểm cuối bi là những số nguyên trong khoảng 1000 1000, ai < bi. Hãy tìm số lượng tối đa K đoạn thẳng gối nhau liên tiếp. Hai đoạn thẳng [a,b] và [c,d] được gọi là gối nhau nếu xếp chúng trên cùng một trục số thì điểm đầu đoạn này trùng với điểm cuối của đoạn kia, tức là c = b hoặc d = a. DOAN.INP DOAN.OUT Dữ liệu vào: tệp văn bản DOAN.INP: xem Đoạn gối 1 Dữ liệu ra: tệp văn bản DOAN.OUT 5 3 chứa duy nhất một số tự nhiên K. 2 7 Thí dụ này cho biết có tối đa 3 đoạn gối nhau liên tiếp là 1 3 [1,3], [3,4] và [4,5]. 7 9 3 4 4 5 Thuật toán Phương pháp: Quy hoạch động + Tham. Giả sử các đoạn được sắp tăng theo đầu phải b. Kí hiệu c(i) là số lượng tối đa các đoạn thẳng gối nhau tạo thành một dãy nhận đoạn i làm phần tử cuối dãy (khi khảo sát các đoạn từ 1 i). Ta có c(1) =1, Với i = 2 N: c(i) = max { c(j) | 1 j < i, Đoạn j kề trước đoạn i: bj = ai } + 1. 8
Lợi dụng các đoạn sắp tăng theo đầu phải b, với mỗi đoạn i ta chỉ cần duyệt ngược các đoạn j đứng trước đoạn i cho đến khi phát hiện bất đẳng thức bj c[i]) then c[i] := c[j]; end; c[i] := c[i] + 1; end; end; procedure Ket; { Tim c max va hien thi ket qua } var i,imax: integer; begin assign(g,gn); rewrite(g); imax := 1; for i := 2 to n do if (c[imax] < c[i]) then imax := i; writeln(g,c[imax]); close(g); end; BEGIN Doc; Qsort(1,n); XuLi; Ket; END. 9
// C# using System; using System.IO; using System.Collections; /*=== Đoạn Gối 1: Số lượng tối đa các đoạn gối nhau ===*/ namespace SangTao2 { class DoanGoi1 { static public Doan[] d; // các đoạn d[0 n-1] static int n; // số đoạn static int m;// số max các đoạn gối nhau const string fn = "doan.inp"; // input file const string gn = "doan.out"; // output file static void Main(string[] args) { Doc(); QSortB(d,0,n-1); XuLi(); Ghi(); XemKetQua(); Console.WriteLine("\n Fini "); Console.ReadLine(); } static public void Doc(): tự viết // Sắp tăng các đoạn d[t p] theo đầu phải b static public void QSortB(Doan[]d,int t,int p): tự viết static public void XuLi() { int[] c = new int[n]; // c[i] – số lượng max đoạn gối kếtthúc tại đoạn i c[0] = 1; // lấy đoạn 0 int imax = 0; for (int i = 1; i = 0; j) { if (d[j].b c[jmax]) jmax = j; } c[i] = c[jmax] + 1; if (c[i] > c[imax]) imax = i; } m = c[imax]; } static public void Ghi(){ StreamWriter g = File.CreateText(gn); g.WriteLine(m); g.Close(); } // Hien thi lai cac files input, output static public void XemKetQua(): tự viết }// DoanGoi1 public struct Doan { public int a,b; public Doan(int x1, int x2) { a = x1; b = x2; } } // Doan } // SangTao2 Chú thích 10
Trong bài này ta không cần sử dụng trường chỉ số riêng id cho kiểu đoạn. Trong phương án C# ta tranh thủ tìm giá trị cmax = c[imax] sau mỗi lần tính c[i]. Bài 1.3 Đoạn gối 2 Cho N đoạn thẳng trên trục số với các điểm đầu ai và điểm cuối bi là những số nguyên trong khoảng 1000 1000, ai 0) then 0 2 4 begin GiaiTrinh(t[i]); writeln(g,d[i].id); end; end; Độ phức tạp: cỡ N2. (* Pascal *) (*=== Doan Goi 2: Liet ke toi da cac doan thang goi nhau liên tiep ===*) program DoanGoi2; uses crt; const mn = 1001; bl = #32; nl = #13#10; fn = 'doan.inp'; gn = 'doan.out'; type KieuDoan = record a,b,id: integer; end; md1 = array[0 mn] of KieuDoan; mi1 = array[0 mn] of integer; var n,m: integer; { n - so luong doan, m - so doan duoc chon } d: md1; // cac doan 11
f,g: text; c: mi1; { c[i] = so luong max doan goi voi doan i } t: mi1; { tro truoc } procedure Doc: tự viết procedure Qsort(i1,i2: integer): tự viết procedure XuLi; var i,j,jmax: integer; begin fillchar(t,sizeof(t),0); {Khởi trị mảng trỏ trước} c[1] := 1; for i := 2 to n do begin c[i] := 0; jmax := i; for j := i-1 downto 1 do begin if (d[j].b c[jmax]) then jmax := j; end; c[i] := c[jmax]+1; t[i] := jmax; end; end; procedure GiaiTrinh(i: integer): tự viết; procedure Ket; var i,imax: integer; begin assign(g,gn);rewrite(g); imax := 1; for i := 2 to n do if (c[imax] < c[i]) then imax := i; writeln(g,c[imax]); GiaiTrinh(imax); close(g); end; BEGIN Doc; Qsort(1,n); XuLi; Ket; END. // C# using System; using System.IO; using System.Collections; /*=== * Doan Goi 2: Liet ke toi da cac doan goi nhau * ===*/ namespace SangTao2 { class DoanGoi2 { static public Doan[] d; static int n; // tong so doan static int[] t; // tro truoc const string fn = "doan.inp"; const string gn = "doan.out"; static void Main(string[] args){ Doc(); QSortB(d,0,n-1); int m = 0; // so doan tim duoc int imax = 0; // chi so doan cuoi trong day max 12
XuLi(ref imax, ref m); Ghi(imax,m); XemKetQua(); Console.ReadLine(); } static public void Doc(): tự viết static public void XuLi(ref int imax, ref int m) { int [] c = new int[n]; t = new int[n]; Array.Clear(t, 0, t.Length); t[0] = -1; // c[i] - so luong doan goi ket thuc tai doan i c[0] = 1; // lay doan 0 imax = 0; for (int i = 1; i = 0; j){ if (d[j].b c[jmax]) jmax = j; } c[i] = c[jmax] + 1; t[i] = jmax; if (c[i] > c[imax]) imax = i; } m = c[imax]; } // Sap tang cac doan theo dau phai (b) static public void QSortB(Doan[] d,int i1,int i2): tự viết static void Path(StreamWriter g, int imax) { if (imax != -1) { Path(g,t[imax]); g.WriteLine(d[imax].id); } } static public void Ghi(int imax, int m){ StreamWriter g = File.CreateText(gn); g.WriteLine(m); Path(g, imax); g.Close(); } // Hien thi lai cac files input, output static public void XemKetQua(): tự viết } // DoanGoi2 public struct Doan: tự viết } // SangTao2 Bài 1.4 Đoạn gối 3 Cho N đoạn thẳng trên trục số với các điểm đầu ai và điểm cuối bi là những số nguyên trong khoảng 1000 1000, ai < bi. i = 1 n. Liệt kê các đoạn thẳng gối nhau có tổng chiều dài C lớn nhất. Dữ liệu vào: tệp văn bản DOAN.INP: xem bài Đoạn gối 1. DOAN.INP DOAN.OUT 13
Dữ liệu ra: tệp văn bản DOAN.OUT 8 39 Dòng đầu tiên: số tự nhiên C. 2 7 2 1 3 4 Mỗi dòng tiếp theo chứa một số tự nhiên biểu thị chỉ số của 7 9 đoạn thẳng gối nhau liên tiếp trong dãy tìm được. 3 40 Thí dụ này cho biết hai đoạn 2 và 4 tạo thành dãy đoạn gối 3 5 nhau liên tiếp có tổng chiều dài max là 39. 2 3 5 9 9 16 Thuật toán Phương pháp: Quy hoạch động kết hợp với con trỏ trước t để giải trình kết quả. Giả sử các đoạn được sắp tăng theo đầu phải b. Kí hiệu c(i) là tổng chiều dài lớn nhất các đoạn thẳng gối nhau liên tiếp tạo thành một dãy nhận đoạn i làm phần tử cuối dãy (khi khảo sát các đoạn từ 1 i). Để ý rằng (bi ai) là chiều dài đoạn thứ i, ta có c(1) = chiều dài đoạn 1 = b1 a1, Với i = 2 N: c(i) = max { c(j) | 1 j < i, đoạn j kề trước đoạn i: bj = ai } + (bi ai), Nếu j là chỉ số đạt max thì đặt ti = j. Độ phức tạp: N2. (* Pascal *) (*=== Doan Goi 3: Liet ke cac doan goi nhau co tong chieu dai max ===*) program DoanGoi3; uses crt; const mn = 1001; bl = #32; nl = #13#10; fn = 'doan.inp'; gn = 'doan.out'; type KieuDoan = record a,b,id: integer; end; md1 = array[0 mn] of KieuDoan; mi1 = array[0 mn] of integer; var n,m: integer; { n – số lượng đoạn, m – số đoạn được chọn } d: md1; f,g: text; c: mi1; {c[i] = chieu dai max nhan i lam doan cuoi} t: mi1; { tro truoc } procedure Doc; tự viết procedure Qsort(l,r: integer); tự viết procedure XuLi; var i,j,jmax: integer; begin fillchar(t,sizeof(t),0);{ Khơỉ tạo mảng trỏ trước } c[1] := d[1].b - d[1].a; { Chieu dai doan 1 } for i := 2 to n do begin c[i] := 0; jmax := i; for j := i-1 downto 1 do begin if (d[j].b < d[i].a) then break; 14
if (d[j].b = d[i].a) then if (c[j] > c[jmax]) then jmax := j; end; c[i] := c[jmax] + (d[i].b - d[i].a); t[i] := jmax; end; end; procedure GiaiTrinh(i: integer); tự viết procedure Ket; tự viết BEGIN Doc; Qsort(1,n); XuLi; Ket; END. // C# using System; using System.IO; using System.Collections; /*=== * Doan Goi 3: Liet ke toi da cac doan goi nhau * * co tong chieu dai max * ===*/ namespace SangTao2 { class DoanGoi3 { static public Doan[] d; static int n; // tong so doan static int[] t; // tro truoc const string fn = "doan.inp"; const string gn = "doan.out"; static void Main(string[] args) { Doc(); QSortB(d,0,n-1); int maxlen = 0; // so doan tim duoc int imax = 0; // chi so doan cuoi trong day max XuLi(ref imax, ref maxlen); Ghi(imax,maxlen); XemKetQua(); Console.ReadLine(); } static public void Doc(): tự viết static public void XuLi(ref int imax, ref int maxlen){ int [] c = new int[n]; t = new int[n]; Array.Clear(t, 0, t.Length); t[0] = -1; // c[i] - so luong doan goi ket thuc tai doan i c[0] = d[0].b-d[0].a; // lay doan 0 imax = 0; for (int i = 1; i = 0; j) { if (d[j].b c[jmax]) jmax = j; } c[i] = c[jmax] + (d[i].b - d[i].a) ; t[i] = jmax; if (c[i] > c[imax]) imax = i; } 15
maxlen = c[imax]; } // Sap tang cac doan theo dau phai (b) static public void QSortB(Doan[] d, int t, int p): tự viết static void Path(StreamWriter g, int imax): tự viết static public void Ghi(int imax, int maxlen): tự viết // Hien thi lai cac files input, output static public void XemKetQua(): tự viết }// DoanGoi3 public struct Doan: tự viết } // SangTao2 Bài 1.5 Đoạn bao nhau 1 Cho N đoạn thẳng trên trục số với các điểm đầu ai và điểm cuối bi là những số nguyên trong khoảng 1000 1000, ai y.b cho kết quả 1, nếu không: xét tiếp  Xét trường hợp x.b = y.b. o Nếu x.a y.a cho kết quả 1, nếu không: xét tiếp o Hai đoạn trùng nhau: x.a = y.a và x.b = y.b cho kết qủa 0. (* Pascal *) uses crt; const MN = 1001; bl = #32; nl = #13#10; 16
fn = 'doan.inp'; gn = 'doan.out'; type Doan = record a,b: integer; end; MD1 = array[0 MN] of Doan; MI1 = array[0 MN] of integer; var f,g: text; d: MD1; { cac doan } n: integer; { so doan } procedure Doc; tự làm function SanhDoan(x,y: Doan): integer; begin if (x.b y.b) then begin SanhDoan := 1; exit end; if (x.a y.a) then begin SanhDoan := -1; exit end; SanhDoan := 0; end; procedure QSortB(t,p: integer); var i,j: integer; m,x: Doan; begin i := t; j := p; m := d[(i+j) div 2]; while (i 0) do j := j-1; if (i = d[i].a) then if (c[j] > c[i]) then c[i] := c[j]; end; c[i] := c[i] + 1; if (cmax < c[i]) then cmax := c[i]; end; XuLi := cmax; end; procedure Ghi(k: integer); begin assign(g,gn); rewrite(g); writeln(g,k); close(g); end; 17
BEGIN Doc; QSortB(1,n); Ghi(XuLi); readln; END. // C# using System; using System.IO; using System.Collections; /*=== Doan Bao 1: So luong toi da cac doan bao nhau ===*/ namespace SangTao2 { class DoanBao1 { static public Doan[] d; // cac doan static int n; // tong so doan const string fn = "doan.inp"; const string gn = "doan.out"; static void Main(string[] args){ Doc(); QSortB(d, 0, n - 1); Ghi(XuLi()); XemKetQua(); Console.WriteLine("\n Fini"); Console.ReadLine(); } static public void Doc(): tự viết static public int XuLi(){ int [] c = new int [n]; int cmax = 0; for (int i = 0; i = 0; j){ if (d[j].b = d[i].a) if (c[j] > c[i]) c[i] = c[j]; } ++c[i]; if (cmax y.b) return 1; if (x.b y.a) return -1; return 0; } // Sap tang cac doan theo dau b // Hai doan cung dau b: doan nao a nho dat sau static public void QSortB(Doan[] d, int t, int p){ int i = t, j = p; Doan m = new Doan(d[(i + j) / 2]); while (i 0) j; 18
if (i <= j){ Doan x = d[i]; d[i] = d[j]; d[j] = x; ++i; j; } } if (t < j) QSortB(d, t, j); if (i < p) QSortB(d, i, p); } static public void Ghi(int m){ File.WriteAllText(gn, m.ToString()); } // Hien thi lai cac files input, output static public void XemKetQua(): tự viết }// DoanBao1 public struct Doan: tự viết } // SangTao2 Bài 1.6 Đoạn bao nhau 2 Cho N đoạn thẳng trên trục số với các điểm đầu ai và điểm cuối bi là những số nguyên trong khoảng 1000 1000, ai < bi, i = 1 n. Liệt kê tối đa K đoạn bao nhau. DOAN.INP DOAN.OUT Dữ liệu vào: tệp văn bản DOAN.INP: xem bài trước 6 3 Dữ liệu ra: tệp văn bản DOAN.OUT -1 12 1 Dòng đầu tiên: số tự nhiên K. 8 10 5 Tiếp đến là K dòng, mỗi dòng chứa một số tự nhiên là 17 18 2 chỉ số của đoạn trong dãy tìm được. Các chỉ số được liệ kê theo trật tự bao nhau từ lớn đến nhỏ. 2 7 Thí dụ này cho biết tối đa có 3 đoạn bao nhau là các 8 11 đoạn 1, 5 và 2: [-1,12]  [8,11]  [8,10]. 13 20 Thuật toán Giống bài Đoạn bao nhau 1. Để có danh sách đoạn bao nhau ta dùng mảng trỏ t[1 n], t[i] trỏ đến đoạn j là đoạn nằm trong đoạn i và c[j] đạt giá trị max. Độ phức tạp: N2. (* Pascal *) uses crt; const MN = 1001; bl = #32; nl = #13#10; fn = 'doan.inp'; gn = 'doan.out'; type Doan = record a,b: integer; id: integer; end; MD1 = array[0 MN] of Doan; MI1 = array[0 MN] of integer; var f,g: text; d: MD1; t: MI1; { tro truoc } n: integer; imax, k: integer; procedure Doc; tự làm function SanhDoan(x,y: Doan): integer; tự làm 19
procedure QSortB(t,p: integer): tự làm procedure XuLi; var c: mi1; i,j: integer; begin imax := 1; for i := 1 to n do begin c[i] := 0; t[i] := 0; for j := i-1 downto 1 do begin if (d[j].b = d[i].a) then if (c[j] > c[i]) then begin c[i] := c[j]; t[i] := j end; end; c[i] := c[i] + 1; if (c[imax] < c[i]) then imax := i; end; k := c[imax]; end; procedure Path(i: integer); begin if (i = 0) then exit; writeln(g,d[i].id); Path(t[i]); end; procedure Ghi; begin assign(g,gn); rewrite(g); writeln(g,k); path(imax); close(g); end; BEGIN Doc; QSortB(1,n); XuLi; Ghi; readln; END. // C# using System; using System.IO; using System.Collections; /*=== Doan Bao 2: Liet ke toi da cac doan bao nhau ===*/ namespace SangTao2 { class DoanBao2 { static public Doan[] d; // Cac doan static public int [] t; // Con tro truoc static int n; // tong so doan const string fn = "doan.inp"; const string gn = "doan.out"; static void Main(string[] args){ Doc(); QSortB(d, 0, n - 1); int k, imax; XuLi(out k, out imax); Ghi(k, imax); XemKetQua(); Console.WriteLine("\n Fini"); Console.ReadLine(); 20
} static public void Doc(): tự làm static public void XuLi(out int cmax, out int imax){ int [] c = new int [n]; t = new int[n]; imax = 0; for (int i = 0; i = 0; j){ if (d[j].b = d[i].a) if (c[j] > c[i]) { c[i] = c[j]; t[i] = j; } } ++c[i]; if (c[imax] < c[i]) imax = i; } cmax = c[imax]; } // XuLi static public int SanhDoan(Doan x, Doan y): tự làm static public void QSortB(Doan[] d, int t, int p): tự làm static void Path(StreamWriter g, int imax){ if (imax != -1) { g.WriteLine(d[imax].id); Path(g, t[imax]); } } static public void Ghi(int k, int imax){ StreamWriter g = File.CreateText(gn); g.WriteLine(k); Path(g, imax); g.Close(); } static public void XemKetQua(): xem bài trước }// DoanBao2 public struct Doan: tự làm } // SangTao2 Bài 1.7 Phủ đoạn 1 Cho N đoạn thẳng trên trục số với các điểm đầu ai và điểm cuối bi là những số nguyên trong khoảng 1000 1000, ai < bi. Hãy chỉ ra ít nhất K đoạn thẳng sao cho khi đặt chúng trên trục số thì có thể phủ kín đoạn [x, y] với tọa độ nguyên cho trước. DOAN.INP DOAN.OUT Dữ liệu vào: tệp văn bản DOAN.INP: xem bài trước Dữ liệu ra: tệp văn bản DOAN.OUT 5 3 Dòng đầu tiên: số K, nếu vô nghiệm K = 0. 3 23 1 Tiếp theo là K số tự nhiên biểu thị chỉ số của các đoạn 1 15 3 thẳng phủ kín đoạn [x, y]. 3 10 4 Thí dụ này cho biết ít nhất là 3 đoạn 1, 3 và 4 sẽ phủ kín đoạn [3, 23]. 8 20 17 25 2 7 Thuật toán Phương pháp: Tham 21
Sắp các đoạn tăng theo đầu phải b. k : = 1; { chỉ số đầu tiên } v := x; { Đầu trái của đoạn [x,y] } Lặp đến khi v y Duyệt ngược từ N đến k Tìm đoạn j [aj, bj] đầu tiên có đầu trái aj v; Nếu không tìm được: vô nghiệm; Nếu tìm được: Ghi nhận đoạn j; Đặt lại v := bj; Đặt lại k := j+1; Độ phức tạp: N2. (* Pascal *) (*=== Phu doan 1 Tìm ít nhất K đoạn có thể phủ kín đoạn [x,y] cho trước ===*) program PhuDoan1; uses crt; const mn = 2002; bl = #32; nl = #13#10; fn = 'doan.inp'; gn = 'doan.out'; type KieuDoan = record a,b: integer; id: integer; { Chỉ số đoạn } end; md1 = array[0 mn] of KieuDoan; mi1 = array[0 mn] of integer; var n: integer; { n - so luong doan } d: md1; { cac doan } f,g: text; t: mi1; x, y: integer; { Doan can phu } procedure Doc; var i: integer; begin assign(f,fn); reset(f); readln(f,n); readln(f,x, y); for i := 1 to n do begin readln(f,d[i].a,d[i].b); d[i].id := i; end; close(f); end; procedure Qsort(l,r: integer): tự viết (* Duyet nguoc cac doan d[s e] tim doan i dau tien thoa d[i].a <= x *) 22
function Tim(s,e,x: integer): integer; var i: integer; begin Tim := 0; for i := e downto s do if (d[i].a = y); Ket(k); { co nghiem } end; BEGIN doc; qsort(1,n); xuli; END. // C# using System; using System.IO; using System.Collections; /*=== * Phu Doan 1: Liet ke toi thieu cac doan * * phu doan [x,y] cho truoc * ===*/ namespace SangTao2 { class PhuDoan1 { static public Doan[] d; // cac doan static int n; // tong so doan static int m;// so doan tim duoc static int[] c; // luu ket qua cac doan duoc chon const string fn = "doan.inp"; const string gn = "doan.out"; static int x, y; // doan [x,y] can phu static void Main(string[] args) { Doc(); QSortB(d, 0, n - 1); m = XuLi(); Ghi(); XemKetQua(); Console.WriteLine("\n Fini "); Console.ReadLine(); } static public void Doc() { int[] a = Array.ConvertAll(File.ReadAllText(fn). Split(new chae[] {' ','\n','\r','\t'}, 23
StringSplitOptions.RemoveEmptyEntries), new Converter (int.Parse)); int j = 0; n = a[j++]; // tong so doan d = new Doan[n]; // Doc doan xy can phu x = a[j++]; y = a[j++]; for (int i = 0; i = s; i) if (d[i].a <= x) return i; return -1; } // Sap tang cac doan theo dau phai (b) static public void QSortB(Doan[] d, int t, int p): tự viết static public void Ghi() : tự viết // Hien thi lai cac files input, output static public void XemKetQua(): tự viết }// PhuDoan1 public struct Doan: tự viết } // SangTao2 Bài 1.8 Xanh đỏ tím vàng 1 Cho 4 loại đoạn thẳng sơn các màu xanh, đỏ, tím và vàng, bao gồm x đoạn màu xanh mỗi đoạn dài dx, d đoạn màu đỏ mỗi đoạn dài dd, t đoạn màu tím mỗi đoạn dài dt và v đoạn màu vàng mỗi đoạn dài dv. Các đoạn thẳng cùng màu thì có cùng chiều dài. Hãy chọn mỗi loại một số đoạn thẳng rồi xếp nối nhau theo chu vi để thu được một hình chữ nhật có diện tích lớn nhất với các cạnh lần lượt mang các màu tính theo chiều quay của kim đồng hồ là xanh, đỏ, tím, vàng. Các đại lượng trong bài đều là các số nguyên dương. XDTV1.INP XDTV1.OUT 15 12 15120 xanh 6 21 15 4 12 3 v 24
14 15 à đ 10 28 n ỏ g tím Dữ liệu vào: tệp văn bản XDTV1.INP gồm 4 dòng, mỗi dòng hai số nguyên dương viết cách nhau Dòng thứ nhất: x dx Dòng thứ hai: d dd Dòng thứ ba: t dt Dòng thứ tư: v dv Dữ liệu ra: tệp văn bản XDTV1.OUT Dòng đầu tiên: Diện tích của hình chữ nhật xanh - đỏ - tím - vàng. Dòng thứ hai: 4 số cho biết số lượng đoạn thẳng cần chọn theo mỗi loại màu để ghép được hình chữ nhật diện tích max. Kết quả trên cho biết cần chọn 15 đoạn xanh, 4 đoạn đỏ, 12 đoạn tím và 3 đoạn vàng để ghép thành hình chữ nhật xanh – đỏ tím vàng với diện tích max là 15120 = (15*12)*(4*21) = (12*15)*(3*28). Thuật toán Phương pháp: Tham. Ta gọi một bộ xanh - tím là một cặp (nx,nt) trong đó nx là số ít nhất các đoạn màu xanh đặt liên tiếp nhau trên đường thẳng tạo thành đoạn AB và nt là số ít nhất các đoạn màu tím đặt liên tiếp nhau trên đường thẳng tạo thành đoạn CD sao cho AB = CD. Ta có ngay nx*dx = nt*dt. Dễ dàng tìm được nx = Bcnn(dx,dt)/dx và nt = Bcnn(dx,dt)/dt, trong đó Bcnn(a,b) là hàm tính bội chung nhỏ nhất của hai số tự nhiên a và b. Tương tự ta tính cho bộ đỏ - vàng. Tiếp đến ta tính xem tối đa có thể lấy được bao nhiêu bộ xanh - tím và bộ đỏ - vàng. Dễ thấy Số bộ xanh - tím = min(x div nx, t div nt). Tương tự ta tính cho bộ đỏ - vàng. Độ phức tạp: O(1). (* Pascal *) ( Xanh Do Tim Vang 1 ) program xdtv1; uses crt; const fn = 'xdtv1.inp'; gn = 'xdtv1.out'; bl = #32; var n: longint; f,g: text; x,d,t,v: longint; { so doan X D T V } dx,dd,dt,dv: longint; { cheu dai moi doan } nx,nt,nd,nv: longint; { so doan X D T V can chon } procedure Doc; begin assign(f,fn); reset(f); readln(f,x,dx); readln(f,d,dd); readln(f,t,dt); readln(f,v,dv); close(f); end; function Ucln(a,b: longint): longint; var r: longint; 25
begin while (b <> 0) do begin r := a mod b; a := b; b := r; end; Ucln := a; end; (* Bcnn(a,b) = (a * b)/Ucln(a,b) *) function Bcnn(a,b: longint): longint; begin Bcnn := a * (b div Ucln(a,b)); end; function Min(a,b: longint): longint; tự viết procedure XuLi; var b, nxt, ndv: longint; begin b := Bcnn(dx,dt); nx := b div dx; { so doan xanh trong 1 bo xanh – tim } nt := b div dt; { so doan tim trong 1 bo xanh – tim } nxt := Min(x div nx, t div nt); { so bo xanh – tim } nx := nxt * nx; { so doan xanh can chon } nt := nxt * nt; { so doan tim can chon } b := Bcnn(dd,dv); nd := b div dd; { so doan do trong 1 bo do – vang } nv := b div dv; { so doan vang trong 1 bo do – vang } ndv := Min(d div nd, v div nv);{ so bo do vang } nd := ndv * nd; { so doan do can chon } nv := ndv * nv; { so doan vang can chon } end; procedure Ghi; begin assign(g,gn); rewrite(g); writeln(g,nx*dx*nd*dd);{ dien tich } writeln(g,nx,bl,nd,bl,nt,bl,nv); { so doan moi loai } close(g); end; BEGIN Doc; XuLi; Ghi; END. // C# using System; using System.IO; using System.Collections; /*=== Xanh Do Tim Vang 1 ===*/ namespace SangTao2 { class Xdtv1 { static int x, dx, d, dd, t, dt, v, dv; static int nx, nd, nt, nv; // Dap so const string fn = "xdtv1.inp"; const string gn = "xdtv1.out"; static void Main(string[] args) { Doc(); XuLi(); Ghi(); XemKetQua(); Console.WriteLine("\n Fini"); Console.ReadLine(); } 26
static public void Doc(){ int[] a = Array.ConvertAll(File.ReadAllText(fn). Split(new chae[] {' ','\n','\r','\t'}, StringSplitOptions.RemoveEmptyEntries), new Converter (int.Parse)); int j = 0; x = a[j++]; dx = a[j++]; d = a[j++]; dd = a[j++]; t = a[j++]; dt = a[j++]; v = a[j++]; dv = a[j]; } // Doc static public void XuLi(){ int b = Bcnn(dx,dt); nx = b / dx; // so doan xanh trong 1 bo xanh – tim nt = b / dt; // so doan tim trong 1 bo xanh – tim int nxt = Min(x / nx, t / nt); // so bo xanh – tim nx = nxt * nx; // so doan xanh can chon nt = nxt * nt; // so doan tim can chon b = Bcnn(dd,dv); nd = b / dd; // so doan do trong 1 bo do – vang nv = b / dv; // so doan vang trong 1 bo do – vang int ndv = Min(d / nd, v / nv);// so bo do vang nd = ndv * nd; // so doan do can chon nv = ndv * nv; // so doan vang can chon } // XuLi static public int Ucln(int a, int b){ int r; while (b != 0) { r = a % b; a = b; b = r; } return a; } static public int Bcnn(int a, int b) { return a*(b/Ucln(a, b));} static public int Min(int a,int b): tự viết static public void Ghi(){ StreamWriter g = File.CreateText(gn); g.WriteLine((nx*dx*nd*dd)); // dien tich g.WriteLine(nx+" "+nd+" "+nt+" "+nv);//so doan moi loai g.Close(); } // Hien thi lai cac files input, output static public void XemKetQua(): tự viết }// Xdtv1 } // SangTao2 Bài 1.9 Xanh đỏ tím vàng 2 Cho 4 loại đoạn thẳng sơn các màu xanh dài dx, đỏ dài dd, tím dài dt và vàng dài dv. Các đoạn thẳng cùng màu thì có cùng chiều dài và số lượng không hạn chế. Hãy chọn ra không quá N đoạn thẳng rồi xếp nối nhau theo chu vi để thu được một hình chữ nhật có diện tích lớn nhất với các cạnh lần lượt mang các màu theo chiều quay của kim đồng hồ là xanh, đỏ, tím, vàng. Dữ liệu trong bài đều là các số nguyên dương. XDTV2.INP XDTV2.OUT Dữ liệu vào: tệp văn bản XDTV2.INP 27
Dòng thứ nhất: số N > 0. 35 480 Dòng thứ hai: bốn số dx dd dt dv 3 2 2 5 8 10 12 4 Dữ liệu ra: tệp văn bản XDTV2.OUT Dòng đầu tiên: Diện tích của hình chữ nhật xanh - đỏ - tím - vàng. Dòng thứ hai: 4 số cho biết số lượng đoạn thẳng cần chọn theo mỗi loại màu để ghép được hình chữ nhật diện tích max. Kết quả trên cho biết cần chọn 8 đoạn xanh, 10 đoạn đỏ, 12 đoạn tím và 4 đoạn vàng để ghép thành hình chữ nhật có diện tích max là 480. Thuật toán Phương pháp: Tham. Tương tự như bài Xanh đỏ tím vàng 1, trước hết ta tính các bộ xanh - tím (nx,nt) và bộ đỏ - vàng (nd, nv). Tiếp đến ta tính xem khi lấy i bộ xanh – tím để kết hợp với j bộ đỏ - vàng thì thu được hình chữ nhật có diện tích max là bao nhiêu. Lưu ý rằng i bộ xanh - tím sẽ gồm i(nx+nt) đoạn thẳng. Số đoạn thẳng còn lại khi đó sẽ là N – i(nx+nt). Số này sẽ tạo ra được j = (N – i(nx+nt)) / (nd+nv) bộ đỏ - vàng. Độ phức tạp: O(n). (* Pascal *) ( Xanh Do Tim Vang 2 ) program xdtv2; uses crt; const fn = 'xdtv2.inp'; gn = 'xdtv2.out'; bl = #32; var n: longint; f,g: text; x,d,t,v: longint; dx,dd,dt,dv: longint; nx,nt,nd,nv: longint; smax,bmax: longint; procedure Doc: Tự viết; function Ucln(a,b: longint): Tự viết; function Bcnn(a,b: longint): Tự viết; function Min(a,b: longint): Tự viết; (* 1 bo xanh - tim = (sx,st) = (so doan xanh, so doan tim) sx = bcnn(dx,dt) div dx st = bcnn(dx,dt) div dt bxt = sx + st *) procedure XuLi; var b: longint; bxt, bdv: longint; s: longint; sx,st, sd, sv: longint; begin b := bcnn(dx,dt); 28
sx := b div dx; st := b div dt; bxt := sx + st; b := Bcnn(dd,dv); sd := b div dd; sv := b div dv; bdv := sd + sv; smax := 0; bmax := 0; for b := 1 to ((n - bdv) div bxt) do begin s := (b*sx*dx)*(((n – b*bxt) div bdv)*sd*dd); if (s > smax) then begin bmax := b; smax := s; end; end; nx := bmax * sx; nt := bmax * st; b := smax div (nx*dx); { Chieu dai canh Do ( = Vang) } nd := b div dd; nv := b div dv; end; procedure Ghi: Tự viết; BEGIN Doc; XuLi; Ghi; END. // C# using System; using System.IO; using System.Collections; /*=== Xanh Do Tim Vang 2 ===*/ namespace SangTao2 { class Xdtv2 { static int n; static int dx, dd, dt, dv; static int nx, nd, nt, nv; // Dap so: so luong moi loai const string fn = "xdtv1.inp"; const string gn = "xdtv1.out"; static void Main(string[] args){ Doc(); XuLi(); Ghi(); XemKetQua(); Console.WriteLine("\n Fini"); Console.ReadLine(); } static public void Doc(){ int[] a = Array.ConvertAll(File.ReadAllText(fn). Split(new chae[] {' ','\n','\r','\t'}, StringSplitOptions.RemoveEmptyEntries), new Converter (int.Parse)); int j = 0; n = a[j++]; dx = a[j++]; dd = a[j++]; dt = a[j++]; dv = a[j]; } // Doc static public void XuLi() { int b = Bcnn(dx,dt); int sx = b / dx; // so luong doan xanh trg 1 bo XT int st = b / dt; // so lg doan tim trg 1 bo X-T int sxt = sx+st; // tg so doan xanh va tim trg bo XT 29
b = Bcnn(dd,dv); int sd = b / dd, sv = b / dv; // do, vang int sdv = sd + sv;// tg so doan do va vg trg bo DV int smax = 0; // dt max int bxtmax = 0; // so bo XT toi da int bb = (n-sdv)/sxt; // can tren cua cac bo XT for (b = 1; b smax) { bxtmax = b; smax = s; } } nx = bxtmax * sx; nt = bxtmax * st; b = smax / (nx * dx); // chieu dai canh Do = Vang nd = b/dd; nv = b/dv; } // XuLi static public int Ucln(int a, int b): Tự viết; static public int Bcnn(int a, int b): Tự viết; static public int Min(int a,int b): Tự viết; static public void Ghi(): Tự viết; static public void XemKetQua(): Tự viết; }// Xdtv2 } // SangTao2 Bài 1.10 Phủ đoạn 2 Cho n đoạn thẳng với các điểm đầu ai và điểm cuối bi là những số nguyên trong khoảng 1000 1000, ai với tọa độ nguyên cho trước. DOAN.INP DOAN.OUT Dữ liệu vào: tệp văn bản DOAN.INP Dòng đầu tiên: số tự nhiên 1 < N 1000. 6 3 Dòng thứ hai: Đoạn x y (4,10 ) 1 Từ dòng thứ ba liệt kê các đoạn, mỗi dòng (-2, 5) 2 có thể chứa nhiều đoạn, mỗi đoạn được ghi trọn trên một dòng. [ 5 , 7] [6, 7) 6 Dữ liệu ra: tệp văn bản DOAN.OUT [7, 8) (8,9) Dòng đầu tiên: số K, nếu vô nghiệm K=0. (7 , 10 ] Tiếp theo là K số tự nhiên biểu thị chỉ số của các đoạn thẳng phủ kín đoạn x y. Kết quả trên cho biết ít nhất là 3 đoạn 1, 2 và 6 sẽ phủ kín đoạn (4,10). Chú ý: Giữa các số và các ký tự trong file input có thể chứa các dấu cách. Thuật toán Phương pháp: Tham 30
Để ứng dụng thuật toán của bài Phủ đoạn 1 ta đưa các đoạn về cùng một dạng đóng bằng cách chỉnh lại các đầu mở. Cụ thể là thêm/bớt điểm đầu mở của mỗi đoạn một lượng  = 0.3 như sau, [d,c] giữ nguyên (d,c] [d + , c], [d,c) [d, c - ], (d,c) [d + , c - ]. Qui tắc trên khá dễ hiểu. Bạn hãy giải thích vì sao chọn  = 0.3 mà không chọn  = 0.5? Hai trường a và b thể hiện các điểm đầu và cuối mỗi đoạn cần được khai báo kiểu real (float). Các biến liên quan đến các trường này trong thủ tục xử lí cũng cần được khai báo theo các kiểu trên. Ta đọc tất cả các đoạn và ghi vào mảng d[0 N], trong đó d[0] sẽ chứa đoạn x, y. Cách đọc các đoạn được tổ chức trên cơ sở giả thiết là các đoạn được viết đúng cú pháp. Mỗi lần ta đọc một kí tự ch từ tệp input. Nếu (ch = „(„) hoặc (ch = „[„) thì ta gặp kí tự đầu đoạn: ta tiến hành đọc một đoạn. Để đọc một đoạn ta lần lượt đọc số thứ nhất, bỏ qua dấu phảy („,‟) ngăn cách giữa hai số rồi đọc số thứ hai. Thủ tục đọc một đoạn kết thúc khi gặp một trong hai dấu đóng ngoặc là „]‟ hoặc „)‟. Căn cứ vào các dấu mở và đóng ngoặc đầu và cuối mỗi đoạn ta xác định lượng  cần thêm hoặc bớt cho mỗi điểm đầu hoặc cuối đoạn, đương nhiên các điểm này cần được biểu diễn dưới dạng số thực. Độ phức tạp: N2. Chú ý Bạn có thể dùng kỹ thuật đồng dạng chuyển trục số sang trục số "phóng đại" gấp 3 lần. Khi đó các đoạn tương ứng sẽ được chuyển như sau: [d,c] [3d - 1, 3c + 1], (d,c] [3d + 1, 3c + 1], [d,c) [3d - 1, 3c - 1], (d,c) [3d + 1, 3c - 1]. Tức là giữ lại kiểu nguyên và chọn  = 1. Cách làm này có đơn giản hơn trong trường hợp giới hạn của d và c là nhỏ. (* Pascal *) (*=== Phu doan 2 ===*) program PhuDoan2; uses crt; const mn = 2002; bl = #32; nl = #13#10; fn = 'doan.inp'; gn = 'doan.out'; MoVuong = '['; DongVuong = ']'; MoTron = '('; DongTron = ')'; NgoacMo = [MoVuong, MoTron]; NgoacDong = [DongVuong, DongTron]; ChuSo = ['0' '9']; CongTru = ['+','-']; eps = 0.3; type KieuDoan = record a,b: real; id: integer; { chỉ số đoạn } end; md1 = array[0 mn] of KieuDoan; mi1 = array[0 mn] of integer; var n: integer; { n - so luong doan } d: md1; f,g: text; t: mi1; xy: KieuDoan; 31
ch: char; k: integer; {dem so doan da doc} Ngoac: char; (* Doc 1 so nguyen tu input file *) function DocSo: integer; var s,dau: integer; begin s := 0; dau := 1; while not (ch in (CongTru + ChuSo)) do read(f,ch); if (ch in CongTru) then begin if (ch = '-') then dau := -1; read(f,ch); end; while not (ch in ChuSo) do read(f,ch); repeat s := 10*s + ord(ch) - ord('0'); read(f,ch); until not (ch in ChuSo); DocSo := dau * s; end; procedure DocDoan; begin k := k + 1; d[k].id := k; Ngoac := ch; d[k].a := DocSo; if (Ngoac = MoTron) then d[k].a := d[k].a + eps; while (ch <> ',') do read(f,ch); d[k].b := DocSo; while not(ch in NgoacDong) do read(f,ch); if (ch = DongTron) then d[k].b := d[k].b - eps; end; procedure Doc; var i: integer; begin assign(f,fn); reset(f); readln(f,n); k := -1; while (k < n) and (not eof(f)) do begin read(f,ch); if (ch in NgoacMo) then DocDoan; end; close(f); xy.a := d[0].a; xy.b := d[0].b; end; procedure Qsort(l,r: integer): xem bài phủ đoạn 1; function Tim(id,ic: integer; x: real): xem bài phủ đoạn 1; procedure Ket(k: integer): xem bài phủ đoạn 1; procedure XuLi: xem bài phủ đoạn 1; BEGIN Doc; Qsort(1,n); XuLi; END. // C# using System; using System.IO; using System.Collections; namespace SangTao2 { class PhuDoan2 { // Cac doan dong mo static public string fn = "Doan.inp"; 32
static public string gn = "Doan.out"; static public string s; // du lieu vao static public Doan[] d; // cac doan static public int[] c; // luu cac doan ket qua static public Doan xy; static public int n = 0; // so luong doan static public int si; // index cho s static int m; // so luong doan phu const float eps = 0.3f; static void Main(string[] args) { Doc(); QSortB(d, 0, n - 1); m = XuLi(); Ghi(); XemKetQua(); Console.WriteLine("\n Fini "); Console.ReadLine(); } static public void XemKetQua(): tự làm static public void Doc() { s = (File.ReadAllText(fn)).Trim(); si = 0; n = DocSo(); xy = DocDoan(0); d = new Doan[n]; for (int i = 0; i '9')&&(s[si]!='+') &&(s[si]!='-')) ++si; } static public int DocSo(){ int m = 0, dau = 1; DenSo(); if (s[si] == '+') ++si; if (s[si] == '-') { ++si; dau = -1; } do { m = m * 10 + s[si++] - '0'; } while (s[si] >= '0' && s[si] <= '9'); return dau*m; 33
} } // PhuDoan2 public struct Doan { // Mô tả một đoạn public float a, b; public id; public Doan(float x1, float x2, int z) // Tạo đoạn mới { a = x1; b = x2; id = z; } } // Doan } // SangTao2 Bài 1.11 Đoạn rời 2 Cho N đoạn thẳng với các điểm đầu ai và điểm cuối bi là những số nguyên trong khoảng 1000 1000, ai 1. 8 5 Từ dòng thứ hai: liệt kê các đoạn, mỗi dòng có thể chứa nhiều đoạn, mỗi đoạn được ghi trọn ( -2, 3) [3 , 5) 1 2 7 3 4 trên một dòng. [8, 12] [13 ,15 ) DOAN.OUT (1 , 9 ) ( 2, 5 ] Dữ liệu ra: tệp văn bản [5 ,8 ) [7, 15] Dòng đầu tiên: số K. Tiếp theo là K số tự nhiên biểu thị chỉ số của các đoạn thẳng rời nhau. Kết quả trên cho biết có tối đa 5 đoạn rời nhau là 1, 2, 7, 3 và 4. Thuật toán Phương pháp: Tham. Trước hết ta chỉnh lại các đầu hở giống như bài trước sau đó áp dụng thuật toán của bài đoạn rời. Các điểm đầu và cuối đoạn và các biến liên quan được khai báo kiểu số thực. Độ phức tạp: N.logN chi phí cho quick sort. (* Pascal *) (*=== liet ke toi da cac doan thang roi nhau ===*) program DoanRoi2; uses crt; Tổ chức dữ liệu: xem bài Phủ đoạn 2 function DocSo: xem bai Phu doan 2; procedure DocDoan: xem bai Phu doan 2; procedure Doc: xem bai Phu doan 2; procedure Qsort(l,r: integer): xem bai Phu doan 2; procedure XuLi : xem bai Doan roi 1; procedure Ket: xem bai Doan roi 1 ; BEGIN Doc; Qsort(1,n); XuLi; Ket; END. 34
// C# using System; using System.IO; using System.Collections; namespace SangTao2 { class DoanRoi2 { // Cac doan dong mo Tổ chức dữ liệu: xem bài Phủ đoạn 2 static void Main(string[] args) { Doc(); QSortB(d, 0, n - 1); XuLi(); Ghi(); XemKetQua(); Console.WriteLine("\n Fini "); Console.ReadLine(); } static public void XemKetQua(): xem bai Phu doan 2 static public void Doc(): xem bai Phu doan 2 static public void Ghi(): xem bai Doan Roi 1 static public void XuLi(): xem bai Doan roi 1 // Sap tang cac doan theo dau phai (b) static public void QSortB(Doan[] d, int t, int p): tự làm static public Doan DocDoan(int i): xem bai Phu doan 2 static public int DocSo(): xem bai Phu doan 2 } // DoanRoi2 public struct Doan: xem bai Phu doan 2 } // SangTao2 Bài 1.12 Ghép hình chữ nhật Cho N đoạn thẳng cùng chiều dài d đơn vị. Hãy chọn K đoạn để ghép thành cạnh của hình chữ nhật có diện tích lớn nhất. Input: Hai số N và d, n 4. Output: Hiển thị trên màn hình - t: Tổng số đoạn cần chọn t, - a: Số đoạn đặt trên 1 chiều rộng - b: Số đoạn đặt trên 1 chiều dài, - s: Diện tích max. Thí dụ, Input: N = 23, d = 2. Output: 22 5 6 120. Thuật toán Định lý Trong các hình chữ nhật cùng chu vi thì hình vuông có diện tích lớn nhất. Chứng minh Gọi c là chu vi của hình chữ nhật, a là chiều rộng, b là chiều dài, b a, d là độ lệch giữa chiều dài b và chiều rộng a. Ta có, b = a + d và c = 2(a+a+d) = 4a + 2d, diện tích s = a(a+d). Thay giá trị a = (c 2d)/4 vào biểu thức tính diện tích và rút gọn ta thu được s = c2/16 – d2/4 = (c2 – 4d2)/16. Giá trị s đạt max khi và chỉ khi d = 0, tức là khi a = b. Vậy hình chữ nhật có diện tích lớn nhất là c2/16 chính là hình vuông. Từ định lý trên ta rút ra heuristics sau đây: muốn xây dựng một hình chữ nhật có diện tích lớn nhất từ một chu vi c cố định với các cạnh nguyên cho trước ta phải chọn độ lệch giữa chiều dài và chiều rộng nhỏ nhất có thể được. Khởi trị: a = b = N div 4. 35
Xét các trường hợp số đoạn còn thừa r = N mod 4. r = 0: bỏ qua r = 1: bỏ qua r = 2: thêm chiều dài 1 đoạn, b := b + 1; r = 3: thêm chiều dài 1 đoạn, b := b + 1; Tổng quát: a = N div 4; b = a + (N mod 4) div 2; Khi đó diện tích sẽ là: s = a*b*d*d. Thí dụ, N = 23, d = 2: a = 23 div 4 = 5; b = a + (N mod 4) div 2 = 5 + (3 div 2) = 5 + 1 = 6; t = 2*(a+b) = 2*(5+6) = 22; s = a*b*d*d = 5*6*2*2 = 120. Độ phức tạp: O(1). (* Pascal *) (*=== Chon t trong n doan de ghep duoc HCN dien tich max ===*) program GhepChuNhat; uses crt; const bl = #32; procedure ChuNhatMax(n,d: longint); var a,b,t,s: longint; begin a := n div 4; b := a + ((n mod 4) div 2); t := 2 * (a + b); { tong so doan } s := a * b * d * d; writeln(t,bl,a,bl,b,bl,s); end; BEGIN ChuNhatMax(23,2); END. Kết quả dự kiến: 22 5 6 120 // C# using System; using System.IO; using System.Collections; namespace SangTao2 { class GhepHCN { static void Main(string[] args){ ChuNhatMax(23,2); Console.WriteLine("\n Fini "); Console.ReadLine(); } static public void ChuNhatMax(int n, int d){ int a = n / 4; int b = a + ((n % 4) / 2); int t = 2 * (a + b); int s = a * b * d * d; Console.WriteLine(t + " " + a + " " + b + " " + s); } } // GhepHCN } // SangTao2 36
Bài 1.13 Xanh đỏ Cho x đoạn thẳng màu xanh có chiều dài bằng nhau là dx đơn vị và d đoạn màu đỏ có chiều dài bằng nhau là dd đơn vị. Hãy chọn nx đoạn xanh và nd đoạn đỏ đặt trên chu vi của hình chữ nhật tạo thành một đường viền đan màu (các màu xen kẽ nhau) và diện tích của hình là lớn nhất. Input: Bốn số x, dx, d và dd, x 2, d 2. Output: Hiển thị trên màn hình - nx: Số đoạn xanh được chọn, - nd: Số đoạn đỏ được chọn, - s: Diện tích max. * Thí dụ 1 input: (x, dx, d, dd) = (5, 2, 7, 2) output: (nx, nd, s) = (5, 5, 24) Hình chữ nhật * Thí dụ 2 có cạnh đan màu input: (x, dx, d, dd) = (6, 2, 7, 3) xanh - đỏ và đạt output: (nx, nd, s) = (6, 6, 56) diện tích max * Thí dụ 3 input: (x, dx, d, dd) = (6, 2, 7, 2) output: (nx, nd, s) = (6, 6, 36) x = 11, dx = 1, * Thí dụ 4 d = 10, dd = 2. input: (x, dx, d, dd) = (7, 2, 7, 3) nx = 10, nd = 10, output: (nx, nd, s) = (6, 6, 56) s = 7 8 = 56. Thuật toán Dễ thấy là để thu được hình có đường viền đan màu thì cần chọn số đoạn xanh nx và số đoạn đỏ nd như nhau, tức là chọn nx = nd = min(x, d). Khi đó chu vi của hình sẽ gồm t = nx + nd = 2nx = 2nd đoạn, và do đó t là một số chẵn. Do t chẵn nên (t mod 4) sẽ bằng 0 hoặc 2. Kí hiệu a là số đoạn (tính cả xanh và đỏ) cần đặt trên một chiều rộng, b là số đoạn (tính cả xanh và đỏ) cần đặt trên một chiều dài của hình. Xét hai trường hợp dx = dd và dx ≠ dd. 1. Trường hợp thứ nhất: dx = dd. Ta có, a = b = t div 4. Nếu (t mod 4 = 2). Ta thêm vào chu vi một cặp xanh đỏ nữa. Vậy ta cần chọn: - nx = min(x,d) đoạn xanh, - nd = nx đoạn đỏ, - Diện tích max: s = a * b * dx * dx với a = t div 4 là số đoạn đặt trên 1 chiều rộng, b = a + ((t mod 4) div 2) là số đoạn đặt trên 1 chiều dài. 2. Trường hợp thứ hai: dx ≠ dd. Ta thấy, để đảm bảo tính đan màu thì a và b phải có cùng tính chẵn lẻ. Từ đó thấy rằng khi (t mod 4 = 2) ta phải bỏ qua số dư, vì nếu thêm cho chiều dài b 1 đoạn nữa thì tính chẵn lẻ của a và b sẽ khác nhau. Để ý rằng khi a và b cùng chẵn thì hình nhận được sẽ vuông và mỗi cạnh chứa đúng z = a div 2 đoạn xanh và z đoạn đỏ. Khi đó diện tích có thể tính theo công thức: s = sqr(z * (dx + dd)). Nếu a và b cùng lẻ thì số lượng đoạn xanh và số lượng đoạn đỏ trong một cạnh sẽ hơn kém nhau 1 đơn vị. Nếu cạnh này nhiều xanh hơn đỏ thì cạnh kề với cạnh đó sẽ nhiều đỏ hơn xanh. Khi đó diện tích sẽ được tính theo công thức s = (z * dx + (z+1) *dd) * (z * dd + (z+1) * dx) = (z * dx + z * dd + dd) * (z * dd + z * dx + dx) = (z * (dx + dd) + dd) * (z * (dx + dd) + dx) = (k + dd) * (k + dx) với z = a div 2, k = (a div 2)*(dx + dd). 37
Kết quả là cần chọn: nx = min(x,d). Chu vi 2*nx phải là bội của 4, tức là nx phải chẵn. Nếu nx lẻ thì đặt lại nx := nx 1. nd = nx; tổng cộng t = nx + nd đoạn, trong đó Số đoạn đặt trên 1 chiều rộng: a = t div 4, Số đoạn đặt trên 1 chiều dài: b = a, - Diện tích max: (k+dd) * (k+dx), k = (a div 2)*(dx+dd). Độ phức tạp: O(1). (* Pascal *) program XanhDo; uses crt; const bl = #32; function Min(a,b: longint): tự viết procedure XD(x,dx,d,dd: longint); var a,b,nx,nd,k,t,s: longint; begin if (dx = dd) then begin nx := Min(x,d); nd := nx; t := nx + nd; a := t div 4; b := a + ((t mod 4) div 2); s := a * b * dx * dx end else { dx 0) then nx := nx - 1; nd := nx; t := nx + nd; a := t div 4; b := a; k := (a div 2) * (dx + dd); if (Odd(a)) then s := (k + dx) * (k + dd) else s = k*k; end; writeln(nx,bl,nd,bl,s); end; BEGIN XD(7, 2, 7, 3); END. // C# using System; using System.IO; using System.Collections; namespace SangTao2 { class XanhDo { static void Main(string[] args){ XD(11, 1, 9, 2); Console.WriteLine("\n Fini "); Console.ReadLine(); } static public void XD(int x, int dx, int d, int dd){ int nx = Min(x,d); // so luong doan xanh can chon int nd; // so luong doan do can chon int t; // tong so: nx + nd int a,b; // chieu rong, dai tinh theo so doan 38
int s; // dien tich max if (dx == dd){ nd = nx; t = nx + nd; a = t / 4; b = a+((t % 4)/2); s = a*b*dx*dx; } else { if (nx % 2 > 0) nx; nd = nx; t = nx+nd; b = a = t / 4; int k = (a/2)*(dx+dd); s = (a % 2 == 0) ? k * k : (k+dx)*(k+dd); } Console.WriteLine("\n " + nx + " " + nd + " " + s); } static public int Min(int a,int b): tự viết } // XanhDo } // SangTao2 Bài 1.14 Xếp đoạn Cho N đoạn thẳng trên trục số với các điểm đầu xi là những số nguyên trong khoảng 1000 1000 và độ dài di là những số nguyên dương trong khoảng 1 1000, i = 1 N. Tính tổng chiều dài các đoạn đó phủ trên trục số. DOAN.INP OUTPUT Dữ liệu vào: tệp văn bản DOAN.INP Dòng đầu tiên: số tự nhiên 1 < N 1000. 5 28 Dòng thứ i trong N dòng tiếp theo, mỗi dòng chứa hai 3 5 số nguyên ai di cách nhau qua dấu cách, biểu thị điểm đầu và chiều dài của đoạn thứ i, i = 1 N. -11 3 Dữ liệu ra: hiển thị trên màn hình tổng chiều dài t các -20 4 đoạn phủ trên trục số. -12 8 2 5 Thuật toán Phương pháp: tham. Sắp tăng các đoạn theo điểm đầu x. Ta dùng kí hiệu [x,y] biểu diễn cho đoạn thẳng có điểm đầu x và điểm cuối y, x:d biểu diễn cho đoạn thẳng có điểm đầu x và chiều dài d. Ta định nghĩa một làn là đoạn tạo bởi các đoạn giao nhau liên tiếp. Hai đoạn [a,b] và [c,d] được gọi là giao nhau nếu chúng có điểm chung. Điều kiện này có nghĩa điểm đầu của đoạn này nằm trong đoạn thứ hai, tức là a c b hoặc c a d. Do các đoạn đã được sắp tăng theo điểm đầu x nên hai đoạn xi:di và xj:dj sẽ giao nhau khi và chỉ khi xj xi + di. Để ý rằng xi + di là điểm cuối của đoan i. Nếu hai đoạn i và j giao nhau thì ta hợp chúng thành một đoạn [a,b] với a = xi và b = max(xi + di, xj+dj). Kết hợp các đoạn giao nhau liên tiếp đến mức tối đa ta thu được một làn gọi là làn tối đại [a,b] có chiều dài b – a. Ta khởi trị làn [a, b] bằng đoạn đầu tiên x1:d1, cụ thể là a := x1, b := x1+d1 (= a + d1). Với mỗi đoạn i := 2 N ta xét: - Nếu đoạn i giao với làn [a,b], tức là xi b thì ta hợp đoạn i với làn để tạo ra làn mới [a,b] bằng cách chỉnh b := max(b, xi + di) . - Nếu đoạn i không giao với làn [a,b] thì ta cộng tích lũy chiều dài của làn [a,b] hiện có vào biến tổng t rồi sinh ra làn mới từ đoạn i. t := t + (b – a); 39
a := xi ; b := a + di; Sau khi kết thúc duyệt các đoạn ta cộng nốt làn cuối cùng vào tổng t bằng thao tác t := t + (b – a). Độ phức tạp: O(N.logN) – chi phí cho sắp xếp Qsort. (* Pascal *) ( Xep doan ) program XepDoan; uses crt; const bl = #32; fn = 'DOAN.INP'; mn = 1001; type KieuDoan = record x: integer; d: integer; end; md1 = array[0 mn] of KieuDoan; var c: md1; { chua cac doan } n: integer; f: text; procedure Doc; var i: integer; begin assign(f,fn); reset(f); readln(f,n); for i := 1 to n do readln(f,c[i].x,c[i].d); close(f); end; (* Sap tang cac doan theo diem dau x *) procedure Qsort(t,p: integer): tự viết; function max(a,b: integer): tự viết function Tong: longint; var t: longint; { tong do dai } a, b: integer; { lan [a, b] } i: integer; begin t := 0; a := c[1].x; b := a + c[1].d; { Khoi tri lan } for i := 2 to n do if (c[i].x <= b) then b := max(b,c[i].x + c[i].d) else begin t := t + (b - a); a := c[i].x; b := a + c[i].d; end; Tong := t + (b - a); end; BEGIN Doc; Qsort(1,n); writeln(Tong); END. // C# using System; using System.IO; using System.Collections; namespace SangTao2 { 40
class XepDoan { const string fn = "doan.inp"; const string gn = "doan.out"; static public int n; // so luong doan static public Doan[] c; // cac doan static void Main(string[] args) { Doc(); QSort(0, n - 1); Console.WriteLine("\n \n Dap so: "+CoverSum()); Console.WriteLine("\n Fini "); Console.ReadLine(); } static public void Doc(): tự viết static public int CoverSum() { int a = c[0].x, b = a + c[0].d, t = 0; for (int i = 1; i < n; ++i) if (c[i].x <= b) b = Max(b, c[i].x + c[i].d); else { t += (b-a); a = c[i].x; b = a+c[i].d; } return t + (b - a); } static public int Max(int a, int b): tự viết // Sap cac doan tang theo diem dau x static public void QSort(int s, int e): tự viết } // XepDoan public struct Doan: tự viết } // SangTao2 Bài 1.15 Các hình chữ nhật ACM Trên mặt phẳng tọa độ cho N hình chữ nhật (HCN) có diện tích khác 0 và có các cạnh song song với các trục tọa độ. Mỗi HCN được mô tả bằng bộ bốn số nguyên (x1,y1) và (x2,y2) biểu thị tọa độ nguyên của hai đỉnh đối diện. Yêu cầu: xác định diện tích phần mặt phẳng bị các HCN phủ. HCN.INP HCN.OUT Dữ liệu vào: tệp văn bản HCN.INP Dòng đầu tiên: số tự nhiên 1 < N 1000. 5 35 Dòng thứ i trong N dòng tiếp theo, mỗi dòng chứa 4 0 0 2 4 số nguyên x1, y1, x2, y2 cách nhau qua dấu cách. 1 2 4 6 Dữ liệu ra: tệp văn bản HCN.OUT chứa tổng đơn vị diện tích trên mặt phẳng bị các HCN phủ. 5 3 3 7 4 1 6 5 7 3 9 0 Thuật toán Phương pháp: Tham. y A B 2 41
1. Đọc dữ liệu và chỉnh lại các tọa độ sao cho x1 x2 và y1 y2. Điều này có nghĩa là ta qui ước mọi HCN ABCD đều được xác định qua 2 đỉnh đối diện D (đỉnh Tây-Nam) y và B (đỉnh Đông-Bắc): D(x1, y1), B(x2, y2). 1 Khi đọc dữ liệu ta đồng thời lược bớt các giá trị y trùng D C lặp và sắp các giá trị y1 và y2 theo chiều tăng để ghi vào một mảng y[1 m]. Như vậy, giá trị lớn nhất của m là 2n. Ta gọi phần x1 x2 mặt phẳng giới hạn bởi hai đường thẳng song song với trục hoành và cắt trục tung tại điểm y[i] và y[i+1] là băng i. Ta có m 1 băng mã số từ 1 đến m 1. Băng đầu tiên có mã số 1 nằm giữa hai đường y[1] và y[2], băng cuối cùng có mã số m 1 nằm giữa hai đường y[m 1] và y[m]. Nhiệm vụ còn lại là tính diện tích bị phủ trên mỗi băng. Tổng số diện tích bị phủ của các băng sẽ là đáp số cho bài toán. 2. Ta lại sắp các HCN theo chiều tăng của tọa độ x1. 3. Với mỗi HCN h(x1, y1, x2, y2) ta xét các băng i trong khoảng từ y1 đến y2. Với băng i giả sử ta đã biết phần bị các HCN 1 (h 1) phủ trên băng này. Ta kí hiệu s[i] và e[i] là giới hạn hoành độ trái và phải của phần đang bị phủ trên băng i. Diện tích hiện bị phủ trên băng i sẽ là: (y[i+1] y[i])*(e[i] – s[i]), trong đó y[i+1] – y[i] là chiều rộng của băng i. Ta cần chỉnh lại phần bị phủ trong băng i khi xét thêm HCN h(x1, y1, x2, y2). Dễ thấy, nếu x1 nằm giữa s[i] và e[i] thì ta cần chỉnh lại e[i] theo công thức e[i] := max(e[i], x2). Ngược lại, nếu x1 > e[i] thì ta kết thúc làn (s[i],e[i]) này như sau: Tính diện tích làn này và đưa vào biến tích lũy diện tích dt sau đó đặt lại cận s[i] := x1; e[i] := x2. Do các hoành độ y1 và y2 được sắp tăng nên ta có thể gọi thủ tục tìm kiếm nhị phân BínSearch để xác định băng chứa y1. Độ phức tạp: Các thuật toán sắp xếp và chèn đòi hỏi tối đa N2, Thủ tục xử lí xét mỗi HCN 1 lần và duyệt 2n băng. Tổng hợp: N2. (* Pascal *) ( Cac hinh chu nhat ) program HinhChuNhat; uses crt; const mn = 2001; fn = 'HCN.INP'; gn = 'HCN.OUT'; bl = #32; nl = #13#10; type CN = record x1, y1: integer; x2, y2: integer; end; mcn1 = array[0 mn] of CN; mi1 = array[0 mn] of integer; var n,m: integer; { n - so HCN, m - so lan } h: mcn1; { cac HCN } y: mi1; { ranh gioi cac lan } s, e: mi1; { Cac diem dau va cuoi cua bang } f,g: text; dt: Longint; function Max(a,b: integer): tự viết (* Hoán đổi trị để a b *) procedure Chinh(var a,b: integer); var c: integer; begin if (a > b) then begin c := a; a := b; b := c; end; 42
end; (* Tim nhi phan v trong y[1 m] *) function BinSearch(v: integer): integer; var d,c,t: integer; begin d := 1 ; c := m; while (d < c) do begin t := (d + c) div 2; if (y[t] < v) then d := t + 1 else c := t; end; BinSearch := d; end; (* Xen them v vao day da sap tang y[1 m] *) procedure Insert(v: integer); var d: integer; begin if (m = 0) then { danh sach rong } begin m := m + 1; y[m] := v; exit; end; d := BínSearch(v); if (y[d] = v) then exit; { da co trong danh sach } if (y[d] < v) then begin m := m + 1; y[m] := v; exit; end; move(y[d], y[d+1],sizeof(integer)*(m-d+1)); y[d] := v; m := m + 1; end; (* Doc du lieu va sap theo Y luoc bot cac Y bang nhau *) procedure Doc; var i: integer; begin assign(f,fn); reset(f); readln(f,n); m := 0; for i := 1 to n do begin readln(f,h[i].x1,h[i].y1,h[i].x2,h[i].y2); Chinh(h[i].x1, h[i].x2); Chinh(h[i].y1, h[i].y2); insert(h[i].y1); insert(h[i].y2); end; close(f); end; procedure SortByX1(d,c: integer); var i,j,m: integer; v: CN; begin i := d; j := c; m := h[(i+j) div 2].x1; while (i <= j) do begin while (h[i].x1 < m) do i := i + 1; while (m < h[j].x1) do j := j - 1; 43
if (i <= j) then begin v := h[i]; h[i] := h[j]; h[j] := v; i := i + 1; j := j - 1; end; end; if (d < j) then SortByX1(d,j); if (i < c) then SortByX1(i,c); end; (* Xet HCN d, tinh tung phan phu trong moi lan *) procedure Hinh(x1, x2, y1, y2: integer); var i: integer; begin { Tim xuat hien cua y1 trong cac lan } i := BinSearch(y1); while (y[i] < y2) do begin if (x1 <= e[i]) then e[i] := Max(e[i], x2) else begin dt := dt + (e[i] - s[i]) * (y[i+1] - y[i]); s[i] := x1; e[i] := x2; end; i := i + 1; end; end; procedure XuLi; var d: integer; begin { Khoi tri } dt := 0; for d := 1 to m-1 do begin s[d] := -maxint; e[d] := s[d]; end; { Duyet cac HCN } for d := 1 to n do Hinh(h[d].x1, h[d].x2, h[d].y1, h[d].y2); { Tong hop ket qua } for d := 1 to m-1 do dt := dt + (e[d] - s[d]) * (y[d+1] - y[d]); end; procedure Ghi; begin assign(g,gn); rewrite(g); writeln(g,dt); close(g) end; BEGIN Doc; SortByX1(1,n); XuLi; Ghi; END. // C# using System; using System.IO; using System.Collections; 44
namespace SangTao2 { class Hcn { const string fn = "hcn.inp"; const string gn = "hcn.out"; static public int n,m; // n - so luong HCN; m - so bang static public HCN[] c; static public int dt; // tong dien tich static public int[] y; static void Main(string[] args) { Doc(); QSortByx1(0, n - 1); XuLi(); Ghi(); XemKetQua(); Console.WriteLine("\n Fini "); Console.ReadLine(); } static public void Ghi() { File.WriteAllText(gn,dt.ToString()); } static public void XemKetQua(): tự viết static public void XuLi(){ dt = 0; // tong dien tich int[] s = new int[m]; // diem dau cac bang int [] e = new int [m]; // diem cuoi cac bang for (int i = 0; i (int.Parse)); int j = 0; n = v[j]; c = new HCN[n]; int dx, dy, bx, by, t; m = 0; y = new int[2*n]; for (int i = 0; i bx) { t = dx; dx = bx; bx = t; } if (dy > by) { t = dy; dy = by; by = t; } 45
c[i] = new HCN(dx, dy, bx, by); Insert(dy); Insert(by); } } // Tim nhi phan gia tri v trong y[0 m-1] static public int BinSearch(int v) { int left = 0, right = m-1, midle; while (left m) j; if (i <= j) { t = c[i]; c[i] = c[j]; c[j] = t; ++i; j; } } if (s < j) QSortByx1(s, j); if (i < e) QSortByx1(i, e); } } // Hcn public struct HCN { public int x1,y1,x2,y2; public HCN(int dx, int dy, int bx, int by) { x1 = dx; y1 = dy; x2 = bx; y2 = by; } } } // SangTao2 Bài 1.16 Các tam giác vuông cân ACM Trên mặt phẳng tọa độ cho N tam giác vuông cân, hai cạnh góc vuông song song với hai trục tọa độ, cạnh huyền nằm ở bên phải tam giác. Cụ thể là nếu kí hiệu tam giác là ABC thì ta qui định đỉnh A là đỉnh góc vuông, cạnh góc vuông AB song song với trục hoành ox, cạnh góc vuông AC song song với trục tung oy, AB = AC = d. Mỗi tam giác được mô tả bằng bộ ba số nguyên x, y, d trong đó (x,y) là tọa độ nguyên của đỉnh A, d là chiều dài cạnh góc vuông. 46 TAMGIAC.INP TAMGIAC.OUT
5 16.50 6 0 3 1 0 3 2 1 3 4 1 2 y C 4 5 2 A B o x Yêu cầu: Tính diện tích do các tam giác phủ trên mặt phẳng tọa độ. Dữ liệu vào: text file TAMGIAC.INP Dòng đầu tiên: số tự nhiên N trong khoảng 2 1000. N dòng tiếp theo: mỗi dòng 3 số x y d cách nhau qua dấu cách, x và y biến thiên trong khoảng 1000 1000, d trong khoảng 1 1000. Dữ liệu ra: text file TAMGIAC.OUT chứa một số thực duy nhất S là diện tích bị các tam giác phủ trên mặt phẳng tọa độ. Thuật toán Y Tương tự như bài Các Hình chữ nhật. Với mỗi tam giác (x, y, d) ta tạo ra hai đường song song với trục hoành và cắt trục tung T M P R tại các điểm y và y+d, cụ thể là một đường chứa cạnh đáy và một đường đi qua đỉnh của tam giác. Các đường thẳng này sẽ tạo ra các băng. Với mỗi tam giác (TG) ta cũng xét tương tự như HCN, nghĩa Q là xét các băng chứa trong TG đó. Biến diện tích dt được khai báo kiểu float vì các hình trong băng j sẽ là hình thang có đáy lớn là S X E V e[j] s[j], đáy nhỏ bằng đáy lớn – h, h là chiều cao: h = y[j+1] y[j] = độ rộng của băng. Khi chuyển từ băng j lên băng j+1 ta phải chỉnh lại đầu phải x2 của cạnh đáy TG thành x2 – h vì TG lúc này sẽ ngắn lại. Khi tính phần giao nhau ta còn phải trừ đi diện tích của TG nằm ngoài phần giao đó. Hình vẽ cho ta thấy khi xét tam giác XYV và băng giới hạn trong 2 đường thẳng TM và SE, thì làn (S, E) sẽ được mở rộng thành làn (S, V). Diện tích trước đó của làn SE chính là diện tích hình thang vuông TMES, nay làn (S,V) có diện tích của hình thang vuông TRVS. Như vậy ta đã tính dôi ra phần diện tích tam giác MPQ. Dễ dàng xác định được diện tích z của tam giác vuông cân này: Đặt k = MP = PQ, ta có z = k2/2.Ta xác định k như sau. k = MP = TP TM = SX TM = x (e[j] h), trong đó h là chiều rộng của băng j đang xét, h = y[j+1] y[j], e[j] là điểm cuối của làn đang xét, x là hoành độ của đỉnh góc vuông trong tam giác XYV đang xét. Độ phức tạp: N2. (* Pascal *) ( Cac tam giac vuong can ) program TamGiacVuongCan; uses crt; const mn = 2001; bl = #32; nl = #13#10; 47
fn = 'TamGiac.inp'; gn = 'TamGiac.out'; type TG = record x,y: integer; d: integer; end; mtg1 = array[0 mn] of TG; mi1 = array[0 mn] of integer; mr1 = array[0 mn] of real; var n,m: integer; { n - so tam giac } y: mi1; { m - so diem y, max(m) = 2n } t: mtg1; f,g: text; dt: real; // tong dien tich (* To chuc du lieu cho Bang i s[i], e[i] - can trai va phai cua Bang *) s, e: mi1; function Max(a,b: integer): tự viết (* Xen them v vao day da sap tang y[1 m] *) procedure Insert(v: integer); tự viết procedure Doc; var i: integer; begin assign(f,fn); reset(f); readln(f,n); m := 0; for i := 1 to n do begin readln(f,t[i].x,t[i].y,t[i].d); Insert(t[i].y); Insert(t[i].y + t[i].d); end; close(f); end; { Sap cac TG tang theo x } procedure SortByX(d,c: integer); tự viết { Tim nhi phan v trong y[1 m] } function BinSearch(v: integer): integer; tự viết (* Xet hinh Tam giac h: tinh cac o hinh h phu tren cac Bang *) procedure Hinh(x1,y1,d: integer); var i,y2,x2,h,k: integer; begin { Tim xuat hien cua toa do y1 trong cac lan } i := BinSearch(y1); x2 := x1 + d; y2 := y1 + d; while (y[i] < y2) do begin h := y[i + 1] - y[i]; if (x1 <= e[i]) then begin k := x1 - (e[i] - h); e[i] := Max(e[i], x2); 48
if (k > 0) then dt := dt - (real(k * k) / 2); end else begin if (e[i] > s[i]) then dt := dt + h * (2 * (e[i] - s[i]) - h) / 2; s[i] := x1; e[i] := x2; end; i := i + 1; x2 := x2 - h; end; end; procedure XuLi; var i, h: integer; begin for i := 1 to m do begin s[i] := -maxint; e[i] := s[i]; end; dt := 0.0; { Duyet cac TG } for i := 1 to n do Hinh(t[i].x,t[i].y,t[i].d); { Tong hop ket qua } for i := 1 to m-1 do begin h := y[i + 1] - y[i]; if (e[i] > s[i]) then dt := dt + h * (2 * (e[i] - s[i]) - h) / 2; end; end; procedure Ghi; begin assign(g,gn); rewrite(g); writeln(g,dt:0:2); close(g) end; BEGIN Doc; SortByX(1,n); XuLi; Ghi; END. // C# using System; using System.IO; using System.Collections; namespace SangTao2 { class TamGiac { const string fn = "TamGiac.inp"; const string gn = "TamGiac.out"; static public int n, m; // n - so luong HCN; m - so bang static public TG[] c; static public float dt; // tong dien tich static public int[] y; static void Main(string[] args){ Doc(); QSortByx1(0, n - 1); XuLi(); Ghi(); XemKetQua(); Console.WriteLine("\n Fini "); Console.ReadLine(); } static public void Ghi(): tự viết static public void XemKetQua(): tự viết static public void XuLi() { dt = 0F; 49
int[] s = new int[m]; int[] e = new int[m]; for (int i = 0; i 0) dt -= (float)(k * k) / 2; e[j] = Max(e[j], x2); } else { if (e[j] > s[j]) dt += (float)(2*(e[j]-s[j])-h)*h/2; s[j] = c[i].x1; e[j] = x2; } x2 -= h; } // xong bang j } // xong TG i // Tong hop ket qua int m1 = m - 1; for (int j = 0; j s[j]) dt += (float)(2*(e[j]-s[j])-h)* h/2; } static public int Max(int a, int b): tự viết static public void Doc() { int[] v = Array.ConvertAll(((File.ReadAllText(fn))).Split( new char[] { ' ', '\t', '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries), new Converter (int.Parse)); int j = 0; n = v[j]; c = new TG[n]; m = 0; y = new int[2 * n]; for (int i = 0; i < n; ++i, j += 3) { Insert(v[j + 2]); Insert(v[j + 2] + v[j + 3]); c[i] = new TG(v[j + 1], v[j + 2], v[j + 3]); } } // Tim nhi phan gia tri v trong y[0 m-1] static public int BinSearch(int v): tự viết // Xen toa do v vao danh sach cac lan y static public void Insert(int v): tự viết // Sap cac TG tang theo x1 static public void QSortByx1(int s, int e): tự viết } // TamGiac public struct TG { public int x1, y1, d; 50
public TG(int dx, int dy, int dd) { x1 = dx; y1 = dy; d = dd; } } } // SangTao2 51
Chương 2 Các hàm Next Trong hầu hết các bài của Chương, khi trình bày tham biến kiểu mảng trong các hàm và thủ tục ta giả thiết là các kiểu này đã được khai báo trước. Thí dụ, kiểu mảng nguyên một chiều được khai báo như sau: (* Pascal *) type mi1 = array[0 MN] of integer; trong đó MN là hằng số đủ lớn cho kích thước mỗi bài toán, thí dụ const MN = 2000; Trong C# mảng được khai báo trực tiếp hoặc thông qua class, thí dụ, int [] a = new int [2000]; Class Array { }; Tùy theo bài toán và ngôn ngữ lập trình đã chọn, ta có thể hoặc không sử dụng phần tử đầu tiên và cuối cùng của mảng. Như vậy, mảng x gồm n phần tử sẽ được kí hiệu là x[1 n] trong Pascal hoặc x[0 n 1] trong C#. Trong Pascal khai báo tham biến kiểu var (truyền theo biến hay địa chỉ) cho mảng thì thủ tục sẽ được gọi nhanh hơn, trong C# các mảng được ngầm định là truyền theo biến / địa chỉ. Bài 2.1 Số sát sau cùng độ cao Chiều dài của một số tự nhiên là số chữ số của số đó. Độ cao của một số tự nhiên là tổng các chữ số của số đó. Cho số tự nhiên x ghi trong hệ đếm b, có chiều dài N. Tìm số tự nhiên y sát sau x có cùng chiều dài, cùng độ cao và cùng hệ đếm với x. DOCAO.INP DOCAO.OUT Dữ liệu vào: tệp văn bản DOCAO.INP Dòng đầu tiên: hai số tự nhiên b và N cách nhau qua dấu cách, 2 b 100, 2 N 1000. 10 5 1 Dòng thứ hai: số x với các chữ số ghi cách nhau qua 2 3 9 9 0 2 4 0 8 9 dấu cách. Dữ liệu ra: tệp văn bản DOCAO.OUT Dòng đầu tiên: ghi 1 nếu có nghiệm, 0: nếu vô nghiệm. Dòng thứ hai: số y với các chữ số ghi cách nhau qua dấu cách. Thuật toán Độ cao của số x sẽ không đổi nếu ta đồng thời tăng và giảm hai chữ số của x cùng một đơn vị. Ta duyệt lần lượt các chữ số của x từ phải qua trái, trước hết tìm chữ số xj > 0 đầu tiên để có thể giảm 1 đơn vị. Tiếp đến ta duyệt tiếp từ j 1 qua trái tìm một chữ số xi < (b 1) đầu tên sau j để có thể tăng thêm 1 đơn 52
vị. Nếu không tìm được xj hoặc xi thì x không có số sát sau. Nếu tìm được đồng thời hai chữ số xj và xi như trên thì ta sửa x như sau: Giảm xj 1 đơn vị, Tăng thêm xi 1 đơn vị, Lật lại đoạn x[i+1 n]. Với thí dụ x[1 5] = (2,3,9,9,0) trong hệ đếm thập phân (b = 10) ta tìm được j = 4, x[j] = 9, i = 2, x[i] = 3. Sau khi giảm x[4] và tăng x[2] 1 đơn vị ta thu được x[1 5] = (2,4,9,8,0). Số này còn lớn, nếu lật lại đoạn x[3 5] sẽ thu được x[1 5] = (2,4,0,8,9). Đây là số cần tìm. Vì sao lại làm như vậy? Giải thích điều này khá dễ nếu để ý rằng x[j+1 n] chứa toàn 0 (chữ số nhỏ nhất trong hệ đếm b) và x[i+1 j 1] chứa toàn (b 1) (chữ số lớn nhất trong hệ đếm b). Từ đó suy ra rằng đoạn x[i+1 n] được sắp tăng. Lật lại đoạn đó ta sẽ thu được dãy các chữ số giảm dần. Vì x[i] đã được thêm 1 đơn vị nên nó lớn hơn số ban đầu. Khi lật lại ta sẽ thu được số sát sau số ban đầu. Hàm Next dưới đây biến đổi trực tiếp x[1 n] để thu được số sát sau. Ta sử dụng phần tử x[0] = b làm giới hạn cho quá trình duyệt ngược. Phần tử x[0] này được gọi là lính canh. Nó có nhiệm vụ làm cho vòng lặp dừng một cách tự nhiên mà không cần phải kiểm tra giới hạn chỉ số của mảng (rang check). Độ phức tạp: cỡ N, do mỗi chữ số của x được thăm và xử lí không quá 2 lần. (* Pascal *) function Next(var x: mi1; n,b: integer): Boolean; var i,j,t,b1: integer; begin Next := FALSE; x[0] := b; j := n; while (x[j] = 0) do j := j - 1; if (j = 0) then exit; { ko co so sat sau } i := j - 1; b1 := b - 1 ; while (x[i] = b1) do i := i - 1; if (i = 0) then exit; { Ko co so sat sau } x[j] := x[j] - 1; x[i] := x[i] + 1; i := i + 1; j := n; { Lat doan x[i n] } while (i = 0; j) if (x[j] > 0) break; if (j = 0; i) if (x[i] < b1) break; if (i < 0) return false; x[j]; ++x[i]; ++i; j = n - 1; int t; while (i < j) { t = x[i]; x[i] = x[j]; x[j] = t; 53
++i; j; } return true; } Bài 2.2 Số sát sau cùng chữ số Cho số tự nhiên x chiều dài N. Hãy đổi chỗ các chữ số của x để thu được số y sát sau số x. NXT.INP NXT.OUT Dữ liệu vào: tệp văn bản NXT.INP Dòng đầu tiên: số tự nhiên N, 2 N 1000. 6 1 Dòng thứ hai: số x 239521 251239 Dữ liệu ra: tệp văn bản NXT.OUT Dòng đầu tiên: ghi 1 nếu có nghiệm, 0: nếu vô nghiệm. Dòng thứ hai: số y. Thuật toán Trước hết để ý rằng muốn thu được số sát sau của x thì ta phải sửa các chữ số ở hàng thấp nhất có thể của x, do đó thuật toán sẽ duyệt các chữ số của x từ phải qua trái. Ta sẽ tìm hai chữ số xj và xi đầu tiên của x tính từ phải qua trái thỏa các điều kiện sau: Thuận thế phải nhất: xi = x[i + 1]) do i := i - 1; 54
{ x[i] = 0; i) if (x[i] i; j) if (x[j] > x[i]) break; char t = x[i]; x[i] = x[j]; x[j] = t; // Doi cho // Lat doan x[i+1 n-1] ++i; j = n-1; while (i < j){ t = x[i]; x[i] = x[j]; x[j] = t; ++i; j; } return true; } Bài 2.3 Các hoán vị Olimpic Moscva Liệt kê tăng dần theo thứ tự từ điển các hoán vị của các số 1 N. Dữ liệu vào: tệp văn bản HV.INP chứa HV.INP HV.OUT duy nhất số N, 1 N 9. Dữ liệu ra: tệp văn bản HV.OUT Mỗi dòng một hoán vị. 3 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 Thuật toán Sử dụng hàm Next trong bài trước. Khởi trị cho x là hoán vị đơn vị x = (1,2, ,N). Độ phức tạp cho hàm Next: 2N, cho cả bài: 2N(N!). 55
Trong các chương trình dưới đây ta xây dựng các hàm Next không có tham biến nhằm mục đích đẩy nhanh quá trình tính toán. Như vậy, dữ liệu được cho dưới dạng các biến tổng thể, bao gồm n - chiều dài của các hoán vị, x[0 n 1] - mảng chứa hoán vị. (* Pascal *) ( Liet ke cac hoan vi cua 1 N theo thu tu tang dan ) program CacHoanVi; uses crt; const bl = #32; mn = 10; fn = 'HV.INP'; gn = 'HV.OUT'; type mb1 = array[0 mn] of byte; var x: mb1; { chua hoan vi } n: byte; { Len(x) } f,g: text; { input, output files } procedure Doc; begin assign(f,fn); reset(f);readln(f,n); close(f); end; function Next: Boolean; var i,j,t : byte; begin Next := false; { Tim diem gay } i := n - 1; while (x[i] >= x[i + 1]) do i := i - 1; { x[i] < x[i+1] } if (i = 0) then exit; j := n; while (x[j] <= x[i]) do j := j - 1; t := x[i]; x[i] := x[j]; x[j] := t; i := i + 1; j := n; while (i < j) do begin t := x[i]; x[i] := x[j]; x[j] := t; i := i + 1; j := j - 1; end; Next := true; end; procedure Run; var i: byte; begin Doc; x[0] := 0; // Dat linh canh assign(g,gn); rewrite(g); for i := 1 to n do x[i] := i;// Hoan vi don vi repeat for i := 1 to n do write(g,x[i],bl); writeln(g); until not Next; close(g); end; BEGIN 56
Run; END. // C# using System; using System.IO; namespace SangTao2 { /* * Cac Hoan Vi * Liet ke cac hoan vi (1,2, ,n) * theo trat tu tu dien tang dan * */ class CacHoanVi { const string fn = "hv.inp"; const string gn = "hv.out"; static char[] x; // chua cac hoan vi static int n; // so phan tu static void Main(){ Run(); Console.ReadLine(); } // Main static void Run() { n = int.Parse((File.ReadAllText(fn)).Trim()); x = new char[n + 1]; for (int i = 0; i = 0; i) if (x[i] i; j) if (x[j] > x[i]) break; char t = x[i]; x[i] = x[j]; x[j] = t; // Doi cho // Lat doan x[i+1 n-1] ++i; j = n - 1; while (i < j){ t = x[i]; x[i] = x[j]; x[j] = t; ++i; j; } return true; 57
} } // CacHoanVi } // SangTao2 Bài 2.4 Tổ hợp Liệt kê các tổ hợp chặp K của N phần tử 1 N theo thứ tự từ điển tăng dần. TOHOP.INP TOHOP.OUT Dữ liệu vào: tệp văn bản TOHOP.INP Dòng đầu tiên: hai số N và K cách nhau qua dấu cách, 1 N 9, K N. 5 3 1 2 3 Dữ liệu ra: tệp văn bản TOHOP.OUT 1 2 4 Mỗi dòng một tổ hợp, các số trên cùng dòng cách nhau 1 2 5 qua dấu cách. 1 3 4 Thuật toán 1 3 5 Phương án 1. Ta khởi trị cho mảng x[1 K] là tổ hợp nhỏ 1 4 5 nhất (1,2, ,K). Sau đó ta dùng hàm Next để sinh ra tổ hợp sát 2 3 4 sau của x. Hàm Next hoạt động theo 2 pha như sau: 2 3 5 Pha 1. Dỡ. Duyệt ngược từ K qua trái bỏ qua những phần 2 4 5 tử mang giá trị N 2, N 1, N đứng cuối mảng. Nếu sau khi dỡ x 3 4 5 không còn phần tử nào thì kết thúc với Next = false với ý nghĩa là sát sau tổ hợp x không còn tổ hợp nào. Thí dụ, nếu N = 7, K = 5, x[1 5] = (2,3,5,6,7) thì sau khi dỡ ba phần tử cuối của x ta thu được i = 2, x[1 2] = (2,3). Điều này cho biết sẽ còn tổ hợp sát sau. Pha 2. Xếp. 2.1. Tăng phần tử x[i] thêm 1 đơn vị. Tiếp tục với thí dụ trên ta thu được x[1 2] = (2,4) 2.2. Xếp tiếp vào x cho đủ K phần tử theo trật tự tăng dần liên tục. Tiếp tục với thí dụ trên ta thu được x[1 5] = (2,4,5,6,7). Ta sử dụng phần tử x[0] = N làm lính canh. (* Pascal, Phuong an 1 *) function Next: Boolean; var i, j, b: integer; begin Next := false; x[0] := N; { Pha 1. Do } i := k; b := n - k; while (x[i] = b + i) do i := i - 1; if (i = 0) then exit; { Pha 2. Xep } x[i] := x[i] + 1; for j := i + 1 to k do x[j] := x[j-1] + 1; Next := true; end; K Độ phức tạp: cho hàm Next: 2N, cho cả bài: 2N.CN = (2N. N!) / (K! (N-K)!) . Phương án 2. Ta cải tiến hàm Next như sau. Giả sử sau pha 1 ta thu được vị trí i thỏa x[i] ≠ n k+i. Ta gọi vị trí này là vị trí cập nhật và sẽ điều khiển nó thông qua một biến v. Ta khởi trị cho x và v như sau for i := 1 to k do x[i] := i; if (x[k] = n) then v := 0 else v := k; Sau đó mỗi lần gọi hàm Next ta kiểm tra 58
Nếu v = 0 thì dừng hàm Next. Nếu v ≠ 0 ta thực hiện pha 2 sau đó chỉnh lại giá trị của v như sau: Nếu x[k] = n thì tức là x[v k] = (n k v, , n 1, n) thì lần gọi Next tiếp theo sẽ cập nhật tại vị trí v-1, ngược lại, nếu x[k] ≠ n thì lần gọi Next tiếp theo sẽ cập nhật tại vị trí k. K Độ phức tạp: cho hàm Next: N. Cho cả bài: N.CN = (N. N!) / (K! (N-K)!). (* Pascal, Phương án 2 *) ( To hop chap k cua n phan tu PHUONG AN 2 ) program ToHopKN; uses crt; const bl = #32; mn = 10; fn = 'TOHOP.INP'; gn = 'TOHOP.OUT'; type mb1 = array[0 mn] of byte; var x: mb1; n, k, v: byte; f,g: text; procedure Doc; begin assign(f,fn); reset(f); readln(f,n,k); close(f); end; function Next: Boolean; var i: byte; begin Next := false; if (v = 0) then exit; { Pha 2. Xep } x[v] := x[v] + 1; for i := v + 1 to k do x[i] := x[i-1] + 1; if (x[k] = n) then v := v - 1 else v := k; Next := true; end; procedure Run; var i: byte; begin Doc; assign(g,gn); rewrite(g); for i := 1 to k do x[i] := i; if (x[k] = n) then v := 0 else v := k; repeat for i := 1 to k do write(g,x[i],bl); writeln(g); until not Next; close(g); end; BEGIN Run; END. // C# using System; 59
using System.IO; namespace SangTao2 { /* To hop (Phuong an 2) Liet ke cac to hop chap k cua n phan tu 1, 2, , n */ class ToHop2 { const string fn = "ToHop.inp"; const string gn = "ToHop.out"; static int[] x; static int n = 0; // so phan tu nen static int k = 0; // so phan tu trong 1 to hop static int v = 0; // vi tri cap nhat trong x static void Main() { GhiToHop(); XemKetQua(); Console.WriteLine("fini"); Console.ReadLine(); } // Main // Doc lai cac tep inp va out de kiem tra static void XemKetQua() { Console.WriteLine(File.ReadAllText(fn)); Console.WriteLine(File.ReadAllText(gn)); } static bool Next(){ if (v == 0) return false; ++x[v]; for (int i = v + 1; i <= k; ++i) x[i] = x[i - 1] + 1; v = (x[k] == n) ? v - 1 : k; return true; } static void Doc(){ char[] cc = new char[] { '\n', ' ', '\t', '\r' }; string[] ss = (File.ReadAllText(fn)).Split(cc, StringSplitOptions.RemoveEmptyEntries); n = int.Parse(ss[0]); k = int.Parse(ss[1]); } static void GhiToHop(){ Doc(); // Tao tep ket qua ToHop.out StreamWriter g = File.CreateText(gn); // Khoi tri; x = new int[k + 1]; for (int i = 1; i <= k; ++i) x[i] = i; v = (x[k] == n) ? 0 : k; do { for (int i = 1; i <= k; ++i) g.Write(x[i] + " "); g.WriteLine(); } while (Next()); g.Close(); } } // ToHop2 } // SangTao2 Chú ý Bạn đọc lưu ý rằng thuật toán trên cho ra dãy sắp tăng các tổ hợp và trong mỗi tổ hợp các thành phần cũng được sắp tăng. 60
Bài 2.5 Số Kapreka Số Kapreka mang tên nhà toán học Ấn Độ và được mô tả như sau. Đó là số tự nhiên x viết trong hệ đếm B có đúng K chữ số khác nhau đôi một và x = x’’ x’, trong đó x’’ và x’ lần lượt là các số thu được bằng cách sắp lại các chữ số của số x theo trật tự giảm và tăng dần. Với mỗi cặp giá trị B và K hãy tìm một số Kapreka. KAPREKA.INP KAPREKA.OUT Dữ liệu vào: tệp văn bản KAPREKA.INP Dòng đầu tiên: hai số B và K cách nhau qua dấu cách, 2 B 10, K < B. 10 4 6174 Dữ liệu ra: tệp văn bản KAPREKA.OUT Số x viết trong hệ đếm B. Bộ dữ liệu trên cho biết: Trong hệ đếm thập phân (B = 10), x = 6174 là số Kapreka có 4 chữ số (khác nhau đôi một), x'' - x' = 7641 1467 = 6174 = x. Thuật toán Ta dựa vào thuật toán tổ hợp Next của bài trước, sinh lần Kaprekar D. R. (1905-1986) nhà lượt các số K chữ số trong hệ b. Lưu ý rằng hệ đếm b sử dụng b toán học Ấn Độ say mê lý thuyết số chữ số 1 (b 1). Với mỗi số x được sinh ra theo thuật toán Next từ nhỏ. Sau khi tốt nghiệp Đại học ta tính hiệu y = x‟‟ x‟, trong đó x‟‟ là số thu được bằng cách sắp Tổng hợp Bombay năm 1929 ông lại các chữ số của x theo trật tự giảm dần và x‟ – tăng dần. Nếu y làm giáo viên phổ thông tại Devlali, chỉ chứa các chữ số của x thì y chính là một số Kapreka. Do các Ấn Độ. Ông viết nhiều bài khảo cứu tổ hợp x được sinh ra đã chứa các chữ số đôi một khác nhau và nổi tiếng về lý thuyết số, ma phương được sắp tăng, nên ta luôn có x'' = x. và các tính chất kỳ lạ của thế giới số. Để tìm hiệu của hai số trong hệ b ta nên biểu diễn ngược các số dưới dạng mảng K phần tử nhận các giá trị trong khoảng 0 b-1. Thí dụ số x = 1234 trong hệ 10 sẽ được biểu diễn là x[1 4] = (4,3,2,1). Giả sử x = (x1, x2, ,xK) và y = (y1, y2, ,yK). Ta tính hiệu z = x – y = (z1, z2, ,zK) theo qui tắc sau: Tính z = x + y* + 1, trong đó y* là dạng bù (b 1) của y. Sau đó ta bỏ đi số nhớ cuối cùng. Dạng bù (b 1) y* = (y1*, y2*, ,yK*) của số y được tính như sau: yi* = (b 1) – yi, i = 1 K. Thí dụ, tính 9217 – 468 trong hệ 10. Ta có x[1 4] = (7,1,2,9), y[1 4] = (8,6,4,0), do đó y*[1 4] = (1,3,5,9). Vậy x y = x + y* + 1 = (7,1,2,9) + (1,3,5,9) + (1,0,0,0) = (9,4,7,8). Kết quả là, 9217 – 468 = 8749. Qui tắc trên được giải thích như sau. Xét các số trong hệ đếm b. Kí hiệu z = b 1, khi đó số (z, K K K K z, ,z) gồm K chữ số z chính là b 1 và y* = (b 1) y. Khi đó, x y = x y + (b 1) + 1 b = x + K K K K ((b 1) y) + 1 b = x + y* + 1 – b . Việc bỏ số nhớ cuối cùng tương đương với phép trừ b vào kết quả. Dưới đây là thủ tục tính hiệu z = x – y cho các số viết ngược có tối đa K chữ số trong hệ b. procedure Hieu; var i,c,t: integer; begin c := 1; { so nho } for i := 1 to K do begin t := x[i] + ((b-1)-y[i]) + c; z[i] := t mod b; c := t div b; end; end; 61
Để ý rằng phép cộng hai số một chữ số trong hệ đếm b > 1 bất kì cho số nhớ tối đa là 1. Ngoài ra do các phép toán div và mod thực hiện lâu hơn các phép cộng và trừ nên ta có thể viết lại thủ tục trên như sau. procedure Hieu; var i,c,t: integer; begin c := 1; for i := 1 to K do begin t := x[i] + (b-1-y[i]) + c; if (t >= b) then begin z[i] := t – b; c := 1; end else begin z[i] := t; c := 0; end; end; end; Với số x có K chữ số sắp tăng tức là dạng viết ngược của x‟‟ ta có thể thực hiện phép trừ y = x‟‟ – x‟ bằng các thao tác trên chính x theo hai chiều duyệt xuôi và ngược. Khi thực hiện phép lấy hiệu ta cũng đồng thời kiểm tra xem mỗi chữ số của y có xuất hiện đúng một lần trong x hay không. Nếu đúng, ta cho kết quả là true, ngược lại, ta cho kết quả false. Để thực hiện việc này ta dùng mảng d[1 K] đánh dấu sự xuất hiện của các chữ số trong x và y. (* y = x'' - x' (he dem B) *) function Hieu: Boolean; var i,c,t: integer; begin fillchar(d,sizeof(d),0); { mang danh dau } Hieu := false; { Ghi nhan cac xuat hien cua x[i] } for i := 1 to k do d[x[i]] := 1; c := 1; { c: so nho } for i := 1 to k do begin t := x[i] + (b - 1 - x[k-i+1]) + c; if (t >= b) then begin y[i] := t - b; c := 1; end else begin y[i] := t; c := 0; end; if (d[y[i]] = 0) then exit; if (d[y[i]] = 1) then d[y[i]] := 0; end; Hieu := true; end; Dưới đây cung cấp 15 thí dụ để bạn đọc test chương trình. Kết quả 0 cho biết không tồn tại số Kapreka cho trường hợp đó. NN B K Đáp số N B K Đáp số N B K Đáp số N N 1 4 3 132 6 8 2 25 1 9 7 0 1 2 5 4 0 7 8 3 374 1 9 8 0 2 3 6 3 253 8 8 7 6417532 1 10 3 495 3 62
4 6 4 0 9 9 5 62853 1 10 4 6174 4 5 6 5 41532 1 9 6 0 1 10 9 864197532 0 5 15 thí dụ về các số Kapreka (* Pascal *) ( So Kapreka ) program SoKapreka; uses crt; const mn = 11; fn = 'KAPREKA.INP'; gn = 'KAPREKA.OUT'; type mb1 = array[0 mn] of byte; var x,y,d: mb1; b,k,b1,v: integer; { b - he dem k - so chu so b1 - chu so lon nhat trong he b, b1 = b-1 v - bien kiem soat cho ham Next } f,g: text; procedure Doc; begin assign(f,fn); reset(f); readln(f,b,k); close(f); b1 := b-1; { Chu so cao nhat trong he dem b } end; function Next: Boolean; var i: integer; begin Next := false; if (v = 0) then exit; x[v] := x[v] + 1; for i := v + 1 to k do x[i] := x[i-1] + 1; if (x[k] = b1) then v := v - 1 else v := k; Next := true; end; (* y = x'' - x' *) function Hieu: Boolean; var i,c,t: integer; begin fillchar(d,sizeof(d),0); Hieu := false; { Ghi nhan cac xuat hien cua x[i] } for i := 1 to k do d[x[i]] := 1; c := 1; { c: so nho } for i := 1 to k do begin t := x[i] + (b1 - x[k-i+1]) + c; if (t > b1) then begin t := t - b; c := 1; end else c := 0; 63
if (d[t] = 0) then exit; { t ko xuat hien trong x } y[i] := t; d[t] := 0; end; Hieu := true; end; function Kapreka: Boolean; var i: integer; t: Boolean; begin Kapreka := true; { Khoi tri x la to hop tang nho nhat } { x[1 k] = (0,1, ,k-1) } for i := 1 to k do x[i] := i-1; if (x[k] = b1) then v := 0 else v := k; repeat if (Hieu) then exit; until not next; Kapreka := false; end; procedure Run; var i: byte; begin Doc; assign(g,gn); rewrite(g); if (Kapreka) then for i := k downto 1 do write(g,y[i]) else write(g,0); writeln(g); close(g); end; BEGIN Run; END. // C# using System; using System.IO; namespace SangTao2 { /* * So Kapreka * x'' - x' = x * x'' - so giam * x' - so tang * */ class Kapreka { const string fn = "Kapreka.inp"; const string gn = "Kapreka.out"; static int[] x; // so x static int[] y; // y = x'' - x' static int[] d; static int b; // he dem static int k; // so chu so static int b1; // b-1: chu so cao nhat trong he b static int v; // bien cam canh static void Main() { Doc(); Ghi(Kap()); XemKetQua(); Console.WriteLine("\n fini"); 64
Console.ReadLine(); } // Main static void Ghi(int ket){ StreamWriter g = File.CreateText(gn); if (ket == 0) g.WriteLine(0); else for (int i = k; i > 0; i) g.Write(y[i]); g.Close(); } // Doc lai cac tep inp va out de kiem tra static void XemKetQua(): tự viết static bool Next() { if (v == 0) return false; ++x[v]; int j = x[v] + 1; for (int i = v + 1; i b1) { c = 1; t = t - b; } else c = 0; if (d[t] == 0) return false; y[i] = t; d[t] = 0; } return true; } static int Kap() { // Khoi tri; x = new int[k + 1]; y = new int[k + 1]; d = new int[b]; for (int i = 1; i <= k; ++i) x[i] = i - 1; v = (x[k] == b1) ? 0 : k; do { if (Hieu()) return 1; } while (Next()); return 0; } } // class Kapreka } // SangTao2 Chú thích Bạn có thể sử dụng thuật toán sau đây: 65
Khởi trị: Tạo số x hệ b gồm k chữ số khác nhau; Lặp từ 1 đến bk – 1 Tính y = x'' – x'; Nếu x = y thì cho kết quả x là số Kapreka; stop; Nếu không gán x := y; Xong lặp. Bài 2.6 Khóa vòng Một ổ khóa gồm M vòng chữ và N vòng số. Mỗi vòng chữ hoặc số chứa các giá trị biến thiên từ giới hạn nhỏ nhất a đến giới hạn lớn nhất b. Hãy liệt kê tăng dần theo trật tự từ điển các giá trị có thể có của khóa. KHOA.INP KHOA.OUT Dữ liệu vào: tệp văn bản KHOA.INP Dòng đầu tiên: hai số tự nhiên M và N, 1 M, N 5. Dòng thứ i trong số M+N dòng tiếp theo: giới hạn ai và bi 1 2 12 cho các vòng khóa. B C B20 Dữ liệu ra: tệp văn bản KHOA.OUT 2 3 B21 Dòng đầu tiên: Tổng số khả năng. 0 2 B22 Từ dòng thứ hai trở đi: mỗi dòng một giá trị khóa liệt kê B30 tăng dần theo trật tự từ điển. Các kí tự chữ và số trong mỗi khóa B31 được viết liền nhau, không có dấu cách ở giữa. Các giá trị chữ B32 được lấy từ bảng chữ HOA tiếng Anh. C20 Thuật toán C21 Phương pháp: duyệt toàn bộ các tổ hợp. C22 Nếu toàn bộ N vòng khóa đều chỉ chứa các chữ số với giới C30 hạn biết trước từ cận dưới a[i] đến cận trên b[i] , i = 1 N thì ta C31 dùng hàm Next sinh ra lần lượt các tổ hợp N phần tử c[1 N] như C32 sau. Khởi trị: c[1 N] là tổ hợp nhỏ nhất chứa toàn cận dưới: c[i] := a[i], i = 1 N. Xử lí: repeat Ghi tổ hợp c[1 N]; until not Next; Mỗi lần gọi hàm Next ta thực hiện giống như phép đếm: Duyệt ngược c[1 N] với mỗi c[i] = b[i] ta đặt lại c[i] := a[i]. Gặp c[i] đầu tiên thỏa điều kiện c[i] < b[i] thì tăng vòng khóa i thêm 1 nấc. Nếu không gặp phần tử i như vậy thì chứng tỏ đã xử lí xong tổ hợp cao nhất. Việc còn lại là chuyển các vòng chữ sang vòng số tương ứng. Độ phức tạp: (b1-a1+1)(b2-a2+1) (bv-av+1), v = M+N. (* Pascal *) ( Khoa Vong ) program KhoaVong; uses crt; const mn = 20; 66
bl = #32; nl = #13#10; fn = 'KHOA.INP'; gn = 'KHOA.OUT'; ChuCai = ['A' 'Z']; type mi1 = array[0 mn] of integer; var m,n: integer; a,b,c: mi1; f,g: text; m: longint; procedure Doc; var i: integer; c: char; begin assign(f,fn); reset(f); readln(f,m,n); n := m + n; for i := 1 to m do begin repeat read(f,c); until c in ChuCai; a[i] := ord(c) - ord('A'); repeat read(f,c); until c in ChuCai; b[i] := ord(c) - ord('A'); end; for i := m + 1 to n do read(f,a[i],b[i]); close(f); m := 1; for i := 1 to n do m := m * (b[i] - a[i] + 1); end; function Min(a,b: integer): integer; begin if (a < b) then Min := a else Min := b; end; function Next: Boolean; var i: integer; begin Next := false; i := n; while (c[i] = b[i]) do begin c[i] := a[i]; i := i - 1; end; if (i = 0) then exit; c[i] := c[i] + 1; Next := true; end; procedure Duyet; var i: integer; begin for i := 1 to n do c[i] := a[i]; c[0] := -1; assign(g,gn); rewrite(g); writeln(g,m); repeat for i := 1 to m do write(g,chr(ord('A')+c[i])); for i := m + 1 to n do write(g,c[i]); writeln(g); 67
until not Next; close(g); end; BEGIN Doc; Duyet; END. // C# using System; using System.IO; namespace SangTao2 { /* * Khoa Vong * */ class KhoaVong { const string fn = "Khoa.inp"; const string gn = "Khoa.out"; static int [] x; // to hop static int[] vmin; // can duoi static int[] vmax; // can tren static int m; // so luong vong chu static int n; // so luong vong so static int mn; // m+n static void Main() { Doc(); Ghi(); XemKetQua(); Console.ReadLine(); } // Main // Doc lai cac tep inp va out de kiem tra static void XemKetQua(): tự viết static bool Next() { int i; for (i = mn - 1; i >= 0; i) if (x[i] == vmax[i]) x[i] = vmin[i]; else break; if (i < 0) return false; ++x[i]; return true; } static void Doc() { char [] cc = new char [] {'\n',' ','\t','\r'}; string [] ss = (File.ReadAllText(fn)).Split(cc, StringSplitOptions.RemoveEmptyEntries); int k = 0; m = int.Parse(ss[k++]); // m vong chu n = int.Parse(ss[k++]); // n vong so mn = m + n; vmin = new int [mn]; vmax = new int [mn]; for (int i = 0; i < m; ++i) { vmin[i] = (int)ss[k++][0] - (int)'A'; vmax[i] = (int)ss[k++][0] - (int)'A'; } for (int i = m; i < mn; ++i) { vmin[i] = int.Parse(ss[k++]); vmax[i] = int.Parse(ss[k++]); } } 68