Giáo án Tin học 10: Trình bày Thuật toán

$4b. Trình bày Thuật toán (Tóm tắt các cách trình bày) Trong tin học, bài toán là một việc mà ta muốn máy tính thực hiện. Cho một bài toán là mô tả đầu vào (Input) và yêu cầu của đầu ra (Output) Ví dụ đơn giản: Giải phương trình ax2 + bx + c = 0. Nếu mình muốn giao cho máy tính làm thì phải nhập các hệ số a, b, c cho máy, rổi máy đưa kết quả ra ngay, ta không cần phải tự tay tính toán gì hết. Tuy nhiên ta phải “dạy” cho máy cách làm “tổng quát” để khi ta đưa a, b, c thế nào cho nó thì cũng phải ra kết quả! Việc chỉ ra một cách tường minh lời giải của một bài toán gọi là thuật toán (Algorithm) giải bài toán đó. SGK đã nêu một định nghĩa chính thức như sau: Thuật toán đẻ giải một bài toán là một dãy hữu hạn các tháo tác, được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm! Chú ý: Chương trình có khác với thuật toán ở chỗ: Chương trình thì nêu lên các bước giải, có thể không tường minh. Trả lời câu hỏi lần lượt làm những gì? Thuật toán nêu bật phương pháp (mưu mẹo) qua các bước tường minh, và trả lời câu hỏi làm thế nào? Thuật toán có thể chỉ nêu một phần của chương trình! Cùng một bài toán có thể có nhiều thuật toán khác nhau! Thuật toán tối ưu là thuật toán giúp máy tính thực hiện nhanh nhất, tốn ít bộ nhớ nhất. Có 3 cách trình bày một thuật toán: Diễn giải thành từng bước: Các bước được thực hiện tuần tự hoặc nhảy đến bước trước hay sau nhưng xa hơn sau khi gặp một điều kiện nào đó. Vẽ sơ đồ khố (lưu đồ): Khoanh hình tròn hay elíp để bắt đầu hay kết thúc, hình thoi để chứa điều kiện, hình chữ nhật chứa công việc, và đoạn thẳng hay véo tơ chỉ đường đi. Giả lập trình: Dùng các cấu trúc của ngôn ngữ lập trình bậc cao, các kí hiệu toán học và ngôn ngữ tự nhiên. Cách này gọn gàng hơn. Nhà quản lý, nhà doanh nghiệp hay nhà khoa học, nên nắm chắc được ít nhất một trong các cách trình bày thuật toán nêu trên. Sau đây là một ví dụ đơn giản về chương trình và so sánh 2 thuật toán khác nhau: Ví dụ: Tính trung bình cộng của n số tự nhiên đầu tiên, n>1 nhập từ bàn phím. Chương trình: Bước 1. Nhập n từ bàn phím. Bước 2. Tính tổng s = 1+2++n. Bước 3. Tính kết quả = s/n. Bước 4. Đáp số: kq. Chú ý: Ta có thể dùng kí hiệu mũi tên ngược để mô ta phép gán giá trị của một biểu thức cho một đại lượng có đặt tên (còn gọi là biến). Ví dụ: Tăng k thêm 1 đơn vị, ta có thể viết: k ¬ k+1. Trong ngôn ngữ lập trình C/C++, ta viết luôn k=k+1. Trong Pascal, ta viết k:=k+1. Sau đây, ta đề cập các một phần chương trình trên, ở bước 2: Tính tổng s = 1+2+..+n. Có các thuật toán sau: Thuật toán 1. (Cơ bắp – cộng dồn): Bước 1. S ¬ 0, k ¬ 1. (Tức là cho S = 0 và cho k = 1). Bước 2. S ¬ S+k. (Tức là cho S mới = S cũ + k). Bước 3. k ¬ k+1. (Tức là tăng k lên 1 đơn vị). Bước 4. Nều k > n thì thu lấy giá tị của S và kết thúc! Trái lại thì quay về thực hiện bước 2. Cách làm trên, phải mất n-1 phép cộng, vô cùng vất vả khi n rất lớn! Chẳng hạn n = 1 triệu, phải mất gần 1 triệu phép cộng! Thuật toán 2. (Carl_Friedrich_Gauss) Bước 1. S ¬ (1+n)*n/2. Chỉ cần một bước! Trên đây là thuật toán tính tổng của một dãy số có quy luật, thì mới sử dụng công thức toán học được. Chỉ trừ không giỏi toán thì mới phải làm theo thuật toán “cơ bắp”. Cho nên, việc kết hợp toán học và tin học là rất có lợi! Một người rất giỏi tin, nhưng lại không giỏi toán thì vẫn tạo ra các thuật toán để giải bài toán tin học, nhưng thường dài dòng và làm cho máy chạy lâu hơn, tốn nhiều bộ nhớ hơn, không tối ưu! 3.- Một số ví dụ Ngoài các ví dụ trong SGK, từ trang 33 đến trang 44). Mình xin nêu một số ví dụ khác để giúp bạn biết cách trình bày thuật toán. Ví dụ 1. Nhập dãy số a1, , an, với n > 1. Nêu thuật toán đếm các số hạng có giá trị bằng 0. Cách1. Bước 1. Nhập n và dãy số an, , an. Bước 2. k ¬ 1, d ¬ 0. (d sẽ là số lượng các số hạng = 0). Bước 3. Nếu ak = 0 thì d ¬ d+1. Bước 4. k ¬ k+1. Bước 5. Nếu k > n thì đáp số là d và kết thúc. Trái lại quay về Bước 3. Cách 2. (Lưu đồ. Chú ý; dấu + là cho trường hợp điều kiện đúng, - nếu sai). Nhập n và dãy số an, , an k ¬ 1, d ¬ 0 k ¬ k+1 ak=0 d ¬ d+1 + -0 -0 - k>n + Đáp số có d sh = 0 Cách 3. (Giả lập trình) Bước 1. Nhập n và dãy số an, , an. Bước 2. d ¬ 0. (d sẽ là số lượng các số hạng = 0). Bước 3. Cho k chạy từ 1 đến n. (Duyệt từ đầu dãy đến cuối dãy). Với mỗi k đó xét ak: Nếu ak = 0 thì d ¬ d+1. Bước 4. Đáp số: Có d số hạng bằng 0. Các bài tập tương tự: Nhập dãy số a1, , an, với n > 1. Nêu thuật toán tính tổng tất cả các số hạng. Nêu thuật toán tính tổng tất cả các số hạng âm. Nêu thuật toán tính tổng tất cả các số hạng dương. Nêu thuật toán tính tổng nghịch đảo các số hạng khác không. Nêu thuật toán tính tổng các căn bậc 2 của các số hạng dương Nêu thuật toán tính tổng các bình phương các số hạng âm. Bạn có thể tự nghĩ ra thêm! Ví dụ 2. Nhập dãy số a1, , an, với n>1. Nêu thuật toán xét xem có số hạng nào bằng 0. (Chỉ cần có hay không, không cần biết nhiều hay ít). Cách1. Bước 1. Nhập n và dãy số an, , an. Bước 2. k ¬ 1. Bước 3. Nếu ak = 0 thì đáp số là có và kết thúc. Bước 4. k ¬ k+1. Bước 5. Nếu k £ n thì về Bước 3. Trái lại đáp số là không có. Cách 2. (Lưu đồ). Nhập n và dãy số an, , an k ¬ 1 k ¬ k+1 ak=0 + -0 Đáp số có. Kết thúc. -0 k>n + - Đáp số không có. Hết. Cách 3. (Giả lập trình) Bước 1. Nhập n và dãy số an, , an. (Nhớ giả thiết sẵn n > 1). Bước 2. k ¬ 1. Bước 3. Chừng nào (ak ¹ 0) và (k £ n) thì k ¬ k+1. (Lặp lại khi điều kiện vẫn còn thỏa nãn). (Giống như còn “đói” và “khát” thì còn làm việc xác định đó). Bước 4. Bước 3 kết thúc (hết lặp) là lúc mà (ak = 0) hoặc (k > n). Khi đó, suy ra ngay: Nếu k>n thì trả lời không có Trái lại trả lời có phần tử ak (với k nhận được phút cuối) là bằng 0.. Ví dụ 3. Nhập dãy số a1, , an, với n > 1. Nêu thuật toán tìm số hạng bằng 0 cuối cùng. Tức là trong các số hạng bằng 0 thì tìm số hạng bằng 0 cuối cùng, k =?. Cách1. Bước 1. Nhập n và dãy số an, , an. (Nhớ giả thiết sẵn n > 1). Bước 2. k ¬ n. Bước 3. Nếu ak = 0 thì đáp số là có số hạng thứ k đó bằng 0 và kết thúc. Bước 4. k ¬ k-1. (Tức là k giảm đi 1 đơn vị) Bước 5. Nếu k > 0 thì về Bước 3. Trái lại đáp số là không có. Cách 2. (Lưu đồ). Nhập n và dãy số an, , an k ¬ n k ¬ k-1 ak=0 + -0 Đáp số ak=0. Hết -0 k=0 + - Đáp số ko có. Hết. Cách 3. (Giả lập trình) Bước 1. Nhập n và dãy số an, , an. Bước 2. k ¬ n. Bước 3. Chừng nào (ak ¹ 0) và (k > 0) thì k ¬ k-1. (While (ak ¹ 0) and (k > 0) do k:=k-1) Bước 4. Bước 3 kết thúc là lúc mà (ak = 0) hoặc (k = 0). Nếu k = 0 thì trả lời không có, trái lại trả lời có số hạng thứ k đó bằng 0. Các bài tập tương tự: Nhập dãy số a1, , an, với n>1, và một số b. Nêu thuật toán tính tìm số hạng đầu tiên bằng b. Nêu thuật toán tính tìm số hạng cuối cùng bằng b. Nêu thuật toán tính tìm số hạng nào mà bình phương lên sẽ bằng b. Nêu thuật toán tính tìm số hạng nào mà căn bậc 2 của nó bằng b. Nêu thuật toán tính tìm số hạng nào mà ngịch đảo sẽ bằng b. Bạn có thể tự nghĩ ra thêm! Ví dụ 4. Nhập dãy số a1, , an, với n > 1. Nêu thuật toán xem đây có phải là dãy số tăng dần không? Cách1. Bước 1. Nhập n và dãy số an, , an. Bước 2. k ¬ 1. Bước 3. Nếu ak ³ ak+1 thì trả lời là không tăng và kết thúc. (Gặp trường hợp đầu tiên không tăng). Bước 4. k ¬ k+1. Bước 5. Nếu k < n thì về Bước 3. Trái lại trả lời đây là dãy tăng, vì không gặp trường hợp nào ak ³ ak+1. Cách 2. Mình nghĩ là bạn đã vẽ được lưu đồ. Từ giờ, bạn tự vẽ lấy! Cách 3. (Giả lập trình) Bước 1. Nhập n và dãy số an, , an. Bước 2. k ¬ 1. Bước 3. Chừng nào (ak < ak+1) và (k < n) thì k ¬ k+1. Bước 4. Bước 3 kết thúc là lúc mà (ak ³ ak+1) hoặc (k = n). Nếu k = n thì trả lời đây là dãy tăng, vì không gặp trường hợp nào ak ³ ak+1. Trái lại trả lời không phải dãy tăng, vì gặp trường hợp nào ak ³ ak+1. Các bài tập tương tự: Nhập dãy số a1, , an, với n>1. Nêu thuật toán tính xét xem dãy này có giảm không (a1 > a2 > a3 >> an). Nêu thuật toán tính xét xem dãy này có là cấp số cộng không. Nêu thuật toán tính xét xem dãy này có là dãy không không đổi không. (a1 = a2 = a3 == an). Nêu thuật toán tính xét xem dãy này có là cấp số nhân không. Nêu thuật toán tính xét xem dãy này có số hạng nào gấp đôi số hạng tiếp theo không. Nêu thuật toán tính xét xem dãy này có số hạng nào bằng bình phương số hạng tiếp theo không. Nêu thuật toán tính xét xem dãy này có số hạng nào bằng căn bậc 2 của số hạng tiếp theo không. Nêu thuật toán tính xét xem dãy này có số hạng nào gấp đôi số hạng trước nó không. Nêu thuật toán tính xét xem dãy này có số hạng nào bằng bình phương số hạng trước nó không. Nêu thuật toán tính xét xem dãy này có số hạng nào bằng căn bậc 2 của số hạng trước nó không. Bạn có thể tự nghĩ ra thêm! Ví dụ 5. Nhập dãy số a1, , an, với n > 1. Nêu thuật toán tìm min của các số hạng âm nếu có? Cách1. Bước 1. Nhập n và dãy số an, , an. Bước 2. k ¬ 1. Bước 3. Nếu ak ³ 0 thì làm 2 việc: k ¬ k+1 và xét k: nếu k > n thì trả lời là không số hạng nào âm và kết thúc, trái lại về Bước 3. Bước 4. min ¬ ak. Bước 5. k ¬ k+1. Khi đó: nếu k > n thì đáp số min ra và kết thúc. Bước 6. Nếu ak < 0 thì về Bước 4, trái lại thì về Bước 5. Cách 2. Bạn tự vẽ lấy! Cách 3. (Giả lập trình) Bước 1. Nhập n và dãy số an, , an. Bước 2. k ¬ 1. Bước 3. Chừng nào (ak ³ 0) và (k £ n) thì k ¬ k+1. (Để tìm ak âm đầu tiên hoặc không có). Bước 4. Bước 3 kết thúc chính là lúc mà có (ak n). Nếu k > n thì trả lời dãy không có số hạng âm nào và kết thúc. Bước 5. min ¬ ak. Bước 6. Duyệt từ k+1 đến n: nếu gặp ak < min thì về Bước 5. Bước 7. Sau khi duyệt thì đáp số min. Các bài tập tương tự: Nhập dãy số a1, , an, với n>1. Nêu thuật toán tìm max của các số hạng dương. Nêu thuật toán tìm max của các số hạng âm. Nêu thuật toán tìm min của các số hạng dương. Nêu thuật toán tìm max của các số hạng lớn hơn 1. Nêu thuật toán tìm min của các số hạng lớn hơn 1. Nêu thuật toán tìm max của các số hạng nhỏ hơn 1. Nêu thuật toán tìm min của các số hạng nhỏ hơn 1. Bạn có thể tự nghĩ ra thêm! Ví dụ 6. Nhập dãy số a1, , an, với n > 1. Thiết kế thuật toán xét xem dãy có 2 số hạng nào bằng nhau không? (Không cần liên tiếp!) Cách1. Bước 1. Nhập n và dãy số an, , an. Bước 2. i ¬ 1. Bước 3. j ¬ i+1. Bước 4. Nếu ai = aj thì trả lời là có và kết thúc, Bước 5. j ¬ j+1.. Bước 6. Nếu j £ n thì về Bước 4 Trái lại thì xét i: Nếu i = n-1 thì trả lời là không có và kết thúc, Trái lại: i ¬ i+1 và về Bước 3. Cách3 (Giả lập trình). Bước 1. Nhập n và dãy số an, , an. Bước 2. Duyệt i từ 1 đến n-1: (For i:=1 to n-1 do) Với mỗi i đó: Duyệt j từ i+1 đến n: (For j:=i+1 to n do) Với mỗi j đó: Nếu ai = aj thì trả lời là có và kết thúc. Bước 3. Duyệt xong mà không bị kết thúc thì rõ ràng là không có. Chú ý: Việc duyệt 2 vòng lồng nhau như trên có thể gặp ở một số bài toán như: Nhập dãy số a1, , an, với n>1. Nêu thuật toán xét xem dãy có 2 số hạng nào nghịch đảo của nhau không. Nêu thuật toán xét xem dãy có 2 số hạng nào đối nhau không. Thậm chí có thể Duyệt 3 vòng lồng nhau như: Tìm bộ 3 số tự nhiên x,y,z (0 < x < y < z < 100) là bộ số Pitago, tức là x2 + y2 = z2. Cách3 (Giả lập trình). Có thể viết phối hợp ngôn ngữ tự nhiên, toán học và tiếng Anh: For x = 1 to 98 do (Ta hiểu là với mỗi giá trị của x từ 1 đên 98, hãy làm việc sau:) For y = x+1 to 99 do (Ta hiểu là với mỗi giá trị của y từ 1 đên 99, hãy làm việc sau:) For z = y+1 to 100 do (Ta hiểu là với mỗi giá trị của z từ 1 đên 100, hãy làm việc sau:) Xét bộ (x,y,z) đó: Nếu x2 + y2 = z2 thì thông báo bộ số (x,y,z) đó ra. www.lightsmok.wordpress.com