Chương I: CƠ SỞ LÝ THUYẾT I. Mô hình quan niệm: Mảng là một dãy có thứ tự (về mặt vị trí) các phần tử với hai đặc điểm sau : + Số lượng phần tử cố định. + Mọi phần tử đều có cùng kiểu dữ liệu (dữ liệu cơ sở của mảng). Các đặc trưng cơ bản: - Cho phép truy cập ngẫu nhiên đến từng phần tử.
Thời gian truy cập đến mọi phần tử đều bằng nhau. - Số lượng phần tử của mảng là cố định. Cấu trúc lưu trữ: - Cấu trúc lưu trữ đơn giản nhất là dùng địa chỉ được tính để thực hiện lưu trữ và tìm kiếm các phần tử, là mảng một chiều hay vectơ. - Các phần tử được bố trí sát nhau trong bộ nhớ và theo thứ tự tăng dần của các chỉ số nên dễ dàng tìm được địa chỉ của một phần tử bất kỳ nếu biết chỉ số.
Các phép toán cơ bản: - Thường chỉ có các phép tạo lập (create) mảng, tìm kiếm (retrieve) một phần tử của mảng, cập nhật (update) một phần tử của mảng …Ngoài giá trị, một phần tử của mảng còn được đặc trưng bởi chỉ số (index) thể hiện thứ tự của phần tử đó trong mảng. Vectơ là mảng một chiều, mỗi phần tử ai của nó ứng với một chỉ số i. Ma trận là mảng hai chiều, mỗi phần tử aij ứng với hai chỉ số i và j. Tương tự người ta cũng mở rộng ra mảng hai chiều , mảng ba chiều, …, mảng n chiều.
Đệ quy là gì? Ta nói: - Một đối tượng là đệ quy nếu nó bao gồm chính nó như một bộ phận hoặc nó được định nghĩa dưới dạng của chính nó. - Một thủ tục được gọi là đệ quy nếu trong quá trình thực hiện nó phải gọi đến chính nó nhưng với kích thước nhỏ hơn của tham số. - Trong thân của một hàm, nếu nó gọi tới chính hàm đó để xử lý bài toán thì gọi là hàm đệ quy. Ví dụ: 1) Định nghĩa số tự nhiên: - là một số tự nhiên.
- n là số tự nhiên nếu n-1 là số tự nhiên. 2) Định nghĩa hàm giai thừa: - 0! = 1 - Nếu n > 0 thì n! = n(n-1)! 2. Cấu trúc chính của một chương trình đệ quy: Một chương trình đệ quy về căn bản gồm 2 phần: - Phần cơ sở : Trong đó, chứa các tác động của hàm hoặc thủ tục với một số giá trị cụ thể ban đầu của tham số (hay gọi trường hợp dừng). Ví dụ : if n=1 then gt:=1; - Phần đệ quy: Trong đó, tác động cần được thực hiện cho giá trị hiện thời của các tham số được định nghĩa bằng các tác động đã được định nghĩa trước đấy với kích thước nhỏ hơn của tham số.
Ví dụ: if n>1 then gt:=n*gt(n-1); -4- Luan van 2. Đặc điểm: - Mỗi một lần hàm tự gọi đệ quy đến nó thì máy tính sẽ tự tạo ra một biến cục bộ mới. - Có bao nhiêu lần hàm gọi đệ quy thì sẽ có bấy nhiêu lần thoát ra khỏi hàm (kiểu như lặp hàm). - Khi thoát ra ngoài hàm đệ quy thì một loạt các biến cục bộ tạo ra do dùng đệ quy lúc này mới được giải phóng, và chúng sẽ giải phóng trước các biến cục bộ (sinh ra do đệ quy) tạo ra sau.
- Sử dụng đệ quy là một phương pháp làm cho chương trình ngắn gọn, dễ hiểu nhưng nó sẽ làm tốn bộ nhớ và thời gian. Ví dụ: Hàm tính giai thừa của n (tính n!): Function giaithua(n:word):integer; begin if n=0 then giaithua:=1 else giaithua:=giaithua(n-1)*n; end; Ví dụ: Tính n! =3 Ta có giá trị truyền vào hàm gt qua biến n. Trong ví dụ này, qui trình thực hiện như sau: - Khi có lệnh gọi hàm, chẳng hạn: n := gt(3); - Thì máy sẽ ghi nhớ là: gt(3) := 3 * gt(2); và đi tính gt(2) - Kế tiếp máy lại ghi nhớ: gt(2) := 2 * gt(1); và đi tính gt(1) - Theo định nghĩa của hàm thì: -5- Luan van gt(1) := 1; - Máy sẽ quay ngược lại: gt(2) := 2 * 1; cho kết quả là 2 - Tiếp tục: - gt(3) := 3 * 2; cho kết quả là 6 - Như vậy kết quả cuối cùng trả về là 6. Nhận xét Ưu điểm: - Điểm mạnh lớn nhất: chương trình, code trở nên ngắn gọn, dễ hiểu, thuận lợi cho việc chỉnh sửa.
- Dễ chuyển thành chương trình trên các ngôn ngữ lập trình. Nhược điểm: - Nhược điểm lớn nhất là tốn bộ nhớ. - Mất nhiều thời gian xử lý, làm giảm tốc độ chạy chương trình. - Không áp dụng cho mọi ngôn ngữ lập trình.
Đệ quy không những là một phương pháp lập trình quan trọng mà còn là một phương pháp suy nghĩ để giải quyết vấn đề một cách tổng quát dựa trên ý tưởng: + Đơn giản hoá công việc + Phân vùng để xử lý. Khử đệ quy: Đệ quy là quả tim trong các nghiên cứu lý thuyết cũng như thực hành tính toán, đã thể hiện rất nhiều sức mạnh và có ưu điểm trong nhiều bài toán. Nhưng có đôi khi, sự hạn hẹp của bộ nhớ dành cho chương trình con không cho phép chúng ta làm điều đó.Vì vậy vấn đề khử đệ quy lại cần được quan tâm, xem xét. Khái niệm: Là quá trình chuyển đổi một giải thuật đệ quy thành một giải thuật không đệ quy bằng cách chúng ta sử dụng vòng lặp hoặc bộ nhớ Stack tự tạo.
Cách thực hiện : - Sử dụng vòng lặp: Với ý tưởng là chúng ta lưu lại các giá trị của lần tính toán trước làm dữ liệu cho việc tính toán của lần sau. Ví dụ: Khử đệ quy trong bài toán giai thừa bằng cách sử dụng vòng lặp int giaithua (int n) { int k=1; For (i=2; i<=n;i++) k=k*i; return(k); } - Sử dụng bộ nhớ Stack: Đặt tất cả các giá trị của các biến cục bộ và địa chỉ của chỉ thị kế tiếp vào ngăn xếp (Stack), quy định các giá trị tham số cho thủ tục và chuyển tới vị trí bắt đầu thủ tục, thực hiện lần lượt từng câu lệnh. Sau khi thủ tục hoàn tất thì nó phải lấy ra khỏi ngăn xếp địa chỉ trả về và các giá trị của các biến cục bộ, khôi phục các biến và chuyển tới địa chỉ trả về. NGÔN NGỮ LẬP TRÌNH: 1.
Vài nét về Visual C#: C# là một ngôn ngữ lập trình hướng đối tượng được phát triển bởi Microsoft, là phần đầu cho kế hoạch .NET của họ. Microsoft phát triển C# dựa trên C++ và Java. C# được thiết kể bởi Anders Hejlsberg kiến trúc sư phần mềm nổi tiếng với các sản phẩm Turbo Pascal. Và ông là người đứng đầu nhóm thiết kế Borland Delphi, một trong những thành công đầu tiên của việc xây dựng môi trường phát triển tích hợp (IDE) cho lập trình Client/Server.
-7- Luan van C# cũng là ngôn ngữ lập trình điều khiển sự kiện, các chương trình được tạo ra sẽ sử dụng IDE (Integrated Developmen Environment). Với IDE, người lập trình có thể tạo, chạy, kiểm tra và debug các chương trình C#. Bên cạnh đó, nền .NET cho phép các thành phần của một phần mềm được viết từ các ngôn ngữ lập trình khác nhau có thể tương tác được với nhau, thậm chí người phát triển ứng dụng có thể đóng gói các phần mềm cũ để nó hoạt động với chương trình C# mới. Giống như các ngôn ngữ lập trình khác, C# cũng hỗ trợ các kiểu dữ liệu cơ bản như integer, float, boolean, string, array.
và các câu lệnh điều khiển (if, while, for, switch, do…while…). Tuy nhiên, như đã trình bày ở trên, C# cũng có những đặc điểm riêng của nó. Đặc điểm của ngôn ngữ C#: C#, theo một hướng nào đó, là ngôn ngữ lập trình phản ánh trực tiếp nhất đến .NET Framework mà tất cả các chương trình .NET chạy và nó phụ thuộc mạnh mẽ vào Framework này. - Không có khái niệm biến toàn cục (global variables) và hàm (functions).
Tất cả các hàm, phương thức trong một chương trình viết bằng ngôn ngữ C# đều được khai báo dưới dạng một lớp. Mọi kiểu biến, kể cả các kiểu giá trị đơn giản đều được xem như các đối tượng. Tuy nhiên, ta có thể dùng thuộc tính static đối với các hàm và biến trong một lớp được khai báo public thay vì sử dụng biến toàn cục và hàm. - C# yêu cầu rất chặt chẽ đối với kiểu Boolean (bool), các câu lệnh có điều kiện như while và if đều đòi hỏi biểu thức điều kiện phải có kiểu bool.
Nếu trong C++ ta có phát biểu if(a) statement, biểu thức trong điều kiện if có thể được chuyển thành giá trị kiểu bool, cho dù a có thể được khai báo kiểu int hay pointer, C# thì khác, nó không có khái niệm “a nguyên là đúng hay sai”. Điều này buộc người lập trình phải sử dụng những biểu thức có kiểu trả về chính xác là bool. Đặc tính này rất hữu ích trong việc giảm những lổi lập trình hay mắc phải. -8- Luan van - C++ cho phép đa thừa kế (multiple interitances) và nếu được sử dụng đúng cách, đây thực sự là điểm rất mạnh.
Tuy nhiên, đa thừa kế rất khó quản lý và như vậy cũng rất khó áp dụng. Đây là một trong những lý do C# chỉ phát triển thừa kế đơn (single inheritance). - Namespaces trong C#: Khái niệm Namespaces được hiểu một cách đơn giản là tập các lớp có mối liên hệ lẫn nhau. Ví dụ như ta gom các lớp có liên quan đến hoạt động của cơ sở dữ liệu lại và đặt cho chúng một không gian tên (namespace) chung gọi là DataActivity.
Vì C# không cho phép có hai lớp cùng tên trong cùng một chương trình, việc dùng namespace sẽ giúp ta tránh được những đụng độ trong vấn đề đặt tên. Sẽ hoàn toàn có thể xảy ra sự đụng độ trên nếu chúng ta có nhiều lớp được khai báo trong cùng một chương trình, chẳng hạn lớp Connection trong DataActivity sẽ xung đột với lớp Connection trong InternetActivity. Để tránh sự đụng độ này, C# quy định tên lớp phải bao gồm namespace của lớp đó. Vì thế tên thích hợp của 2 lớp Connection trong trường hợp trên là DataActivity.
Connection và InternetActivity. Điểm nổi bật của C# Namespace là không ánh xạ một cách vật lý như đối với Java. Các lớp với cùng một namespace có thể ở nhiều thư mục khác nhau. Và namespace có thể bao gồm các lớp, các sự kiện, các exception và thậm chí là các namespace khác.
-9- Luan van Chương II: PHƯƠNG PHÁP QUAY LUI I. KHÁI NIỆM QUAY LUI: Kĩ thuật quay lui (backtracking) như tên gọi của nó, là một quá trình phân tích đi xuống và quay lui trở lại theo con đường đã đi qua.