Các đặc trưng khác của thuật toán
Bên cạnh 3 đặc trưng chính là xác định, hữu hạn và đúng, thuật toán còn có thêm 3 đặc trưng phụ khác. 1. Ðầu vào và đầu ra (input/output) : mọi thuật toán, dù có đơn giản đến mấy cũng phải nhận dữ liệu đầu vào, xử lý nó và cho ra kết quả cuối ...
Bên cạnh 3 đặc trưng chính là xác định, hữu hạn và đúng, thuật toán còn có thêm 3 đặc trưng phụ khác.
1. Ðầu vào và đầu ra (input/output) : mọi thuật toán, dù có đơn giản đến mấy cũng phải nhận dữ liệu đầu vào, xử lý nó và cho ra kết quả cuối cùng.
2. Tính hiệu quả (effectiveness) : tính hiệu quả của thuật toán được đánh giá dựa trên một số tiêu chuẩn như khối lượng tính toán, không gian và thời gian khi thuật toán được thi hành. Tính hiệu quả của thuật toán là một yếu tố quyết định để đánh giá, chọn lựa cách giải quyết vấn đề-bài toán trên thực tế. Có rất nhiều phương pháp để đánh giá tính hiệu quả của thuật toán. Trong mục 3 của chương , ta sẽ tìm hiểu một tiêu chuẩn được dùng rộng rãi là độ phức tạp của thuật toán.
3. Tính tổng quát (generalliness) : thuật toán có tính tổng quát là thuật toán phải áp dụng được cho mọi trường hợp của bài toán chứ không phải chỉ áp dụng được cho một số trường hợp riêng lẻ nào đó. Chẳng hạn giải phương trình bậc hai sau đây bằng Delta đảm bảo được tính chất này vì nó luôn giải được với mọi giá trị số thực a,b,c bất kỳ. Tuy nhiên, không phải thuật toán nào cũng đảm bảo được tính tổng quát. Trong thực tế, có lúc người ta chỉ xây dựng thuật toán cho một dạng đặc trưng của bài toán mà thôi.
1. Yêu cầu cho biết giá trị của 3 hệ số a, b, c
2. Nếu a=0 thì
2.1. Yêu cầu đầu vào không đảm bảo.
2.2. Kết thúc thuật toán.
3. Trường hợp a khác 0 thì
3.1. Tính giá trị D = b2-4ac
3.2. Nếu D > 0 thì
3.2.1. Phương trình có hai nghiệm phân biệt x1 và x2
3.2.2. Giá trị của hai nghiệm được tính theo công thức sau ;
X 1 = − b + Δ 2a size 12{X rSub { size 8{1} } = { { size 8{ - b+ sqrt {Δ} } } over { size 8{2a} } } } {}
3.2.3. Kết thúc thuật toán.
3.3. Nếu D = 0 thì
3.3.1. Phương trình có nghiệm kép x0
3.3.2. Giá trị của nghiệm kép là
3.3.3. Kết thúc thuật toán
3.4. Nếu D < 0 thì
3.4.1. Phương trình vô nghiệm.
3.4.2. Kết thúc thuật toán.
Vấn đề : Có n hộp có khối lượng khác nhau và một cái cân dĩa. Hãy chỉ ra cách cân để tìm được hộp có trọng lượng nặng nhất. Vấn đề này là thể hiện của một bài toán tổng quát : Cho một tập hợp A hữu hạn và một thứ tự toàn phần trên A. Hãy xây dựng thuật toán tìm phần tử lớn nhất của A. Bài toán trong toán học có vẻ rất phức tạp nhưng một thể hiện trên thực tế lại rất dễ hiểu, và cách giải quyết cũng đơn giản. Từ đó ta có thể dễ dàng suy ra cách giải bài toán tổng quát.
1. Nếu chỉ có 1 hộp (n=1) thì
1.1. Hộp đó chính là hộp nặng nhất.
1.2. Kết thúc thuật toán.
2. Ngược lại nếu có từ hai hộp trở lên (n>1)
2.1. Chọn hai hộp bất kỳ và đặt lên bàn cân.
2.2. Giữ lại hộp nặng hơn, cất hộp nhẹ hơn sang chỗ khác.
3. Nếu còn hộp chưa được cân thực hiện các bước sau, nếu không còn hộp nào nữa, sang bước 5.
3.1. Chọn một hộp bất kỳ và để lên dĩa cân còn trống.
3.2. Giữ lại hộp nặng hơn, cất hộp nhẹ hơn sang chỗ khác.
4. Trở lại bước 3.
5. Hộp còn lại trên cân chính là hộp nặng nhất. Kết thúc.
Bài toán : Cho hai số nguyên dương a và b. Tìm ước số chung lớn nhất của a và b.
1. Yêu cầu cho biết giá trị của a, b.
2. a0 = a
3. b0 = b
4. i = 0
5. Nếu ai khác bi thì thực hiện các thao tác sau, ngược lại qua bước 7.
5.1 Tăng i lên 1.
5.2. Nếu ai-1 > bi-1 thì
ai = ai-1 - bi-1
bi = bi-1
5.3. Ngược lại
bi = bi-1 - ai-1
ai = ai-1
6. Trở lại bước 5.
7. Ước số chung lớn nhất của a, b là ai .
