SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ

PHÒNG GD&ĐT HẬU LỘC
TRƯỜNG THPT ĐINH CHƯƠNG DƯƠNG

SÁNG KIẾN KINH NGHIỆM

CÁCH VIẾT THUẬT TOÁN CỦA MỘT SỐ BÀI TOÁN CỤ THỂ
BẰNG PHƯƠNG PHÁP LIỆT KÊ HAY SƠ ĐỒ KHỐI

Người thực hiện: Đỗ Thị Hiền
Chức vụ: Giáo viên
Đơn vị công tác:Trường THPT Đinh chương Dương
SKKN thuộc lĩnh vực (môn): Tin học

THANH HOÁ NĂM 2016
-1-


I.MỞ ĐẦU

MỤC LỤC
I. Mở đầu
1.Lí do chọn đề tài...........................................................................................3
2.Mục đích nghiên cứu....................................................................................4
3.Đối tượng nghiên cứu...................................................................................4
4.Phương pháp nghiên cứu..............................................................................4
II. Nội dung sáng kiến kinh nghiệm................................................................4
1 Cơ sở lí luận của sáng kiến kinh nghiệm......................................................4
2.Thực trạng của vấn đề trước khi áp dụng sáng kiến kinh nghiệm................4
3. Các sáng kiến kinh nghiệm hoặc các giải pháp đã sử dụng để giải quyết

viết thuật toán bằng cách liệt kê hay sơ đồ khối và nội dung của bài này nó
cũng là cơ sở để giúp cho chúng ta viết chương trình trên máy tính một cách dễ
dàng bằng cách dựa vào thuật toán của bài toán, nội dung này rất khó và mới
đối với các em.
Từ lí do trên, tôi xin trình bày sáng kiến kinh nghiệm “CÁCH VIẾT
THUẬT TOÁN CỦA MỘT SỐ BÀI TOÁN CỤ THỂ BẰNG PHƯƠNG
PHÁP LIỆT KÊ HAY SƠ ĐỒ KHỐI “ .Với các ví dụ được trình bày trong
sáng kiến kinh nghiệm của mình sẽ giúp cho học sinh nắm bắt hơn về cách viết
thuật toán của một bài toán khi học bài 4 tin học 10.
Do lần đầu tiên thực hiện làm sáng kiến kinh nghiệm, nên không tránh
khỏi những thiếu sót. Mong quý thầy cô góp ý để lần sau làm tốt hơn.

3


2. Mc ớch nghiờn cu
S dng tớnh chõt lp ca cỏc thuõt toỏn trc ht hc sinh nm c cỏc
bc, ý ngha ca thuõt toỏn. V thụng qua cỏc vớ d hng dn hc sinh nm
vng, hiu rừ thuõt toỏn.
3. i tng nghiờn cu.
Hc sinh khi 10 tai trng THPT inh Chng Dng.
S dng cỏc vớ d thc hin thuõt toỏn.
4. Phng phỏp nghiờn cu .
Kt hp thc tin giỏo dc trng THPT inh Chng Dng.
Cú tham kho cỏc ti liu tin hc 10 v ti liu v sỏng kin kinh
nghim.

II. NI DUNG SNG KIN KINH NGHIM
CCH VIT THUT TON CA MT S BI TON C TH
BNG PHNG PHP LIT Kấ HAY S KHI

b

Bài 3: Viết thuật toán để sắp xếp 1 dãy số nguyên bất kỳ nhập từ
bàn phím theo thứ tự giảm dần.
Kết quả kiểm tra nh sau:
Điểm
3
4
5
6
7

Số học sinh
9
8
8
5
5

Tỉ
26
23
23
14
14

lệ
%
%
%

ở ví dụ 1
Các hệ số a, b, c bất Nghiệm của phơng
kỳ
trình (nếu có) có dạng
số nguyên hoặc số
thực.
ở ví dụ 2
S nguyờn dng N
N la s nguyờn t hoc N
khụng phi l s nguyờn t
Phát vấn học sinh: Em hãy nhận xét sự giống và khác nhau
giữa bài trong Tin học và bài toán trong Toán học?
Học sinh trả lời: Bài toán trong Toán học yêu cầu chúng ta
giải cụ thể để tìm ra kết quả, còn bài toán trong Tin học yêu
cầu máy tính giải và đa ra kết quả cho chúng ta.
Từ đây giáo viên trình chiếu khái niệm Bài toán trong
Tin học : Là một việc nào đó mà ta muốn máy tính thực hiện
để từ thông tin đầu vào (dữ kiện) máy tính cho ta kết quả
mong muốn.
- Những dữ kiện của bài toán đợc gọi là Input.
- Kết quả máy tính trả ra đợc gọi là Output của bài toán.
Sau đó giáo viên yêu cầu học sinh tìm lại Input và Output của
2 ví dụ trên.
Nh vậy, khái niệm bài toán không chỉ bó hẹp trong phạm vi
môn toán, mà phải đợc hiểu nh là một vấn đề cần giải quyết
trong thực tế, để từ những dữ kiện đã cho máy tính tìm ra
kết quả cho chúng ta.
6



Xỏc nh bi toỏn: L i tỡm Input v Output ca bi toỏn .
Tỡm ý tng gii bi toỏn
7


Vit thut toỏn bng phng phỏp lit kờ hay s khi
Bớc 3: Giới thiệu cho học sinh 2 cách biểu diễn một
thuật toán
- Cách l: Liệt kê các bớc: Chính là dùng ngôn ngữ tự nhiên
để diễn tả các bớc cần làm khi giải một bài toán bằng máy
tính.
- Cách 2: Dùng sơ đồ khối.
S dng s khi : trong s khi ngi ta dựng mt s khi, ng
mi tờn vi quy c :
Hỡnh thoi

th hin thao tỏc so sỏnh

Hỡnh ch nht

th hin cỏc phộp tớnh toỏn

Hỡnh ụ van

th hin thao tỏc nhp, xut d liu

Cỏc mi tờn

trỡnh t thc hin cỏc thao tỏc.


- Bớc 6: Nếu > 0 thông báo phơng trình có 2 nghiệm
x1,x2=

b
, rồi kết thúc.
2a

- Bớc 7: Kết thúc.
Cách 2: Biểu diễn thuật toán bằng sơ đồ khối
Bắt
đầu
Nhập
a,b,c
Tính = b24ac


- B3 : Nếu a=0
- B3.1 Nếu b=0 thì kết luận phương trình có vô số nghiệm => B4
- B3.2 Nếu b< > 0 thì kết luận phương trình vô nghiệm => B4
- B4: Kết thúc
C¸ch 2: BiÓu diÔn thuËt to¸n b»ng s¬ ®å khèi
Nhập a,b
Đúng

Phương trình có
nghiệm x=-b/a

a0
Sai

b0

Phương trình
vô nghiệm

Đúng

Kết thúc

Sai

Phương trình có
vô số nghiệm

Bài tập 3 Viết thuật toán tính tổng sau:
S=1/2+1/3+1/4+…+1/N

ii+1
Bài 4 : Cho N và dãy a1,…,aN, hãy tìm giá trị nhỏ nhất (Min) của dãy đó .
Lời giải:
Yêu cầu học sinh tìm Input và Output của bài toán


Xác định bài toán :
+ Input : Nhập N và dãy a1,…,aN
+ Output : Giá trị nhỏ nhất (Min) của dãy số

Gọi học sinh dựa vào bài toán tìm Max của dãy hãy nêu ý tưởng giải bài toán


Ý tưởng của bài toán: - Khởi tạo giá trị Min =a1

11


- Lần lược với I chạy từ 2 đến N, so sánh giá trị số
hạng ai với giá trị Min, nếu ai< Min thì Min sẽ nhận giá trị mới là ai.
 Thuật toán của bài toán:
C¸ch 1: LiÖt kª tõng bíc

- Bước 1. Nhập N và dãy a1,…,aN
- Bước 2. Min ¬ a1, i ¬ 2
- Bước 3. Nếu i >N thì đưa ra giá trị Min rồi kết thúc
- Bước 4
• Bước 4.1 Nếu ai
muối cô muốn hoán đổi số lượng gạo trong xô phải được đựng vào
chậu và số lượng muối ở trong chậu phải được chuyển sang đựng
trong xô” để làm được điều đó em nào có thể nêu cách làm ?
Học sinh trả lời
- B1: Em đổ gạo ở trong xô sang một thùng không
- B2: Đổ lượng muối ở trong chậu sang xô
- B3: Em lấy gạo ở trong thùng không đổ chậu
- B4: Kết quả là em được xô thì đựng muối chậu thì đựng gạo
Từ ví dụ trên giáo viên hình thành ý tưởng giải bài toán


Ý tưởng của bài toán:Việc hoán giá trị của hai biến A và C được làm
theo các bước sau:
(Giá trị A và C lúc nhập ban đầu)

B1
:

A

B2
:

B

C ( B lấy giá trị của biến A)
( A lấy giá trị của C )

B3
:


Đưa ra giá trị mới của A
và C rồi kết thúc

13


Bài 6 : Viết thuật toán đếm các số âm trong dãy số A={ a 1,a2,…aN } cho
trước.
Lời giải:
Yêu cầu học sinh tìm Input và Output của bài toán


Xác định bài toán :
+ Input : Nhập N và dãy a1,…,aN
+ Output : Số lượng các số âm trong dãy số



Ý tưởng của bài toán:
- Khởi tạo giá trị Dem =0
- Lần lược với i chạy từ 1 đến N, nếu ai nhỏ hơn 0 thì tăng biến Dem
lên 1 đơn vị cho đến khi i >N thì dừng lại và xuất giá trị biến Dem.

 Thuật toán của bài toán:
C¸ch 1: LiÖt kª tõng bíc

B1:sốNhập
số nguyên
dương N và n số a1,…,aN;

khèi
-

S

ai
i1; Sum 0


i>N

a ra giỏ tr Sum ri
kt thỳc

S


ai >0

Sum Sum +1

S

ii+1

4. Hiu qu ca sỏng kin kinh nghim
So sánh, đối chứng tỉ lệ % kết quả của học sinh trớc và
sau khi thực hiện đề tài ta thấy rõ ràng kết quả của học sinh
sau khi đợc học bằng giáo án điện tử trên máy chiếu kết hợp
mô phỏng cụ thể, kết quả thực tế đối với lớp 10A4 có 35 học
sinh (với đề kiểm tra giống lớp 10A1 ở trên) sau khi thực hiện
đề tài nh sau:
-

Cỏc em trong lp cú thỏi hc tớch cc hn rõt nhiu. Th hin
tinh thn tham gia tr li cõu hi.


TØ lệ
14%
29%
29%
14%
14%

III. PHẦN KẾT LUẬN
Tin học nói chung đóng vai trò hết sức quan trọng trong xã hội hiện đại,
tin học đã làm thay đổi nhận thức của con người và ứng dụng trong hầu hết các
hoạt động của xã hội loài người.
Với việc xây dựng các thuật toán minh họa như trên, trong quá trình
giảng dạy Tin học 10, bản thân thấy rằng các tiết học về bài toán và thuật toán
không còn nhàm chán, khô cứng nữa mà trở nên sôi nổi hơn và học sinh cũng
có thể hiểu các thuật toán một cách dễ dàng hơn.
Hơn nữa, với mỗi thuật toán, giáo viên có thể minh họa bằng rất nhiều bộ
Test khác nhau mà không mất nhiều công sức, có thể nói đây là đặc điểm nổi
bật mà máy tính có thể trợ giúp cho con người.
Đề tài này ra đời từ kinh nghiệm của bản thân trong quá trình giảng dạy và
từ những kiến thức mà tôi đã tham khảo với đồng nghiệp, có thể chương trình
của tôi còn chưa đạt tối ưu. Tôi rất mong sự góp ý chân thành của quý thầy cô
để tôi có một sáng kiến kinh nghiệm hoàn hảo hơn.
HIỆU TRƯỞNG

Hậu lộc, ngày 15/5/2016
Người thực hiện

Phạm Thế Dũng