Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán
MỘT SỐ PHƯƠNG PHÁP
TÌM HIỂU VỀ BÀI TOÁN VÀ THUẬT TOÁN
I/ LÍ DO CHỌN ĐỀ TÀI
Ngày nay, trên thế giới nói chung và Việt Nam nói riêng đang diễn ra quá
trình tin học hoá trên nhiều lĩnh vực hoạt động của xã hội loài người và đem lại
nhiều hiệu quả to lớn. Việc sử dụng máy tính không còn chỉ bó hẹp trong viện
nghiên cứu, các trường đại học, các trung tâm máy tính mà còn mở rộng ra mọi
cơ quan, tổ chức kinh tế,.. và trong các gia đình. Song song với quá trình trên,
việc giảng dạy Tin học trong các trường đại học, THPT cũng được đẩy mạnh đi
đôi với việc tăng cường trang bị máy vi tính. Đảng và Nhà nước ta đã nhận thấy
được tầm quan trọng của ngành Tin học và đã đưa môn học này vào trường phổ
thông như những môn học khác bắt đầu từ năm học 2006-2007.
Chính vì vậy, đối với mỗi giáo viên giảng dạy môn Tin học ở các trường
phổ thông, việc tìm hiểu, nghiên cứu các vấn đề về Tin học, cùng với việc tìm
các biện pháp giảng dạy Tin học trong các trường phổ thông là một công việc
cần phải làm thường xuyên, nhằm đáp ứng với sự đòi hỏi ngày càng cao của xã
hội.
Trong nghiệp vụ của người thầy (cô) giáo có hai vấn đề quan trọng: thứ
nhất là thực tiễn về tiềm năng - những kiến thức lý thuyết mà họ được học rất cơ
bản. Thứ hai là thực tiễn về nghiệp vụ - thầy (cô) giáo phải biết cách truyền thụ
kiến thức phù hợp với trình độ của học sinh. Trong đó, thực tiễn thứ hai là điều
quyết định trong nghiệp vụ của thầy (cô) giáo, nó đánh giá chất lượng giảng dạy
của thầy (cô) giáo. Hai thực tiễn trên vừa mâu thuẫn với nhau, lại vừa thống nhất
với nhau. Thầy (cô) giáo không thể mang hết các kiến thức lý thuyết cao xa và
trừu tượng dạy cho học sinh, nhưng cũng không thể dạy tốt cho học sinh nếu
thầy (cô) giáo hiểu biết quá ít.
Trong bối cảnh toàn ngành Giáo dục và Đào tạo đang nỗ lực đổi mới
phương pháp dạy học theo hướng phát huy tính tích cực chủ động của học sinh
trong hoạt động học tập. Điều 24.2 của Luật giáo dục đã nêu rõ: “Phương pháp
giáo dục phổ thông phải phát huy tính tích cực, tự giác, chủ động, sáng tạo của
Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình
1
Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán
học sinh, phù hợp với đặc điểm của từng khu vực, lớp học và môn học; bồi
dưỡng phương pháp tự học, rèn luyện kỹ năng vận dụng kiến thức vào thực tiễn,
tác động đến tình cảm, đem lại niềm vui, hứng thú học tập cho học sinh”. Như
vậy, chúng ta có thể thấy định hướng đổi mới phương pháp dạy học đã được
khẳng định, không còn là vấn đề tranh luận. Cốt lõi của việc đổi mới phương
pháp dạy học ở trường phổ thông là giúp học sinh hướng tới việc học tập chủ
động, chống lại thói quen học tập thụ động.
Đổi mới phương pháp dạy học theo hướng tích cực hóa hoạt động của học
sinh là một quá trình lâu dài; không thể ngày một ngày hai mà đông đảo giáo
viên từ bỏ được kiểu dạy học truyền thụ kiến thức, tiếp thu thụ động đã quen
thuộc từ lâu. Việc phát triển các phương pháp tích cực đòi hỏi một số điều kiện,
trong đó quan trọng nhất là bản thân mỗi giáo viên cần có một sự nỗ lực để tìm
tòi, sáng tạo trong công tác giảng dạy của mình.
Đổi mới phương pháp dạy học là một vấn đề hết sức quan trọng, nhất là
với bộ môn Tin học hiện đang được đưa vào giảng dạy ở các trường phổ thông.
Là một giáo viên giảng dạy bộ môn này, theo tôi không phải cứ tìm được nhiều
bài toán khó, bài toán hay để giảng dạy cho học sinh. Mà vấn đề đặt ra là chúng
ta cần phải tích cực tìm tòi, sáng tạo trong việc đưa ra những bài toán đó như thế
nào để giúp cho học sinh có sự hứng thú, tìm tòi sáng tạo trong quá trình học
tập, từ đó biết vận dụng linh hoạt trong các tình huống cụ thể ngoài thực tế.
Trong việc giảng dạy cho học sinh, ngoài việc giúp học sinh lĩnh hội
những kiến thức cơ bản. Người thầy còn phải biết kích thích tính tích cực, sự
sáng tạo say mê học hỏi của học sinh trong việc học tập của các em. Bởi vì, việc
học tập tự giác, tích cực, chủ động và sáng tạo đòi hỏi học sinh phải có ý thức về
những mục tiêu đặt ra và tạo được động lực bên trong thúc đẩy bản thân họ hoạt
động để đạt các mục tiêu đó.
Các cách thiết kế bài giảng hiện nay nhằm mục đích áp dụng phương
pháp hiện đại để bồi dưỡng cho học sinh năng lực ham muốn học hỏi, tư duy
sáng tạo, năng lực tự giải quyết vấn đề, rèn luyện và phát triển năng lực tự học
sáng tạo, nghiên cứu, nghĩ và làm việc một cách tự chủ… Đồng thời để thích
Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình
2
Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán
ứng với sự phát triển tư duy của học sinh trong xã hội mới và tiếp cận với các
công nghệ tiên tiến trên thế giới. Bên cạnh đó, trong các kỹ thuật dạy học mới,
vai trò của người thầy có sự thay đổi là: “hướng dẫn học sinh biết tự mình tìm ra
hướng giải quyết những vấn đề nảy sinh trong quá trình học tập, biết cách làm
việc độc lập, làm việc tập thể. Thầy là người định hướng, là người cố vấn giúp
học sinh tự đánh giá, cũng như giúp học sinh luôn đi đúng con đường tìm hiểu,
lĩnh hội kiến thức…”.
Xuất phát từ thực tiễn giảng dạy tại trường THPT Thanh Bình tôi thấy
rằng, để đạt hiệu quả cao trong mỗi phần học, tiết học cần có cách thiết kế bài
giảng cho phù hợp với nội dung kiến thức, phương pháp, phương tiện dạy học
phải phù hợp với từng đối tượng học sinh. Để qua mỗi phần học, tiết học học
sinh thích thú với kiến thức mới, qua đó hiểu được kiến thức đã học trên lớp,
đồng thời học sinh thấy được tầm quan trọng của vấn đề và việc ứng dụng của
kiến thức trước hết để đáp ứng những yêu cầu của môn học, sau đó là việc ứng
dụng của nó vào các công việc thực tiển trong đời sống xã hội (nếu có).
Tuy nhiên, với các em học sinh nói chung và đặc biệt ở vùng nông thôn
nói riêng, việc tiếp cận với bộ môn Tin học còn nhiều hạn chế. Một lẽ dễ hiểu đó
là vì hầu hết các em ít có điều kiện tiếp xúc, nguyên nhân chính là điều kiện
kinh tế cũng như cơ sở vật chất chưa đáp ứng đầy đủ, vì thế lĩnh vực công nghệ
thông tin vấn còn khá mới mẻ!
Vì vậy quá trình dạy và học bộ môn Tin học trong nhà trường phổ thông
còn gặp rất nhiều khó khăn. Từ thực tế này tôi muốn chia sẻ một kinh nghiệm
nho nhỏ để chúng ta cùng tham khảo trong quá trình dạy học, đó là kinh nghiệm
về việc phối hợp một số phương pháp trong giờ dạy- học để giúp học sinh có cái
nhìn trực quan, giúp các em nắm được bài tốt hơn. Cụ thể tôi muốn nói ở đây là
dùng "giáo án điện tử" do giáo viên tự biên soạn để trình chiếu bài giảng, kết
hợp thuyết trình, vấn đáp và mô phỏng bằng các ví dụ thực tế cho học sinh.
Trước đây chúng ta thường sử dụng phương pháp thuyết trình, vấn đáp
đơn thuần trên lớp do chưa đủ phương tiện. Nhưng những năm gần đây, được sự
Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình
3
Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán
quan tâm của Bộ Giáo dục _ Sở Giáo dục và Đào tạo đã trang bị cho các trường
phổ thông một số máy tính (Computer) và máy chiếu (Projector), vì vậy chúng
ta có nhiều điều kiện dùng "giáo án điện tử" để trình chiếu bài giảng cho học
sinh.
Tôi xin trình bày phương pháp giảng dạy của mình thông qua một ví dụ
về một bài giảng cụ thể trong chương trình Tin học lớp 10, đó là bài "Tìm hiểu
bài toán và thuật toán". Đây được coi là bài học khó trong chương trình giáo
khoa lớp 10 và có liên quan chặt chẽ đến kiến thức lớp 11 sau này.
Giúp học sinh hiểu được 2 khái niệm then chốt là "bài toán" và "thuật
toán", nắm được các tính chất của thuật toán và cách diễn tả thuật toán bằng 2
cách: liệt kê và sơ đồ khối.
Giúp cho học sinh có cái nhìn trực quan sinh động hơn đối với môn Tin
học.
Rèn luyện cho học sinh có tư duy khoa học, logic, tác phong sáng tạo, say
mê môn học.
II/ CƠ SỞ LÍ LUẬN VÀ THỰC TIỄN
1/ Cơ sở lí luận
- Nhiều gia đình và học sinh chưa có điều kiện trang bị máy tính cho học
sinh vì đời sống gia đình còn gặp nhiều khó khăn.
- Nhiều gia đình còn ngại cho học sinh sử dụng máy tính vì sợ con em
mình ham mê các trò chơi điện tử . . .
- Một số học sinh chưa thực sự số gắng tự học, tự nâng cao khả năng tư
duy về toán học cũng như các thuật toán.
- Một số học sinh chưa hiểu hết tầm quan trong của thuật toán và chưa ứng
dụng môn học này vào quá trình giải quyết một số bài toán đại số và vật lý bằng
máy tính điện tử.
- Tình hình ứng dụng tin học nói chung và ngôn ngữ lập trình đã góp phần
không nhỏ trong việc học tập của học sinh trong một vài năm gần đây cùng với
Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình
4
Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán
xu hướng đổi mới phương pháp giảng dạy, học sinh đã không ngừng ứng dụng
thành quả của lập trình vào học tập.
- Trong giáo dục phổ thông cần phải phát huy tính tích cực, tự giác, chủ
động sáng tạo của học sinh phù hợp với từng lớp học, môn học, tác động đến
tình cảm đem lại niềm vui, hứng thú trong khi học môn tin học.
- Phương pháp tích cực là phương pháp giáo dục, dạy học theo hướng phát
huy tính tích cực, chủ động sáng tạo của người học thông qua việc tổ chức hiệu
quả các hoạt động của học sinh.
2/ Thực tiễn của vấn đề
a /Tình trạng thực tiễn khi chưa thực hiện đề tài
Trước đây khi chưa áp dụng phương pháp giảng dạy bằng giáo án điện tử,
lấy ví dụ từ thực tế… học sinh luôn phản ánh với giáo viên rằng: “Bài toán và
thuật toán” này khó hiểu và trừu tượng. Khi kiểm tra với mức độ đề tương
đương với một vài ví dụ trong sách giáo khoa, các em vẫn mơ hồ và đạt kết quả
chưa cao.
b/ Khảo sát thực tế
Giáo viên đưa ra đề kiểm tra 1 tiết đối với lớp 10A3 có 38 học sinh như
sau:
Bài 1: Xác định Input và Output của bài toán sau:
“Tính tổng các bình phương các chữ số của 1 số tự nhiên bất kỳ có 4 chữ số ”
Bài 2: Liệt kê các bước của thuật toán để giải bài toán sau :
a
Rút gọn phân số b với a, b bất kỳ, b 0 .
Kết quả kiểm tra như sau:
Điểm
2.5 đến 3
4
5
6
7
8
9
Số học sinh
10
7
8
6
4
3
0
Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình
Tỉ lệ
29%
18%
21%
15%
10%
8%
0%
5
Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán
10
0
0%
Đối với Bài 1: Hầu như học sinh chỉ tìm được Input và Output của bài toán mà
chưa viết được đầy đủ thuật toán để giải.
Đối với Bài 2: Học sinh chưa mô phỏng được thuật toán bằng cách liệt kê hoặc
sơ đồ khối
III/ TỔ CHỨC THỰC HIỆN CÁC GIẢI PHÁP
1/ Chuẩn bị
a/ Về phương pháp:
- Giáo viên soạn trước bài giảng "Tìm hiểu Bài toán và Thuật toán" trên
máy tính bằng phần mềm PowerPoint “Bài soạn này được dạy trong 5 tiết học”.
Sử dụng phương pháp thuyết trình kết hợp pháp vấn.
- Chuẩn bị một số bài tập áp dụng để rèn luỵên kỹ năng biểu diễn thuật
toán.
b/ Về phương tiện:
- Giáo viên chuẩn bị máy tính “để bàn hoặc xách tay”, một máy chiếu, một
màn chiếu, bút chỉ laze, bảng phụ …
- Học sinh cần có đầy đủ sách bút, vở ghi…
2/ Các bước thực hiện bài giảng "Tìm hiểu bài toán và thuật toán"
* Hoạt động 1: Giúp học sinh hiểu rõ khái niệm "Bài toán" trong Tin học:
Giáo viên đặt vấn đề bằng cách đưa ra các ví dụ để học sinh quan sát:
Ví dụ 1: Giải phương trình bậc 2 tổng quát: ax2+ bx+ c= 0 (a 0).
Ví dụ 2: Giải bài toán
"Trăm trâu trăm cỏ
Trâu đứng ăn năm
Trâu nằm ăn ba
Lụ khụ trâu già
Ba con một bó"
Hỏi có bao nhiêu trâu mỗi loại ?
Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình
6
Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán
Ví dụ 3: Bài toán quản lý học sinh trong một kỳ thi tốt nghiệp bằng máy tính:
SBD
Điểm
Điểm Điểm
Điểm Điểm Điểm Tổng Xếp
Họ và tên
Ngoại
toán văn
lý
sinh
sử điểm loại
ngữ
Đào T Hoa
8
9
7
8
6
5
43 Khá
51012
3
51012 Mai T Hà
2
3
4
4
5
3
21 Yếu
4
51012 Đỗ T Nga
9
8
7
8
9
10
51 Giỏi
5
51012 Lê T Nhàn
6
5
4
9
8
7
45 Khá
6
51012 Mai V Sơn
6
7
4
3
6
5
31
TB
7
Phát vấn học sinh: Em hãy xác định dữ kiện ban đầu và kết quả của mỗi
bài toán sẽ có dạng gì? (Dạng số, hình ảnh, hay văn bản?)
Học sinh trả lời:
Dữ kiện
Ví dụ 1
Ví dụ 2
Ví dụ 3
Các hệ số a, b, c bất kỳ
Có 100 con trâu và 100 bó cỏ.
Mỗi con trâu đứng ăn 5 bó.
Mỗi con trâu nằm ăn 3 bó.
3 con trâu già ăn chung một bó
Số báo danh, họ tên, ngày sinh,
điểm toán, điểm văn, điểm lý…
Kết quả
Nghiệm của phương trình (nếu có)
có dạng số nguyên hoặc số thực.
Số lượng trâu đứng, trâu nằm và
trâu già (dạng số nguyên)
Tổng điểm của mỗi học sinh, xếp
loại tốt nghiệp nào, đỗ hay trượt…
Phát vấn học sinh: Một bài toán trong “toán học” gồm mấy phần? đó là
những phần nào?
Học sinh trả lời: Một bài toán trong “toán học” gồm hai phần:
- Giả thiết
- Kết luận
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 toán
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.
Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình
7
Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán
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.
Toán học
Giả thiết
Kết luận
Tin học
Thông tin đưa vào máy
Thông tin muốn lấy tứ máy
Thuật ngữ
Input
Output
- 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 3 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.
* Hoạt động 2: Giúp học sinh hiểu rõ khái niệm "Thuật toán" trong Tin
học:
+ Bước 1: Giáo viên nêu tình huống:
Bài toán
Input
Output
- Làm thế nào để từ Input của bài toán, máy tính tìm cho ta Output ?
Học sinh trả lời: Ta cần tìm cách giải bài toán và làm cho máy tính hiểu được
cách giải đó.
Đến đây sẽ có em thắc mắc: Như vậy chúng ta vẫn phải giải bài toán mà
có khi còn phức tạp hơn trong Toán học?
Bài toán
Input
Bước 1, Bước 2 . . . . . . . . . . . . . . .Bước n
Output
Thuật toán
Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình
8
Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán
Giáo viên giải thích: Nếu như trong Toán học chúng ta phải giải trực tiếp
từng bài để lấy kết quả, thì ở đây, chúng ta chỉ cần tìm cách giải bài toán tổng
quát và máy tính sẽ giải cho ta một lớp các bài toán đồng dạng.
Ví dụ: Bài toán giải phương trình bậc 2 với 3 hệ số a,b,c bất kỳ, bài toán
tìm diện tích tam giác với độ dài 3 cạnh được nhập bất kỳ, bài toán tìm UCLN
của 2 số nguyên bất kỳ, bài toán quản lý học sinh ,v.v…
+ Bước 2: Giáo viên đưa ra khái niệm thuật toán và các tính chất của một thuật
toá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
các thao tác ấy, từ thông tin đầu vào (Input) của bài toán ta nhận được kết quả
(Output) cần tìm”.
Các tính chất của một thuật toán:
- Tính dừng
- Tính xác định
- Tính đúng đắn
+ 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.
Một số quy ước khi biểu diễn thuật toán bằng sơ đồ khối:
Khối hình oval: mô tả thao tác nhập xuất dữ liệu
Khối hình chữ nhật: mô tả các thao tác tính toán
Khối hình thoi: mô tả các thao tác so sánh
Mũi tên: mô tả trình tự thực hiện các bước
Giáo viên nhắc học sinh phải nhớ các quy ước trên để biểu diễn thuật toán
được chính xác.
Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình
9
Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán
* Hoạt động 3: Giới thiệu và hướng dẫn học sinh mô tả, biểu diễn thuật toán
của một số bài toán điển hình. “Trọng tâm”
Bài toán 1: Giải phương trình bậc 2 tổng quát : ax2+bx+c = 0 ( a ≠ 0).
Trước tiên giáo viên yêu cầu học sinh xác định Input và Output của bài toán:
- Input:
3 hệ số a,b,c.
- Output:
Nghiệm của phương trình .
Sau đó gọi một học sinh đứng lên nhắc lại cách giải một phương trình bậc
2 đầy đủ hoặc có thể một em lên bảng giải bài toán phương trình bậc 2 dạng
tổng quát, rồi từ đó từng bước hướng dẫn học sinh viết thuật toán theo 2 cách.
Lưu ý rằng giáo viên vừa trình chiếu từng bước của thuật toán vừa vấn
đáp học sinh “dùng hiệu ứng xuất hiện phù hợp”
Cách 1: Liệt kê từng bước
- Bước 1: Bắt đầu
- Bước 2: Nhập 3 hệ số a,b,c.
- Bước 3: Tính biệt số = b2- 4ac
- Bước 4: Nếu < 0 thông báo phương trình vô nghiệm rồi kết thúc.
- Bước 5: Nếu = 0 thông báo phương trình có nghiệm kép
x
b
2a rồi
kết thúc.
- Bước 6: Nếu
b
> 0 thông báo phương trình có 2 nghiệm x1,x2= 2a
, rồi kết thúc.
- Bước 7: Kết thúc.
Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình
10
Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán
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
= b2- 4ac
Đúng
<0
=0
Phương trình vô nghiệm
Sai
Phương trình
có nghiệm kép x= -b/2a
Đúng
Sai
Kết thúc
Phương trình có 2 nghiệm
x1,x2=(-b
)/2a
Sau khi đã hướng dẫn xong các cách biểu diễn thuật toán để giải bài toán trên,
giáo viên nêu ra các ứng dụng của bài toán này trong thực tế: dùng để giải các
phương trình bậc 2 trên máy tính cá nhân, tích hợp vào máy tính bỏ túi như:
Casio FX 500A, Casio FX 500MS... mà học sinh chỉ cần nhập 3 hệ số a,b,c vào
máy là ngay lập tức máy tính sẽ cho nghiệm chính xác.
Bài toán 2: Giải phương trình bậc nhất ax +b = 0
- Phát vấn học sinh: Khác với phương trình bậc 2 dạng tổng quát theo em
để giải phương trình bậc nhất ta có các cách nào?
- Học sinh lên bảng trình bày?
Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình
11
Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán
Giáo viên lưu ý phân tích cho học sinh hiểu: Để trình bày thuật toán
này bằng cách liệt kê có rất nhiều lựa chọn và từ đó đưa ra lựa chọn ngắn gọn,
đơn giản, dễ hiểu và dễ trình bày nhất.
Giáo viên bắt đầu trình chiếu các cách liệt kê biểu diễn thuật toán và giải
thích ý nghĩa từng biến dùng trong thuật toán:
Cách 1: Liệt kê các bước
- Bước 1: Nhập a, b
- Bước 2: Nếu a = b thì
- Bước 2.1: Nếu Nếu b= 0 Xuất phương trình vô số nghiệm rồi kết
thúc
- Bước 2.2: Nếu b<>0 Xuất phương trình vô nghiệm rồi kết thúc
- Bước 3: Nếu a<> 0 thì x = -b/a Xuất giá trị x rồi kết thúc.
Cách 2:
- Bước 1:
Nhập a, b
- Bước 2:
NẾU a= 0 thì
Nếu b = 0
Xuất phương trình vô số nghiệm rồi kết thúc
Ngược lại thì
Xuất phương trình vô nghiệm rồi kết thúc
NGƯỢC LẠI thì
x = -b/a Xuất giá trị x rối kết thúc
* Thuật toán sơ đồ khối:
Nhập a, b
Đúng
Xuất pt vô số nghiệm
rồi (kết thúc)
Đúng
a = 0?
b = 0?
Sai
Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình
Sai
Xuất pt vô
nghiệm rồi (kết
thúc)
12
Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán
x = -b/a
Xuất x
rồi (kết thúc)
* Chú ý: Giáo viên nên chọn hiệu ứng xuất hiện từng bước để học sinh
tiện theo dõi.
Bài toán 3: Tìm Max của hai số nguyên dương A và B
Trước tiên giáo viên phát vấn học sinh nêu ý tưởng để giải bài toán này.
* Ý tưởng:
- Trước tiên ta có thể mời hai hoc sinh lên bảng sau dó so sanh chiều cao
của hai bạn.
- Nếu bạn A cao hơn bạn B thì Max là bạn A ngược lại Max là bạn B
- Trình chiếu thuật toán:
Cách 1: Liệt kê các bước
- Bước 1: Hai số nguyên dương A và B
- Bước 2: Nếu A> B thì Max là A rồi chuyển đền bước 4
- Bước 3: Nếu A< B thì Max là b rồi chuyển đền bước 4
- Bước 4 : Đưa ra Max của A và B rồi kết thúc
Cách 2: Biểu diễn bằng sơ đồ khối
Nhập A, B
A>B
Đ
Max A
S
Max B
Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình
Đưa ra Max
rồi
Kết thúc
13
Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán
Bài toán 4: Tìm UCLN của hai số nguyên dương A và B
- Pháp vấn học sinh: Thế nào là UCLN của hai số nguyên dương?
- Học sinh trả lời : UCLN của một số nguyên dương là hai số đó chia hết cho
một số lớn nhất.
Cách 1: Thuật toán liết kê.
Bước 1: Nhập hai số nguyên dương A và B
Bước 2: Nếu A = B thì UCLN của A và B là A or là B rồi kết thúc.
Bước 3: Nếu A > B thì A = A – B rồi quay lại Bước 2
Bước 4: Nếu B > A thì B = B – A rối quay lại Bước 2
Bước 5: Xuất UCLN của A và B rồi kết thúc
Cách 2: Thuật toán sơ đồ khối
- Ở bài toán này giáo viên cho học sinh thảo luận nhóm để từ đó học sinh
có thể hình dung và trình bày thuật toán này bằng sơ đồ khối.
- Sau mười phút giáo viên gọi học sinh lên bảng trình bày thuật toán, các
nhóm khác đưa ra những nhận xét góp ý.
- Các nhóm đã nhận xét góp ý xong, giáo viên củng cố lại và trình chiếu
thuật toán:
Nhập A,B
A=B
Đúng
Đưa ra UCLN
của A, B rồi (kết
thúc)
Sai
A>B
Đúng
A= A- B
Sai
Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình
14
Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán
B=B-A
Bài toán 5 : Tìm UCLN của hai số nguyên dương A = 25 và B= 15.
* Ý tưởng: Duyệt lần lượt cho đến khi hai số đó chia cho một số lớn nhất
- Giáo viên lại tiếp tục trình chiếu và hướng dẫn học sinh 2 cách biểu diễn
thuật toán.
Cách 1: Liệt kê các bước
Bước 1: Nhập hai số nguyên dương A = 25 và B = 15
Bước 2: Nếu A = B thì UCLN của A và B là A or là B rồi kết thúc.
Bước 3: Nếu A > B thì A = 25 – 15 rồi quay lại Bước 2 (A = 10)
Bước 4: Nếu B > A thi B = 15 – 10 rồi quay lại Bước 2 (B = 5)
Bước 4: Nếu A > B thi B = 10 – 5 rồi quay lại Bước 2
(A =5)
Bước 5: Xuất UCLN của A=25 và B=15 là 5 rồi kết thúc
Cách 2: Biểu diễn bằng sơ đồ khối
Nhập A= 25,B=15
Đúng
A=B
Đưa ra UCLN của
A, B rồi (kết thúc)
Sai
Đúng
A>B
Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình
A = 25 - 15
15
Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán
Sai
B=B-A
Duyệt lần thứ nhất:
A = 25 và B =15 A > B; A = A – B (25 -15) A = 10
- Lần duyệt thứ nhất ta thấy A =10 và B = 15 nên A < B vì thế ta chuyển
sang lần duyệt thứ hai
Lần duyệt thứ hai
Nhập A= 25, B=15
Đúng
A=B
Đưa ra UCLN của
A, B rồi (kết thúc)
Sai
Sai
AB
A = 10 - 5
Sai
B=B-A
Duyệt lần thứ ba:
A = 10 và B =5 A > B; A = A – B (10 -5) A = 5
- Lần duyệt thứ ba ta thấy A =5 và B = 5 nên A = B vậy UCLN của A = 25
và B = 15 là 5
* Sau ba lần duyệt ta tìm ra được UCLN của hai số nguyên dương A = 25 và B =
15 là 5 rồi kết thúc.
Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình
17
Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán
Bài toán 6: Tính tổng của 100 số tự nhiên đầu tiên:
- Trước tiên giáo viên cần yêu cầu học sinh xác định hai yêu tố Input và Output.
+ Input: Dãy 100 số tự nhiên đầu tiên: 1, 2, 3, . . ., 100.
+ Output: Giá trị tổng 1 + 2 + 3 + . . . + 100.
* Ý tưởng: Để giải bài toán này là dùng một biến Sum để lưu giá trị của
tổng. Việc tìm Sum có thể được thực hiện như sau:
Đầu tiên gán cho Sum giá trị bằng 0. Tiếp theo lần lượt thêm các giá trị 1,
2, 3, 4, ….., 100 vào Sum. Vấn đề là ở chỗ tổ chức việc “lần lượt thêm vào” như
thế nào? Cách dễ nhận thấy nhất là thực hiện liên tiếp 100 phép cộng:
Bước 1: Sum 0.
Bước 2: Sum Sum + 1.
...
Bước 101: Sum Sum + 100.
Tuy nhiên việc mô tả thuật toán như trên là quá dài dòng (nhất là khi
không chỉ tính tổng của 100 số mà các số cần tính tổng lớn hơn nhiều). Để ý một
chút ta có thể thấy trong tất cả các bước nêu trên đều chỉ có một phép toán để
thực hiện: cộng thêm vào Sum lần lượt các giá trị 1, 2, 3, …, 100. Tức là chỉ có
một thao tác “cộng” được lặp đi lặp lại 100 lần. Mặt khác, việc cộng thêm số i
vào Sum chỉ được thực hiện khi i không vượt quá 100. Vì vậy, thuật toán tìm
Sum có thể được mô tả ngắn gọn hơn như sau:
Bước 1: Sum 0; i 0.
Bước 2: i i + 1.
Bước 3: Nếu i <= 100, thì Sum Sum + i và quay lại bước 2.
Bước 4: Thông báo kết quả rồi kết thúc.
Giáo viên có thể mô ta bằng hình vẽ
8
7
để học sinh nắm bắt dễ hơn.
6
.
.
.
.
.
.
5
4
3
2
3
2
1
1
Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình
18
Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán
Bài toán 7: Tìm số lớn nhất trong dãy A các số a1, a2, …, an cho trước.
* Ý tưởng: Ta sẽ dùng biến Max để lưu giá trị phần tử lớn nhất của dãy A.
Việc xác định Max có thể được thực hiện như sau:
Đầu tiên ta gán giá trị a1 cho biến Max, tiếp theo ta lần lượt so sánh các số
a2, …, an của dãy A với Max. Nếu ai > Max, ta gán ai cho Max.
Từ đó ta có thuật toán như sau:
+ Input: Dãy A các số a1, a2, …, an (n>=1).
+ Output: Giá trị Max = max
a1, a2, …, an
Bước 1: Max a1; i 1.
Bước 2: i i + 1.
Bước 3: Nếu i > n, chuyển đến bước 5.
Bước 4: Nếu ai > Max, Max ai. Quay lại bước 2.
Bước 5: Kết thúc thuật toán.
* Ta có thể minh họa thuật toán trên với một trường hợp chọn Thỏ lớn
nhất trong bốn chú Thỏ như sau:
Max
1
2
1
3
4
- Duyệt lần 1: Trước hết, ta giả sử thỏ lớn nhất là thỏ số 1, tức là Max 1.
Max 1
Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình
19
Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán
1
2
3
4
- Duyệt lần 2: So sánh Max (thỏ số 1) với thỏ số 2. Vì thỏ số 2 nhỏ hơn thỏ số 1,
do đó Max vẫn bằng 1.
Max 3
1
2
3
4
- Duyệt lần 3: So sánh Max (thỏ số 1) với thỏ số 3. Vì thỏ số 3 lớn hơn thỏ số 1,
do đó Max được đặt lại bằng 3 (thỏ số 3)
Max 3
Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình
20
- Xem thêm -