GIẢI THUẬT

Khái niệm giải thuật Giải thuật là một hệ thống chặt chẽ và rõ ràng các quy tắc nhằm xác định một dãy các thao tác trên những dữ liệu vào sao cho sau một số hữu hạn bước thực hiện các thao tác đó ta thu được kết quả của bài toán.

Ví dụ 1: Giả sử có hai bình A và B đựng hai loại chất lỏng khác nhau, chẳng hạn bình A đựng rượu, bình B đựng nước mắm. Giải thuật để hoán đổi (swap) chất lỏng đựng trong hai bình đó là:

• Yêu cầu phải có thêm một bình thứ ba gọi là bình C.

• Bước 1: Đổ rượu từ bình A sang bình C.

• Bước 2: Đổ nước mắm từ bình B sang bình A.

• Bước 3: Đổ rượu từ bình C sang bình B.

Ví dụ 2: Một trong những giải thuật tìm ước chung lớn nhất của hai số a và b là:

• Bước 1: Nhập vào hai số a và b. 7/199

• Bước 2: So sánh 2 số a,b chọn số nhỏ nhất gán cho UCLN.

• Bước 3: Nếu một trong hai số a hoặc b không chia hết cho UCLN thì thực hiện bước 4, ngược lại (cả a và b đều chia hết cho UCLN) thì thực hiện bước 5.

• Bước 4: Giảm UCLN một đơn vị và quay lại bước 3

• Bước 5: In UCLN - Kết thúc. Các đặc trưng của giải thuật

• Tính kết thúc: Giải thuật phải dừng sau một số hữu hạn bước.

• Tính xác định: Các thao tác máy tính phải thực hiện được và các máy tính khác nhau thực hiện cùng một bước của cùng một giải thuật phải cho cùng một kết quả.

• Tính phổ dụng: Giải thuật phải "vét' hết các trường hợp và áp dụng cho một loạt bài toán cùng loại.

• Tính hiệu quả: Một giải thuật được đánh giá là tốt nếu nó đạt hai tiêu chuẩn sau:

- Thực hiện nhanh, tốn ít thời gian.

- Tiêu phí ít tài nguyên của máy, chẳng hạn tốn ít bộ nhớ. Giải thuật tìm UCLN nêu trên đạt tính kết thúc bởi vì qua mỗi lần thực hiện bước 4 thì UCLN sẽ giảm đi một đơn vị cho nên trong trường hợp xấu nhất thì UCLN=1, giải thuật phải dừng. Các thao tác trình bày trong các bước, máy tính đều có thể thực hiện được nên nó có tính xác định. Giải thuật này cũng đạt tính phổ dụng vì nó được dùng để tìm UCLN cho hai số nguyeên dương a và b bất kỳ. Tuy nhiên tính hiệu quả của giải thuật có thể chưa cao; cụ thể là thời gian chạy máy có thể còn tốn nhiều hơn một số giải thuật khác mà chúng ta sẽ có dịp trở lại trong phần lập trình C.