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

282 trang phuongnguyen 3390

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 1", để 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:

sang_tao_trong_thuat_toan_va_lap_trinh_voi_ngon_ngu_pascal_v.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 1

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 1 T u y ể n các bài toán Tin nâng cao cho học sinh và sinh viên giỏi
Sáng tạo trong Thuật toán và Lập trình Tập I 2 M Ụ C L Ụ C Lời nói đầu i Chƣơng I GIẢI MỘT BÀI TOÁN TIN 1 Bài 1.1. Số thân thiện 2 Bài 1.2. Số cấp cộng 8 Bài 1.3. Số cấp nhân 11 Bài 1.4. Mảng ngẫu nhiên 13 Bài 1.5. Chia mảng tỉ lệ 1:1 16 Bài 1.6. Chia mảng tỉ lệ 1:k 21 Chƣơng II SINH DỮ LIỆU VÀO VÀ RA 27 Bài 2.1. Sinh ngẫu nhiên theo khoảng 27 Bài 2.2. Sinh ngẫu nhiên tăng 29 Bài 2.3. Sinh hoán vị ngẫu nhiên 31 Bài 2.4. Sinh ngẫu nhiên đều 33 Bài 2.5. Sinh ngẫu nhiên tỉ lệ 36 Bài 2.6. Sinh ngẫu nhiên tệp tăng 40 Bài 2.7. Sinh ngẫu nhiên tệp cấp số cộng 42 Bài 2.8. Sinh ngẫu nhiên mảng đối xứng 43 Bài 2.9. Số độ cao h 46 Bài 2.10. Tệp các hoán vị 49 Bài 2.11. Đọc dữ liệu từ tệp vào mảng biết hai kích thước 53 Bài 2.12. Đọc dữ liệu từ tệp vào mảng biết một kích thước 56 Bài 2.13. Đọc dữ liệu từ tệp vào mảng đối xứng 60 Bài 2.14. Đếm tàu 62 Bài 2.15. Sắp đoạn 65 Chƣơng III BÀN PHÍM VÀ MÀN HÌNH 79 Bài 3.1. Bảng mã ASCII 79 Bài 3.2. Bộ Tú lơ khơ 80 Bài 3.3. Hàm GetKey 88 Bài 3.4. Trò chơi 15 90 Bài 3.5. Bảng nhảy 95 Chƣơng IV TỔ CHỨC DỮ LIỆU 107 Bài 4.1. Cụm 107 Bài 4.2. Bài gộp 112 Bài 4.3. Chuỗi hạt 120
Sáng tạo trong Thuật toán và Lập trình Tập I 3 Bài 4.4. Sắp mảng rồi ghi tệp 129 Bài 4.5. abc - sắp theo chỉ dẫn 133 Bài 4.6. Xâu mẫu 141 Chƣơng V PHƢƠNG PHÁP THAM LAM 153 Bài 5.1. Băng nhạc 153 Bài 5.2. Xếp việc 158 Bài 5.3. Xếp ba lô 165 Bài 5.4. Cây bao trùm ngắn nhất 170 Bài 5.5. Trộn hai tệp 177 Chƣơng VI PHƢƠNG PHÁP QUAY LUI 193 Bài 6.1. Tám Hậu 195 Bài 6.2. Từ chuẩn 207 Bài 6.3. Tìm đường trong mê cung 216 Chƣơng VII QUY HOẠCH ĐỘNG 227 Bài 7.1. Chia thưởng 228 Bài 7. 2. Palindrome 235 Bài 7.3. Cắm hoa 243 Bài 7.4. Tìm các đường ngắn nhất 253 Chƣơng VIII SUY NGẪM 267 Bài 8.1. Lát nền 267 Bài 8.2. Chữ số cuối khác 0 276 Bài 8.3. Hình chữ nhật tối đại trong ma trận 0/1 281 Bài 8.4. Ma phương 291 Bài 8.5. Tháp Hà Nội cổ 308 Bài 8.6. Tháp Hà Nội xuôi 311 Bài 8.7. Tháp Hà Nội ngược 316 Bài 8.8. Tháp Hà Nội thẳng 321 Bài 8.9. Tháp Hà Nội sắc màu (Hà Nội Cầu vồng) 325
Sáng tạo trong Thuật toán và Lập trình Tập I 4 Lời nói đầu Thể theo yêu cầu của đông đảo bạn đọc, chúng tôi biên soạn lại cuốn Sáng tạo trong Thuật toán và Lập trình với các bài Toán Tin nâng cao cho học sinh và sinh viên nhằm cung cấp những kĩ thuật lập trình cơ bản để giải những bài toán khó trên máy tính. Một bài toán tin được hiểu là khó nếu ta sử dụng thuật giải mới nảy sinh trong đầu khi vừa biết nội dung bài toán thì hoặc là ta thu được kết quả sai hoặc là lời giải thu được sẽ không hữu hiệu theo nghĩa chương trình đòi hỏi quá nhiều bộ nhớ hoặc/và chạy quá lâu. Những thuật giải nảy sinh lập tức trong đầu như vậy thường được gọi là thuật giải tự nhiên. Dĩ nhiên, khái niệm này chỉ là tương đối. Nếu bạn đã nắm vững nhiều dạng thuật giải và đã từng thử sức với nhiều bài toán khó thì đến một lúc nào đó các thuật giải tự nhiên của bạn sẽ đáng tin cậy. Đó cũng chính là mục đích của sự học tập và rèn luyện và cũng là ước mơ của người viết tập sách này. Để đọc sách không đòi hỏi bạn phải có tri thức gì đặc biệt. Để tiếp thu tốt và đóng góp cho việc hiệu chỉnh và cải tiến nội dung cuốn sách chỉ cần bạn biết sử dụng một trong các ngôn ngữ lập trình: Pascal trong môi trường Turbo hoặc Free Pascal hoặc C#. Các kĩ thuật lập trình được minh hoạ qua những bài toán cụ thể tương đương với trình độ nâng cao của học sinh và sinh viên. Hình thức phát biểu bài toán suy cho cùng là không quan trọng. Các kĩ thuật lập trình và phương pháp xây dựng thuật giải cho những bài toán thường được dùng rộng rãi trong quá trình thiết kế và cài đặt các phần mềm ứng dụng trong thực tiễn, cho nên việc sớm làm chủ các tri thức này mới thật sự là cần thiết. Chính vì vậy mà chúng tôi cho rằng nội dung cuốn sách có thể phù hợp với các bạn học sinh, sinh viên các trường đại học và những bạn đọc muốn tự hoàn thiện tri thức trong lĩnh vực giải thuật và lập trình. Thiết nghĩ cuốn sách cũng có thể được dùng làm tài liệu tham khảo để dạy ở các lớp chuyên tin của các trường phổ thông. Nội dung sách gồm hai phần. Phần thứ nhất giới thiệu vắn tắt về bản chất các phương pháp và kĩ thuật lập trình và các đề toán để các bạn thử sức. Phần thứ hai trình bày và phân tích chi tiết lời giải cùng với những bình luận và xuất xứ của các bài toán. Trong tập sách này cũng cung cấp toàn văn các chương trình viết bằng ngôn ngữ lập trình Pascal và C# để bạn đọc tiện so sánh với lời giải của mình. Cả hai phần đều đề cập đến nội dung của tám chương như sau. Chương thứ nhất trình bày sơ đồ chung để giải một bài toán tin. Các bài tập ở chương này hầu hết thuộc loại dễ giải. Chương thứ hai giới thiệu các kĩ thuật sinh dữ liệu một cách tự động nhằm phục vụ cho việc kiểm thử (test) chương trình. Chương thứ ba trình bày các kĩ thuật quản lí bàn phím và màn hình. Chương thứ tư đề cập đến cách thức tổ chức dữ liệu cho một bài toán tin. Ba chương tiếp theo giới thiệu ba trong số các phương pháp khá phổ biến thường được vận dụng trong thiết kế thuật giải. Đó là phương pháp tham lam, phương pháp quay lui và quy hoạch động. Các phương pháp này đều là không vạn năng theo nghĩa không thể dùng chúng để giải mọi bài toán tin. Trong thực
Sáng tạo trong Thuật toán và Lập trình Tập I 5 tế, một phương pháp vạn năng như vậy là không hữu hiệu. Tuỳ theo nội dung bài toán mà ta chọn phương pháp phù hợp. Đó cũng là điểm khó, đòi hỏi ở bạn đọc một quá trình tìm tòi và tích luỹ kinh nghiệm. Riêng chương cuối cùng của cuốn sách, chương thứ tám giới thiệu một số bài toán tin để bạn đọc tự phát hiện phương pháp giải. Những nội dung trong tập sách này được tập hợp và chỉnh lí từ các bài giảng về thuật toán và lập trình, từ các cuốn sách Tìm đường trong mê cung, Bắn tàu trên biển và từ các bài viết của tác giả đăng trong tạp chí Tin học và nhà trường và một số lời giải hay của các bạn học sinh. Lần xuất bản này chúng tôi trình bày thêm các bài giải viết trong môi trường ngôn ngữ C# để các bạn sinh viên cùng tham khảo. Hi vọng rằng trong các dịp khác chúng tôi sẽ cung cấp thêm các phương án giải với bạn đọc. Tuy nhiên, suy cho cùng, môi trường lập trình chỉ mang tính minh hoạ. Khi đã biết thuật toán, việc thể hiện thuật toán đó trong môi trường lập trình cụ thể chắc chắn là việc làm quen thuộc của bạn đọc. Xin được chân thành cảm ơn các em học sinh, sinh viên, các thầy cô giáo, bạn bè và đồng nghiệp đã chia sẻ kinh nghiệm và trợ giúp tài liệu, nhận xét và bình luận để hình thành nội dung cơ bản của cuốn sách. Chúng tôi hi vọng sẽ tiếp tục nhận được những ý kiến phê bình của bạn đọc về nội dung, chất lượng và hình thức trình bày để có thể định hướng cho các tập tiếp theo. Hà Nội, Lễ Hội Đạp Thanh - 2008 N.X.H
Sáng tạo trong Thuật toán và Lập trình Tập I 6 CHƢƠNG 1 GIẢI MỘT BÀI TOÁN TIN Phần này sẽ giới thiệu một số bước thường vận dụng trong quá trình giải các bài toán tin. 1. Bước đầu tiên và là bước quan trọng nhất là hiểu rõ nội dung bài toán. Đây là yêu cầu quen thuộc đối với những người làm toán. Để hiểu bài toán theo cách tiếp cận của tin học ta phải gắng xây dựng một số thí dụ phản ánh đúng các yêu cầu đề ra của đầu bài rồi thử giải các thí dụ đó để hình thành dần những hướng đi của thuật toán. 2. Bước thứ hai là dùng một ngôn ngữ quen thuộc, tốt nhất là ngôn ngữ toán học đặc tả các đối tượng cần xử lí ở mức độ trừu tượng, lập các tương quan, xây dựng các hệ thức thể hiện các quan hệ giữa các đại lượng cần xử lí. 3. Bước thứ ba là xác định cấu trúc dữ liệu để biểu diễn các đối tượng cần xử lí cho phù hợp với các thao tác của thuật toán. Trong những bước tiếp theo ta tiếp tục làm mịn dần các đặc tả theo trình tự từ trên xuống, từ trừu tượng đến cụ thể, từ đại thể đến chi tiết. 4. Bước cuối cùng là sử dụng ngôn ngữ lập trình đã chọn để viết chương trình hoàn chỉnh. Ở bước này ta tiến hành theo kĩ thuật đi từ dưới lên, từ những thao tác nhỏ đến các thao tác tổ hợp. Sau khi nhận được chương trình ta cho chương trình chạy thử với các dữ liệu lấy từ các thí dụ đã xây dựng ở bước đầu tiên. Điều quan trọng là xây dựng các thủ tục một cách khoa học và có chủ đích nhằm kiểm tra tính tin cậy của chương trình thu được và thực hiện một số cải tiến. Chúng ta sẽ vận dụng cách tiếp cận trên để giải một số bài toán cụ thể. Những phần trình bày dưới đây có thể sử dụng một vài kí pháp quen thuộc của tin học, thí dụ: x = abc số tự nhiên x được tạo bởi ba chữ số a, b và c. a, b = 0 9 hai số a và b có thể nhận các giá trị từ 0 đến 9.
Sáng tạo trong Thuật toán và Lập trình Tập I 7 Sở dĩ ta không sử dụng các kí hiệu toán học vì trên bàn phím máy tính không có các kí hiệu đó. Chọn các kí hiệu có sẵn trong các ngôn ngữ lập trình giúp chúng ta có thể viết các chú thích ngay trong chương trình. Bài 1.1. Số thân thiện Tìm tất cả các số tự nhiên hai chữ số mà khi đảo trật tự của hai chữ số đó sẽ thu được một số nguyên tố cùng nhau với số đã cho. Hiểu đầu bài Ta kí hiệu (a, b) là ước chung lớn nhất (ucln) của hai số tự nhiên a và b. Hai số tự nhiên a và b được gọi là nguyên tố cùng nhau khi và chỉ khi (a, b) = 1. Khi đó, chẳng hạn: a. (23, 32) = 1, vậy 23 là một số cần tìm. Theo tính chất đối xứng, ta có ngay 32 cũng là một số cần tìm. b. (12, 21) = 3, vậy 12 và đồng thời 21 không phải là những số cần tìm. Đặc tả: Gọi hai chữ số của số tự nhiên cần tìm x là a và b, ta có: (1) x = ab. (2) a, b = 0 9 (a và b biến thiên trong khoảng 0 9). (3) a > 0 vì x là số có hai chữ số. (4) (ab, ba) = 1. Ta kí hiệu x' là số đối xứng của số x theo nghĩa của đầu bài, khi đó ta có đặc tả như sau: (5) x = 10 99 (x biến thiên từ 10 đến 99, vì x là số có hai chữ số). (6) (x, x') = 1. Nếu x = ab thì x' = ba. Ta có thể tính giá trị của x' theo công thức: x' = (chữ số hàng đơn vị của x) * 10 + (chữ số hàng chục của x). Kí hiệu Đơn(x) là toán tử lấy chữ số hàng đơn vị của số tự nhiên x và kí hiệu Chục(x) là toán tử lấy chữ số hàng chục của x, ta có: x' = Đơn(x)*10 + Chục(x). Tổng hợp lại ta có đặc tả: Số cần tìm x phải thoả các tính chất sau:x = 10 99 (x nằm trong khoảng từ 10 đến 99). (7) x' = Đơn(x)*10 + Chục(x). (8) (x, x') = 1 (ước chung lớn nhất của x và x' bằng 1). Đặc tả trên được thể hiện qua ngôn ngữ phỏng trình tựa Pascal như sau: (9) for x:=10 to 99 do if ucln(x, đơn(x)*10+Chục(x))=1 then Lấy(x); trong đó, ucln(a,b)là hàm cho ước chung lớn nhất của hai số tự nhiên a và b; Lấy(x) là toán tử hiển thị x lên màn hình hoặc ghi x vào một mảng nào đó với mục đích sử dụng lại, nếu cần. Ta làm mịn đặc tả (10): ucln(a, b): Thuật toán Euclid là chia liên tiếp, thay số thứ nhất bằng dư của nó khi chia cho số thứ hai rồi hoán vị hai số. (* Tim uoc chung lon nhat cua hai so a va b. Thuat toan Euclid *) function Ucln(a,b: integer): integer;
Sáng tạo trong Thuật toán và Lập trình Tập I 8 var r: integer; begin while b > 0 do begin r:= a mod b; a:= b; b:= r; end; Ucln:= a; end; Đơn(x) = (x mod 10): số dư của phép chia nguyên x cho 10, thí dụ: Đơn(19) = 19 mod 10 = 9. Chục(x) = (x div 10): thương nguyên của phép chia x cho 10, thí dụ: Chục(19) = 19 div 10 = 1. Lấy(x): write(x) hoặc nạp giá trị x vào mảng s theo các thao tác sau: n := n + 1; s[n] := x; n đếm số phần tử hiện đã nạp trong mảng s. Biểu diễn dữ liệu Ta dùng mảng s để lưu các số tìm được. Dễ thấy s phải là một mảng nguyên chứa tối đa 90 phần tử vì các số cần khảo sát nằm trong khoảng từ 10 đến 99. var s: array[1 90] of integer; Phương án 1 của chương trình sẽ hoạt động theo hai bước như sau: 1. n := Tim; 2. Xem(n); Bước 1. Tìm và ghi vào mảng s các số thoả điều kiện đầu bài, n là số lượng các số tìm được. Bước 2. Hiển thị các phần tử của mảng s[1 n] chứa các số đã tìm được. Toán tử x' được viết dưới dạng hàm cho ta số tạo bởi các chữ số của x theo trật tự ngược lại. Ta đặt tên cho hàm này là SoDao (số đảo). Hàm có thể nhận giá trị vào là một số tự nhiên có nhiều chữ số. Để tạo số đảo y của số x cho trước, hàm SoDao lấy dần các chữ số hàng đơn vị của x để ghép vào bên phải số y: y := y*10 + (x mod 10) Sau mỗi bước, chữ số hàng đơn vị đã lấy được loại hẳn khỏi x bằng toán tử: x := x div 10 Chỉ thị {$B-} trong chương trình NTCN (nguyên tố cùng nhau) dưới đây đặt chế độ kiểm tra biểu thức lôgic vừa đủ. Khi đã xác định được giá trị chân lí cần thiết thì không tiến hành tính tiếp giá trị của biểu thức đó nữa. Thí dụ, với các lệnh x := 1; y := 5; if (x > 5) and (x + y 5) = false, chương trình sẽ bỏ qua nhân tử logic (x + y 5) = false vẫn tiếp tục tính giá trị của (x + y < 7) rồi lấy tích của hai giá trị tìm được (false and true = false) làm giá trị của biểu thức điều kiện trong cấu trúc rẽ nhánh nói
Sáng tạo trong Thuật toán và Lập trình Tập I 9 trên. Cuối cùng toán tử y := y - 1 cũng được thực hiện giống như trường hợp trên nhưng khối lượng tính toán lại nhiều hơn. (* Pascal *) (* So than thien (xy,yx) = 1 *) program SoThanThien; {$B-} uses Crt; const MN = 90; var s: array[1 MN] of integer; function Ucln(a,b: integer): integer; tự viết function SoDao(x: integer): integer; var y: integer; begin y := 0; repeat { ghep chu so hang don cua x vao ben phai y } y := 10*y + (x mod 10); x := x div 10; { loai chu so hang don } until (x = 0); SoDao := y; end; (* Tim cac so thoa dieu kien dau bai ghi vao mang s. Output: so luong cac so tim duoc *) function Tim: integer; var x,d: integer; begin d := 0; {So luong cac so can tim } for x := 10 to 99 do if Ucln(x,SoDao(x)) = 1 then begin d := d + 1; s[d]:= x; end; Tim := d; end; (* Hien thi mang s[1 n] tren man hinh. *) procedure Xem(n: integer); var i: integer; begin writeln; for i := 1 to n do write(s[i]:4); writeln; end; BEGIN n := Tim; Xem(n); writeln;
Sáng tạo trong Thuật toán và Lập trình Tập I 10 write(' Tong cong ',n,' so'); readln; END. // C# using System; namespace SangTao1 { / So Than Thien: (xy, yx) = 1 / class SoThanThien { static int mn = 90; static int [] s = new int[mn]; static void Main(string[] args) { Run(); Console.ReadLine(); } static void Run() { int n = Find(); for (int i=0;i b 0. Trường hợp a = b ta không xét vì khi đó x' = x và do đó Ucln(x, x) = x 10 1. Nếu b = 0 ta có x = 10a và x' = a. Ta thấy Ucln(10a, a) = a = 1 khi và chỉ khi a = 1. Do đó ta xét riêng trường hợp này. Khi ab = 10 ta có (10, 1) = 1. Vậy 10 chính là một số cần tìm và là số đầu tiên.
Sáng tạo trong Thuật toán và Lập trình Tập I 11 Mỗi khi tìm được hai chữ số a và b thoả điều kiện a > b và Ucln(a*10 + b, b*10 + a) = 1 ta đưa a*10 + b vào kết quả, nếu b > 0 ta đưa thêm số đảo b*10 + a vào kết quả. (* Pascal *) (* So Than thien: Phuong an 2 *) function Tim2: integer; var a,b,d: integer; begin d:= 1; {So luong cac so can tim} s[d] := 10; for a := 1 to 9 do for b := 1 to a-1 do if Ucln(a*10+b,b*10+a)=1 then begin d := d + 1; s[d] := a*10 + b; d := d + 1; s[d] := b*10 + a; end; Tim2 := d; end; // C# // Phuong an 2 static int Find2() { int a,b, d = 0; s[d++] = 10; for (a = 1; a <= 9; ++a) for (b = 1; b < a; ++b) if (Ucln(10*a + b, 10*b + a) == 1) { s[d++]=10*a+b; s[d++]=10*b+a; } return d; } Bài 1.2. Số cấp cộng Tìm các số tự nhiên lẻ có ba chữ số. Ba chữ số này, theo trật tự từ trái qua phải tạo thành một cấp số cộng. Đặc tả 1. x là số tự nhiên có ba chữ số: x = 100*a + 10*b + c. 2. x là số lẻ nên chữ số hàng đơn vị c phải là số lẻ: c = 1, 3, 5, 7, 9. 3. Chữ số hàng trăm của x phải khác 0: a = 1 9. 4. Nếu dãy a, b, c lập thành một cấp số cộng thì số đứng giữa b là trung bình cộng của hai số đầu và cuối: b = (a + c)/2 hay 2b = a+c. Từ (4) ta suy ra (a + c) là số chẵn. Do c lẻ, (a + c) chẵn nên a lẻ. Nếu biết a và c ta tính được x = 100a +10(a + c) / 2 + c = 100a + 5(a + c) + c = 105a + 6c. Vì chỉ có 5 chữ số lẻ là 1, 3, 5, 7 và 9 nên tổ hợp của a và c sẽ cho ta 25 số. Tổ chức dữ liệu
Sáng tạo trong Thuật toán và Lập trình Tập I 12 Ta tạo sẵn mảng nguyên 5 phần tử ChuSoLe[1 5] và gán trước các giá trị 1, 3, 5, 7, 9 cho mảng này. Trong Turbo Pascal (TP) việc này được thực hiện thông qua khai báo: const ChuSoLe: array[1 5] of integer = (1,3,5,7,9); Chú ý rằng khai báo này phải đặt trong mục const là nơi khai báo hằng. Trong C# ta khai báo như sau: int [] ChuSoLe = {1,3,5,7,9}; Ý nghĩa của dòng khai báo trên là như sau: Xin cấp phát một biến mảng kiểu nguyên có 5 phần tử với chỉ dẫn từ 1 đến 5, tên biến là ChuSoLe. 5 phần tử của biến được gán trước các trị 1, 3, 5, 7 và 9. Sau đó, mỗi khi cần, ta chỉ việc duyệt mảng ChuSoLe là thu được toàn bộ các chữ số lẻ theo trật tự đã khai báo trước. Chú ý Thủ tục inc(d) trong chương trình TP dưới đây tăng giá trị của biến d lên thêm 1 đơn vị, tức là tương đương với câu lệnh d := d + 1 và ++d (C#). Tương tự, thủ tục dec(d) sẽ giảm giá trị của biến d xuống 1 đơn vị, tương đương với câu lệnh d := d – 1 và d (C#). Tổng quát hơn, ta có thể viết: inc(d,n) tương đương với d := d + n và dec(d,n) tương đương với d := d – n. Khi n = 1 thì có thể bỏ qua tham số thứ hai. (* Pascal *) ( Cac so tu nhien le 3 chu so lap thanh cap so cong *) program CapCong; uses crt; const ChuSoLe: array [1 5] of integer = (1,3,5,7,9); var s: array [1 25] of integer; n: integer; (* Phat sinh cac so dang 105a+6c; a,c = 1,3,5,7,9 *) Function Tim: integer; var a,c,d,x: integer; begin d := 0; for a := 1 to 5 do begin x := 105*ChuSoLe[a]; for c := 1 to 5 do begin inc(d); s[d] := x + 6*ChuSoLe[c]; end; end; Tim := d; end;
Sáng tạo trong Thuật toán và Lập trình Tập I 13 (* Hien thi mang s[1 n] moi dong 20 so *) procedure Xem(n: integer); tự viết BEGIN n := Tim; Xem(n); writeln; write('Tong cong ',n,' so'); readln; END. // C# using System; namespace SangTao1 { class SoCapCong { static void Main(string[] args) { Show(Find()); Console.WriteLine("\n fini"); Console.ReadLine(); } static int[] Find() { int d = 0; int [] ChuSoLe = {1,3,5,7,9}; int []s = new int[25]; int x; for (int i = 0; i < 5; ++i) { x = 105 * ChuSoLe[i]; for (int j = 0; j < 5; ++j) s[d++] = x + 6 * ChuSoLe[j]; } return s; } static void Show(int[] s) { foreach (int x in s) Console.Write(x + " "); } } // SoCapCong } // SangTao1 Chú thích 1. Trong C# một hàm có thể cho ra giá trị là một mảng như hàm Find trong chương trình trên. 2. Lệnh foreach (int x in a) P(x) thực hiện thao tác P(x) trên mọi phần tử x của mảng, từ phần tử đầu tiên a[0] đến phần tử cuối cùng a[a.Length] với a.Length là chiều dài (số phần tử) của mảng a. Chú ý
Sáng tạo trong Thuật toán và Lập trình Tập I 14 1. Dựa vào nhận xét: dãy ba số a, b, c tạo thành cấp số cộng khi và chỉ khi b là trung bình cộng của a và c, tức là 2b = a + c ta có thể giải bài toán trên bằng phương pháp vét cạn dùng ba vòng for như sau: for a := 1 to 9 do for b := 0 to 9 do for c := 0 to 9 do if odd(c) and (2*b=a+c) then Ghi nhận số 100*a+10*b+c; Hàm odd(c) kiểm tra tính lẻ của số nguyên c. Phương pháp vét cạn đòi hỏi khoảng 10*10*10 = 1000 lần duyệt trong khi chỉ có 25 số, tức là một phần bốn mươi các số thoả mãn điều kiện của đầu bài. Phương pháp mô tả trong chương trình được gọi là phương pháp sinh: nó sinh ra đúng 25 số cần tìm. 2. Ta cần ghi nhận phương pháp sinh Phương pháp sinh Thay vì duyệt tìm các đối tượng hãy sinh ra chúng. Bài 1.3. Số cấp nhân Tìm các số tự nhiên có ba chữ số. Ba chữ số này, theo trật tự từ trái qua phải tạo thành một cấp số nhân với công bội là một số tự nhiên khác 0. Đặc tả Chú ý rằng ta chỉ xét các cấp số trên dãy số tự nhiên với công bội d là một số nguyên dương. Gọi x là số cần tìm, ta có: 1. x là số có ba chữ số: x = 100*a + 10*b + c. 2. a = 1 9; b = a*d; 0 < c = a*d*d 9. Hệ thức 2 cho phép ta tính giới hạn trên của d: ad 2 9 d 9/ a Vì d là số nguyên nên ta phải có d trunc(sqrt(9 div a)), trong đó sqrt là hàm tính căn bậc hai, trunc là hàm lấy phần nguyên. Ta cho a biến thiên trong khoảng 1 9 rồi cho công bội d biến thiên trong khoảng từ 1 đến trunc(sqrt(9 div a)). Với mỗi cặp số a và d ta tính x = 100*a+10*a*d+a*d*d = a*(100+10*d+d*d) Tuy nhiên, ta có thể nhẩm tính trước cận trên của d thì sẽ đỡ phải gọi các hàm trunc và sqrt là những hàm thao tác trên số thực do đó sẽ tốn thời gian. a 1 2 3 4 5 6 7 8 9 Cận trên d 3 2 1 1 1 1 1 1 1 (* Pascal *) (* Cac so tu nhien 3 chu so lap thanh cap nhan
Sáng tạo trong Thuật toán và Lập trình Tập I 15 *) program CapNhan; uses crt; const MN = 30; cd: array[1 9] = (3,2,1,1,1,1,1,1,1); var s: array [1 MN] of integer; n: integer; function Tim: integer; var a,d,n: integer; begin n:= 0; for a:= 1 to 9 do for d:=1 to cd[a]do begin inc(n); s[n]:= a*(100+10*d+d*d); end; Tim:= n; end; procedure Xem(n: integer): tự viết BEGIN clrscr; n:= Tim; Xem(n); writeln; write('Tong cong ',n,' so'); readln; END. // C# using System; using System.Collections; namespace SangTao1 { class SoCapNhan { static void Main(string[] args) { Show(Find()); Console.WriteLine("\n fini"); Console.ReadLine(); } static ArrayList Find() { ArrayList s = new ArrayList(); int[] cd = {0,3,2,1,1,1,1,1,1,1}; for (int a = 1; a <= 9; ++a) { for (int d = 1; d <= cd[a]; ++d) s.Add(a * (100 + 10 * d + d * d)); } return s; } static void Show(ArrayList s) tự viết } // SoCapNhan } SangTao1 Chú thích
Sáng tạo trong Thuật toán và Lập trình Tập I 16 Trong C# một hàm có thể cho ra giá trị là một mảng - danh sách kiểu ArrayList như hàm Find trong chương trình. Khi không biết có bao nhiêu phần tử được sinh ra trong quá trình tìm kiểm thì nên dùng kiểu mảng - danh sách để chứa kết quả. Mảng cd chứa các cận của d ứng với mỗi trị của a = 1 9, ta thêm cho cd phần tử 0 để tiện truy nhập. Bài 1.4. Mảng ngẫu nhiên Sinh ngẫu nhiên n số nguyên không âm cho mảng nguyên a. Đặc tả Trong TP hàm random(n) sinh một số ngẫu nhiên kiểu nguyên nằm trong khoảng từ 0 đến n - 1. Hãy tưởng tượng có một quân súc sắc n mặt mã số các mặt từ 0 đến n - 1. Khi ta gọi hàm random(n) thì máy tính sẽ gieo quân súc sắc đó và cho ta giá trị xuất hiện trên mặt ngửa. Trong C# phương thức Next(n) của lớp Random hoạt động tương tự như random(n) của TP. Chú ý 1. Trước khi gọi hàm random ta cần gọi thủ tục randomize để máy tính khởi động cơ chế phát sinh số ngẫu nhiên. 2. Thủ tục Gen(m) trong chương trình dưới đây sinh ngẫu nhiên m số nguyên trong khoảng từ 0 đến m - 1. Ta có thể cải tiến để viết thủ tục Gen(n,d,c) - sinh ngẫu nhiên n số nguyên trong khoảng từ d đến c (d < c) như sau. Để ý rằng random(c–d+1) biến thiên trong khoảng từ 0 đến c–d, do đó d+random(c–d+1) sẽ biến thiên trong khoảng từ d đến d+c–d = c. (* Pascal *) program RandomGen; (* Sinh ngau nhien n so nguyen khong am cho mang a *) {$B-} uses crt; const MN = 500; var a: array [1 MN] of integer; n: integer; Procedure Gen(m: integer); var i: integer; begin randomize; n := m; for i := 1 to n do a[i] := random(m); end; procedure Xem: tự viết; BEGIN Gen(200); Xem; END.
Sáng tạo trong Thuật toán và Lập trình Tập I 17 // C# using System; namespace SangTao1 { class RandomGen { static void Main(string[] args) { Show(Gen(200)); Console.WriteLine("\n Fini "); Console.ReadLine(); } static int [] Gen(int n) { int [] a = new int[n]; Random r = new Random(); for (int i = 0; i 1 cho trước thành hai đoạn có tổng các phần tử trong mỗi đoạn bằng nhau. Đặc tả Ta quy ước viết #E là "tồn tại" và #V là "với mọi". Kí hiệu sum(a[d c]) là tổng các phần tử liên tiếp nhau từ a[d] đến a[c] của dãy a: sum(a[d c]) = a[d] + a[d +1]+ + a[c]. Gọi t là tổng các phần tử của mảng: t = sum(a[1 n]). Muốn chia a thành hai đoạn a[1 i] và a[i+1 n] có tổng bằng nhau ta phải có: 1. t là số chẵn (t chia hết cho 2). Đặt t2 = t div 2. 2. (#E i: 1 t2 bài toán vô nghiệm. Ta khởi trị ngẫu nhiên cho mảng a. Tuy nhiên ta muốn số lần có nghiệm (mảng a chia được thành hai phần có tổng bằng nhau) xấp xỉ bằng số lần vô nghiệm. Ta sẽ thực hiện mục tiêu đề ra như sau: Mỗi lần khởi trị ta tung đồng xu hai mặt. Nếu gặp mặt sấp (random(2)=0), ta sẽ khởi trị tùy ý cho mảng a, ngược lại, nếu gặp mặt ngửa (random(2)=1) ta khởi trị a là mảng có nghiệm. Để khởi trị sao cho mảng a có nghiệm ta lại chọn ngẫu nhiên một điểm cắt d trong khoảng 1 (n/2). Sau đó ta khởi trị ngẫu nhiên cho các phần tử a[1 d]. Với các phần tử còn lại ta cũng khởi trị ngẫu nhiên trong khoảng hợp lí sao cho tổng các giá trị
Sáng tạo trong Thuật toán và Lập trình Tập I 18 của chúng đúng bằng tổng t của đoạn a[1 d]. Bạn đọc xem chi tiết thủ tục Gen trong chương trình. (* Pascal *) (* Chia mang nguyen a thanh 2 doan co tong bang nhau *) program ChiaTiLe11; {$B-} uses crt; const MN = 500; Esc = #27; var a: array [1 MN] of integer; n: integer; (* Sinh ngau nhien n so nguyen khong am cho mang a *) procedure Gen(m: integer); var i,d,t: integer; begin randomize; n := m; if random(2)=0 then begin {khoi tri tuy y} for i := 1 to n do a[i]:=random(m); exit; end; { Khoi tri mang co tong d phan tu dau bang tong cac phan tu con lai } d := random(n div 2)+ 1; { diem chia } t := 0; for i := 1 to d do begin a[i] := random(n); t := t + a[i]; end; { t = sum(a[1 d]) } for i := d+1 to n-1 do begin { sum(a[d+1 i]) + t = sum(a[1 d]) } a[i] := random(t); t := t-a[i]; end; a[n] := t; { sum(a[1 d]) = sum(a[d+1 n]) } end; procedure Xem: Hiển thị mảng a, tự viết function Chia: integer; var i, t, t2, tr: integer; begin Chia := -1; t := 0; for i:=1 to n do t:=t+a[i]; {t=sum(a[1 n]} if Odd(t) then exit; { vo nghiem } t2 := t div 2; tr := 0; for i:=1 to n do begin
Sáng tạo trong Thuật toán và Lập trình Tập I 19 tr := tr + a[i]; if tr > t2 then exit; {vo nghiem } if tr = t2 then { co nghiem i } begin Chia:= i; exit; end; end; end; procedure Test; var i: integer; begin repeat Gen(10); Xem; i := Chia; if i = -1 then writeln('Khong chia duoc') else begin writeln('Doan thu nhat: a[1 ',i,']'); writeln('Doan thu hai: a[',i+1,' ',n,']'); end; until ReadKey=Esc; end; BEGIN Test; END. Chú ý 1. Muốn dừng chương trình hãy nhấn phím Esc có mã ASCII là #27. 2. Nếu mảng a có chứa một số giá trị 0 thì bài toán có thể có nhiều nghiệm (nhiều cách chia). // C# using System; namespace SangTao1 { class ChiaMangTiLe1_1 { static void Main() { do { Run(20); Console.Write("\n Bam phim ENTER “ + “de tiep tuc, "); Console.Write("\n Bam phim T de thoat: "); } while (Console.ReadLine() == ""); } static public void Run(int n) { int[] a = new int[n]; Gen(a, n); // sinh ngau nhien 1 test Print(a, n); int t = 0, d = Chia(a, n, ref t); if (d < 0) Console.WriteLine("\n Khong chia duoc"); else if (KiemTra(a, n, d)) { Console.WriteLine("\n Doan thu nhat: 1 {0} ",d); Console.WriteLine("\n Doan thu hai: {0} {1} ",
Sáng tạo trong Thuật toán và Lập trình Tập I 20 d+1, n); Console.WriteLine("\n Tong moi doan: " + t); } else Console.WriteLine("\n Loi giai sai!"); } // end Run // Kiem tra sum(a[1 d] == sum(a[d+1 n]) ? static public bool KiemTra(int[] a, int n, int d) { if (d = n) return false; int t = 0; for (int i = 0; i < d; ++i) t += a[i]; for (int i = d; i < n; ++i) t -= a[i]; return (t == 0) ? true : false; } static public int Chia(int[] a, int n, ref int t) { int sum = 0; // sum = tong(a[1 n]) for (int i = 0; i < n; ++i) sum += a[i]; if (sum % 2 != 0) return -1; t = sum / 2; // tong moi doan int tr = 0; // tong rieng // doan 1: tr = sum a[1 i] for (int i = 0; i < n; ++i) { tr += a[i]; if (tr == t) return i+1; } return -1; } // sinh ngau nhien n so ghi vao mang a static public void Gen(int[] a, int n) { Random r = new Random(); if (r.Next(2) == 0) { // 1/2 so test la vo nghiem for (int i = 0; i < n; ++i) a[i]=r.Next(n); return; } // sinh mang a: sum(a[0 d-1])=sum(a[d n-1]) int d = r.Next(n / 2) + 1; // diem chia int t = 0; // sinh doan a[0 d-1] for (int i = 0; i < d; ++i) { a[i] = r.Next(n); t += a[i]; } // sinh tiep doan a[d n-1] int n1 = n-1; for (int i = d; i < n1; ++i) { a[i] = r.Next(t); t -= a[i]; } a[n-1] = t; // phan tu cuoi } static public void Print(int[] a, int n): tự viết } // SoCapNhan } // SangTao1
Sáng tạo trong Thuật toán và Lập trình Tập I 21 Bài 1.6. Chia mảng tỉ lệ 1:k Tìm cách chia dãy số nguyên không âm a1, a2, ,an, n > 1 cho trước thành hai đoạn có tổng các phần tử trong một đoạn gấp k lần tổng các phần tử trong đoạn kia, k nguyên dương. Đặc tả Gọi t là tổng các phần tử của dãy a, t = sum(a[1 n]) Muốn chia a thành hai đoạn a[1 i] và a[i + 1 n] có tổng gấp nhau k lần ta phải có: 1. t chia hết cho (k + 1). Đặt t1 = t div (k + 1) và tk = t - t1. 2. (#E i: 1 1 thì t1 t1 ta chưa thể kết luận là bài toán vô nghiệm. Trường hợp này ta phải tiếp tục tích luỹ tr để hi vọng đạt được tổng tr = tk. Nếu sau khi tích luỹ ta thu được tr = tk thì bài toán có nghiệm i, ngược lại, khi tr > tk ta kết luận là bài toán vô nghiệm. Function Chia(n,k: integer): integer; var i: integer; t, t1, tk, tr: longint; begin Chia := -1; t := 0; { t = sum(a[1 n]) } for i := 1 to n do t := t+a[i]; if (t mod (k+1) <> 0) then exit; { vo nghiem } { Xu li truong hop co nghiem } t1 := t div (k+1); { doan tong nho } tk := t - t1; { tk = k * t1} tr := 0; { tong rieng tr = sum(a[1 i]) } for i := 1 to n do begin tr := tr + a[i]; if (tr = t1) or (tr = tk) then begin { lay nghiem i } Chia:= i; exit; end; end; end; Ta gọi thủ tục Gen để sinh dữ liệu kiểm thử. Cũng giống như bài trước, ta sẽ sinh ngẫu nhiên dữ liệu kiểm thử cho hai trường hợp: chắc chắn có nghiệm và có thể vô nghiệm. Với trường hợp có thể vô nghiệm ta sinh ngẫu nhiên như bình thường, for i := 1 to n do a[i] := random(n); Với trường hợp có nghiệm, ta sinh ngẫu nhiên mảng a gồm hai đoạn: Đoạn thứ nhất a[1 d] và đoạn thứ hai a[d + 1 n] trong đó d là một điểm chia được sinh ngẫu nhiên d := random(n div 2)+1; {diem chia} Ta lại chọn ngẫu nhiên một trong hai trường hợp:
Sáng tạo trong Thuật toán và Lập trình Tập I 22 Trường hợp thứ nhất: đoạn thứ nhất gấp k lần đoạn thứ hai. Trường hợp thứ hai: đoạn thứ hai gấp k lần đoạn thứ nhất. (* Pascal *) (* Chia mang nguyen a thanh 2 doan co tong ti le 1:k *) {$B-} uses Crt; const MN = 500; Esc = #27;{ dau thoat } bl = #32; { dau cach } nl = #13#10; { xuong dong } var a: array [0 MN] of integer; n: integer; (* Sinh ngau nhien n so nguyen khong am cho mang a *) Procedure Gen(m,k: integer); var i,d: integer; t: longint; begin n := m; t := 0; if random(2) = 0 then { vo nghiem } begin for i := 1 to n do a[i]:= random(n); exit; end; { co nghiem } d := random(n div 2)+1; { diem chia } for i := 1 to d do begin a[i] := random(n); t := t+a[i]; end; if (random(2) = 0) then { doan a[1 d] gap k lan doan cuoi } a[d] := a[d]+(k-1)*t else { doan cuoi gap k lan doan a[1 d] } t := k*t; for i := d+1 to n-1 do begin a[i] := random(t); t := t-a[i]; end; a[n] := t; end; Procedure Xem; Hiển thị mảng a, tự viết Function Chia(n,k: integer): integer; Tự viết Procedure Test; var j,i,k: integer; t: longint; begin randomize; repeat
Sáng tạo trong Thuật toán và Lập trình Tập I 23 n := 10 + random(10); k := random(5)+1; writeln(nl,' n = ',n,' k = ',k); Gen(n,k); Xem; i := Chia(n,k); if i 1000000 || k < 1) return; int[] a = Gen(n, k); Print(a); int d = Chia(a, k); if (d < 0) {
Sáng tạo trong Thuật toán và Lập trình Tập I 24 Console.WriteLine("\n Vo nghiem"); return; } Console.WriteLine("\n “+ Test(a, d, k)); } // Kiem tra k*Sum(a[1 d]) = Sum(a[d+1 n]) ? // hoac Sum(a[1 d]) = k*Sum(a[d+1 n]) static public bool Test(int[] a, int d, int k) { Console.WriteLine("\n\n Test, k = " + k); Console.WriteLine(" Diem Chia = " + d); int t1 = 0; for (int i = 0; i < d; ++i) t1 += a[i]; int t2 = 0; for (int i = d; i < a.Length; ++i) t2 += a[i]; Console.WriteLine("Sum1 = {0}, Sum2 = {1}", t1, t2); return (t1 == k * t2 || t2 == k * t1); } static public int Chia(int[] a, int k) { int t = 0; foreach (int x in a) t += x; if (t % (k + 1) != 0) return -1; int t1 = t / (k + 1); // tong 1 phan chia int t2 = t - t1; // tong phan con lai int tr = 0; // tong rieng for (int i = 0; i < a.Length; ++i) { tr += a[i]; if (tr == t1 || tr == t2) return i+1; } return -1; } static public int[] Gen(int n, int k) { Random r = new Random(); int[] a = new int[n]; if (r.Next(2) == 0) { // khoang 1/2 so test la vo nghiem for (int i = 0; i < n; ++i) a[i] = r.Next(n); return a; } int d = r.Next(n / 2) + 1; //diem chia int t = 0; int d1 = d - 1; for (int i = 0; i < d1; ++i) { a[i] = r.Next(n); t += a[i]; } if (r.Next(2) == 0) // doan dau a[1 d] // gap k lan doan cuoi a[d+1 n] a[d1] += (k - 1) * t;
Sáng tạo trong Thuật toán và Lập trình Tập I 25 else t *= k; // doan cuoi gap k lan doan dau int n1 = n - 1; for (int i = d; i < n1; ++i) { a[i] = r.Next(t); t -= a[i]; } a[n1] = t; return a; } static public void Print(int[] a) tự viết } // ChiaMangTiLel_k } // SangTao1
Sáng tạo trong Thuật toán và Lập trình Tập I 26 CHƢƠNG 2 SINH DỮ LIỆU VÀO VÀ RA Hầu hết các bài toán tin đều đòi hỏi dữ liệu vào và ra. Người ta thường dùng ba phương thức sinh và nạp dữ liệu sau đây: 1. Nạp dữ liệu trực tiếp từ bàn phím. Phương thức này được dùng khi dữ liệu không nhiều. 2. Sinh dữ liệu nhờ hàm random (xem chương 1). Phương thức này nhanh chóng và tiện lợi, nếu khéo tổ chức có thể sinh ngẫu nhiên được các dữ liệu đáp ứng được một số điều kiện định trước. 3. Đọc dữ liệu từ một tệp, thường là tệp văn bản. Phương thức này khá tiện lợi khi phải chuẩn bị trước những tệp dữ liệu phức tạp. Kết quả thực hiện chương trình cũng thường được thông báo trực tiếp trên màn hình hoặc ghi vào một tệp văn bản. Bài 2.1. Sinh ngẫu nhiên theo khoảng Sinh ngẫu nhiên cho mảng nguyên a n phần tử trong khoảng -M M; M > 0. Đặc tả Ta viết thủ tục tổng quát Gen(n,d,c) - sinh ngẫu nhiên n số nguyên trong khoảng từ d đến c (d < c) (xem bài giải 1.4). Để giải bài 2.1 ta chỉ cần gọi Gen(n,-M,M). Để ý rằng random(c–d+1) biến thiên trong khoảng từ 0 đến c-d do đó d+random(c–d+1) sẽ biến thiên trong khoảng từ d đến d+c-d = c. (* sinh ngau nhien n so nguyen trong khoang d den c va ghi vao mang a *) Procedure Gen(n,d,c: integer); var i,len: integer; begin randomize; len := c-d+1; for i:=1 to n do a[i]:= d+random(len); end;
Sáng tạo trong Thuật toán và Lập trình Tập I 27 (* Pascal *) (* Sinh ngau nhien cho mang nguyen a n phan tu trong khoang -M M; M > 0. *) program RGen; uses crt; const MN = 1000; var a: array[1 MN] of integer; (* sinh ngau nhien n so nguyen trong khoang d den c va ghi vao mang a *) Procedure Gen(n,d,c: integer); tự viết procedure Xem(n: integer); Hiển thị mảng a, tự viết procedure Test; var n: integer; begin n := 20; { sinh ngau nhien 20 so trong khoang -8 8 } Gen(n,-8,8); Xem(n); readln; end; BEGIN Test; END. // C# using System; using System.Collections.Generic; using System.Text; namespace SangTao1 { /* * Sinh ngau nhien n so * trong khoang d c * */ class RGen { static void Main(string[] args) { Print(Gen(20, -8, 8)); Console.ReadLine(); } static public int[] Gen(int n, int d, int c) { Random r = new Random(); int len = c-d+1; int [] a = new int[n]; for (int i = 0; i < n; ++i) a[i] = d + r.Next(len);
Sáng tạo trong Thuật toán và Lập trình Tập I 28 return a; } static public void Print(int [] a) { Console.WriteLine(); foreach (int x in a) Console.Write(x + " "); Console.WriteLine(); } } // RGen } // SangTao1 Bài 2.2. Sinh ngẫu nhiên tăng Sinh ngẫu nhiên n phần tử được sắp không giảm cho mảng nguyên a. Thuật toán 1. Sinh ngẫu nhiên phần tử đầu tiên: a[1] := random(n); 2. Từ phần tử thứ hai trở đi, trị được sinh bằng trị của phần tử sát trước nó cộng thêm một đại lượng ngẫu nhiên: (i = 2 n): a[i] := a[i - 1] + random(n), do đó a[i] >= a[i - 1]. (* Pascal *) (* Sinh ngau nhien cho mang nguyen a n phan tu sap khong giam *) program IncGen; uses crt; const MN = 1000; var a: array [1 MN] of integer; (* Sinh ngau nhien day tang gom n phan tu *) procedure Gen(n: integer); var i: integer; begin randomize; a[1]:= random(5); {khoi tao phan tu dau tien } for i:= 2 to n do a[i]:= a[i-1]+random(10); end; procedure Xem(n: integer); tự viết procedure Test; var n: integer; begin n := 200; { test voi 200 phan tu } Gen(n); Xem(n); readln; end; BEGIN Test; END. // C#
Sáng tạo trong Thuật toán và Lập trình Tập I 29 using System; using System.Collections.Generic; using System.Text; namespace SangTao1 { /* * Sinh ngau nhien n so * tao thanh day khong giam * */ class IncGen { static void Main(string[] args) { Print(Gen(200)); Console.ReadLine(); } static public int[] Gen(int n) { Random r = new Random(); int [] a = new int[n]; a[0] = r.Next(5); for (int i = 1; i < n; ++i) a[i] = a[i-1] + r.Next(10); return a; } static public void Print(int [] a) tự viết } // IncGen } // SangTao1 Bài 2.3. Sinh hoán vị ngẫu nhiên Sinh ngẫu nhiên cho mảng nguyên a một hoán vị của 1 n. Đặc tả Xuất phát từ hoán vị đơn vị a = (1, 2, , n) ta đổi chỗ a[1] với một phần tử tuỳ ý (được chọn ngẫu nhiên) a[j] sẽ được một hoán vị. Ta có thể thực hiện việc đổi chỗ nhiều lần. (* Pascal *) (* Sinh ngau nhien cho mang nguyen a mot hoan vi cua 1 n *) program GenPer; const MN = 1000; { so luong toi da } Esc = #27; { dau thoat } BL = #32; { dau cach } var a: array[1 MN] of integer; (* Sinh du lieu *) procedure Gen(n: integer); var i,j,x: integer; begin { Khoi tao hoan vi don vi }
Sáng tạo trong Thuật toán và Lập trình Tập I 30 for i:= 1 to n do a[i]:= i; for i:= 1 to n do begin j := random(n)+1; x := a[1]; a[1] := a[j]; a[j] := x; end; end; procedure Xem(n: integer); tự viết procedure Test; var n: integer; begin randomize; repeat {chon ngau nhien kich thuoc n = 10 39} n := random(30)+10; Gen(n); Xem(n); until ReadKey = Esc; { Nhan ESC de thoat } end; BEGIN Test; END. // C# using System; using System.Collections.Generic; using System.Text; namespace SangTao1 { /* * Sinh ngau nhien hoan vi * 1 n * */ class GenPer { static void Main(string[] args) { Print(Gen(20)); Console.ReadLine(); } static public int[] Gen(int n) { Random r = new Random(); int[] a = new int[n]; for (int i = 0; i < n; ++i) a[i] = i+1; for (int i = 0; i < n; ++i) { int j = r.Next(n); int t = a[0]; a[0] = a[j]; a[j] = t; } return a; } static public void Print(int [] a) tự viết
Sáng tạo trong Thuật toán và Lập trình Tập I 31 } // IncGen } // SangTao1 Bài 2.4. Sinh ngẫu nhiên đều Sinh ngẫu nhiên n phần tử cho mảng nguyên a thoả điều kiện n phần tử tạo thành k đoạn liên tiếp có tổng các phần tử trong mỗi đoạn bằng nhau và bằng giá trị t cho trước. Thuật toán 1. Chọn số lượng các phần tử trong mỗi đoạn là random(n div k) + 1, khi đó số lượng các phần tử được phát sinh ngẫu nhiên sẽ không vượt quá k*(n div k) ≤ n Sau đó ta sẽ chỉnh sao cho số lượng các phần tử đúng bằng n. 2. Giả sử a[d c] là đoạn thứ j cần được sinh ngẫu nhiên sao cho a[d] + a[d + 1] + + a[c] = t Ta sinh đoạn này như sau: 2.1. Gán tr := t; { tr - giá trị còn lại của tổng }. 2.2. Gán trị ngẫu nhiên 0 tr-1 cho các phần tử a[d (c - 1)] (i = d c ): a[i] := random(tr) 2.3. Đồng thời chỉnh giá trị còn lại của tr: tr := tr - a[i] Ta có: a[d] < t a[d+1] < t - a[d] a[d+2] < t - a[d+1] - a[d] a[c - 1] < t - a[d] - a[d + 1] - - a[c - 2] Chuyển vế các phần tử a[*] trong biểu thức cuối cùng, ta thu được a[d] + a[d + 1] + + a[c – 1] < t 2.4. Ta đặt giá trị còn lại của tổng riêng vào phần tử cuối đoạn: a[c] := tr sẽ thu được a[d] + a[d + 1] + + a[c] = t. (* Pascal *) (* Sinh ngau nhien cho mang nguyen a n phan tu tao thanh k doan lien tiep co tong bang nhau *) program KGen; uses crt; const MN = 1000; {kich thuoc toi da cua mang a} Esc = #27; {dau thoat} BL = #32; {dau cách} var a: array[1 MN] of integer; (* Sinh du lieu *) procedure Gen(n,k,t: integer); var i,j,p,tr,s: integer;
Sáng tạo trong Thuật toán và Lập trình Tập I 32 begin if (k n) then exit; s := n div k;{s - so toi da phan tu trong moi doan} i := 0; {chi dan lien tuc cho cac phan tu moi sinh} for j := 1 to k do {sinh doan thu j} begin tr := t; for p := 1 to random(s) do { random(s)+1 = so phan tu trong 1 doan } begin inc(i); a[i] := random(tr); tr := tr – a[i]; {gia tri con lai cua tong} end; inc(i); {i phan tu cuoi cung cua doan j} a[i] := tr; end; {bu 0 cho cac phan tu con lai} for i := i+1 to n do a[i] := 0; end; procedure Xem(n: integer); Hiển thị mảng a, tự viết procedure Test; var n,k: integer; begin randomize; repeat n := random(30) + 1; k := random(8) + 1; t := random(30)+10; writeln('n = ',n,' k = ',k,' t = ',t); Gen(n,k,t); Xem(n); until ReadKey = Esc; end; BEGIN Test; END. // C# using System; using System.Collections.Generic; using System.Text; using System; namespace SangTao1 { class KGen { static void Main(string[] args) { Random r = new Random(); int n, k, t; do { n = r.Next(30) + 1;
Sáng tạo trong Thuật toán và Lập trình Tập I 33 t = r.Next(30) + 1; k = r.Next(8) + 1; Console.WriteLine("\n n = " + n + " k = " + k + " t = " + t); Print(Gen(n, k, t)); Console.Write("\n Bam RETURN de tiep tuc: "); } while (Console.ReadLine() == ""); } // sinh n phan tu chia thanh k doan, // moi doan co tong t static public int[] Gen(int n, int k, int t) { if (k n) return new int[0]; Random r = new Random(); int[] a = new int[n]; int s = n / k; // so phan tu trong 1 doan int i = 0; for (int j = 0; j < k; ++j) { // sinh doan thu j int tr = t; int endp = r.Next(s); for (int p = 0; p < endp; ++p,++i) { a[i] = r.Next(tr); tr -= a[i]; } a[i++] = tr; } // dien 0 cho du n phan tu for (; i < n; ++i) a[i] = 0; return a; } static public void Print(int[] a) tự viết } // KGen } // SangTao1 Bài 2.5. Sinh ngẫu nhiên tỉ lệ Sinh ngẫu nhiên cho mảng nguyên a có n phần tử tạo thành hai đoạn liên tiếp có tổng các phần tử trong một đoạn gấp k lần tổng các phần tử của đoạn kia. Thuật toán 1. Sinh ngẫu nhiên tổng t1 := random(n) + 1. 2. Tính t2 := k*t1. 3. Gieo đồng xu bằng cách gọi random(2) để xác định tổng nào trong số t1 và t2 được chọn trước. 4. Sinh random(n div 2)+1 phần tử cho đoạn thứ nhất sao cho tổng các phần tử của đoạn này bằng t1 (xem bài 2.4). 5. Sinh nốt các phần tử cho đoạn thứ hai sao cho tổng các phần tử của đoạn này bằng t2. (* Pascal *) program K2gen; uses crt; const MN = 1000;
Sáng tạo trong Thuật toán và Lập trình Tập I 34 var a: array[1 MN] of integer; (* Sinh du lieu *) procedure Gen(n,k:integer); var i,j,t1,t2:integer; begin if (k n) then exit; t1 := random(n) + 1; {tong mot doan; tong doan con lai = k*t1 } {chon ngau nhien doan co tong lon dat truoc hay sau } if random(2)= 0 then t2 := k*t1 else begin t2 := t1; t1 := k*t2; end; i := 0; {sinh doan thu nhat} for j := 1 to random(n div 2) do begin inc(i); a[i] := random(t1); t1 := t1 – a[i]; end; inc(i); a[i] := t1; while i < n do {sinh doan thu hai } begin inc(i); a[i]:= random(t2); t2 := t2 – a[i]; end; a[n] := a[n] + t2; end; procedure Xem(n: integer); tự viết procedure Test; var n,k: integer; begin randomize; repeat n := random(30) + 1; k := random(8) + 1; write(' n = ',n,' k = ',k); Gen(n,k); Xem(n); until ReadKey = #27; end; BEGIN Test;
Sáng tạo trong Thuật toán và Lập trình Tập I 35 END. // C# using System; using System.Collections.Generic; using System.Text; namespace SangTao1 { class K2Gen { static void Main(string[] args) { Random r = new Random(); int n, k; do { n = r.Next(30) + 2; k = r.Next(8) + 1; Console.WriteLine("\n n = " + n + " k = " + k); int [] a = new int [n]; int n1 = Gen(a,n,k); Print(a); Test(a, n1, k); Console.Write("\n Bam RETURN " + " de tiep tuc: "); } while (Console.ReadLine() == ""); } // Kiem tra ket qua static void Test(int[] a, int n1, int k) { int t1 = 0; for (int i = 0; i < n1; ++i) t1 += a[i]; Console.WriteLine("\n Doan thu nhat: " + "sum(a[0 " + (n1 - 1) + "]) = " + t1); int t2 = 0; for (int i = n1; i < a.Length; ++i) t2 += a[i]; Console.WriteLine("\n Doan thu hai: " + "sum(a["+n1+" "+(a.Length - 1)+"]) = "+t2); if ((t1 == k * t2) || (t2 == k * t1)) Console.WriteLine("\n DUNG"); else Console.WriteLine("\n SAI"); }
Sáng tạo trong Thuật toán và Lập trình Tập I 36 static public int Gen(int [] a, int n, int k) { Random r = new Random(); int i = 0; // phan tu thu i trong a // n1 - so phan tu trong doan 1 int n1 = r.Next(n / 2) + 1; int t1 = 0; // tong doan 1 // sinh doan thu 1 for (; i < n1; ++i) // { a[i] = r.Next(10); t1 += a[i]; } int t2 = k* t1; int tt = t1; // xac dinh ngau nhien // 0. t2 gap k lan t1, hoac // 1. t1 gap k lan t2 if (r.Next(2)==1) { // t1 gap k lan t2 t1 = t2; t2 = tt; a[i-1] += (t1-t2); } // sinh doan 2 for (; i < n; ++i) // { a[i] = r.Next(t2); t2 -= a[i]; } a[n-1] += t2; return n1; } static public void Print(int[] a) { Console.WriteLine(); foreach (int x in a) Console.Write(x + " "); Console.WriteLine(); } } // K2Gen } // SangTao1 Bài 2.6. Sinh ngẫu nhiên tệp tăng Sinh ngẫu nhiên n số tự nhiên sắp tăng và ghi vào một tệp văn bản có tên cho trước. Thuật toán Bạn đọc xem trực tiếp chương trình và giải thích cách làm.
Sáng tạo trong Thuật toán và Lập trình Tập I 37 (* Pascal *) (* Sinh ngau nhien n so tu nhien sap tang va ghi vao tep van ban co ten cho truoc *) program FincGen; uses crt; const BL = #32; { dau cach } (* Sinh du lieu *) procedure Gen(fn: string; n: integer); var f: text; i: integer; x: longint; begin assign(f,fn); {fn: file name (ten tep)} rewrite(f); randomize; x := 0; for i:= 1 to n do begin x := x+random(10); write(f,x,BL); { moi dong trong file chua 20 so } if i mod 20 = 0 then writeln(f); end; if i mod 20 <> 0 then writeln(f); close(f); end; procedure Test; begin Gen('DATA.INP',200); write('Ket'); readln; end; BEGIN Test; END. // C# using System; using System.Collections.Generic; using System.Text; using System.IO; namespace SangTaoT1 { class FincGen { static void Main(string[] args) { string fn = "Data.txt"; GenToFile(fn, 81); Show(fn); Console.ReadLine(); } static public void GenToFile(string fn, int n)
Sáng tạo trong Thuật toán và Lập trình Tập I 38 { StreamWriter f = File.CreateText(fn); Random r = new Random(); int x = r.Next(10); for (int i = 0; i 0 then writeln(f); close(f); end; BEGIN
Sáng tạo trong Thuật toán và Lập trình Tập I 39 Gen('DATA.INP',200); write('Ket'); readln; END. // C# using System; using System.Collections.Generic; using System.Text; using System.IO; namespace SangTao1 { class FCapCong { static void Main(string[] args) { string fn = "Data.txt"; GenToFile(fn, 81); Show(fn); Console.ReadLine(); } static public void GenToFile(string fn, int n) { StreamWriter f = File.CreateText(fn); Random r = new Random(); int s = r.Next(n), d = r.Next(10)+1; for (int i = 0; i < n; ++i) { f.Write(s + " "); if (i % 20 == 19) f.WriteLine(); s += d; } if (n % 20 != 19) f.WriteLine(); f.Close(); } static public void Show(string fn) { Console.WriteLine(File.ReadAllText(fn)); } } // FcapCong } // SangTao1 Bài 2.8. Sinh ngẫu nhiên mảng đối xứng Sinh ngẫu nhiên các giá trị để ghi vào một mảng hai chiều a[1 n, 1 n] sao cho các phần tử đối xứng nhau qua đường chéo chính, tức là a[i, j] = a[j, i], 1 ≤ i, j ≤ N. Thuật toán 1. Sinh ngẫu nhiên các phần tử trên đường chéo chính a[i,i],i=1 n. 2. Sinh ngẫu nhiên các phần tử nằm phía trên đường chéo chính a[i,j], i=1 n, j=i+1 n rồi lấy đối xứng: a[j,i]:= a[i,j]. Độ phức tạp: n2. (* Pascal *)
Sáng tạo trong Thuật toán và Lập trình Tập I 40 program GenMatSym; uses crt; const MN = 100; var a = array[1 MN,1 MN] of integer; procedure Gen(n: integer); var i, j: integer; begin randomize; for I := 1 to n do begin a[i,i] := random(n); for j := i+1 to n do begin a[i,j]:=random(n); a[j,i]:=a[i,j]; end; end; end; procedure Xem(n: integer); var i, j: integer; begin writeln; for i:= 1 to n do begin writeln; for j:= 1 to n do write(a[i,j]:4); end; end; BEGIN Gen(20); Xem(20); readln; END. // C# using System; using System.Collections.Generic; using System.Text; namespace SangTao1 { class GenMatSym { static void Main(string[] args) { int n = 20; int[,] a = Gen(n); Print(a, n); Console.WriteLine("\n Fini "); Console.ReadLine(); } static public int [,] Gen(int n) { int[,] a = new int[n, n]; Random r = new Random(); for (int i = 0; i < n; ++i)
Sáng tạo trong Thuật toán và Lập trình Tập I 41 { a[i, i] = r.Next(100); for (int j=i+1; j<n; ++j) { a[i, j] = r.Next(100); a[j, i] = a[i, j]; } } return a; } // hiển thị mảng a[0 (n-1] static public void Print(int [,] a,int n) tự viết } // GenMatSym } // SangTao1 Bài 2.9. Số độ cao h Độ cao của một số tự nhiên là tổng các chữ số của số đó. Sinh toàn bộ các số tự nhiên có tối đa ba chữ số và có độ cao h cho trước. Ghi kết quả vào một tệp văn bản có tên cho trước. Thuật toán Bài toán này có cách phát biểu khác và tổng quát như sau: có n cốc nước dung tích 9 thìa mỗi cốc. Cho một bình đựng h thìa nước. Hãy xác định mọi phương án chia nước vào các cốc. Ta xét lời giải với n = 3. Ta có h = 0 27. 1. Các số cần tìm y có dạng y = abc, a + b + c = h và a biến thiên từ mina đến maxa, trong đó mina là lượng nước ít nhất trong cốc đầu tiên a, maxa là lượng nước lớn nhất trong cốc a. Nếu đổ đầy hai cốc b và c, mỗi cốc 9 thìa nước thì lượng nước còn lại sẽ là tối thiểu cho cốc a. Ngược lại, nếu tổng cộng chỉ có h < 9 thìa nước thì lượng nước tối đa trong cốc a phải là h. Ta có if h 18 then mina := 0 else mina := h-18; if h 9 then maxa := 9 else maxa := h; 2. Với mỗi a = mina maxa ta tính 2.1. bc = h-a (biến bc chứa tổng các chữ số b và c). 2.2. Giải bài toán nhỏ với n = 2. if bc 9 then minb := 0 else minb := bc-9; if bc 9 then maxb := 9 else maxb := bc; 2.3. Với mỗi b = minb maxb ta tính y = 100*a + 10*b + (bc – b). Ghi số này vào tệp. (* Pascal *) (*-= Sinh cac so khong qua 3 chu so co do cao h va ghi vao tep fn *) program HGen; uses crt;
Sáng tạo trong Thuật toán và Lập trình Tập I 42 function Gen(fn:string;h:integer): integer; var f: text; a,b,bc,mina,maxa,minb,maxb: integer; x,y,d: integer; begin {tong 3 chu so toi da la 27, toi thieu la 0 } if (h 27) then exit; assign(f,fn); rewrite(f); d:= 0; {dem so luong cac so do cao h} if h = 9 then maxa := 9 else maxa := h; for a := mina to maxa do begin x := 100*a; bc := h-a; if bc = 9 then maxb := 9 else maxb := bc; for b := minb to maxb do begin y := x + 10*b + (bc - b); write(f,y:4); inc(d); { Ghi moi dong 10 so } if d mod 10 = 0 then writeln(f); end; end; close(f); Gen := d; end; procedure Test; var n: integer; begin n := Gen('HEIGHT.NUM',10); write('Tong cong ‟,n,' so'); readln; end; BEGIN Test; END. // C# using System; using System.Collections.Generic; using System.Text; using System.IO; namespace SangTao1 { class HGen { static void Main(string[] args) { string fn = "HGen.txt"; int h = 10; Console.WriteLine("\n File " + fn);
Sáng tạo trong Thuật toán và Lập trình Tập I 43 Console.WriteLine(" H = " + h); int d = Gen(fn,10); Test(fn,d); Console.WriteLine("\n Fini "); Console.ReadLine(); } static public int Gen(string fn, int h) { int a, b, mina, maxa, minb, maxb, bc, x, y, d = 0; StreamWriter f = File.CreateText(fn); mina = (h = 9) ? 9 : bc; for (b = minb; b <= maxb; ++b) { ++d; y=x+10*b+(bc-b); f.Write(y+" "); if (d % 10 == 0) f.WriteLine(); } } f.Close(); return d; } // Doc lai file de kiem tra static public void Test(string fn,int d) { Console.WriteLine("\n Tong cong " + d + " so"); Console.WriteLine(File.ReadAllText(fn)); } } // HGen } // SangTao1 Chú ý 1. Có thể giải bài toán trên bằng phương pháp vét cạn dùng ba vòng for như sau: for a := 0 to 9 do for b := 0 to 9 do for c := 0 to 9 do if a+b+c = h then write(f,a,b,c,#32); 2. Phương pháp vét cạn đòi hỏi 10*10*10 = 1000 lần duyệt trong khi với h = 10 chỉ có 63 số thoả mãn điều kiện của đầu bài. Dùng phương pháp sinh ta nhận được đúng 63 số cần tìm, không phải duyệt thừa số nào. Bài 2.10. Tệp các hoán vị
Sáng tạo trong Thuật toán và Lập trình Tập I 44 Với mỗi số n cho trước trong khoảng 1 9, ghi vào một tệp văn bản có tên cho trước toàn bộ các hoán vị của 1 n. Hoán vị được sắp xếp tăng theo thứ tự từ điển, thí dụ 21345 s[i]. 2.3. Đổi chỗ s[i] với s[j]. 2.4. Lật: Đảo lại trật tự của dãy s[i + 1 n] ta sẽ thu được hoán vị đứng sát sau hoán vị s. 3. Đặt trị true cho hàm Next. Next = true có nghĩa là tìm được hoán vị sát sau hoán vị s. Chú ý Khi khởi trị hoán vị đơn vị ta sử dụng phần tử s[0] = 0 làm lính canh. Nhờ vậy, khi duyệt ngược để tìm điểm gãy ta không phải kiểm tra giới hạn mảng. Thay vì viết i := n-1; while (i > 0) and (s[i] > s[i+1]) do i:= i-1; ta chỉ cần viết i := n-1; while (s[i] > s[i+1]) do i := i-1; Hàm Next được mô tả như sau: function Next(n: integer): Boolean; var i, j, t: integer; begin Next := false; i := n-1; while (s[i] > s[i+1]) do i:= i-1; if i = 0 then exit; { s[i] a[i] } while (s[j] < s[i]) do j := j-1; { Đổi chỗ s[i] , s[j] } t:= s[i]; s[i]:= s[j]; s[j]:= t; { Lật s[i+1 n] } i:= i+1; j:= n; while i < j do begin t:= s[i];s[i]:= s[j]; s[j]:= t; i:= i+1; j:= j-1;
Sáng tạo trong Thuật toán và Lập trình Tập I 45 end; Next:= true; end; Thí dụ, với n = 8, giả sử ta đã ghi được hoán vị s = 74286531, khi đó hoán vị sát sau s sẽ được xây dựng như sau:      S 7 4 2 8 6 5 3 1 Tìm điểm gãy: i = 3, vì s[3] s[3] 7 4 2 8 6 5 3 1 Đổi chỗ điểm gãy và điểm vượt: s[3]  s[7] 7 4 3 8 6 5 2 1 Lật đoạn s[4 8] 7 4 3 1 2 5 6 8 Quy trình hoạt động của hàm Next 74286531 74312568 (* Pascal *) program GenAllPer; {$B-} uses crt; const MN = 9; {max n} BL = #32; {dau cach} var s: array[0 MN] of integer; function Next(n: integer): Boolean; tự viết procedure Gen(n: integer); const fn = 'HoanVi.dat'; {ten tep ket qua} var d: longint; {dem so luong hoan vi} i: integer; f: text; {tep ket qua} begin if (n MN) then exit; assign(f,fn); rewrite(f); d := 0; {dem so hoan vi} {Sinh hoán vị đơn vị. Đặt lính canh s[0] = 0} for i := 0 to n do s[i]:= i; repeat d := d+1; {Ghi hoan vi thu d, s vao tep} for i:= 1 to n do write(f, s[i], BL); writeln(f); until not (next(n)); writeln(f,' Tong cong ',d, ' hoan vi'); close(f); end; BEGIN Gen(5); write('fini'); readln; END. // C# using System; using System.Collections.Generic; using System.Text;
Sáng tạo trong Thuật toán và Lập trình Tập I 46 using System.IO; namespace SangTao1 { class GenAllPer { static void Main(string[] args) { string fn = "HoanVi.txt"; int d = Gen(fn,5); Test(fn,d); // Xem kết quả Console.WriteLine("\n Fini "); Console.ReadLine(); } // Sinh các hoán vị, ghi file fn static public int Gen(string fn, int n) { if (n 9) return 0; int d = 0; // dem so hoan vi d = n! StreamWriter f = File.CreateText(fn); int[] a = new int[n + 1]; for (int i=0; i a[i+1]; i) ; if (i == 0) return false; for (j = n; a[j] < a[i]; j) ; t = a[i]; a[i] = a[j]; a[j] = t; for (++i, j = n; i < j; ++i, j) { t = a[i]; a[i] = a[j]; a[j] = t; } return true; } static public void Test(string fn, int d) { Console.WriteLine("\n Tong cong " + d + " so"); Console.WriteLine(File.ReadAllText(fn)); } } // GenAllPer } // SangTao1 Bài 2.11. Đọc dữ liệu từ tệp vào mảng biết hai kích thước Đọc dữ liệu kiểu nguyên từ một tệp văn bản vào một mảng hai chiều. Tệp có cấu trúc như sau: - Hai số đầu tiên n, m là kích thước của mảng gồm n dòng và m cột.
Sáng tạo trong Thuật toán và Lập trình Tập I 47 - Tiếp đến là các dữ liệu ghi liên tiếp nhau theo từng dòng của mảng. - Các số cách nhau ít nhất một dấu cách. Thí dụ: 2 3 -1 4 5 3 7 1 cho biết mảng có n = 2 dòng và m = 3 cột với dữ liệu như sau: -1 4 5 3 7 1 Đặc tả Ta viết hàm Doc cho giá trị true nếu đọc được dữ liệu. Chú ý rằng dữ liệu vào là đúng do đó không cần kiểm tra tính đúng đắn của chúng. Như vậy Doc sẽ cho giá trị false trong trường hợp không mở được file, do ghi sai đường dẫn hoặc file không được tạo lập từ trước. Chỉ thị {$I-} yêu cầu hệ thống chỉ ghi nhận chứ không bắt các lỗi vào/ra, tức là không dừng sự thực hiện chương trình. Biến hệ thống IORESULT sẽ ghi nhận số hiệu lỗi. Nếu IORESULT=0 thì thao tác vào ra không sinh lỗi, ngược lại, nếu IORESULT ≠ 0 tức là đã có lỗi. Chỉ thị {$I+} yêu cầu hệ thống bắt mọi lỗi vào/ra. Như vậy, dòng lệnh {$I-} reset(f); {$I+} sẽ được hiểu như sau: Thoạt tiên ta yêu cầu hệ thống bỏ chế độ bắt lỗi vào/ra {$I-}. Sau đó thực hiện lệnh mở tệp để đọc reset(f).Tiếp đến đặt lại chế độ bắt lỗi {$I+}. (* Pascal *) uses crt; const MN = 100; var a: array[1 MN,1 MN] of integer; m,n: integer; Function Doc(fn: string): Boolean; var f: text; i, j: integer; begin Doc := false; assign(f,fn); {$I-} reset(f); {$I+} if IORESULT <> 0 then exit; {không mở được file} read(f,n,m);{doc kich thuoc n va m cua mang } for i := 1 to n do for j:= 1 to m do read(f,a[i, j]); close(f); Doc := true; end; procedure Xem(n,m: integer); Hiển thị mảng 2 chiều, tự viết BEGIN if Doc('DATA.INP') then Xem(n,m) else write('Khong mo duoc tep '); readln;
Sáng tạo trong Thuật toán và Lập trình Tập I 48 END. // C# using System; using System.Collections.Generic; using System.Text; using System.IO; namespace sabgTao1 { class DocMang2Chieu { static void Main(string[] args) { string fn = "Data.inp"; int n = 0, m = 0; int [,] a = Doc(fn, ref n, ref m); if (a != null) { PrintInput(fn); Print(a, n, m); } else Console.WriteLine("\n " + " Khong mo duoc file " +fn); Console.WriteLine("\n Fini "); Console.ReadLine(); } static public int[,] Doc(string fn, ref int n, ref int m) { if (!File.Exists(fn)) return null; // Cac dau ngan char[] cc = new char[] { ' ', '\n', '\t', '\r' }; // Mo tep ten fn doc, tỏch, dong tep string[] ss = (File.ReadAllText(fn)). Split(cc, StringSplitOptions.RemoveEmptyEntries); // Chuyển sang mảng 1 chiều int [] c int [] c = Array.ConvertAll(ss, new Converter (int.Parse)); n = c[0]; m = c[1]; int[,] a = new int[n, m]; int k = 2; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) a[i,j] = c[k++]; return a; } static void Print(int[,] a, int n, int m) Hiển thị mảng 2 chiều a, tự viết
Sáng tạo trong Thuật toán và Lập trình Tập I 49 static public void PrintInput(string fn) Đọc lại file fn, tự viết } // DocMang2Chieu } // sangTao1 Giải thích Trong các máy tính hiện đại, bộ nhớ trong RAM đủ lớn để có thể chứa toàn bộ dữ liệu trong hầu hết các file input vì thế với môi trường C# .NET bạn nên đọc một lần dữ liệu từ các file này. Hàm Doc cho ra mảng nguyên hai chiều. Nếu file không tồn tại, hàm cho ra giá trị null. Bạn cần chuẩn bị trước file input với tên Data.inp và ghi vào thư mục BIN\DEBUG trong Project hiện hành. Nếu ghi file vào thư mục khác thì trong tham biến fn phải ghi chi tiết đường dẫn, thí dụ “D:\\MyDIR\\Data.inp”. Khi viết đường dẫn, thay vì viết dấu “\” ta phải viết hai dấu đó, tức là “\\” vì bản thân dấu “\” trong đóng vai trò báo hiệu kí tự đứng sát sau nó là kí tự điều khiển, thí dụ, “\n” biểu thị dấu xuống dòng. Bạn cũng có thể viết dấu đổi mức @ cạnh đường dẫn để chỉ thị rằng bạn muốn dùng một dấu “\” thay vì hai dấu, thí dụ, @“D:\MyDIR\Data.inp” Lệnh File.ReadAllText(fn) mở file với đường dẫn fn đọc toàn bộ dữ liệu một lần vào một biến string sau đó tự động đóng file. Lệnh Split(cc,StringSplitOptions.RemoveEmptyEntries) tách các đơn vị trong biến string để ghi vào biến string[] ss đồng thời bỏ đi các dấu trắng mô tả trong biến cc, bao gồm dấu cách „ „, dấu xuống dòng „\n‟, dấu tab „\t‟ và dấu kết RETURN „\r‟, cuối cùng loại bỏ các đơn vị rỗng, tức là các string không chứa kí tự nào (Length = 0). Lệnh int[] c = Array.ConvertAll(ss, New Converter (int.Parse)); chuyển các string trong ss sang dạng số nguyên và ghi vào mảng nguyên (một chiều) c. Đến đây toàn bộ dữ liệu trong file input fn đã được đọc và ghi vào mảng nguyên c. Các mảng trong C# được đánh chỉ dẫn từ 0 đến Length-1. Theo điều kiện của đầu bài c[0] chứa giá trị n, c[1] chứa giá trị m, từ c[2] trở đi chứa lần lượt các giá trị trên các dòng của mảng hai chiều. Bài 2.12. Đọc dữ liệu từ tệp vào mảng biết một kích thước Đọc dữ liệu kiểu nguyên từ một tệp văn bản vào một mảng hai chiều a[n,m] cho biết một kích thước m (số cột). Tệp có cấu trúc như sau: - Số đầu tiên ghi số lượng cột m của mảng tức là số phần tử trên một dòng. - Tiếp đến là các dữ liệu ghi liên tiếp nhau theo từng dòng của mảng. - Các số cách nhau ít nhất một dấu cách. Thí dụ: 3 -1 4 5 3 7 1 sẽ được bố trí vào mảng n = 3 dòng, m = 3 cột như sau: -1 4 5 3 7 1 Thuật toán
Sáng tạo trong Thuật toán và Lập trình Tập I 50 1. Mở tệp. 2. Đọc giá trị đầu tiên vào biến m: số lượng cột của ma trận. 3. Mỗi lần đọc xong một dòng ta tăng con đếm dòng (n) thêm 1. Chú ý Do có thể gặp dòng trống nên ta cần sử dụng hàm SeekEof. Hàm SeekEof duyệt tiếp từ vị trí hiện thời của con trỏ tệp, bỏ qua các dấu trắng (gồm dấu cách, dấu kết thúc dòng, dấu đầu dòng, dấu nhảy TAB), nếu gặp dấu hết tệp thì cho giá trị true, ngược lại, nếu sau khi đã bỏ qua các dấu trắng mà chưa gặp dấu hết tệp thì cho giá trị false. (* Pascal *) uses crt; const MN = 100; var a: array[1 MN,1 MN] of integer; m,n: integer; Function Doc(fn: string): Boolean; var f: text; j: integer; begin Doc := FALSE; assign(f,fn); {$I-} reset(f); {$I+} if IORESULT <> 0 then exit; read(f,m); {m: so luong cot} n := 0; {n: so luong dong} while NOT SeekEof(f) do begin inc(n); for j := 1 to m do read(f,a[n,j]); end; close(f); Doc := TRUE; end; procedure Xem(n,m: integer); tự viết BEGIN if Doc('DATA.INP') then Xem(n,m) else write('Khong mo duoc tep '); readln; END. Chú ý Cần chuẩn bị trước dữ liệu và ghi trong tệp văn bản DATA.INP, thí dụ: DATA.INP 3 -1 4 5 3 7 1 // C# using System; using System.Collections.Generic; using System.Text; using System.IO;
Sáng tạo trong Thuật toán và Lập trình Tập I 51 namespace SangTao1 { class DocMang2 { static void Main(string[] args) { string fn = "Data.inp"; int n = 0, m = 0; int [,] a = Doc(fn, ref n, ref m); if (a != null) { PrintInput(fn); Print(a, n, m); } else Console.WriteLine("\n " + " Khong mo duoc file " + fn); Console.WriteLine("\n Fini "); Console.ReadLine(); } static public int[,] Doc(string fn, ref int n, ref int m) { if (!File.Exists(fn)) return null; int [] c = Array.ConvertAll( File.ReadAllText(fn). Split(new char[] {' ','\n','\t','\r'}, StringSplitOptions.RemoveEmptyEntries), new Converter (int.Parse)); int k = 0; m = c[k++]; n = (c.Length-1)/m; int[,] a = new int[n, m]; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) a[i,j] = c[k++]; return a; } static void Print(int [,] a, int n, int m) Hiển thị mảng 2 chiều a[n,m], tự viết static public void PrintInput(string fn) Hiển thị file fn; tự viết } // DocMang2 } // SangTao1 Giải thích Biết số cột của mảng là m ta có thể tính ra số dòng n của mảng theo công thức n = (c.Length-1) / m, trong đó c.Length chứa số lượng các giá trị đã đọc từ file input, bao gồm giá trị m và n.m giá trị của mảng, tức là c.Length = n.m+1. Bài 2.13. Đọc dữ liệu từ tệp vào mảng đối xứng
Sáng tạo trong Thuật toán và Lập trình Tập I 52 Đọc dữ liệu kiểu nguyên từ một tệp văn bản có tên fn vào một mảng hai chiều đối xứng. Tệp có cấu trúc như sau: - Số đầu tiên ghi số lượng cột (và đồng thời là số lượng dòng) của mảng. - Tiếp đến là các dữ liệu ghi liên tiếp nhau theo nửa tam giác trên tính từ đường chéo chính. - Các số cùng dòng cách nhau ít nhất một dấu cách. Thí dụ: 3 1 2 3 4 6 8 sẽ được bố trí vào mảng 3 3 như sau: 1 2 3 2 4 6 3 6 8 Thuật toán 1. Mở tệp. 2. Đọc giá trị đầu tiên vào biến n: số lượng cột và dòng của ma trận vuông đối xứng. 3. Với mỗi dòng i ta đọc phần tử trên đường chéo chính của dòng đó a[i, i], sau đó ta đọc các phần tử nằm ở bên phải a[i, i], tức là a[i, j] với j = i + 1 n rồi lấy đối xứng bằng phép gán a[j, i]:= a[i, j]. (* Pascal *) uses crt; const MN = 100; var a: array[1 MN,1 MN] of integer; n: integer; { kich thuoc mang } Function Doc(fn: string): Boolean; var f: text; i, j: integer; begin Doc := FALSE; assign(f,fn); {$I-} reset(f); {$I+} if IORESULT <> 0 then exit; read(f,n); for i := 1 to n do begin read(f,a[i,i]); for j := i+1 to n do begin read(f,a[i,j]); a[j,i]:= a[i,j]; end; end; close(f); Doc:= TRUE; end; procedure Xem(n,m: integer); tự viết BEGIN if Doc('DATA.INP') then Xem(n,n) else write('Khong mo duoc tep '); readln; END. // C#
Sáng tạo trong Thuật toán và Lập trình Tập I 53 using System; using System.Collections.Generic; using System.Text; using System.IO; namespace SangTao1 { class MangDoiXung { static void Main(string[] args) { string fn = "Data.inp"; int n = 0; int [,] a = Doc(fn, ref n); if (a != null) { PrintInput(fn); Print(a, n); } else Console.WriteLine("\n " + " Khong mo duoc file "+fn); Console.WriteLine("\n Fini "); Console.ReadLine(); } static public int[,] Doc(string fn, ref int n) { if (!File.Exists(fn)) return null; int [] c = Array.ConvertAll( File.ReadAllText(fn). Split(new char[] {' ','\n','\t','\r'}, StringSplitOptions.RemoveEmptyEntries), new Converter (int.Parse)); int k = 0; n = c[k++]; int[,] a = new int[n, n]; for (int i = 0; i < n; ++i) for (int j = i; j < n; ++j) a[i,j] = a[j,i] = c[k++]; return a; } static void 1 1 1 1 0 0 1 1 1 Print(int [,] a, int n) 0 0 0 0 0 0 1 1 1 Hiển thị mảng 2 chiều a[n,n], tự viết static public void PrintInput(string fn) Hiển thị file fn, tự viết } // MangDoiXung } // SangTao1 Bài 2.14. Đếm tàu
Sáng tạo trong Thuật toán và Lập trình Tập I 54 Một tệp văn bản có tên fn có ghi sơ đồ 1 1 0 0 0 0 0 0 0 một vùng biển hình chữ nhật chiều ngang 1 1 0 0 1 1 0 0 1 250 kí tự, chiều dọc (số dòng) không hạn chế. Trên biển có các con tàu hình chữ 5 tàu nhật chứa các kí tự 1, vùng nước được biểu thị qua các kí tự 0. Biết rằng các con tàu không dính nhau. Hãy đếm số lượng tàu. Ví dụ, hình bên có 5 tàu. Thuật toán Vì các tàu không dính nhau nên ta phân biệt các tàu qua mũi tàu, tức là góc A - góc Tây-Bắc của tàu. Ta có, số lượng tàu = số lượng mũi tàu Mũi tàu là điểm nhận giá trị 1 và nếu bước một bước sang trái hoặc lên trên sẽ lên bờ hoặc rơi xuống biển. Sau khi mở tệp ta đọc và xử lí từng dòng văn bản y và so sánh nó với dòng x đã xử lí trước đó. Nếu y là dòng đầu tiên, tức là dòng nằm sát bờ Bắc, ta khởi trị cho x với 250 ks tự 0 tức là ta loại trừ trường hợp bước lên bờ Bắc. Khi xử lí y, ta chú ý tách riêng trường hợp tàu nằm sát bờ Tây, tức là xét riêng y[1]. Sau mỗi lần xử lí dòng y ta copy dòng y sang x và luôn giữ cho x có chiều dài tối đa 250 kí tự như yêu cầu của đầu bài. (* Pascal *) program Ships; A 0 0 0 0 0 B {$B-} 0 1 1 1 1 1 uses crt; const MN = 250; 0 1 1 1 1 1 boong = '1'; nuoc = '0'; D 0 0 0 0 0 C Function Dem(fn: string): integer; var Con tàu ABCD f: text; d,i: integer; x,y: string;{x:dong tren, y:dong duoi } begin Dem := 0; assign(f,fn); {$I-} reset(f); {$I+} if IORESULT <> 0 then exit; x := nuoc; for i := 1 to 8 do x:= x+x; {x = ‟00 0‟} d := 0; while NOT EOF(f) do begin readln(f,y); if (y[1]=boong)AND(x[1]=nuoc) then d:=d+1; for i:=2 to length(y) do if (y[i]= boong) AND (y[i-1]= nuoc) AND (x[i]= nuoc) then d:=d+1;
Sáng tạo trong Thuật toán và Lập trình Tập I 55 x := y; end; Dem := d; end; BEGIN n:= Dem('TAU.INP'); if n=0 then write('Khong mo duoc tep/khong co tau') else write('Tong so tau: ',n); readln; END. // C# using System; using System.Collections.Generic; using System.Text; using System.IO; namespace SangTao1 { class Ships { static public string fn = "Tau.inp"; static public string gn = "Tau.out"; static public char boong = '1'; static public char nuoc = '0'; static void Main(string[] args) { Save(Count()); Test(); Console.WriteLine("\n Fini "); Console.ReadLine(); } static public int Count()// dem tau { StreamReader f = File.OpenText(fn); string x = new string(nuoc,251); string y; string empty = ""; int d = 0; while ((y=(f.ReadLine()).Trim()) != empty) { d += Scan(x, y); x = y; } f.Close(); return d; } // Sánh dòng tren x với dòng dưới y static public int Scan(string x, string y) { int d = 0; if ((y[0]==boong)&&(x[0]==nuoc)) ++d; for (int i = 1; i < y.Length; ++i)
Sáng tạo trong Thuật toán và Lập trình Tập I 56 if ((y[i]==boong)&&(y[i-1]==nuoc) && (x[i]==nuoc)) ++d; return d; } static public void Save(int d) // ghi file { File.WriteAllText(gn, d.ToString()); } static public void Test() { Console.WriteLine("\n" + File.ReadAllText(fn) + "\n"); Console.WriteLine("\n" + File.ReadAllText(gn) + "\n"); } } // Ships } // SangTao1 Bài 2.15. Sắp đoạn Trong một tệp văn bản chứa những đoạn cắt ra từ một trục số. Mỗi đoạn có dạng trong đó " có thể là một trong hai kí tự ) hoặc], d và c là các biểu thức dạng x hoặc x + y hoặc x*y với x và y là những số tự nhiên. Ta luôn có d c. Chiều dài của đoạn là hiệu c - d. Hãy sắp xếp các đoạn tăng theo chiều dài và ghi chúng vào một tệp văn bản theo đúng dạng thức đọc được của mỗi đoạn. Có thể thêm, bớt một số dấu cách trong và ngoài các đoạn. Trên mỗi dòng của tệp luôn luôn chứa trọn một số đoạn. Thí dụ cho dữ liệu vào trong file input “Doan.inp” là: [2+1,7) (4,4*3) (5,6] Sau khi sắp ta được kết quả sau trong file output “Doan.out”: (5,6] [2+1,7) (4,4*3) Thuật toán Ta mô tả cấu trúc của mỗi đoạn như sau: mo so1[toan1 so2] , so3[toan2 so4] trong đó:  mo là một trong hai dấu mở ngoặc: ( hoặc [.  so1, so2, so3 và so4 là các số tự nhiên xuất hiện trong thành phần của đoạn.  toan1 và toan2 là dấu các phép toán (+, *), nếu có trong thành phần của đoạn.  dong là một trong hai dấu đóng ngoặc: ) hoặc]. Trong mô tả trên, chúng ta sử dụng kí pháp [*] để chỉ ra thành phần * có thể bỏ qua. Nếu thành phần thứ i (i = 1 2) của đoạn không có dấu phép toán, thì cũng không có toán hạng thứ hai, tức là thành phần đó có dạng là một số tự nhiên thì ta đặt toan[i] = BL (dấu cách). Nếu số thứ i không xuất hiện trong đoạn, ta đặt so[i] = 0. Thí dụ: Đoạn mo so1 Toan1 so2 so3 Toan2 so4 dong
Sáng tạo trong Thuật toán và Lập trình Tập I 57 [2+10,7*6) [ 2 + 10 7 * 6 ) [2+10,7) [ 2 + 10 7 BL 0 ) (2,7+5] ( 2 BL 0 7 + 5 ] Ngoài ra ta thêm một thành phần len để xác định chiều dài của đoạn. len của mỗi đoạn được tính theo công thức sau len = TriCuoi-TriDau TriCuoi = so3 Toan2 so4, nếu Toan2 là dấu '+' hoặc ' ' và TriCuoi = so3, nếu Toan2 = BL. Tương tự, TriDau = so1 Toan1 so2, nếu Toan1 là dấu '+' hoặc ' ' và TriDau = so1, nếu Toan1 = BL. Ta sử dụng cấu trúc bản ghi để biểu diễn dữ liệu cho mỗi đoạn: type MangSo = array[1 4] of integer; {4 toan hang} MangToan = array[1 2] of char; {2 toan tu +,*} KieuDoan = record mo: char; dong: char; so: MangSo; Toan: MangToan; len: integer; end; Các đoạn đọc được sẽ được ghi dần vào mảng a với biến đếm số phần tử n: type MangDoan = array[0 1000] of KieuDoan; var a: MangDoan; n: integer; Khi đó thủ tục tính chiều dài len của mỗi đoạn sẽ được cài đặt như sau: procedure LenSeg(i: integer); var dau, cuoi: integer; begin with a[i] do begin dau := so[1]; if Toan[1]='+' then dau := dau+so[2] else if Toan[1]='*' then dau:=dau*so[2]; cuoi:=so[3]; if Toan[2]='+' then cuoi:=cuoi+so[2] else if Toan[2]='*' then cuoi:=cuoi*so[2]; end; len := cuoi-dau; end; Cấu trúc with x do T cho phép ta thực hiện thao tác T trên các thành phần của bản ghi x mà không phải viết lại phần tiếp đầu x. Để đọc các đoạn từ tệp ta sử dụng một máy trạng thái như sau. Hãy tưởng tượng mắt bạn bị bịt kín, do đó bạn phải dùng tay để nhận biết từng kí tự trong tệp văn bản.
Sáng tạo trong Thuật toán và Lập trình Tập I 58 Mỗi lần bạn sờ một kí tự c nào đó rồi dựa vào kí tự đó bạn xác định các thủ tục cần thực hiện để nhận biết từng đối tượng. Muốn vậy ta sử dụng một biến gọi là biến trạng thái q với mục đích ghi nhận các tình huống đã gặp và trên cơ sở đó xác định các thao tác cần thiết. Gọi q là biến trạng thái. Trong quá trình đọc và xử lí tệp input ta có thể gặp năm trạng thái như sau: q = 0: Trạng thái dò tìm đầu đoạn: Nếu gặp kí tự mở đầu một đoạn, cụ thể là nếu gặp kí tự c = '(' hoặc c = '[' thì cần tạo một đoạn mới như sau: - Tăng chỉ dẫn ghi nhận đoạn mới: n := n + 1; - Ghi nhận kí tự mở đầu đoạn: a[n].mo:= c; - Khởi trị mảng số: a[n].so := (0, 0, 0, 0); - Khởi trị mảng dấu các phép toán: a[n].Toan:= (BL, BL); - Chuyển qua trạng thái q := 1 là trạng thái tìm đọc so[1]. 0: if c in['(','['] then begin n:=n+1; a[n].mo:=c; a[n].so:=KhoiTriSo; a[n].Toan:=KhoiTriToan; q:= 1; end; Các biến KhoiTriSo và KhoiTriToan được khai báo và gán trị khởi đầu như sau: const KhoiTriSo: MangSo = (0,0,0,0); KhoiTriToan: MangToan = (BL,BL); q = 1: Trạng thái tìm đọc số thứ nhất, so[1]: Ở trạng thái này, nếu gặp chữ số thì ta ghép thêm chữ số đó vào so[1], nếu gặp dấu phép toán thì ta hiểu là thành phần thứ nhất của đoạn là một biểu thức dạng: so[1] Toan[1] so[2] Ta ghi nhận dấu phép toán vào trường Toan[1] và chuyển qua trạng thái q = 2 để đọc số thứ hai. Nếu gặp dấu phẩy (,) là dấu ngăn giữa hai thành phần của đoạn ta chuyển qua trạng thái q = 3 để đọc số đầu tiên của thành phần thứ hai, tức là đọc so[3]. 1: if c in ChuSo then DocSo(n,1) else if c in PhepToan then begin a[n].Toan[1]:=c; q:=2; end else if c=',' then q:=3; Thủ tục DocSo(i,j) nhận thêm 1 chữ số để ghép vào biến a[i].so[j]. q = 2: Đọc số thứ hai, so[2]: Ở trạng thái này, nếu gặp chữ số thì ta ghép thêm chữ số đó vào so[2], nếu gặp dấu phẩy là dấu ngăn giữa hai thành phần của đoạn ta chuyển qua trạng thái q = 3 để đọc số đầu tiên của thành phần thứ hai, tức là đọc so[3]. 2: if c in ChuSo then DocSo(n,2) else if c =',' then q:=3; q = 3: Đọc số thứ ba, so[3]: Ở trạng thái này, nếu gặp chữ số thì ta ghép thêm chữ số đó vào so[3], nếu gặp dấu phép toán thì ta hiểu là thành phần thứ hai của đoạn là một biểu thức dạng:
Sáng tạo trong Thuật toán và Lập trình Tập I 59 so[3] Toan[2] so[4] Ta ghi nhận dấu phép toán vào trường Toan[2] và chuyển qua trạng thái q = 4 để đọc số thứ tư, so[4], nếu gặp kí tự c = ')' hoặc c = ']' thì ta hiểu là đã kết thúc một đoạn, ta gọi thủ tục KetDoan để thực hiện các thao tác sau: - Ghi nhận kí tự đóng đoạn: a[n].dong:= c. - Tính chiều dài của đoạn: LenSeg(n); - Chuyển qua trạng thái q = 0 để tiếp tục với đoạn tiếp theo, nếu còn. procedure KetDoan; begin a[n].dong:=c; LenSeg(n); q:=0; end; Đoạn chương trình thể hiện trạng thái q = 3 khi đó sẽ như sau: 3: if c in ChuSo then DocSo(n,3) else if c in PhepToan then begin a[n].Toan[2]:=c; q:=4 end else if c in[')',']'] then KetDoan; q = 4: Đọc số thứ tƣ, so[4]: Ở trạng thái này, nếu gặp chữ số thì ta ghép thêm chữ số đó vào so[4], nếu gặp kí tự c = ')' hoặc c = ']' thì ta hiểu là đã kết thúc một đoạn, ta gọi thủ tục KetDoan. 4: if c in ChuSo then DocSo(n,4) else if c in[')',']'] then KetDoan; Đọc tệp xong ta dùng thủ tục qsort sắp các đoạn tăng dần theo chiều dài. Sau khi sắp ta ghi các đoạn vào tệp gn theo các trường. (* Pascal *) {$B-} program Segments; uses crt; const fn = 'DOAN.INP'; {Tep input} gn = 'DOAN.OUT';{Tep output} MN = 1000; {So luong toi da cac doan} BL = #32;{Dau cach} ChuSo = ['0' '9']; PhepToan = ['+','*']; type MangSo = array[1 4] of integer; MangToan = array[1 2] of char; KieuDoan = record mo: char; {dau mo ngoac} dong: char; {dau dong ngoac} so: MangSo; {4 so trong doan} Toan: MangToan; {2 phep toan} len: integer; {chieu dai doan}
Sáng tạo trong Thuật toán và Lập trình Tập I 60 end; MangDoan = array[0 MN] of KieuDoan; const KhoiTriSo: MangSo = (0,0,0,0); KhoiTriToan: MangToan = (BL,BL); var f,g:text; a: MangDoan; c: char;{ky tu dang xet} n: integer;{chi so doan dang xet} q: integer;{bien trang thai} (* Cac trang thai q = 0: do tim dau doan 1: doc so[1] 2: doc so[2] 3: doc so[3] 4: doc so[4] *) procedure LenSeg(i: integer); tự viết procedure KetDoan; tự viết (* Them 1 chu so vao so thu j cua doan i *) procedure DocSo(i,j: integer); begin a[i].so[j]:=a[i].so[j]*10+(ord(c)-ord('0')) end; (* Doc cac doan *) procedure doc; begin assign(f,fn); reset(f); q:=0; n:=0; while not eof(f) do begin read(f,c); case q of 0: if c in['(','['] then begin n:=n+1; a[n].mo:=c; a[n].so:=KhoiTriSo; a[n].Toan:=KhoiTriToan; q:=1; end;
Sáng tạo trong Thuật toán và Lập trình Tập I 61 1: if c in ChuSo then DocSo(n,1) else if c in PhepToan then begin a[n].Toan[1]:=c; q:=2 end else if c=',' then q:=3; 2: if c in ChuSo then DocSo(n,2) else if c =',' then q:=3; 3: if c in ChuSo then DocSo(n,3) else if c in PhepToan then begin a[n].Toan[2]:=c; q:=4; end else if c in[')',']'] then KetDoan; 4: if c in ChuSo then DocSo(n,4) else if c in [')',']'] then KetDoan; end; { case } end; { while } close(f); end; procedure qsort(d,c:integer); var i,j,m: integer; x: KieuDoan; begin i:=d; j:=c; m:=a[(i+j) div 2].len; while i m do j:=j-1; if i BL then write(g,mo, so[1],Toan[1],so[2])
Sáng tạo trong Thuật toán và Lập trình Tập I 62 else write(g,mo, so[1]); if Toan[2]<>BL then write(g,',',so[3],Toan[2],so[4],dong,BL) else write(g,',',so[3],dong,BL); { moi dong viet 10 doan } if i mod 10 = 0 then writeln(g); end; close(g); end; BEGIN Doc; qsort(1,n); Ghi; END. // C# using System; using System.IO; using System.Collections; namespace SangTao1 { class SapDoan { static public string fn = "Doan.inp"; static public string gn = "Doan.out"; static public string s; // du lieu vao static public Doan[] d = new Doan[5000]; // cac doan static public int n = 0; // so luong doan static public char Ket = '#'; static void Main(string[] args) { s = File.ReadAllText(fn) + Ket.ToString(); Console.WriteLine("\n Du lieu " + "truoc khi xu li:\n " + s); n = DocDoan(); Console.WriteLine("\n Tong cong " + n + " Doan"); Console.WriteLine(n); Printd(); QSort(d, 0, n-1); Console.WriteLine("\n Da sap: "); Printd(); Ghi(); XemLai(); Console.WriteLine("\n Fini "); Console.ReadLine(); } static public void XemLai() { Console.WriteLine("\n Kiem tra lai:\n"); Console.WriteLine("\n Input:\n" + File.ReadAllText(fn)); Console.WriteLine("\n Output:\n" + File.ReadAllText(gn)); } static public int DocDoan() {
Sáng tạo trong Thuật toán và Lập trình Tập I 63 int n = -1; int q = 0; // trang thai int i = 0; // bien tro trong s int dau, cuoi; for (; s[i] != Ket; ++i) { switch(q) { case 0: // Tim dau doan if (GapMo(s[i])) { ++n; d[n] = new Doan(); d[n].Mo = s[i]; q = 1; } break; case 1: // Doc so1 if (GapSo(s[i])) d[n].So1 = DocSo(ref i); else if (GapToan(s[i])) {d[n].Toan1 = s[i]; q = 2;} else if (s[i]==',') q = 3; break; case 2: // Doc so2 if (GapSo(s[i])) d[n].So2 = DocSo(ref i); else if (s[i]==',') q = 3; break; case 3: // Doc so3 if (GapSo(s[i])) d[n].So3 = DocSo(ref i); else if (GapToan(s[i])) { d[n].Toan2 = s[i]; q = 4; } else if (GapDong(s[i])) q = 5; break; case 4: // Doc so4 if (GapSo(s[i])) d[n].So4 = DocSo(ref i); else if (GapDong(s[i])) q = 5; break; case 5: // Xong 1 doan d[n].Dong = s[ i]; dau = d[n].So1; if (d[n].Toan1 == '+') dau += d[n].So2; else if (d[n].Toan1 == '*') dau *= d[n].So2; cuoi = d[n].So3; if (d[n].Toan2 == '+') cuoi += d[n].So4;
Sáng tạo trong Thuật toán và Lập trình Tập I 64 else if (d[n].Toan2 == '*') cuoi *= d[n].So4; d[n].Len = cuoi-dau; Console.Write("\n Doan "+ n + ". "); d[n].Print(); q = 0; break; } } // endfor return (++n); } static public bool GapSo(char c) { return (c >= '0' && c m) j; if (i <= j) { t = d[i]; d[i] = d[j]; d[j] = t; ++i; j; } } if (s < j) QSort(d,s,i); if (i < e) QSort(d,i,e); } } // SapDoan
Sáng tạo trong Thuật toán và Lập trình Tập I 65 public class Doan { public char Mo; public char Dong; public int So1; public int So2; public int So3; public int So4; public char Toan1; public char Toan2; public int Len; public Doan() { Mo = ' '; So1 = So2 = So3 = So4 = 0; Toan1 = Toan2 = '#'; Len = 0; } public void FWrite(StreamWriter g) { g.Write(Mo.ToString()); if (Toan1 != '#') g.Write(So1 + Toan1.ToString() + So2); else g.Write(So1); g.Write(","); if (Toan2 != '#') g.Write(So3 + Toan2.ToString() + So4); else g.Write(So3); g.WriteLine(Dong.ToString()); } public void Print() { Console.Write(Mo.ToString()); if(Toan1!='#') Console.Write(So1+Toan1.ToString()+So2); else Console.Write(So1); Console.Write(","); if(Toan2!='#') Console.Write(So3+Toan2.ToString()+So4); else Console.Write(So3); Console.WriteLine(Dong.ToString()+ " Len = "+Len); } // Print } // Doan } // SangTao1
Sáng tạo trong Thuật toán và Lập trình Tập I 66 CHƢƠNG 3 BÀN PHÍM VÀ MÀN HÌNH Bài 3.1. Bảng mã ASCII Sinh tệp có tên ASCII.DAT chứa mã ASCII để tiện dùng. Chú ý ASCII (đọc là a-ski) là bộ mã chuẩn dùng trong trao đổi thông tin của Mĩ và đầu tiên được cài đặt trong các máy tính sử dụng hệ điều hành MS-DOS. Trong bảng mã này, mỗi kí tự có một mã số riêng biệt chiếm 1 byte. Trong TP Ta viết 65 là để biểu thị mã số 65, viết #65 là để biểu thị kí tự có mã số 65, tức là chữ 'A'. Các kí tự mang mã số từ 0 đến 31 là các kí tự điều khiển, thí dụ, kí tự #13 điều khiển con trỏ văn bản xuống dòng mới, kí tự #10 điều khiển con trỏ văn bản về đầu dòng. Như vậy, xâu kí tự #13#10 sẽ điều khiển con trỏ về đầu dòng mới và do đó lệnh write(#13#10) sẽ tương đương với lệnh writeln. Lệnh writeln(#13#10) sẽ tương đương với hai lệnh writeln; writeln. Chương trình dưới đây ghi vào tệp văn bản có tên ASCII.DAT các kí tự và mã của chúng. Tất cả có 256 kí tự chia làm hai phần. 128 kí tự đầu tiên mã số từ 0 đến 127 là các kí tự cơ sở, 128 kí tự còn lại, mã số từ 128 đến 255 là các kí tự mở rộng. Sau khi thực hiện chương trình, bạn có thể mở tệp ASCII.DAT để xem từng kí tự và mã của chúng. Lưu ý rằng có kí tự hiển thị được và có kí tự không hiển thị được trên màn hình, chẳng hạn như các kí tự điều khiển. (* Pascal *) program ASCII; uses crt; procedure ASCII; var f: text; i: byte; begin assign(f,'ASCII.DAT'); rewrite(f); for i := 0 to 255 do
Sáng tạo trong Thuật toán và Lập trình Tập I 67 begin write(f,chr(i), ': ',i:3,' '); if i mod 5 = 0 then writeln(f); end; close(f); writeln('OK'); readln; end; BEGIN ASCII; END. // C# Chương trình dưới đây lưu lại mã của 128 kí tự đầu tiên ứng với phần cơ sở của bảng mã ASCII. Các kí tự phần mở rộng phụ thuộc vào từng phiên bản cài đặt của các hệ điều hành. using System; using System.IO; namespace SangTao1 { class ASCII { static void Main() { string fn = "ASCII.TXT"; StreamWriter g = File.CreateText(fn); for (int i = 0; i < 128; ++i) g.WriteLine("{0}: {1}", i, (char)i); g.Close(); Console.WriteLine(File. ReadAllText(fn)); // Doc lai Console.ReadLine(); } } // class } // space Bài 3.2. Bộ Tú lơ khơ Lập chương trình hiển thị trên màn hình các quân bài Tú lơ khơ gồm Rô, Cơ, Pích, Nhép theo quy định quân A mang mã số 1 và có 1 hình đơn vị, các quân mã số i từ 2 đến 10 có i hình đơn vị, các quân J, Q và K lần lượt có 11, 12 và 13 hình đơn vị tương ứng. Hình đơn vị gồm bốn loại kí tự có mã ASCII tương ứng như sau:  (Rô) : #4,  (Cơ) : #3,  (Pích): #6, . (Nhép): #5. 8 A Q . .   . .     . .     . .    . .  
Sáng tạo trong Thuật toán và Lập trình Tập I 68 8 A Q Ba quân bài Tú lơ khơ Gợi ý Trước hết ta cần thống nhất một số quy định sau:  Quân bài được vẽ bằng một màu M tùy chọn.  Nếu là quân Rô hoặc Cơ ta đặt màu chữ là đỏ (RED), với các quân Pích và Nhép ta đặt màu chữ là đen (BLACK).  Mỗi quân bài có hai thuộc tính là loại (Rô, Cơ, Pích hoặc Nhép) và mã số. Mã số của quân A là 1, J là 11, Q là 12 và K là 13. Các quân còn lại mang mã số từ 2 đến 10 ứng với số ghi trên quân bài đó.  Trên nền các quân bài J, Q và K không vẽ hình người mà vẽ số lượng hình đơn vị (Rô, Cơ, Pích hoặc Nhép) tương ứng với mã số của quân đó. Để bố trí số lượng hình đơn vị trên mỗi quân bài cho cân đối ta cần 5 dòng. Thủ tục Dong(q:char;s:string;x,y:byte) vẽ 5 dòng chứa hình đơn vị loại q, bắt đầu tính từ toạ độ (x, y) ứng với vị trí góc trên trái của quân bài trên màn hình, theo dấu hiệu ghi trong xâu mẫu s. Thí dụ, lời gọi với xâu mẫu s = '20302' sẽ vẽ 5 dòng thể hiện cho quân mang mã số 7 thuộc loại v (Rô, Cơ, Pích hoặc Nhép) như sau: 1. Dòng thứ nhất có 2 kí tự v. 2. Dòng thứ hai có 0 kí tự v tức là để trống. 3. Dòng thứ ba có 3 kí tự v. 4. Dòng thứ tư có 0 kí tự v tức là để trống. 5. Dòng thứ năm có 2 kí tự v. Vì trong xâu mẫu s tổng cộng có 2 + 3 + 2 = 7 kí tự v nên quân bài mang mã số 7. procedure Dong(v: char;s: string;x,y: byte); var i: byte; begin x := x+3; y := y+TY; for i := 1 to 5 do begin gotoxy(x,y); case s[i] of '1': write(BL,BL,v,BL,BL); '2': write(v,BL,BL,BL,v); '3': write(v,BL,v,BL,v); end; y := y+TY; end; end; Các mẫu dòng s được tính toán trước và khởi trị như sau: MauDong: array[1 13] of string[5] = ('00100', '01010', '10101', '20002', '20102', '20202', '20302', '21212', '30303', '22222', '22322', '23232', '23332'); Ta dễ dàng nhận ra có tất cả 13 mẫu dòng ứng với 13 mã số 1(A), 2, , 10, 11(J), 12(Q) và 13(K). Tóm lại mẫu dòng thứ i cho ta phương thức vẽ i hình đơn vị trên quân bài mang mã số i. Mỗi mẫu dòng được biểu diễn qua một xâu 5 kí tự.
Sáng tạo trong Thuật toán và Lập trình Tập I 69 Các thủ tục điều khiển màn hình có ý nghĩa như sau: gotoxy(x,y): Chuyển con trỏ màn hình đến cột x dòng y. TextColor(c): Đặt màu c cho nét chữ. Thí dụ, kể từ sau khi gặp lệnh TextColor(BLACK) các kí tự xuất hiện trên màn hình sẽ có nét màu đen, TextBackGround(m): Đặt màu m cho nền chữ. Thí dụ, kể từ sau khi gặp lệnh TextBackGround(WHITE) các kí tự sẽ được viết trên nền trắng. textattr: Biến hệ thống có giá trị 1 byte, tính từ phải qua trái, 4 bit đầu tiên (gọi là các bit thấp) tạo thành một số nguyên thể hiện màu cho nét chữ, 4 bit tiếp theo (gọi là các bit cao) thể hiện màu cho nền chữ. Thí dụ phép gán textattr:=7 sẽ được nhận giá trị nhị phân là (0000)(0111) và do đó hệ thống sẽ đặt màu nét chữ là 7 (màu trắng) và màu nền chữ là 0 (màu đen). Như vậy phép gán trên tương đương với tổ hợp của hai lệnh TextColor và TextBackGround. Lệnh write(a:m) hiển thị đơn vị dữ liệu a với độ rộng m vị trí. Nếu chiều dài dữ liệu của a nhỏ hơn m thì hệ thống tự động điền thêm dấu cách cho đủ m vị trí. Nếu chiều dài dữ liệu của a lớn hơn m thì hệ thống hiển thị đủ vị trí cho a. Thí dụ, lệnh write(BL:20)sẽ hiển thị 20 dấu cách trên màn hình. Vì màn hình trong hệ điều hành Windows có độ phân giải cao, khác với màn hình văn bản trong DOS nên thủ tục VeBai được cài đặt với tham số điều khiển Kieu quy định kiểu của hệ điều hành. Kieu = Wind sẽ hiển thị bộ bài trong chế độ Windows, Kieu = DOS sẽ hiển thị bộ bài trong chế độ màn hình DOS. Hai kiểu chỉ khác nhau ở một giá trị cần khởi trị cho vài tham số, cụ thể là: Kích thước quân bài. Nếu coi mỗi quân bài như một hình chữ nhật thì DX là chiều rộng, DY là chiều dài. Độ giãn dòng TX. Khi hiển thị trên màn hình Windows thì ta để cách hai dòng, TX = 2, ngược lại, trên màn hình DOS ta đặt TX = 1. Bảng dưới đây mô tả các tham số cần khởi trị cho hai môi trường WINDOWS và DOS. WINDOWS DOS DX 9 9 DY 12 6 TX 2 1 Các tham số kích thước quân bài DX DY và độ giãn cách dòng TX trong môi trường WINDOWS và DOS. (* Pascal *) uses crt; const CO = #3; RO = #4; NHEP = #5; PIC = #6; WIND = 1; DOS = 2; BL = #32; DX: byte = 9; DY: byte = 12; {kich thuoc quan bai} TY: byte = 2; MauDong: array[1 13] of string[5] = ('00100', '01010', '10101', '20002', '20102',
Sáng tạo trong Thuật toán và Lập trình Tập I 70 '20202', '20302', '21212', '30303', '22222', '22322', '23232', '23332'); Nhan: array[1 13] of string[2] = ('A','2','3','4','5', '6','7','8',‟9', 10', 'J','Q','K'); procedure Dong(q: char;s: string;x,y: byte); tự viết { Ve nen mau M cho quan bai tai vi tri goc tren trai (x,y) } procedure Nen(M,x,y: byte); var i: byte; begin TextBackGround(M); for i:= 0 to DY do begin gotoxy(x+1,y+i); write(BL:DX); end; end; { Ve 1 quan bai kieu q (ro, co, bich, nhep); so n (2 10; 1 = A; 11 = J; 12 = Q; 13 = K) goc Tay-Bac tai cot x, dong y cua man hinh, } procedure VeQuanBai(q: char; n, x, y: byte); var i, j: byte; begin {VeQuanBai} if (q = RO) OR (q = CO) then TextColor(RED) else TextColor(BLACK); Nen(WHITE,x,y); Dong(q,MauDong[n],x,y); {viet so} gotoxy(x+1,y+1); write(Nhan[n]:2); gotoxy(x+DX-1,y+DY-1); write(Nhan[n]); end; Procedure VeBai(Kieu: byte); var i: integer; begin if Kieu = DOS then begin DY:= 6; TY:= 1; end else if Kieu = WIND then begin
Sáng tạo trong Thuật toán và Lập trình Tập I 71 DY:= 12; TY:= 2; end else begin writeln('Dat kieu khong dung'); write('Cach goi thu tuc: '); writeln('VeBai(WIND) hoac VeBai(DOS)'); readln; halt; end; textbackground(BLUE); clrscr; for i := 1 to 13 do {Ve bo Tu lo kho} begin VeQuanBai(RO,i,5,10); VeQuanBai(CO,i,20,10); VeQuanBai(PIC,i,35,10); VeQuanBai(NHEP,i,50,10); if ReadKey=#27 then halt; end; textattr:= 7; clrscr; end; BEGIN VeBai(WIND); END. // C# using System; using System.IO; namespace SangTao1 { /* * Bo bai Tulokho * */ class TuLoKho { static void Main() { BoBai b = new BoBai(); b.Draw(6, 4); Console.ReadLine(); } } // Class /* * Mo ta bo bai Tulokho * */ class BoBai { private char CO = (char)3; private char RO = (char)4; private char NHEP = (char)5; private char PIC = (char)6;
Sáng tạo trong Thuật toán và Lập trình Tập I 72 const int DX = 9; const int DY = 6;// kich thuoc quan bai // 1 khoang cach giua 2 dong const int TY = 1; const int SOQUAN = 13; private string[] MauDong = {"00100", "01010", "10101", "20002", "20102", "20202", "20302", "21212", "30303", "22222", "22322", "23232", "23332" }; private string[] Nhan = {"A","2","3","4","5","6","7", "8","9","10","J","Q","K"}; // Dat mau nen va text cho man hinh private void SetColors(ConsoleColor bg, ConsoleColor fg) { Console.BackgroundColor = bg; Console.ForegroundColor = fg; } // Viet s tai cot x, dong y private void WriteAt(string s, int x, int y) { Console.SetCursorPosition(x, y); Console.Write(s); } // WriteAt // Ve bo bai tai vi tri x, y public void Draw(int x, int y) { int DD = DX + 10; Console.BackgroundColor = ConsoleColor.Blue; Console.Clear(); for (int i = 0; i < SOQUAN; ++i) { VeQuanBai(RO, i, x, y); VeQuanBai(CO, i, x + DD, y); VeQuanBai(PIC, i, x + 2 * DD, y); VeQuanBai(NHEP, i, x + 3 * DD, y); Console.ReadLine(); } Console.ResetColor(); // tra lai nen cu } // Draw /* Ve 5 dong trong quan bai */ private void Lines(char q, string s,
Sáng tạo trong Thuật toán và Lập trình Tập I 73 int x, int y) { const string BL = " "; string qs = q.ToString(); x += 3; for (int i = 0; i < 5; ++i) { y += TY; Console.SetCursorPosition(x, y); switch (s[i]) { case '1': Console.WriteLine(BL + BL + qs + BL + BL); break; case '2': Console.WriteLine(qs + BL + BL + BL + qs); break; case '3': Console.WriteLine(qs + BL + qs + BL + qs); break; } // switch } // for } // Dat mau nen cho quan bai private void Nen(ConsoleColor m, int x, int y) { string s = new string(' ', DX); Console.BackgroundColor = m; for (int i = 0; i <= DY; ++i) WriteAt(s, x + 1, y + i); } /* Ve 1 quan bai kieu q (ro, co, bich, nhep); so n (1 10; 0 = A; 10 = J; 11 = Q; 12 = K) goc Tay-Bac tai cot x, dong y cua man hinh, */ private void VeQuanBai(char q, int n, int x, int y) { // Chon mau chu RO, CO: mau do // PIC, NHEP: mau den Console.ForegroundColor = (q == RO || q == CO) ? ConsoleColor.Red : ConsoleColor.Black; // Dat nen quan bai mau trang Nen(ConsoleColor.White, x, y); // Ve 5 dong Lines(q, MauDong[n], x, y); // Viet so o goc tren-trai
Sáng tạo trong Thuật toán và Lập trình Tập I 74 WriteAt(Nhan[n], x + 2, y);// + 1); // Viet so o goc duoi-phai if (n == 9) WriteAt(Nhan[n], x + DX - 2, y + DY ); else WriteAt(Nhan[n], x + DX - 1, y + DY ); } // VeQuanBai } // TuLoKho } // SangTao1 Chú thích Các tham số x, y và DX, DY phụ thuộc vào độ phân giải màn hình. Bạn cần điều chỉnh các tham số này cho phù hợp với chế độ phân giải màn hình đã chọn. Bài 3.3. Hàm GetKey Mỗi khi ta nhấn một phím, trong vùng đệm 2 byte sẽ được nạp 1 hoặc 2 byte tuỳ theo kiểu phím đã nhấn. Nếu là phím thường như a, b, c, %, $, trong vùng đệm sẽ được nạp 1 byte chứa mã ASCII của kí tự tương ứng. Nếu ta nhấn phím mở rộng như F1, , F10, các phím dịch chuyển con trỏ, , , , , Ins (chèn), Del (xoá), PageUp/PgUp (lên một trang), PageDown/PgDn (xuống một trang), trong vùng đệm sẽ được nạp hai byte, byte thứ nhất có giá trị 0, byte thứ hai chứa mã riêng của phím đã nhấn. Mã riêng này có thể trùng với mã của các kí tự thường. Thí dụ, khi ta nhấn phím mở rộng F10 trong vùng đệm sẽ được nạp 2 byte (0, 68). Mã riêng 68 trùng với mã của kí tự D. Hàm ReadKey cho ta kí tự của phím đã nhấn và không hiển thị kí tự đó (trên màn hình), ta gọi là hàm nhận thầm một kí tự. ReadKey trước hết kiểm tra vùng đệm bàn phím xem còn byte nào chưa được đọc không. Nếu còn, ReadKey sẽ đọc byte đó. Ngược lại, nếu vùng đệm trống, ReadKey sẽ chờ để ta nhấn một phím rồi sau đó đọc 1 byte từ vùng đệm. Hãy viết hàm GetKey cho ra mã ASCII của phím thường đã nhấn và cho ra mã riêng của phím mở rộng cộng thêm 128 nhằm phân biệt được phím thường với phím mở rộng. Chú ý: Hàm GetKey ở bài 3.3 cho mã của một số phím mở rộng dùng để điều khiển con trỏ màn hình như sau: LEN: 200 Mũi tên trỏ lên  XUONG: 208 Mũi tên trỏ xuống  PHAI: 205 Mũi tên trỏ qua phải TRAI: 203 Mũi tên trỏ qua trái  ESC (27) và ENTER/RETURN (13) là những phím thường. Gợi ý Trước hết gọi hàm c:= ReadKey rồi kiểm tra giá trị của kí tự c. Nếu c có mã 0 tức là đã nhấn phím mở rộng, ta cần đọc tiếp byte thứ hai và gán cho hàm giá trị của byte đó cộng thêm dấu hiệu nhận biết phím mở rộng là 128. Nếu c có mã khác 0, ta gán cho hàm giá trị đó. (* Pascal *) (* Ham GetKey *) program Conio;
Sáng tạo trong Thuật toán và Lập trình Tập I 75 uses crt; const Esc = 27; Function GetKey: integer; var c: char; begin c:= ReadKey; if c 128 then writeln(' Phim mo rong (0, ',k-128,') ==> ',k) else writeln(' Phim thuong ',chr(k), '(',k,')'); until k = Esc; readln; end; BEGIN Test; END. Bài 3.4. Trò chơi 15 Có 15 quân cờ được đánh mã số từ 1 đến 15 được đặt trong một bàn cờ hình vuông 4 4 ô theo hình trạng ban đầu như rong hình . Mỗi bước đi, ta được phép di chuyển một quân nằm cạnh ô trống vào trong ô trống. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Trò chơi 15 Viết chương trình thực hiện hai chức năng sau đây: a) Đảo ngẫu nhiên các quân cờ để chuyển từ hình trạng ban đầu về một hình trạng H nào đó. b) Nhận phím điều khiển của người chơi rồi di chuyển quân cờ theo phím đó. Khi nào người chơi đạt được hình trạng ban đầu thì kết thúc một ván. Trò chơi này có tên là Trò chơi 15, từng nổi tiếng ở thế kỉ XIX như trò chơi Rubic ở thời đại chúng ta vậy. Gợi ý