Tài liệu Xây dựng thuật toán để giải bài toán bằng cách lập sơ đồ khối

SỞ GIÁO DỤC VÀ ĐÀO TẠO VĨNH PHÚC TRƯỜNG THPT TAM DƯƠNG II BÁO CÁO KẾT QUẢ NGHIÊN CỨU, ỨNG DỤNG SÁNG KIẾN Tên sáng kiến: XÂY DỰNG THUẬT TOÁN ĐỂ GIẢI BÀI TOÁN BẰNG CÁCH LẬP SƠ ĐỒ KHỐI Tác giả sáng kiến:Nguyễn Minh Tuyết Mã sáng kiến: 08.62.01 SỞ GIÁO DỤC VÀ ĐÀO TẠO VĨNH PHÚC TRƯỜNG THPT TAM DƯƠNG II BÁO CÁO KẾT QUẢ NGHIÊN CỨU, ỨNG DỤNG SÁNG KIẾN Tên sáng kiến: XÂY DỰNG THUẬT TOÁN ĐỂ GIẢI BÀI TOÁN BẰNG CÁCH LẬP SƠ ĐỒ KHỐI Tác giả sáng kiến:Nguyễn Minh Tuyết Mã sáng kiến: 08.62.01 BÁO CÁO KẾT QUẢ NGHIÊN CỨU, ỨNG DỤNG SÁNG KIẾN I. LỜI GIỚI THIỆU. Cuộc cách mạng công nghiệp 4.0 mở ra nhiều cơ hội lớn nhưng lại cũng mang đến nhiều thách thức cho thế hệ trẻ. Trong tương lai, khi robot sẽ thay thế công việc của con người, nhiều lao động có nguy cơ bị thất nghiệp. Chính vì vậy, các bạn học sinh – thế hệ trẻ ngày nay phải chăm chỉ học công nghệ thông tin. Mục đích của việc học trong thời đại ngày nay là để trở thành người tự do, thành công dân toàn cầu. Có rất nhiều con đường dẫn tới thành công cho các bạn học sinh – những người chủ tương lai của đất nước. Tuy nhiên, các em phải tích cực tiếp cận với nền công nghệ mới và phải không ngừng phấn đấu vươn lên. Chính vì vậy việc trang bị kiến thức về công nghệ cho học sinh ngay khi còn ngồi trên ghế nhà trường sẽ giúp các em có những hành trang cần thiết để bắt đầu con đường chinh phục làm chủ công nghệ trong tương lai. Trong chương trình tin học 11 hiện nay, học sinh được tiếp cận với ngôn ngữ lập trình bậc cao Pascal. Là một ngôn ngữ lập trình cơ bản giúp các em tiếp cận với các ngôn ngữ lập trình khac. Tuy nhiên phần lớn các em đều rất lúng túng trong việc viết chương trình, hoặc chương trình viết ra không cho kết quả tối ưu do việc lựa chọn và xây dựng thuật toán còn chưa thành thạo, chưa xây dựng được thuật toán tốt nhất cho một bài toán. Việc lựa chọn và xây dựng 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 vì cũng giống như các môn tự nhiên như toán, lí hay hoá... để 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. 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 việc lựa chọn và xây dựng thuật toán giải bài toán để việc lập trình đạt kết quả tốt hơn. Do đó tôi chọn sáng kiến “Xây dựng thuật toán để giải bài toán bằng cách lập sơ đồ khối” để các em thấy hứng thú, tích cực chủ động hơn đối với bộ môn tin học đặc biệt chương trình tin học lớp 11. 5 II. TÊN SÁNG KIẾN “Xây dựng thuật toán để giải bài toán bằng cách lập sơ đồ khối” III. TÁC GIẢ SÁNG KIẾN: - Họ và tên: Nguyễn Minh Tuyết - Địa chỉ tác giả sáng kiến: Trường THPT Tam Dương II - Số điện thoại:.0383.543.952 - E_mail: [email protected] IV. CHỦ ĐẦU TƯ TẠO RA SÁNG KIẾN : Nguyễn Minh Tuyết V. LĨNH VỰC ÁP DỤNG SÁNG KIẾN: Sáng kiến áp dụng cho học sinh lớp 11 trong việc lựa chọn và xây dựng thuật toán để giải bài toán trước khi tiến hành lập trình giải quyết bài toán. VI. NGÀY SÁNG KIẾN ĐƯỢC ÁP DỤNG LẦN ĐẦU: Tháng 9 năm 2016 VII. MÔ TẢ BẢN CHẤT CỦA SÁNG KIẾN: 1. NỘI DUNG CỦA SÁNG KIẾN: 1.1. 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. Bài toán được cấu tạo bởi hai thành phần cơ bản: + Input: Các thông tin đã có + Output: Các thông tin cần tìm từ Input b. Thuaät toaùn. - Khái niêm: 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 tính chất của thuật toán: + Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác. + Tính xác định: Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng một thao tác xác định để được thực hiện bước tiếp theo. + 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. 6 Thuật toán có thể phân loại như sau: - Thuật toán không rẽ nhánh: Thuật toán không có thao tác so sánh khi trình bày thuật toán - Thuật toán có rẽ nhánh: Thuật toán có thao tác so sánh khi trình bày thuật toán - Thuật toán có bước lặp xác định: Xác định trước số lần lặp - Thuật toán có bước lặp không xác định: Không xác định được trước số lần lặp 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 Chú ý: Với hình ô van : chỉ có một mũi tên ra với thao tác nhập dữ liệu và một mũi tên vào cho thao tác in kết quả Với hình chữ nhật thì có một mũi tên vào và một hướng mũi tên ra Với hình thoi thì có mộtmũi tên vào và hai g mũi tên ra hai hướng thể hiện thao tác đúng, sai 7 1.2. Một số ví dụ . Thuật toán không rẽ nhánh VD1: Cho A = x + y;B = x + 5A; C = A - 3B; Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối để tính C HƯỚNG DẪN: * Xác định bài toán Input: x, y Output: C * Ý tưởng: Muốn tính được C thì đầu tiên ta phải tính A và B * Sơ đồ khối Nhập x, y Ax+y B x+ 5*A C A-3*B Thông báo C rồi kết thúc VD2: Một người đi xe đạp với vận tốc 10km/h và một người đi xe máy với tốc độ 30km/h cùng xuất phát từ một vị trí, cùng một thời điểm và đi cùng một hướng. Lập trình tính khoảng cách giữa hai người sau t giờ (t là số nguyên dương, t<=15). Dữ liệu t nhập vào từ bàn phím. Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối. HƯỚNG DẪN: * Xác định bài toán Input: t Output: khoảng cách d *Ý tưởng: 8 Tính quãng đường của xe đạp: S1= t*10; Tính quãng đường của xe máy: S2 = t*30; Khoảng cách d = S2-S1; * Sơ đồ khối Nhập t S1 t*10; S2 t*30; d S2 – S1; Thông báo d rồi kết thúc VD3. Lập trình nhập từ bàn phím hai số thực a và b, tính và đưa ra màn hình a) Trung bình cộng các bình phương của hai số đó b) Trung bình cộng các giá trị tuyệt đối của a và b Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối. HƯỚNG DẪN: * Xác định bài toán Input: a, b Output: TB1 là trung bình cộng bình phương của hai số a, b; TB2 là trung bình cộng trị tuyệt đối của hai số a, b *Ý tưởng: Tính TB1= (a2+b2)/2; Tính TB2 = (|a|+|b|)/2; * Sơ đồ khối Nhập a, b TB1 (a*a+b*b)/2; TB2 (abs(a)+abs(b))/2; 9 Thông báo TB1, TB2 rồi kết thúc 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 các số thực (xa, ya), (xb, yb), (xc, yc) là toạ độ ba đỉnh A, B, C của tam giác ABC a) Tính và đưa ra màn hình diện tích tam giác theo công thức Hê-rông b) Tính và đưa ra màn độ dài các đường cao ha, hb, hc Hướng dẫn: - Input: xa, ya, xb, yb, xc, yc - Output: dientich (S), các đường cao ha, hb, hc - Sử dụng các công thức: Diện tích: s = p(p-a)(p-b)(p-c) ; Trong đó a, b, c là độ dài các cạnh của tam giác và p= (a+b+c)/2. Độ dài cạnh tính theo công thức: a = √(xa−xb)2 +( ya− yb)2 b = √(xc−xb)2 +( yc− yb)2 c = √ (xa−xc)2 +( ya− yc)2 a 2s 2s b 2s c Các đường cao: ha= ; , hb= ; hc= ; 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: - Input: Toạ độ 3 điểm A, B và C; 10 - Output: Tích vô hướng ⃗AB.⃗AC ; - Sử dụng các công thức: AB=(x -x ;y -y ) vectơ: B A B A ; AC=(x C -x A ;y C -y A ) ; Tích vô hướng: AB.AC=(x -x ).(x -x )+(y -y ).(y -y ) B A C A B A C A ; Bài 3. Cho số nguyên N có bốn chữ số. Hãy dùng các phép DIV và MOD tính tổng các chữ số của N. Dữ liệu nhập vào từ bàn phím. Hướng dẫn: Gọi N = abcd khi đó d = n mod 10; N = n div 10; c = n mod 10; N = n div 10; b = n mod 10; a = n div 10; Tổng các chữ số T = a+b+c+d Bài 4. Tính chu vi và diện tích của một hình thang cân có đáy lớn là a, đáy nhỏ là ab (b=y Đúng Nhỏ nhất là y và kết thúc Sai Nhỏ nhất là x và kết thúc VD5: Tìm số nhỏ nhất trong ba số thực x , y và z 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 x,y,z Output: Số nhỏ nhất trong ba số * Ý tưởng: Lần lượt so sánh hai số với nhau số nào nhỏ hơn đem so sánh với số còn lại 14 Sơ đồ khối Nhập x, y, z S Đ x>y Đ x>z y>z S S Min x Min z VD6: Cho bài Thông báo Min và kết thúc Z= Min y |x| +|y| nếu điểm (x, y) thuộc hình tròn bán kính r (r>0), tâm (a,b) x + y trong trường hợp còn lại 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,a,b,r Output: z * Ý tưởng: bán kính r (r>0), tâm (a,b) là: S z y+x R*R =s qr(x- a) +s qr( y- Điều kiện để điểm (x, y) thuộc R*R = (x - a)2 + (y - b)2 * Sơ đồ khối N yxpậh,,a, rb, 15 Đ Đ z a bs( x)+ abs(y) rồiThô kếng tthbáúcoz S Đ VD7: 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 < 6.5 thì trung bình, từ 6.5 đến <8 thì khá, từ 8 đến < 9 thì giỏi, >=9 đến 10 thì xuất sắ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: x Output: xếp loại của học sinh theo điểm 16 * Sơ đồ khối Nhập x X< 5 Đúng xeploai ’khong dat’ ← Sai Đúng X< 6.5 xeploai←’trung binh’ Sai X< 8 Đúng xeploai←’kha’ Đúng xeploai←’gioi’ Sai X<9 Sai xeploai←’xuat sac’ Thông báo xeploai rồi kết thúc 17 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 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 2: 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 3: Cho ba số nguyên m , n, k. Nếu ba số này theo thứ tự nhập vào tạo thành một cấp số cộng thì tăng gấp đôi mỗi số, trong trường hợp còn lại thì giảm mỗi số một đơn vị Hướng dẫn: Tính chất của cấp số cộng: 2*n = m + k Bài 4. Cho ba số nguyên p, q, r (≠ 0) Kiểm tra ba số theo thứ tự nhập vào có tạo thành cấp số nhân không. Hướng dẫn: Tính chất của cấp số nhân: q*q = p*r . Thuật toán theo chu trình có bước lặp xác định. Sơ đồ: Câu lệnh Điều kiện Đúng 1 2 50 VD8: Tính tổngs= 1+a +2+a +…+ 50+a Sai 50 ∑ n=1 n n+a 18 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: nhập a Output: Tổng S Sơ đồ khối Nhập a S0 i1 SS+(i/(i+a) ii+1 Đúng i <= 50 Sai Thông báo S rồi kết thúc VD9: 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 19 Nhập n GT1 i1 GTGT*i ii+1 Đúng in Sai Thông báo GT rồi kết thúc VD10: Tính tổng P= 1+ 2x + 3x2 + … + nxn-1 +(n+1)xn (x là số thực, n là số nguyê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 và x; Output: Tổng P Sơ đồ khối 20 Nhập n và x P1 i1 PP+(i+1)*x^i ii+1 Đúng in Sai S Thông báo P rồi kết thúc 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= 12 + 22 + 32 + ………..+ n2 với n nhập từ bàn phím Bài 2: Tính tổng S 1 1! 1 2! 1 ....... n! 1 với n nhập từ bàn phím Bài 3: Tính tích n P x 1 *x 2 *...* x n ; (P xi) i1 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ụ 8, 9, 10 19