0 bình luận về “Thuật toán có thể trình bày bằng cách nào?”
án sau đây:
Dùng ngôn ngữ tự nhiên.
Dùng lưu đồ hay sơ đồ khối.
Dùng mã giả.
Lưu đồ:
Ngôn ngữ lưu đồ hay sơ đồ khối là một công cụ rất trực quan để diễn đạt các thuật toán. Biểu diễn bằng lưu đồ sẽ giúp ta có được một cái nhìn tổng quan về toàn cảnh của quá trình xử lý theo thuật toán.
Lưu đồ là một hệ thống các nút có hình dạng khác nhau, thể hiện các chức năng khác nhau và được nối với nhau bởi các cung. Lưu đồ được tạo thành bởi 4 thành phần chủ yếu sau đây:
1/ Nút giới hạn: được biểu diễn bởi hình ôvan có ghi chữ bên trong như :
Các nút trên còn được gọi là nút đầu và nút cuối của lưu đồ.
2/ Nút thao tác: là một hình chữ nhật có ghi các lệnh cần thực hiện. Ví dụ:
3/ Nút điều kiện: thường là một hình thoi có ghi điều kiện cần kiểm tra. Trong các cung nối với nút này có 2 cung ra chỉ hướng đi theo 2 trường hợp: điều kiện đúng và điều kiện sai. Ví dụ:
4/ Cung: là các đường nối từ nút này đến nút khác của lưu đồ.
Hoạt động của thuật toán theo lưu đồ được bắt đầu từ nút đầu tiên. Sau khi thực hiện các thao tác hoặc kiểm tra điều kiện ở mỗi nút thì bộ xử lý sẽ theo một cung để đến nút khác. Quá trình thực hiện thuật toán dừng khi gặp nút kết thúc hay nút cuối.
Trong bài này chúng ta chủ yếu là sử dụng ngôn ngữ tự nhiên và mã giả để trình bày thuật toán. Trong cách sử dụng ngôn ngữ tự nhiên ta sẽ liệt kê các bước thực hiện các thao tác hay công việc nào đó của thuật toán bằng ngôn ngữ mà con người sử dụng một cách phổ thông hàng ngày. Các thuật toán được trình bày trong hai ví dụ trên chính là cách biểu diễn thuật toán dùng ngôn ngữ tự nhiên. Mặc dù cách biểu diễn này khá tự nhiên và không đòi hỏi người viết thuật toán phải biết nhiều quy ước khác, nhưng nó không thể hiện rõ tính cấu trúc của thuật toán nên không thuận lợi cho việc thiết kế và cài đặt những thuật toán phức tạp. Hơn nữa trong nhiều trường hợp việc biểu diễn thuật toán bằng ngôn ngữ tự nhiên tỏ ra dài dòng và dẽ gây ra sự nhầm lẫn đối với người đọc. Còn việc sử dụng lưu đồ sẽ rất cồng kềnh đối với các thuật toán phức tạp => chúng ta cần chọn phương thức thích hợp để biểu diễn thuật toán.
Mã giả:
Ðể biểu diễn thuật toán một cách hiệu quả, người ta thường dùng mã giả (pseudocode). Theo cách này, ta sẽ sử dụng một số qui ước của một ngôn ngữ lập trình, chẳng hạn là ngôn ngữ lập trình PASCAL, nhất là các cấu trúc điều khiển của ngôn ngữ lập trình như các cấu trúc chọn, các cấu trúc lặp.
Trong mã giả ta còn sử dụng cả các ký hiệu toán học, các biến, và đôi khi cả cấu trúc kiểu thủ tục. Cấu trúc thuật toán kiểu thủ tục thường được sử dụng để trình bày các thuật toán đệ qui hay các thuật toán quá phức tạp cần phải được trình bày thành nhiều cấp độ.
Cùng với việc sử dụng các biến, trong thuật toán rất thường gặp một phát biểu hành động đặt (hay gán) một giá trị cho một biến. Ví du:?hành động tăng biến i lên 1 đơn vị có thể được viết như sau:
i := i + 1
hay
i ? i + 1 (ít dùng)
Các cấu thường được sử dụng trong mã giả dựa theo ngôn ngữ lập trình PASCAL gồm:
1/ Cấu trúc chọn:
if (điều kiện) then (hành động)
if (điều kiện) then (hành động)
else (hành động)
2/ Cấu trúc lặp:
while (điều kiện) do (hành động)
Repeat
(hành động)
Until (điều kiện)
for (biến đếm) := (giá trị đầu) to (giá trị cuối) do (hành động)
for (biến đếm) := (giá trị cuối) downto (giá trị đầu) do (hành động)
3/ Cấu trúc nhảy goto. Ngoài ra người ta còn sử dụng lệnh ngắt vòng lặp break.
Dưới đây là các thuật toán được biểu diễn bằng mã giả (sử dụng các cấu trúc điều khiển của ngôn ngữ lập trình PASCAL). Trước khi viết các bước thực hiện thuật toán ta thường ghi rõ những gì được cho trước (phần nhập) và kết quả cần đạt được (phần xuất).
Thuật toán tìm phần tử lớn nhất trong một dãy hữu hạn các số nguyên:
Nhập: dãy số a1, a2, . . ., an
Xuất: max là giá trị lớn nhất trong dãy số đã cho trong input.
Thuật toán:
max := a1
for i := 2 to n do
if max < a1 then max := a1
max là giá trị lớn nhất trong dãy số.
Thuật toán giải phương trình bậc hai ax2 + bx + c = 0 (a ≠ 0):
Nhập : 3 hệ số a, b, c
Ðiều kiện : a ≠ 0
Xuất : nghiệm của phương trình
Thuật toán:
delta := b2– 4*a*c
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
esle 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;
(Trong thuật toán này, ký hiệu sqrt(delta) dùng để chỉ căn bậc hai dương của delta)
1.3 Các tính chất của thuật toán
Thuật toán có vai trò rất quan trọng trong khoa học máy tính. Ðể có thể lập trình giải bài toán trên máy tính, ta cần có một thuật toán bảo đảm những tính chất nhất định. Khi mô tả một thuật toán chúng ta cần chú ý đến các tính chất sau đây:
Nhập (input): Các thuật giải có các giá trị đầu vào (input values) từ một tập hợp nhất định nào đó.
Xuất (output): Từ mỗi tập hợp các giá trị được nhập một thuật toán thường tạo ra những giá trị kết quả (output values) thuộc một tập hợp nhất định nào đó thể hiện lời giải cho bài toán.
Tính xác định (definiteness): Các bước trong thuật toán phải chính xác rõ ràng.
Tính hữu hạn (finiteness): Thuật toán phải cho ra lời giải (hay kết quả) sau một số hữu hạn bước.
Tính hiệu quả (về thời gian): Thuật toán cần phải được thực hiện một cách chính xác và trong một khoảng thời gian cho phép.
Tính tổng quát. Thuật toán phải áp dụng được cho tất cả các bài toán có dạng như mong muốn, chứ không phải chỉ áp dụng được cho một số trường hợp đặc biệt nào đó.
Tính đúng: Thuật toán phải cho kết quả như mong muốn.
Trong các tính chất trên, 3 tính chất cơ bản của thuật toán đòi hỏi phải được thỏa mãn là tính xác định, tính hữu hạn và tính đúng.
Các thuật toán trong hai ví dụ 1 và 2 được trình bày ở trên đều thỏa mãn các tính chất nêu trên.
án sau đây:
Dùng ngôn ngữ tự nhiên.
Dùng lưu đồ hay sơ đồ khối.
Dùng mã giả.
Lưu đồ:
Ngôn ngữ lưu đồ hay sơ đồ khối là một công cụ rất trực quan để diễn đạt các thuật toán. Biểu diễn bằng lưu đồ sẽ giúp ta có được một cái nhìn tổng quan về toàn cảnh của quá trình xử lý theo thuật toán.
Lưu đồ là một hệ thống các nút có hình dạng khác nhau, thể hiện các chức năng khác nhau và được nối với nhau bởi các cung. Lưu đồ được tạo thành bởi 4 thành phần chủ yếu sau đây:
1/ Nút giới hạn: được biểu diễn bởi hình ôvan có ghi chữ bên trong như :
Các nút trên còn được gọi là nút đầu và nút cuối của lưu đồ.
2/ Nút thao tác: là một hình chữ nhật có ghi các lệnh cần thực hiện. Ví dụ:
3/ Nút điều kiện: thường là một hình thoi có ghi điều kiện cần kiểm tra. Trong các cung nối với nút này có 2 cung ra chỉ hướng đi theo 2 trường hợp: điều kiện đúng và điều kiện sai. Ví dụ:
4/ Cung: là các đường nối từ nút này đến nút khác của lưu đồ.
Hoạt động của thuật toán theo lưu đồ được bắt đầu từ nút đầu tiên. Sau khi thực hiện các thao tác hoặc kiểm tra điều kiện ở mỗi nút thì bộ xử lý sẽ theo một cung để đến nút khác. Quá trình thực hiện thuật toán dừng khi gặp nút kết thúc hay nút cuối.
Trong bài này chúng ta chủ yếu là sử dụng ngôn ngữ tự nhiên và mã giả để trình bày thuật toán. Trong cách sử dụng ngôn ngữ tự nhiên ta sẽ liệt kê các bước thực hiện các thao tác hay công việc nào đó của thuật toán bằng ngôn ngữ mà con người sử dụng một cách phổ thông hàng ngày. Các thuật toán được trình bày trong hai ví dụ trên chính là cách biểu diễn thuật toán dùng ngôn ngữ tự nhiên. Mặc dù cách biểu diễn này khá tự nhiên và không đòi hỏi người viết thuật toán phải biết nhiều quy ước khác, nhưng nó không thể hiện rõ tính cấu trúc của thuật toán nên không thuận lợi cho việc thiết kế và cài đặt những thuật toán phức tạp. Hơn nữa trong nhiều trường hợp việc biểu diễn thuật toán bằng ngôn ngữ tự nhiên tỏ ra dài dòng và dẽ gây ra sự nhầm lẫn đối với người đọc. Còn việc sử dụng lưu đồ sẽ rất cồng kềnh đối với các thuật toán phức tạp => chúng ta cần chọn phương thức thích hợp để biểu diễn thuật toán.
Mã giả:
Ðể biểu diễn thuật toán một cách hiệu quả, người ta thường dùng mã giả (pseudocode). Theo cách này, ta sẽ sử dụng một số qui ước của một ngôn ngữ lập trình, chẳng hạn là ngôn ngữ lập trình PASCAL, nhất là các cấu trúc điều khiển của ngôn ngữ lập trình như các cấu trúc chọn, các cấu trúc lặp.
Trong mã giả ta còn sử dụng cả các ký hiệu toán học, các biến, và đôi khi cả cấu trúc kiểu thủ tục. Cấu trúc thuật toán kiểu thủ tục thường được sử dụng để trình bày các thuật toán đệ qui hay các thuật toán quá phức tạp cần phải được trình bày thành nhiều cấp độ.
Cùng với việc sử dụng các biến, trong thuật toán rất thường gặp một phát biểu hành động đặt (hay gán) một giá trị cho một biến. Ví du:?hành động tăng biến i lên 1 đơn vị có thể được viết như sau:
i := i + 1
hay
i ? i + 1 (ít dùng)
Các cấu thường được sử dụng trong mã giả dựa theo ngôn ngữ lập trình PASCAL gồm:
1/ Cấu trúc chọn:
if (điều kiện) then (hành động)
if (điều kiện) then (hành động)
else (hành động)
2/ Cấu trúc lặp:
while (điều kiện) do (hành động)
Repeat
(hành động)
Until (điều kiện)
for (biến đếm) := (giá trị đầu) to (giá trị cuối) do (hành động)
for (biến đếm) := (giá trị cuối) downto (giá trị đầu) do (hành động)
3/ Cấu trúc nhảy goto. Ngoài ra người ta còn sử dụng lệnh ngắt vòng lặp break.
Dưới đây là các thuật toán được biểu diễn bằng mã giả (sử dụng các cấu trúc điều khiển của ngôn ngữ lập trình PASCAL). Trước khi viết các bước thực hiện thuật toán ta thường ghi rõ những gì được cho trước (phần nhập) và kết quả cần đạt được (phần xuất).
Thuật toán tìm phần tử lớn nhất trong một dãy hữu hạn các số nguyên:
Nhập: dãy số a1, a2, . . ., an
Xuất: max là giá trị lớn nhất trong dãy số đã cho trong input.
Thuật toán:
if max < a1 then max := a1
Thuật toán giải phương trình bậc hai ax2 + bx + c = 0 (a ≠ 0):
Nhập : 3 hệ số a, b, c
Ðiều kiện : a ≠ 0
Xuất : nghiệm của phương trình
Thuật toán:
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
Xuất kết quả: phương trình có nghiệm kép là -b / (2*a)
Xuất kết quả: phương trình vô nghiệm;
(Trong thuật toán này, ký hiệu sqrt(delta) dùng để chỉ căn bậc hai dương của delta)
1.3 Các tính chất của thuật toán
Thuật toán có vai trò rất quan trọng trong khoa học máy tính. Ðể có thể lập trình giải bài toán trên máy tính, ta cần có một thuật toán bảo đảm những tính chất nhất định. Khi mô tả một thuật toán chúng ta cần chú ý đến các tính chất sau đây:
Nhập (input): Các thuật giải có các giá trị đầu vào (input values) từ một tập hợp nhất định nào đó.
Xuất (output): Từ mỗi tập hợp các giá trị được nhập một thuật toán thường tạo ra những giá trị kết quả (output values) thuộc một tập hợp nhất định nào đó thể hiện lời giải cho bài toán.
Tính xác định (definiteness): Các bước trong thuật toán phải chính xác rõ ràng.
Tính hữu hạn (finiteness): Thuật toán phải cho ra lời giải (hay kết quả) sau một số hữu hạn bước.
Tính hiệu quả (về thời gian): Thuật toán cần phải được thực hiện một cách chính xác và trong một khoảng thời gian cho phép.
Tính tổng quát. Thuật toán phải áp dụng được cho tất cả các bài toán có dạng như mong muốn, chứ không phải chỉ áp dụng được cho một số trường hợp đặc biệt nào đó.
Tính đúng: Thuật toán phải cho kết quả như mong muốn.
Trong các tính chất trên, 3 tính chất cơ bản của thuật toán đòi hỏi phải được thỏa mãn là tính xác định, tính hữu hạn và tính đúng.
Các thuật toán trong hai ví dụ 1 và 2 được trình bày ở trên đều thỏa mãn các tính chất nêu trên.