Các phương pháp bd thuật toán

Bài viết Các phương pháp bd thuật toán thuộc chủ đề về Hỏi & Đáp thời gian này đang được rất nhiều bạn quan tâm đúng không nào !! Hôm nay, Hãy cùng HLink tìm hiểu Các phương pháp bd thuật toán trong bài viết hôm nay nhé ! Các bạn đang xem bài : “Các phương pháp bd thuật toán”

Đánh giá về Các phương pháp bd thuật toán

Các phương pháp bd thuật toán

2. CÁC PHƯỢNG PHÁP BIỂU DIỄN THUẬT TOÁN

    Khi chứng minh hoặc giải một bài toán trong toán học, ta thường sử dụng những ngôn từ toán học như : “ta có”, “điều phải chứng minh”, “giả thuyết”, … và sử dụng những phép suy luận toán học như phép suy ra, cũng như, …Thuật toán là một phương pháp thể hiện lời giải bài toán nên cũng phải tuân theo một vài quy tắc nhất định. Ðể có khả năng truyền đạt thuật toán cho người khác hay chuyển thuật toán thành chương trình máy tính, ta phải có phương pháp biểu diễn thuật toán. Có 3 phương pháp biểu diễn thuật toán :

1. dùng ngôn ngữ tự nhiên.

2. sử dụng lưu đồ-sơ đồ khối (flowchart).

3. sử dụng mã giả (pseudocode).

2.1. Ngôn ngữ một cách tự nhiên

    Trong cách biểu diễn thuật toán theo ngôn ngữ một cách tự nhiên, người ta dùng ngôn ngữ thường ngày để liệt kê các bước của thuật toán (Các ví dụ về thuật toán trong mục 1 của chương dùng ngôn ngữ tự nhiên). Phương pháp biểu diễn này không yêu cầu người viết thuật toán cũng như người đọc thuật toán phải nắm các quy tắc. Tuy vậy, cách biểu diễn này thường dài dòng, không thể hiện rõ cấu trúc của thuật toán, đôi lúc gây ra hiểu lầm hoặc khó hiểu cho người đọc. hầu như không có một quy tắc cố định nào trong việc thể hiện thuật toán bằng ngôn ngữ một cách tự nhiên. Tuy vậy, để dễ đọc, ta nên viết các bước con lùi vào bên phải và đánh số bước theo quy tắc phân cấp như 1, 1.1, 1.1.1, … Bạn có khả năng tham khảo lại ba ví dụ trong mục 1 của chương để hiểu cách biểu diễn thuật toán theo ngôn ngữ tự nhiên.

2.2. Lưu đồ – sơ đồ khối

Lưu đồ hay sơ đồ khối là một công cụ trực quan để diễn đạt các thuật toán. Biểu diễn thuật toán bằng lưu đồ sẽ giúp người đọc theo dõi được sự phân cấp các trường hợp và quá trình xử lý của thuật toán. Phương pháp lưu đồ thường được sử dụng trong những thuật toán có tính rắc rối, khó theo dõi được quy trình xử lý.

Ðể biểu diễn thuật toán theo sơ đồ khối, ta phải phân biệt hai loại thao tác. Một thao tác là thao tác chọn lựa dựa theo một khó khăn nào đó. Chẳng hạn : thao tác “nếu a = b thì thực hiện thao tác B2, ngược lại thực hiện B4” là thao tác chọn lựa. Các thao tác còn lại không thuộc loại chọn lựa được xếp vào loại hành động. Chẳng hạn, “Chọn một hộp bất kỳ và để lên dĩa cân còn trống.” là một thao tác thuộc loại hành động.

    2.2.1. Thao tác chọn lựa (decision)

Thao tác chọn lựa được biểu diễn bằng một hình thoi, bên trong chứa biểu thức điều kiện.

    2.2.2. Thao tác xử lý (process)

Thao tác xử lý được biểu diễn bằng một hình chữ nhật, bên trong chứa nội dung xử lý.

    2.2.3.Ðường đi (route)

Khi dùng ngôn ngữ tự nhiên, ta mặc định hiểu rằng quá trình thực hiện sẽ lần lượt đi từ bước trước đến bước sau (trừ khi có bắt buộc nhảy sang bước khác). Trong ngôn ngữ lưu đồ, do thể hiện các bước bằng hình vẽ và có khả năng đặt các hình vẽ này ở vị trí bất kỳ nên ta phải có phương pháp để thể hiện trình tự thực hiện các thao tác.

Hai bước kế tiếp nhéu được nối bằng một cung, trên cung có mũi tên để chỉ hướng thực hiện. Chẳng hạn trong hình dưới, trình tự thực hiện sẽ là B1, B2, B3.

Từ thao tác chọn lựa có thể có đến hai hướng đi, một hướng ứng với khó khăn thỏa và một hướng ứng với khó khăn không thỏa. Do vậy, ta dùng hai cung xuất phát từ các đỉnh hình thoi, trên mỗi cung có ký hiệu Ð/Ðúng/Y/Yes để chỉ hướng đi ứng với điều kiện thỏa và ký hiệu S/Sai/N/No để chỉ hướng đi ứng với điều kiện không thỏa.

    2.2.4. Ðiểm cuối (terminator)

Ðiểm cuối là điểm khởi đầu và kết thúc của thuật toán, được biểu diễn bằng hình ovan, bên trong có ghi chữ bắt đầu/start/begin hoặc kết thúc/end. Ðiểm cuối chỉ có cung đi ra (điểm khởi đầu) hoặc cung đi vào (điểm kết thúc). Xem lưu đồ thuật toán giải phương trình bậc hai ở trên để thấy cách dùng của điểm cuối.

    2.2.5. Ðiểm nối (connector)

Ðiểm nối được sử dụng để nối các phần khác nhau của một lưu đồ lại với nhéu. Bên trong điểm nối, ta đặt một ký hiệu để biết sự LH giữa các điểm nối.

    2.2.6. Ðiểm nối sang trang (off-page connector)

Tương tự như điểm nối, nhưng điểm nối sang trang được dùng khi lưu đồ quá lớn, phải vẽ trên nhiều trang. Bên trong điểm nối sang trang ta cũng đặt một ký hiệu để biết được sự liên lạc giữa điểm nối của các trang.

Ở trên chỉ là các ký hiệu cơ bản và thường được sử dụng nhất. Trong thực tế, lưu đồ còn có nhiều ký hiệu khác nhưng thường chỉ sử dụng trong những lưu đồ lớn và phức tạp. Ðối với các thuật toán trong cuốn sách này, ta chỉ cần dùng các ký hiệu trên là đủ.

2.3. Mã giả

Tuy sơ đồ khối thể hiện rõ quá trình xử lý và sự phân cấp các trường hợp của thuật toán nhưng lại cồng kềnh. Ðể mô tả một thuật toán nhỏ ta phải sử dụng một không gian rất lớn. Hơn nữa, lưu đồ chỉ phân biệt hai thao tác là rẽ nhánh (chọn lựa có điều kiện) và xử lý mà trong thực tế, các thuật toán còn có thêm các thao tác lặp (Chúng ta sẽ tìm hiểu thông tin về thao tác lặp trong các bài sau).

Khi thể hiện thuật toán bằng mã giả, ta sẽ vay mượn các cú pháp của một ngôn ngữ lập trình nào đó để thể hiện thuật toán. Tất nhiên, mọi ngôn ngữ lập trình đều có những thao tác cơ bản là xử lý, rẽ nhánh và lặp. dùng mã giả vừa tận dụng được các khái niệm trong ngôn ngữ lập trình, vừa giúp người cài đặt dễ dàng nắm bắt nội dung thuật toán. Tất nhiên là trong mã giả ta vẫn dùng một phần ngôn ngữ một cách tự nhiên. Một khi đã vay mượn cú pháp và khái niệm của ngôn ngữ lập trình thì chắc chắn mã giả sẽ bị phụ thuộc vào ngôn ngữ lập trình đó. Chính vì lý do này, chúng ta chưa vội tìm hiểu về mã giả trong bài này (vì chúng ta chưa biết gì về ngôn ngữ lập trình!). Sau khi tìm hiểu xong bài về hồ sơ – hàm bạn sẽ hiểu mã giả là gì !

Một đoạn mã giả của thuật toán giải phương trình bậc hai

if Delta > 0 then begin

x1=(-b-sqrt(delta))/(2*a)

x2=(-b+sqrt(delta))/(2*a)

xuất kết quả : phương trình có hai nghiệm là x1 và x2

end

else

if delta = 0 then

xuất kết quả : phương trình có nghiệm kép là -b/(2*a)

else trường hợp delta < 0

xuất kết quả : phương trình vô nghiệm

   * Các từ in đậm là các từ khóa của ngôn ngữ Pascal

Các câu hỏi về biểu diễn giải thuật là gì