Các cách biểu diễn thuật toán

      542

Khi chứng minc hoặc giảimột bài toán thù vào toán thù học, ta thường dùng những ngôn từ toánhọc như : "ta có", "điều phải chứng minh", "giảthuyết", ... cùng sử dụng những phnghiền suy luận tân oán học như phépsuy ra, tương đương, ...Thuật toán là một phương pháp thể hiện lờigiải bài xích tân oán buộc phải cũng phải tuân thủ theo đúng một số quy tắc nhất định.Ðể gồm thể truyền đạt thuật tân oán đến người khác xuất xắc chuyển thuậttoán thù thành chương trình laptop, ta phải bao gồm phương pháp biểu diễnthuật toán. Có 3 phương pháp biểu diễn thuật tân oán :

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

2. Dùng lưu đồ-sơ đồ khối (flowchart).

Bạn đang xem: Các cách biểu diễn thuật toán

3. Dùng mã giả (pseudocode).

2.1. Ngôn ngữtự nhiên

Trong giải pháp biểu diễn thuật toán thù theo ngôn ngữtự nhiên, người ta sử dụng ngôn ngữ thường ngày để liệt kêcác bước của thuật tân oán (Các ví dụ về thuật tân oán vào mục 1của chương sử dụng ngôn ngữ tự nhiên). Phương pháp biểu diễnnày không yêu thương cầu người viết thuật toán thù cũng như ngườiđọc thuật toán thù phải nắm những quy tắc. Tuy vậy, bí quyết biểu diễn nàythường lâu năm loại, không thể hiện rõ cấu trúc của thuật toán,đôi dịp khiến hiểu lầm hoặc khó hiểu đến người đọc. Gần nhưkhông tồn tại một quy tắc cố định nào vào việc thể hiện thuật toánbằng ngôn ngữ tự nhiên. Tuy vậy, để dễ đọc, ta buộc phải viết cácbước nhỏ lùi vào bên phải cùng đánh số bước theo quy tắc phâncấp như 1, 1.1, 1.1.1, ... Bạn gồm thể tsay mê khảo lại cha ví dụ vào mục 1của chương để hiểu phương pháp biểu diễn thuật tân oán theo ngôn ngữ tựnhiên.

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

Lưu đồ tốt sơ đồkhối là một công cụ trực quan tiền để diễn đạt những thuật tân oá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 cùng quá trình xử lý củathuật toán thù. Phương pháp lưu đồ thường được sử dụng vào nhữngthuật tân oán tất cả tính rắc rối, cạnh tranh quan sát và theo dõi được quá trình xử lý.

Xem thêm: Cách Làm Trò Chơi Lucky Number Trên Powerpoint 2010, Hướng Dẫn Làm Trò Chơi Lucky Number

Ðể biểu diễn thuật toán theo sơ đồ khối, taphải phân biệt nhị loại thao tác làm việc. Một thao tác làm việc là làm việc chọn lựadựa theo một điều kiện như thế nào đó. Chẳng hạn : thao tác làm việc "nếu a= b thì thực hiện làm việc B2, ngược lại thực hiện B4" làthao tác chọn lựa. Các thao tác làm việc còn lại ko thuộc loại chọnlựa được xếp vào loại hành động. Chẳng hạn, "Chọnmột hộp bất kỳ và để lên dĩa cân còn trống." là mộtlàm việ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, phía bên trong chứa nội dung xử lý.

*

2.2.3.Ðường đi (route)

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

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

Từ thao tác làm việc chọn lựa tất cả thể bao gồm đến hai hướng đi, một hướng ứng với điều kiện thỏa với một hướng ứng với điều kiện không thỏa. Do vậy, ta dùng nhị cung xuất vạc từ các đỉnh hình thoi, bên trên mỗi cung có ký kết hiệu Ð/Ðúng/Y/Yes để chỉ hướng đi ứng với điều kiện thỏa và cam kết hiệu S/Sai/N/No để chỉ hướng đi ứng với điều kiện ko 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 tân oán, được biểu diễn bằng hình ovan, phía bên trong có ghi chữ bắt đầu/start/begin hoặc kết thúc/over. Ðiểm cuối chỉ gồm 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 tân oán giải phương trình bậc nhị ở bên trên để thấy biện pháp sử 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ông giống nhau của một lưu đồ lại với nhau. Bên vào điểm nối, ta đặt một cam kết hiệu để biết sự liên hệ giữa những đ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 lịch sự trang được cần sử dụng Khi lưu đồ vượt lớn, phải vẽ bên trên nhiều trang. Bên trong điểm nối lịch sự trang ta cũng đặt một ký kết hiệu để biết được sự liên hệ giữa điểm nối của các trang.

*

Ở trên chỉ là những ký kết hiệu cơ bản với 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 cùng phức tạp. Ðối với những thuật toán thù trong cuốn sách này, ta chỉ cần sử dụng các ký kết hiệu bên trên là đủ.

2.3. Mã giả

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

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

*
Một đoạn mã giả của thuật toán thù 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ó nhì nghiệm là x1 và x2

end

else

if delta = 0 then

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

else {trường hợp delta

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