Trường Đại học Điện lực Tập đoàn Điện lực Việt Nam
Các đặc trưng của thuật giải
tải về 1.67 Mb.
|
- Điều hướng trang này:
- 3.3 Các phương pháp biểu diễn thuật giải
- 3.3.2 Lưu đồ - sơ đồ khối
- 3.3.3. Mã giả
3.2 Các đặc trưng của thuật giảiKnuth – tác giả của bộ sách nổi tiếng “Nghệ thuật lập trình” đã đưa ra 5 đặc trưng sau đây của thuật toán: 1. Input: Mỗi thuật giải cần có một số (có thể bằng không) dữ liệu vào. Đó là giá trị cần đưa vào khi thuật giải bắt đầu làm việc. Chẳng hạn trong thuật giải Euclid trên thì m và n là các dữ liệu vào 2. Output: Mỗi thuật giải cần có một hoặc nhiều dữ liệu ra. Đó là các giá trị có quan hệ xác định với giá trị vào và là kết quả của sự thực hiện thuật giải. Trong thuật giải Euclid thì dữ liệu ra là U. 3. Tính xác định: Mỗi bước của thuật giải cần phải được mô tả một cách chính xác, chỉ có một cách hiểu duy nhất. Bởi vì, nếu một bước có thể hiểu theo nhiều cách khác nhau, thì cùng một dữ liệu vào, những người thực hiện thuật giải khác nhau có thể cho ra kết quả khác nhau. Nếu ta mô tả thuật giải bằng ngôn ngữ tự nhiên, không có gì đảm bảo người đọc hiểu đúng ý của người viết thuật giải, bởi ngôn ngữ tự nhiên thường là đa nghĩa. Để đảm bảo đòi hỏi này, thuật giải cần được mô tả trong một ngôn ngữ lập trình, chẳng hạn một ngôn ngữ lập trình (Pascal, C...). trong các ngôn ngữ này, các mệnh đề được tạo thành theo các qui tắc cú pháp nghiêm nghặt và chỉ có một ý nghĩa duy nhất. 4. Tính khả thi: Tất cả các phép giải có mặt trong các bước của thuật giải phải đủ đơn giản. Điều đó có nghĩa là các phép giải phải sao cho, ít nhất về nguyên tắc có thể thực hiện được bởi con người trong một khoảng thời gian hữu hạn. Chẳng hạn trong thuật giải Euclid, ta chỉ cần thực hiện các phép chia các số nguyên, các phép gán và các phép so sánh. 5. Tính dừng: Với mọi bộ dữ liệu vào thoả mãn điều kiện qui định, thuật giải phải dừng lại sau một số hữu hạn bước thực hiện. Chẳng hạn đối với thuật giải Euclid là thuật giải thoả mãn điều kiện này. Bởi vì số dư r luôn nhỏ hơn n, nếu r0 thì giá trị của n ở bước sau là giá trị của r ở bước trước, ta có n>r=n1>r1=n2>r2.....Dãy số nguyên dương giảm dần cần phải kết thúc ở 0, do đó sau một số bước giá trị của r=0 thuật giải dừng. 3.3 Các phương pháp biểu diễn thuật giải3.3.1 Ngôn ngữ tự nhiênTrong cách biểu diễn thuật giải 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 giải (Các ví dụ về thuật giải trong mục 1 của chương sử 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 giải cũng như người đọc thuật giải 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 giải, đôi lúc gây hiểu lầm hoặc khó hiểu cho người đọc. Gần như không có một quy tắc cố định nào trong việc thể hiện thuật giải bằng ngôn ngữ 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ó thể 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 giải theo ngôn ngữ tự nhiên. 3.3.2 Lưu đồ - sơ đồ khốiLưu đồ hay sơ đồ khối là một công cụ trực quan để diễn đạt các thuật giải. Biểu diễn thuật giải 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 giải. Phương pháp lưu đồ thường được dùng trong những thuật giải có tính rắc rối, khó theo dõi được quá trình xử lý. Vẽ lưu đồ hoặc sơ đồ khối, mỗi khối mô tả một bước. Sử dụng mũi tên nối khối này với khối kia để chỉ trình tự thực hiện các bước. Để dễ dàng nhận biết chức năng của từng khối, mỗi khối được thể hiện ở một dạng như sau: - - Kết thúc 
- Thực hiện công việc 
- Điều kiện Ví dụ 3.1:. Tìm nghiệm thực của phương trình bậc hai ax2+bx+c=0. Thuật toán được dạy gồm các bước sau: + Nhập dữ liệu a, b, c. + Tính biệt số = b2-4ac. + So sánh với 0. Bước tiếp theo sẽ phụ thuộc vào giá trị của . + Nếu <0, đáp số của bài toán là “Vô nghiệm”. + Nếu =0, tính và ghi đáp số trị của nghiệm kép + Nếu >0, tính và ghi đáp số trị của hai nghiệm phân biệt:
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 dùng một không gian rất lớn. 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 hiểu chính xác thuật toán. Tất nhiên là trong mã giả ta vẫn dùng một phần ngôn ngữ 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ề thủ tục - hàm bạn sẽ hiểu mã giả là gì !
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 Каталог: images images -> Hướng dẫn sử dụng Dropbox Để sử dụng được Dropbox images -> BÀi thuyết trình cách xáC ĐỊnh và chế ĐỘ pháp lý CỦa các vùng biển theo công ưỚc của liên hiệp quốc về luật biển năM 19821 images -> Céng hßa x· héi chñ nghÜa viÖt nam Độc lập tự do hạnh phúc images -> Lúa gạo Việt Nam Giới thiệu images -> Trung Tâm kt tc-đl-cl images -> Số: 105/2008/QĐ-ttg CỘng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh phúc images -> ChuyêN ĐỀ ĐẠi số TỔ HỢP, XÁc suất kiến thức cơ bản Đại số tổ hợp images -> BỘ giáo dục và ĐÀo tạo trưỜng đẠi học luật tp. HỒ chí minh dưƠng kim thế nguyên thủ TỤc phá SẢn các tổ chức tín dụng theo pháp luật việt nam images -> Review of Condor, Sun Grid Engine and pbs tải về 1.67 Mb. Chia sẻ với bạn bè của bạn:
|
Bắt đầu
.
.
