Đề tài Lựa chọn và thiết kế thuật toán

Thuaät toaùn GV: Huøynh Minh Taân Trang: 1 THUẬT TOÁN I. LÝ DO CHỌN SÁNG KIẾN. Ngày nay, công nghệ thông tin được ứng dụng rộng rãi trong thực tế ở nhiều lĩnh vực. Để đáp ứng nhu cầu đó của xã hội, môn Tin học đã được đưa vào trường trung học phổ thông nhằm bước đầu cung cấp cho các em học sinh những kiến thức cơ bản. Tuy nhiên, do đặc trưng của môn học có những khái niệm trừu tượng nên các em gặp nhiều khó khăn trong quá trình tiếp thu bài. Đặc biệt trong chương trình Tin học 11, khi học phần lập trình đòi hỏi phải tư duy thì khó khăn nhất đối với các em là bước “Lựa chọn và thiết kế thuật toán”. Việc lựa chọn và thiết kế thuật toán để giải bài toán trên máy tính là một bước rất quan trọng. Bởi vì nếu bỏ qua bước này thì đôi khi việc lập trình cho ra kết quả không tối ưu. Cũng giống như khi giải một bài tập toán, vật lý,... để tìm ra kết quả chính xác thì buộc học sinh phải xác định công thức cần áp dụng là công thức nào. Khi nắm vững cách lựa chọn và thiết kế thuật toán, các em học sinh có thể dễ dàng viết chương trình để giải bài toán trên máy tính bằng bất kỳ ngôn ngữ bậc cao nào. Làm được việc này sẽ kích thích sự hứng thú học môn Tin học hơn. Điều quan trọng hơn, việc lựa chọn và thiết kế thuật toán để giải bài toán trên máy tính giúp rèn luyện cho học sinh khả năng tư duy, sáng tạo, biết phân tích và giải quyết tình huống. Đây là những kỹ năng rất cần thiết để sau này các em hoà nhập vào thực tế cuộc sống. Từ những lý do nêu trên, qua thực tế giảng dạy bản thân tôi thấy cần đưa ra một số kinh nghiệm để trao đổi với các đồng nghiệp nhằm giúp học sinh bước đầu hiểu rõ và tiếp cận với thuật toán giải bài toán để việc lập trình đạt kết quả tốt hơn. Vì thời gian có hạn, tôi chỉ trình bày cách xây dựng thuật toán để giải bài toán bằng cách lập sơ đồ khối. Trong phần trình bày của tôi không tránh khỏi những thiếu sót. Tôi rất mong sự trao đổi, góp ý của quý thầy cô đồng nghiệp. Tôi xin chân thành cảm ơn. Thuaät toaùn GV: Huøynh Minh Taân Trang: 2 II.THỰC TRẠNG TRƯỚC KHI THỰC HIỆN CÁC GIẢI PHÁP CỦA SÁNG KIẾN 1) Thuận lợi:  Toàn ngành, toàn xã hội đang đề cao việc ứng dụng công nghệ thông tin vào tất cả các lĩnh vực.  Môn Tin học là môn chính khoá trong trường phổ thông.  Các em học sinh thích được thực hành trên máy tính để nghiên cúu tìm tòi.  Ngôn ngữ bậc cao trong môn Tin học gần gũi với ngôn ngữ giao tiếp trong cuộc sống. 2) Khó khăn:  Máy vi tính và các thiết bị hổ trợ còn hạn chế  Phần lập trình hoàn toàn xa lạ với học sinh. 3) Số liệu thống kê Qua các lớp tôi đang dạy, khi học đến phần lập trình Pascal đa số các em học sinh còn lúng túng khi viết một chương trình. Đặc biệt là khái niệm về bài toán và thuật toán, các em chưa nắm vững và hay bỏ quên bước này. Do đó khi viết chương trình, sản phẩm thu được chưa đảm bảo tính tối ưu. III. NỘI DUNG ĐỀ TÀI 1) Cơ sở lý luận  Đa số các câu nói hàng ngày của con người như: “Các bước để vá một ruột xe bị lủng”, “Nếu.thì”, “Nếuthìngược lại”, “Trong khi .thì làm.” đều có thể diển đạt bằng ngôn ngữ Sơ đồ khối .  Điều quan trọng là khi đã xây dựng được thuật toán bằng sơ đồ khối thì ta có thể sử dụng bất kỳ một ngôn ngữ bậc cao nào cũng viết được chương trình một cách rất thuận tiện và đảm bảo tính tối ưu. 2). Noäi dung,biện pháp thực hiện các giải pháp cuûa saùng kieán. Thuaät toaùn GV: Huøynh Minh Taân Trang: 3 TÓM TẮT LÝ THUYẾT A) BAØI TOAÙN.  Trong phạm vi tin học, có thể quan niệm bài toán là một việc nào đó mà ta muốn máy tính thực hiện.  Khi dùng máy tính giải bài toán, ta cần quan tâm đến hai yếu tố: o Đưa vào máy thông tin gì (Input) o Cần lấy ra thông tin gì (Output). B) THUAÄT TOAÙN a). Thuật toán để giải một bài toán là một dãy hữu hạn các thao 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. Những đặc trưng cơ bản của thuật toán:  Tính tổng quát: Thuật toán không đề cập chỉ một bài toán riêng lẽ mà bao hàm một lớp bài toán cùng một kiểu,  Có giới hạn: Quá trình biến đổi từ thông tin ban đầu đến kết quả cuối cùng qua một số giới hạn các biến đổi.  Tính duy nhất: Toàn bộ quá trình biến đổi, cũng như trình tự thực hiện phải được xác định và là duy nhất. Như vậy khi dùng thuật toán cùng một tin tức ban đầu phải có cùng một kết quả.Trong thuật toán ở mỗi giai đoạn phải nêu chính xác các bước tiếp theo, có nghĩa là thứ tự thực hiện, các thao tác và quyết định phải được quy định rõ ràng.  Tính đúng đắn: Sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm. Thuật toán có thể phân loại như sau:  Thuật toán không phân nhánh  Thuật toán có phân nhánh  Thuật toán theo chu trình có bước lặp xác định và có bước lặp không xác định. Thuật toán không phân nhánh là thuật toán đơn giản nhất. Trong thực tế thường gặp thuật toán phân nhánh theo các điều kiện so sánh đúng Thuaät toaùn GV: Huøynh Minh Taân Trang: 4 hoặc sai. Phổ biến nhất trong các bài toán thực tế là thuật toán gồm nhiều chu trình , theo nhiều nhánh, đó là đặc trưng của thuật toán giaỉ các bài toán khoa học kỷ thuật b). Các kí hiệu để diễn tả thuật toán bằng sơ đồ khối. Thể hiện thao tác so sánh Thể hiện các phép tính toán Thể hiện các thao tác nhập, xuất dữ liệu Quy định trình tự thực hiện các phép toán Lưu ý:  Với hình ô van thì chỉ có một hướng mũi tên đi ra cho trường hợp thao tác nhập dữ liệu và chỉ có một hướng đi vào cho thao tác xuất dữ liệu  Với hình chữ nhật thì có một hướng mũi tên vào và một hướng mũi tên ra  Với hình thoi thì có một hướng mũi tên vào và hai hướng mũi tên ra Thuaät toaùn GV: Huøynh Minh Taân Trang: 5 MỘT SỐ VÍ DỤ VỀ LỰA CHỌN VÀ THIẾT KẾ THUẬT TOÁN . Thuật toán không phân nhánh VD1: Cho A=x2+y2; B=x+y+3A; C=xy+A-2B2; x,y R. Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối để tính C * Xác định bài toán  Input: x,y  Output: C Lưu ý: Muốn tính được C thì đầu tiên ta phải tính A và B Sơ đồ khối VD2: Nhập x, y Ax*x+y*y Bx+y+3*A Cx*y+A-2*B*B Thông báo C rồi kết thúc Thuaät toaùn GV: Huøynh Minh Taân Trang: 6 Tính vận tốc v khi chạm đất của một vật rơi từ độ cao h, biết rằng v= gh2 , trong đó g là gia tốc rơi tự do và g = 9.8 m/s2. Độ cao h được nhập từ bàn phím. Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối. * Xác định bài toán  Input: h  Output: v Lưu ý: Ta có thể khai báo g là hằng số hoặc không cũng được Sơ đồ khối BÀI TẬP ĐỀ NGHỊ Hãy mô tả thuật toán giải các bài toán sau bằng sơ đồ khối: Bài 1: Nhập từ bàn phím độ dài 3 cạnh của tam giác ABC, rồi tính chu vi, diện tích và các đường cao của tam giác. Hướng dẫn: - Input: độ dài 3 cạnh a,b,c - Output: chuvi, dientich, các đường cao ha,hb,hc - Sử dụng các công thức: Chu vi: 2p=a+b+c; Diện tích: s = p(p-a)(p-b)(p-c) ; Các đường cao: ha= a s2 ; , hb= b s2 ; hc= c s2 ; Bài 2 Nhập từ bàn phím toạ độ 3 điểm A,B,C. Tính tích vô hướng của hai vectơ AB và AC . Hướng dẫn: Nhập h v  sqrt(2*9.8*h) Thông báo v rồi kết thúc Thuaät toaùn GV: Huøynh Minh Taân Trang: 7 - Input: Toạ độ 3 điểm A, B và C; - Output: Tích vô hướng ACAB. ; - Sử dụng các công thức: vectơ: B A B AAB=(x -x ;y -y ) uuur ; C A C AAC=(x -x ;y -y ) uuur ; Tích vô hướng: B A C A B A C AAB.AC=(x -x ).(x -x )+(y -y ).(y -y ) uuur uuur ; Bài 3 Nhập từ bàn phím toạ độ 3 điểm A,B,C. Tính độ dài các đoạn thẳng AB,AC và BC. Hướng dẫn: - Input: Toạ độ 3 điểm A, B và C; - Output: Độ dài các đoạn thẳng AB,AC và BC - Sử dụng các công thức: AB= 2 2B A B AAB = (x -x ) +(y -y ) uuur ; Bài 4 Giải tam giác khi biết góc B, cạnh a và góc C. Hướng dẫn - Input: Góc B , C và cạnh a; - Output: Góc A, cạnh b và c - Sử dụng các công thức: * Đổi độ ra rad : 180 . ; * A+B+C=180 0 ; * a b c = = sinA sinB sinC ; Thuaät toaùn GV: Huøynh Minh Taân Trang: 8 . Thuật toán có phân nhánh Sơ đồ: Dạng thiếu Dạng đủ Chú ý:  Ta có thể sử dụng cấu trúc rẽ nhánh lồng nhau Sai Đúng Điều kiện Câu lệnh Sai Đúng Điều kiện Câu lệnh 1 Câu lệnh 2 Thuaät toaùn GV: Huøynh Minh Taân Trang: 9 VD3: Tìm số lớn nhất trong hai số thực A và B Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối * Xác định bài toán  Input: A,B  Output: Số lớn nhất trong hai số Sơ đồ khối Đ S Nhập A,B A>=B Lớn nhất là B và kết thúc Lớn nhất là A và kết thúc Thuaät toaùn GV: Huøynh Minh Taân Trang: 10 VD4: Tìm số lớn nhất trong ba số thực A , B và C Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối * Xác định bài toán  Input: ba số thực A,B,C  Output: Số lớn nhất trong ba số Sơ đồ khối Đ Đ S S S Đ Nhập A,B,C A > B B > C A > C Max  A Max  C Max  B Thông báo Max và kết thúc Thuaät toaùn GV: Huøynh Minh Taân Trang: 11 VD5: Cho phương trình bậc hai ax2+bx+c=0 Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối * Xác định bài toán  Input: a,b,c (a0)  Output: Nghiệm x thoả phương trình ax2+bx+c=0 Sơ đồ khối S Đ S Đ Nhập a,b,c (a0) Db*b-4*a*c D<0 Thông báo PT vô nghiệm rồi kết thúc D=0 Thông báo PT có nghiệm kép x rồi kết thúc x-b/(2*a) x1(-b+sqrt(D))/(2*a) x2(-b-sqrt(D))/(2*a) Thông báo PT có 2 nghiệm x1 và x2 rồi kết thúc Thuaät toaùn GV: Huøynh Minh Taân Trang: 12 nếu nếu nếu 2 2 2 2 2 2 2 2 x y ; x y 1 z x y; x y 1 và y x 0.5; x y 1 và y x               VD6: Cho bài toán Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối * Xác định bài toán  Input: x,y;  Output: z Sơ đồ khối S Đ Đ S Nhập x, y x*x+y*y<=1 Thông báo z rồi kết thúc z  x*x+y*y y>=x z  x+y Thông báo z rồi kết thúc z  0.5 Thông báo z rồi kết thúc Thuaät toaùn GV: Huøynh Minh Taân Trang: 13 BÀI TẬP ĐỀ NGHỊ Hãy mô tả thuật toán giải các bài toán sau bằng sơ đồ khối: Bài 1: Nhập dữ liệu là tháng trong năm Hướng dẫn - Tháng trong năm phải từ 1 đến 12 - Nếu thoả thì thông báo là tháng, ngược lại thì thông báo không phải là tháng trong năm Bài 2: Nhập vào một năm cho ra số ngày của năm đó Hướng dẫn - Có hai loại ngày là 365 ngày và 366 ngày - Năm nhuận là 365 ngày, không nhuận là 366 ngày - Năm nhuận là năm chia hết cho 400 hoặc chia hết cho 4 nhưng không chia hết cho 100 Bài 3: Tính căn bậc hai của một số Hướng dẫn - Sử dụng hàm Sqrt(x) - Nếu nhập vào số âm thì thông báo số đó không có căn bậc hai Bài 4: Giải bất phương trình ax+b> 0 Hướng dẫn - Sử dụng thuật toán như các bài đã gặp Bài 5: Nhập một điểm thi của học sinh và phân loại nếu điểm thấp hơn 5 thì không đạt, từ 5 đến =9 đến 10 thì xuất sắc. Hướng dẫn - Sử dụng If lồng nhau Thuaät toaùn GV: Huøynh Minh Taân Trang: 14 . Thuật toán theo chu trình có bước lặp xác định. Sơ đồ: Sai Đúng Điều kiện Câu lệnh Thuaät toaùn GV: Huøynh Minh Taân Trang: 15 VD7: Tính tổng n 1 2 n k k 1 S x x ... x ;(S x )       Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối * Xác định bài toán  Input: Số nguyên dương n và x1,x2,,xn;  Output: Tổng S Sơ đồ khối S Đ Nhập n và x1,x2,,xn S0 i1 SS+xi ii+1 i <= n Thông báo S rồi kết thúc Thuaät toaùn GV: Huøynh Minh Taân Trang: 16 VD8: Tính giai thừa của một số nguyên dương n (n!=1.2.......(n-1).n. Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối * Xác định bài toán  Input: Số nguyên dương n;  Output: Giai thừa của n (GT) Sơ đồ khối Đ S Nhập n GT1 i1 GTGT*i ii+1 i  n Thông báo GT rồi kết thúc Thuaät toaùn GV: Huøynh Minh Taân Trang: 17 VD9: Tính tồng 1 1 1 1 S ... a a 1 a 2 a n         (a số nguyên và a > 2 ) Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối * Xác định bài toán  Input: Số nguyên dương n và a;  Output: Tổng S Sơ đồ khối S Đ Nhập n và a S0 i0 SS+1/(a+i) ii+1 i  n Thông báo S rồi kết thúc Thuaät toaùn GV: Huøynh Minh Taân Trang: 18 BÀI TẬP ĐỀ NGHỊ Hãy mô tả thuật toán giải các bài toán sau bằng sơ đồ khối: Bài 1: Tính tổng S= 1 + 2 + 3 + ..+ n với n nhập từ bàn phím Bài 2: Tính tổng 1 1 1 S 1 ....... 2 3 n      với n nhập từ bàn phím Bài 3: Tính tổng S= 12 + 22 + 32 + ..+ n2 với n nhập từ bàn phím Bài 4: Tính tổng 1 1 1 S 1 ....... 1! 2! n!      với n nhập từ bàn phím Bài 5: Tính tích n 1 2 n i i 1 P x *x *...* x ;(P x )    với n nhập từ bàn phím Hướng dẫn Các bài trên làm tương tự như ví dụ 7, 8, 9 Thuaät toaùn GV: Huøynh Minh Taân Trang: 19 . Thuật toán theo chu trình có bước lặp không xác định. Sơ đồ: VD10: Tìm ước số chung lớn nhất của hai số nguyên dương a và b Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối * Xác định bài toán  Input: Số nguyên dương a,b;  Output: UCLN(a,b) Sơ đồ khối S Đ S Đ Nhập a, b a b a > b bb - a aa - b Thông báo UCLN là a, kết thúc Sai Đúng Điều kiện Câu lệnh Thuaät toaùn GV: Huøynh Minh Taân Trang: 20 VD11: Tính 1 1 1 S 1 ... 1! 2! n!      cho đến khi 1 e (n 1)!   với e là lượng nhập khá nhỏ Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối * Xác định bài toán  Input: Số thực dương e;  Output: Tổng S; Sơ đồ khối Đ S Nhập e S  1 i  1 gt  1 sh  1/gt sh>=e S  S + sh i  i + 1 gt  gt*i sh  1/gt Thông báo S và kết thúc Thuaät toaùn GV: Huøynh Minh Taân Trang: 21 BÀI TẬP ĐỀ NGHỊ Hãy mô tả thuật toán giải các bài toán sau bằng sơ đồ khối: Bài 1 : Nhập vào x. Tính 2 n x x x xe 1 ... 1! 2! n!      cho đến khi n 1x e (n 1)!    với e là lượng nhập khá nhỏ Hướng dẫn - Tương tự VD11. Bài 2: Tính tổng các số dương và trung bình cộng các số âm của các số nhập vào từ bàn phím cho đến khi số nhập vào bằng 0. Hướng dẫn - Công việc lặp phải có sử dụng cấu trúc If để tính tổng các số dương và trung bình các số âm. Bài 3: Kiểm tra xem khi nhập một số tự nhiên vào có phải là số nguyên tố hay không. Hướng dẫn - Nhập vào số tự nhiên N - Chú ý: N<=1 thì thông báo “Không xét” - Lấy N chia cho các số tự nhiên lớn hơn 1 và nhỏ hơn nó. Nếu N là số nguyên tố thì các phép chia có số dư khác 0. Nếu N không là số nguyên tố thì sẽ có một phép chia có dư bằng 0 IV. KEÁT QUAÛ Nói chung, thông qua một môn học, giáo viên không chỉ truyền đạt cho học sinh những kiến thức tối thiểu mà còn kích thích cho các em sự hứng thú học tập, sự tìm tòi sáng tạo. Từ đó các em sẽ mang những điều đã học vận dụng vào thực tế cuộc sống. Riêng bộ môn Tin học, người giáo viên càng có nhiểu thuận lợi để thực hiện điều đó. Thực tế sau khi áp dụng sáng kiến kinh nghiệm này vào giảng dạy môn Tin học lớp 11 ở trường tôi nhận thấy chất lượng bộ môn được nâng cao đáng kể:  Kỹ năng tư duy, sáng tạo, biết phân tích và giải quyết tình huống của các em học sinh ngày càng tốt hơn.  Các em có thể tự viết được những chương trình để giải các bài tập Toán, Lý, Hoá của bậc phổ thông.  Vì nhận thấy được những ứng dụng rất hữu ích của môn Tin học thông qua việc lựa chọn và thiết kế thuật toán để viết một chương trình nên các em học sinh càng yêu thích và say mê học hơn, kết quả học tập của các em tốt hơn. Thuaät toaùn GV: Huøynh Minh Taân Trang: 22 V. BAØI HOÏC KINH NGHIEÄM Sau khi thực hiện sáng kiến tôi rút ra những kinh nghiệm sau:  Vì “lựa chọn và thiết kế thuật toán” nằm trong chương trình Tin học lớp 10 nhưng được ứng dụng vào chương trình Tin học lớp 11, nên khi giáo viên yêu cầu viết chương trình để giải một bài toán thì học sinh hay bỏ qua bước này.  Trong quá trình dạy luôn phát huy tính tích cực, chủ động, sáng tạo của học sinh.  Tổ chức hoạt động nhóm để các em thảo luận và xây dựng ý tưởng trước khi thiết kế thuật toán.  Hướng dẫn để giúp các em học sinh biết lựa chọn thuật toán tối ưu nhất.  Tạo không khí học tập thân thiện. VI. TAØI LIEÄU THAM KHAÛO - Tin học lớp 10 – Nhà xuất bản giáo dục - Tin học lớp 10 – Sách giáo viên– Nhà xuất bản giáo dục - Tin học lớp 11 – Nhà xuất bản giáo dục - Tin học lớp 11 – Sách giáo viên– Nhà xuất bản giáo dục Vónh an, ngaøy 20 thaùng 10 naêm 2011 Ngöôøi thöïc hieän GV: Huỳnh Minh Taân ----0----