Sáng kiến kinh nghiệm Dạy bài toán và thuật toán trong Tin học cho học sinh lớp 10

 SKKN: Dạy bài toán và thuật toán trong Tin học cho học sinh lớp 10
 MỤC LỤC
CÁC KÝ HIỆU VIẾT TẮT TRONG SÁNG KIẾN KINH NGHIỆM .................2
I. Lời giới thiệu......................................................................................................3
II. Tên sáng kiến:...................................................................................................4
III. Tác giả sáng kiến:............................................................................................4
IV. Chủ đầu tư tạo ra sáng kiến:............................................................................4
V. Lĩnh vực áp dụng sáng kiến: ............................................................................4
VI. Ngày sáng kiến được áp dụng lần đầu hoặc áp dụng thử:...............................4
VII. Mô tả bản chất của sáng kiến:........................................................................5
 1. Bài toán..........................................................................................................5
 1.1. Khái niệm ...............................................................................................5
 1.2. Ví dụ xác định INPUT và OUTPUT của các bài toán sau.....................5
 2. Thuật toán......................................................................................................6
 2.1. Khái niệm ...............................................................................................6
 2.2. Phương pháp...........................................................................................6
 2.3. Tính chất.................................................................................................6
 2.4. Ví dụ.......................................................................................................6
 2.5. Bài tập vận dụng...................................................................................26
VIII. Những thông tin cần bảo mật: Không ........................................................26
IX. Các điều kiện cần thiết để áp dụng sáng kiến: Học sinh lớp 10 hoặc học sinh 
mới làm quen với lập trình. .................................................................................26
X. Đánh giá lợi ích thu được hoặc dự kiến có thể thu được do áp dụng sáng kiến 
theo ý kiến của tác giả:........................................................................................26
XI. Danh sách những tổ chức/cá nhân đã tham gia áp dụng thử hoặc áp dụng 
sáng kiến lần đầu:................................................................................................28
TÀI LIỆU THAM KHẢO...................................................................................29
 1 SKKN: Dạy bài toán và thuật toán trong Tin học cho học sinh lớp 10
 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 
 Trong kỷ nguyên công nghệ bùng nổ, không có gì bất ngờ khi công nghệ 
 thông tin luôn giữ vững vị thế là một trong những ngành hàng đầu về nhu cầu 
 nhân lực và tiềm năng phát triển. Vị thế này càng được củng cố trong bối cảnh thế 
 giới và đất nước bước vào thời đại Cách mạng công nghiệp 4.0. Vì thế đòi hỏi 
 mỗi chúng ta dù là học sinh hay giáo viên đều phải tích cực học tập, nghiên cứu 
 để có thể hội nhập được với thời đại. 
 Môn Tin học là môn học giúp các em dễ dàng tiếp cận được với công nghệ, 
 với thế giới. Tuy nhiên nó khá mới mẻ với học sinh THPT đặc biệt là học sinh 
 trường THPT Nguyễn Viết Xuân với phần đông học sinh thuộc khu vực nông 
 thôn. Học sinh mới chỉ được làm quen với máy tính chứ chưa thực sự có khái 
 niệm về công nghệ thông tin, khái niệm về bài toán và thuật toán trong Tin học. 
 Trong khi đó phần bài toán và thuật toán được học ở lớp 10 là phần kiến thức 
 quan trọng nhất. Là nền tảng cho kiến thức tin học lớp 11. Là cốt lõi cho các em 
 muốn theo học lập trình. Nên rất cần những phương pháp, cách tiếp cận bài toán 
 và thuật toán sao cho học sinh không cảm thấy sợ dẫn đến mất gốc. 
 BÀI TOÁN
 Muốn máy tính đưa ra
INPUT OUTPUT
 Output từ Input
 Muốn viết chương trình
 CHƯƠNG TRÌNH THUẬT TOÁN
 CẦN
 Bài toán và thuật toán trong Tin học khá là quen thuộc với giáo viên. Và 
 sự thật tôi cũng đã làm một sáng kiến kinh nghiệm về phần này cách đây ba năm. 
 Nhưng khi đó tôi thường tập trung vào những thuật toán khó phức tạp mà quên đi 
 3 SKKN: Dạy bài toán và thuật toán trong Tin học cho học sinh lớp 10
VII. Mô tả bản chất của sáng kiến:
1. Bài toán
1.1. Khái niệm
 Là việc nào đó mà ta muốn máy tính thực hiện để từ thông tin đưa vào 
(Input) tìm được thông tin ra (Output).
Vậy bài toán trong tin học gồm:
 Thông tin, dữ liệu vào: Input
 Thông tin ra, kết quả: Output
1.2. Ví dụ xác định INPUT và OUTPUT của các bài toán sau
Ví dụ 1: Cho hai số a, b. Tính tổng hai số.
 Input: a, b
 Output: Tổng hai số
Ví dụ 2: Cho hai số a, b, c. Tìm max của ba số.
 Input: a, b, c
 Output: Max (a,b,c)
Ví dụ 3: Giải phương trình: ax + b = 0.
 Input: Hai số nguyên a và b.
 Output: Kết luận nghiệm của PT.
Ví dụ 4: Giải phương trình: ax2 + bx + c = 0 (a 0)
 5 SKKN: Dạy bài toán và thuật toán trong Tin học cho học sinh lớp 10
* Thuật toán
- Phương pháp liệt kê
 B1: Nhập a, b
 B2: S := a + b
 B3: Tổng là S
- Phương pháp sơ đồ khối
* Mô phỏng thuật toán 
 - Với a = 2, b = 3 thì tổng S là 5
 - Với a = 10, b = 6 thì tổng S là 16
Ví dụ 2: Cho số nguyên N. Trình bày thuật toán kiểm tra tính chẵn lẻ của N.
 Lời giải
* Cách xác định bài toán
 - Input: N
 - Output: N là số chẵn hoặc N là số lẻ
* Thuật toán
- Phương pháp liệt kê
 B1: Nhập N
 B2: Nếu N chia hết cho 2 thì N là số chẵn
 B3: Ngược lại N là số lẻ Nhập N
- Phương pháp sơ đồ khối
 Đ
 N  2 N là số chẵn
 7 S
 N là số lẻ SKKN: Dạy bài toán và thuật toán trong Tin học cho học sinh lớp 10
- Với a = 1, b = 1 thì phương trình có nghiệm x := -1
Ví dụ 4: Trình bày thuật toán giải phương trình: ax2 + bx + c = 0 (a#0)
 Lời giải
* Cách xác định bài toán
 - Input: a, b, c
 - Output: Kết luận nghiệm của PT
* Thuật toán
- Phương pháp liệt kê
 B1: Nhập a, b, c
 B2: D:= b*b - 4*a*c
 B3: Nếu D < 0 thì phương trình vô nghiệm
 B4: Nếu D = 0 thì phương trình có nghiệm kép x := b
 2*a
 B5: Ngược lại phương trình có hai nghiệm phân biệt 
 b D b D
 x1 := , x2 := 
 2*a 2*a
- Phương pháp sơ đồ khối
 Đ
* Mô phỏng thuật toán
- Với a = 1, b = 2, c = 4 
 9 SKKN: Dạy bài toán và thuật toán trong Tin học cho học sinh lớp 10
 Nhập N; a1, a2,  an
 S := 0; i := 1
 Đ
 i > N Tổng dãy là S
 S
 S := S + ai
 i := i + 1
* Mô phỏng thuật toán
 - Với N = 0 thì tổng của dãy là 0
 - Với N = 3 và dãy số 4, 7, 2
 + B1: Nhập 3; 4, 7, 2
 + B2: S := 0; i := 1
 + B3: 1 > 3 (sai)
 + B4: S := 0 + 4
 + B5: i := 2, quay lại B3
 ....
 Vậy Tổng dãy là 13
Ví dụ 6: Cho dãy có N phần tử a 1, a2,  an. Trình bày thuật toán tính tổng các 
phần tử chẵn của dãy.
 Lời giải
* Cách xác định bài toán
 Input: N; a1, a2,  an
 Output: Tổng các phần tử chẵn của dãy
* Thuật toán 
- Phương pháp liệt kê
 11 SKKN: Dạy bài toán và thuật toán trong Tin học cho học sinh lớp 10
 Lời giải
* Cách xác định bài toán
 - Input: a, b, c
 - Output: Max (a, b, c)
* Thuật toán
- Phương pháp liệt kê
 B1: Nhập a, b, c
 B2: Gán Max := a
 B3: Nếu Max < b thì Max := b
 B4: Nếu Max < c thì Max := c
 B5. Đưa ra GTLN là Max
- Phương pháp sơ đồ khối
* Mô phỏng
- Với a = 7, b = 1, c = 5
 B1 : Nhập 7, 1, 5
 B2 : Gán Max := 7
 B3: Max < 1 (sai)
 13 SKKN: Dạy bài toán và thuật toán trong Tin học cho học sinh lớp 10
 Nhập N; a1, a2, ..., aN 
 Max := a1; i := 2
 Đ
 i > N GTLN là Max
 S
 Đ
 Max := ai
 ai > Max 
 S
 i := i + 1
* Mô phỏng
- Với N = 1; dãy có 1 phần tử 5 
 B1: Nhập 1; 5
 B2: Max := 5 ; i :=2
 B3: 2 > 1 (đúng) Vậy GTLN là 5
- Với N = 6 và dãy số 5, 1, 4, 7, 8, 2
 Dãy số 5 1 4 7 8 2
 i 2 3 4 5 6 7
 Max 5 5 5 7 8 8
 B1: Nhập 6 ; 5, 1, 4, 7, 8, 2
 B2: Max := 5 ; i := 2
 B3: 2 > 6 (sai)
 B4: 1 > 5 (sai) 
 B5: i := 3, quay về B3
 Vậy GTLN là 8
 15 SKKN: Dạy bài toán và thuật toán trong Tin học cho học sinh lớp 10
- Với N = 1 thì 1 không là số nguyên tố
- Với N = 2 thì 2 là số nguyên tố
- Với N = 3 thì 3 là số nguyên tố
- Với N = 17 
 B1: Nhập 17
 B2: 17 = 1 (sai) 
 B3: 17 < 4 (sai) 
 B4: i := 2; d := [ 17 ] = 4
 i 2 3 4 5
 N/i 17/2 17/3 17/4
 Chia hết 
 không không không
 không?
 17 là số nguyên tố
Ví dụ 10: Cho số nguyên dương N. Trình bày thuật toán tính tổng các chữ số 
của N.
 Lời giải
* Cách xác định bài toán
 - Input: N
 - Output: Tổng các chữ số
* Thuật toán
- Phương pháp liệt kê
B1: Nhập N
B2: S := 0
B3: Nếu N = 0 thì đưa ra tổng S
B4: S := S + N mod 10
B5: N := N div 10
B5: Quay về B3
- Phương pháp sơ đồ khối
 17 SKKN: Dạy bài toán và thuật toán trong Tin học cho học sinh lớp 10
 B2: Nếu N = M thì UCLN là M
 B3: Nếu M > N thì M := M – N rồi quay lại B2
 B4: N := N – M rồi quay lại B2
- Phương pháp sơ đồ khối
 Nhập N, M
 Đ
 M = N UCLN là M
 S
 Đ
 M := M -N M > N
 S
 N := N - M
* Mô phỏng thuật toán
- Với N = 8; M =8
 B1: Nhập 8, 8
 B2: 8=8 (đúng) UCLN là 8
- Với N = 6, M = 9
 B1: Nhập 6, 9
 B2: 6 = 9 (sai) 
 B3: 6 > 9 (sai) 
 B4: N := 9 – 6 = 3, quay về B2
 .
 UCLN là 3
Ví dụ 12: Cho số nguyên N. Trình bày thuật toán tính tổng các ước của N.
 Lời giải
* Cách xác định bài toán
 19