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

hươ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
Nhập N
N 2
N là số chẵn
N là số lẻ
Đ
S
B2: Nếu N chia hết cho 2 thì N là số chẵn
B3: Ngược lại N là số lẻ
- Phương pháp sơ đồ khối
* Mô phỏng thuật toán 
	- Với N = 4 thì N là số chẵn
	- Với N = 7 thì N là số lẻ
Ví dụ 3: Trình bày thuật toán giải phương trình: ax + b = 0
Lời giải
* Cách xác định bài toán
- Input: a, b
- 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
B2: Nếu a = 0	
	B21: b = 0 kết luận PT VSN
	B22: Ngược lại kết luận PT VN
B3: Ngược lại phương trình có 1 nghiệm x := -b/a
- Phương pháp sơ đồ khối
* Mô phỏng thuật toán
- Với a = 0, b = 0 thì phương trình vô số nghiệm
- Với a = 0, b = 1 thì phương trình vô nghiệm
- 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 := 
B5: Ngược lại phương trình có hai nghiệm phân biệt 
	x1 := , x2 := 
- Phương pháp sơ đồ khối
Đ
* Mô phỏng thuật toán
- Với a = 1, b = 2, c = 4 
	B1: Nhập 1, 2, 4
	B2: D := 2*2 – 4*1*4 = -12. 
	B3: D < 0 (đúng)à Vậy PT vô nghiệm
- Với a = 1, b = 2, c = 1 
	B1: Nhập 1, 2, 1	
	B2: D := 2*2 – 4*1*1 = 0
	B3: D = 0 (đúng) à Vậy PT có 1 nghiệm
- Với a =1, b = 3, c = 2 
	B1: Nhập 1, 3, 2
	B2: D := 3*3 – 4*1*2 = 1.	 
	B3: D = 0 (sai) à Vậy PT có hai nghiệm phân biệt 
	x1 := = -2, x2 := = -1
Ví dụ 5: Cho dãy có N phần tử a1, a2,  an. Trình bày thuật toán tính tổng các phần tử 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ử của dãy
* Thuật toán 
- Phương pháp liệt kê
B1: Nhập N; a1, a2,  an
B2: S := 0; i := 1
B3: Nếu i > N thì dãy có tổng là S
B5: S := S + ai
B6: i := i + 1
B7: Quay về B3 
- Phương pháp sơ đồ khối
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ử a1, 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ê
B1: Nhập N; a1, a2,  an
B2: S := 0; i := 1
B3: Nếu i > N thì dãy có tổng là S
B4: Nếu ai 2 thì S := S + ai
B5: i := i + 1
B6: Quay về B3 
Nhập N; a1, a2,  an
S := 0; i := 1
i > N
Tổng dãy là S
Đ
S
S := S + i
i := i + 1
ai 2 
Đ
S
- Phương pháp sơ đồ khối
* Mô phỏng thuật toán
	- Với N = 0 thì tổng của dãy là 0
	- Với N = 5 và dãy số 6, 5, 7, 8, 9
	+ B1: Nhập 5; 6, 5, 7, 8, 9
	+ B2: S := 0; i := 1
	+ B3: 1 > 5 (sai)
	+ B4: 62 nên S := S + 6
	+ B5: i := 2, quay lại B3
	....
	àVậy Tổng dãy là 14
Ví dụ 7: Cho ba số a, b, c. Trình bày thuật toán tìm Max (a, b, c).
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)
	B4: Max < 5 (sai)
	B5: Vậy GTLN là 7
- Với a = 2, b = 8, c = 1
	B1 : Nhập 2, 8, 1
	B2 : Gán Max := 2
	B3: Max < 8 (đúng) nên Max := 8
	B4: Max < 1 (sai)
	B5: Vậy GTLN là 8
Ví dụ 8: Cho N và dãy các số nguyên a1, a2,  an. Trình bày thuật toán tìm Max của dãy.
Lời giải
* Cách xác định bài toán
- Input: N; a1, a2,  an
- Output: Max(a1, a2,  an)
* Thuật toán
- Phương pháp liệt kê
B1: Nhập N và các số nguyên a1, a2, ..., aN 
B2: Max := a1; i := 2;
B3: Nếu i > N thông báo giá trị Max rồi kết thúc.
B4: Nếu ai > Max thì Max = ai
B5: i := i + 1 rồi quay lại B3.
- Phương pháp sơ đồ khối
GTLN là Max
Nhập N; a1, a2, ..., aN 
Max := a1; i := 2
i > N
Đ
S
Max := ai
i := i + 1
ai > Max 
Đ
S
* 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
Ví dụ 9: Cho số N nguyên dương. Trình bày thuật toán kiểm tra tính nguyên tố của N.
Lời giải
* Cách xác định bài toán
- Input: N là 1 số nguyên dương
- Output: N là số nguyên tố hay không
* Thuật toán
- Phương pháp liệt kê
B1: Nhập N.
B2: Nếu N = 1 thì thông báo N không là số nguyên tố.
B3: Nếu N < 4 thì thông báo N là số nguyên tố
B4: Gán i := 2; d := [] (i = 2 àd)
B5: Nếu i >= d thì thông báo N là số nguyên tố
B6: Nếu N chia hết cho i thì N không là số nguyên tố
B7: i := i + 1 à quay trở lại B5
- Phương pháp sơ đồ khối
* Mô phỏng
- 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 := [] = 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
Đưa ra tổng các chữ số là S
Nhập N 
S := 0
N = 0
Đ
S
S := S + N mod 10
N := N div 10
* Mô phỏng
- Với N = 0 à Đưa ra tổng S = 0 
- Với N = 3265
	B1: Nhập 3265
	B2: S := 0
	B3: 3265 = 0 (Sai)
	B4: S := 0 + 3265 mod 10 = 0 + 5
	B5: N := N div 10 = 326
	.....
	à Đưa ra tổng chữ số là 16
Ví dụ 11: Cho hai số nguyên M và N. Trình bày thuật toán tìm ước chung lớn nhất của hai số.
	Lời giải
* Cách xác định bài toán
- Input: M, N
- Output: UCLN (M,N)
* Thuật toán
- Phương pháp liệt kê
B1: Nhập M, N
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
M := M -N
Đ
Đ
M > N
S
N := N - M
S
* 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
- Input: N
- Output: Tổng các ước của N
* Thuật toán
- Phương pháp liệt kê	
B1: Nhập N
B2: S := 0; i := 1; d := [N : 2]
B3: Nếu i > d thì đưa ra tổng S
B4: Nếu N i = 0 thì S := S + i
B5: i := i + 1, quay về B3
- Phương pháp sơ đồ khối	
Nhập N 
S := 0; i := 1; d := [N : 2]
Đưa ra tổng S
i > d
Đ
S := S + i
N i
Đ
S
i := i + 1
S
* Mô phỏng
- Với N = 1
	B1: Nhập 1
	B2: S := 0; i := 1; d := [1 : 2] = 1
	B3: 1 > 1 (sai)
	B4: 1 1 (đúng) nên S := 0 + 1
	à Vậy tổng là 1
- Với N = 20
	B1: Nhập 20
	B2: S := 0; i := 1; d := [20 : 2] = 10
	B3: 10 > 1 (sai)
	B4: 10 1 (đúng) nên S := 0 + 1
	à Vậy tổng là 22
Ví dụ 13: Cho N nguyên. Trình bày thuật toán tính giai thừa của N
	Lời giải
* Cách xác định bài toán
- Input: N
- Output: N!
* Thuật toán
- Phương pháp liệt kê	
B1: Nhập N
B2: S := 1; i := 2
B3: Nếu i > N thì đưa ra giai thừa của N là S
Giai thừa của N là S
Nhập N 
S := 1; i := 2
i > N
Đ
S
i := i + 1
S := S * i
B4: S := S * i
B5: i := i + 1, quay về B3
- Phương pháp sơ đồ khối	
* Mô phỏng
- Với N = 1
	B1: Nhập 1
	B2: S := 1; i := 2
	B3: 2 > 1 (đúng) à Giai thừa của 1 là 1
- Với N = 5
	B1: Nhập 5
	B2: S := 1; i := 2
	B3: 2 > 5 (sai)
	B4 : S := 1 * 2
	B5: i := 2+1
	.
	à Giai thừa của 5 là 120
Ví dụ 14: Cho N và dãy các số nguyên a1, a2,  an. Trình bày thuật toán tìm sắp xếp các phần tử của dãy theo thứ tự tăng dần.
* Cách xác định bài toán
- Input: Dãy số nguyên a1, a2, ..., aN
- Output: Dãy số đã được sắp xếp.
* Thuật toán 	
- Phương pháp sơ liệt kê
B1: Nhập N và dãy a1, a2, ..., aN
B2: Gán giá trị M := N
B3: Nếu M <2 thông báo dãy đã được sắp xếp và kết thúc.
B4: Gán M := M - 1; i := 0;
B5: Gán i := i + 1
B6: Nếu i > M quay lại B3
B7: Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau
B8: quay lại bước 5.
- Phương pháp sơ đồ khối
Dãy đã SX
Nhập N; a1, a2, ..., aN 
M := N
M < 2
Đ
S
M := M - 1; i := 0
i := i + 1
i > M
S
Đ
Tráo đổi ai với ai+1
ai > ai+1
S
Đ
* Mô phỏng thuật toán
- Với N = 1; dãy có 1 phần tử 6
	B1: Nhập 1; 6
	B2: M := 1
	B3: 1 < 2 (đúng) à Dãy đã sắp xếp
- Với N = 10; dãy có các phần tử 6, 2, 5, 3, 7, 8, 10, 7, 12, 4
	B1: Nhập 10; 6, 2, 5, 3, 7, 8, 10, 7, 12, 4
	B2: M := 10	
	B3: 10 < 2 (sai)
	B4: M := 10 – 1; i := 0
	B5: i := 1
	B6: 1 > 9 (sai). Ta thực hiện so sánh các số với nhau và thực hiện đổi chỗ
	Thực hiện tương tự cho các lần duyệt tiếp theo cho đến khi không còn sự đổi chỗ nào nữa. 
Ví dụ 15: Cho N và dãy các số nguyên a1, a2, , an và số nguyên K. Trình bày thuật toán cho biết vị trí xuất hiện của K trong dãy.
* Cách xác định bài toán
- Input: N; Dãy số nguyên a1, a2, ..., aN; K
- Output: Vị trí xuất hiện của K hoặc K không có trong dãy
* Thuật toán
- Phương pháp liệt kê
B1: Nhập N và dãy a1, a2, ..., aN; K
B2: Gán i := 1
B3: Nếu ai = K thì thông báo vị trí xuất hiện K là i
B4: i := i + 1
B5: Nếu i > N thì thông báo trong dãy không có K
B6: Quay về B3
- Phương pháp sơ đồ khối
Nhập N; a1, a2, .. an; K
i := 1
ai = k
K xuất hiện tại i
i := i+1
i > N
Không có K trong dãy
Đ
S
S
Đ
* Mô phỏng thuật toán
- Với N = 5; dãy các phần tử là 6, 7, 2, 5, 8; K =5
	B1: Nhập 5; 6, 7, 2, 5, 8; 5
	B2: i := 1
	B3: 6 = 5 (sai) 
	B4: i := 2
	B5: 2 > 5 (sai)
	B6: Quay về B3
	à Vị trí xuất hiện của K là 4
2.5. Bài tập vận dụng
Bài 1: Cho dãy có N phần tử a1, a2,  an. Trình bày thuật toán tính tổng các phần tử lẻ của dãy.
Bài 2: Cho N và dãy các số nguyên a1, a2,  an. Trình bày thuật toán tìm Min của dãy.
Bài 3: Cho số nguyên dương N. Trình bày thuật toán tính tích các chữ số của N.
Bài 4: Cho số nguyên dương N. Trình bày thuật toán tính tổng các ước nguyên tố của N
Bài 5: Cho số N. Trình bày thuật toán kiểm tra N có là số chính phương hay không
Gợi ý: Số chính phương là số bằng bình phương của một số tự nhiên.
Ví dụ: 4 = 22; 9 = 32 . là các số chính phương
Bài 6: Cho số N. Trình bày thuật toán kiểm tra N có là số hoàn hảo hay không
Gợi ý: N được gọi là số hoàn hảo nếu N có giá trị bằng tổng các ước của nó (không kể chính nó). Ví dụ: N = 6; N = 28 
Bài 7: Cho N và dãy các số nguyên a1, a2,  an. Trình bày thuật toán tìm sắp xếp các phần tử của dãy theo thứ tự giảm dần.
Bài 8: Cho N và dãy các số nguyên a1, a2, , an và số nguyên K. Trình bày thuật toán đếm số lần xuất hiện của K trong dãy.
VIII. Những thông tin cần bảo mật: Không
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.
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ả:
	Học sinh được học theo nội dung trình bày trong sáng kiến sẽ có cái nhìn toàn diện hơn, tự tin hơn khi đối mặt với bài toán trong Tin học từ đó các em sẽ thích học và chủ động tìm hiểu kiến thức. Nội dung sáng kiến được trình bày logic, phù hợp với trình độ phát triển tư duy của học sinh từ nhận biết, thông hiểu đến vận dụng, nâng cao và sáng tạo qua đó giúp cho học sinh phát triển tư duy tổng hợp và rèn luyện các kĩ năng viết thuật toán.	
	Bảng số liệu kết quả của học sinh lớp 10 – khối A trường THPT Nguyễn Viết Xuân năm học 2016 – 2017 khi chưa thực hiện đề tài:
STT
Lớp
Sỉ số
Đạt yêu cầu
Không đạt yêu cầu
1
10A2
36
88%
12%
2
10A3
38
62.5%
37.5%
3
10A5
38
56%
44%
- Khi thực hiện thực nghiệm qua các đối tượng học sinh đã nêu trên, đa số các em tránh được các lỗi thường gặp khi trình bày thuật toán
- Một số không ít học sinh có tiến bộ rõ rệt khi trình bày thuật toán bằng hai phương pháp.
- Nâng cao việc yêu thích học tin học đối với một bộ phận học sinh và một số em có định hướng nghề nghiệp sau này.
- Bảng số liệu kết quả đạt được của học sinh lớp 10 – khối A trường THPT Nguyễn Viết Xuân năm học 2017 – 2018 sau khi thực hiện đề tài:
STT
Lớp
Sĩ số
Đạt yêu cầu
Không đạt yêu cầu
1
10A2
36
95%
05%
2
10A3
36
88%
22%
3
10A5
36
80%
20%
	Bản thân tôi khi viết đề tài này đã phần nào đó rèn luyện cho mình khả năng nghiên cứu khoa học, tìm tòi và phân tích và tổng hợp tài liệu từ nhiều nguồn khác nhau, tăng cường khả năng tự học, tự bồi dưỡng chuyên môn.
	Sáng kiến kinh nghiệm sẽ là tài liệu tham khảo cơ bản về thuật toán để trao đổi kinh nghiệm với đồng nghiệp và truyền đạt cho học sinh.
	Mặc dù đã cố gắng rất nhiều trong quá trình viết sáng kiến kinh nghiệm này nhưng chắc chắn sẽ không tránh khỏi những sai sót. Kính mong quý thầy cô, đồng nghiệp và học sinh chân thành góp ý để sáng kiến kinh nghiệm: “Dạy bài toán và thuật toán cho học sinh lớp 10” được hoàn thiện hơn và trở thành một tài liệu hay, hữu ích trong việc dạy và học thuật toán.
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:
STT
Tên tổ chức/ Cá nhân
Địa chỉ
Phạm vi/ Lĩnh vực
áp dụng sáng kiến
1
Lớp 10A2
Trường THPT Nguyễn Viết Xuân
Lĩnh vực giáo dục – Bộ môn Tin học
2
Lớp 10A3
Trường THPT Nguyễn Viết Xuân
Lĩnh vực giáo dục – Bộ môn Tin học
3
Lớp 10A5
Trường THPT Nguyễn Viết Xuân
Lĩnh vực giáo dục – Bộ môn Tin học
4
Nguyễn Thị Hà
Trường THPT Nguyễn Viết Xuân
Lĩnh vực giáo dục – Bộ môn Tin học

Vĩnh Tường, 
ngày 31 tháng 01 năm 2019
Thủ trưởng đơn vị/
Chính quyền địa phương
(Ký tên, đóng dấu)

., 
ngày .... tháng .... năm 201..
CHỦ TỊCH HỘI ĐỒNG 
SÁNG KIẾN CẤP CƠ SỞ
(Ký tên, đóng dấu)
Vĩnh Tường, 
ngày 29 tháng 01 năm 2019 
Tác giả sáng kiến
(Ký, ghi rõ họ tên)
Nguyễn Thị Hà
TÀI LIỆU THAM KHẢO
1. Sách giáo khoa tin học 10 – NXB Giáo dục
2. Sách giáo khoa tin học 11 – NXB Giáo dục
3. Giải thuật và lập trình – Lê Minh Hoàng
4. Một số vấn đề về thuật toán – NXB Giáo dục – Tác giả: Nguyễn Hữu Điển
5. Giáo trình thuật toán và kỹ thuật lập trình Pascal – NXB Sở giáo dục và đào tạo Hà Nội – Tác giả: Nguyễn Chí Trung