S GIÁO D C VÀ ĐÀO T O NGH ANỞ Ụ Ạ Ệ
===== =====
Đ C NG SÁNG KI N KINH NGHI MỀ ƯƠ Ế Ệ
S D NG QUY HO CH ĐNG Đ NÂNG CAO NĂNG L C GI IỬ Ụ Ạ Ộ Ề Ự Ả
QUY T M T S V N Đ V DÃY CON B NG NGÔN NG L PẾ Ộ Ố Ấ Ề Ề Ằ Ữ Ậ
TRÌNH C++
THU C MÔN: TIN H CỘ Ọ
THÁNG 3/ 2022
S GIÁO D C VÀ ĐÀO T O NGH ANỞ Ụ Ạ Ệ
===== =====
Đ C NG SÁNG KI N KINH NGHI MỀ ƯƠ Ế Ệ
S D NG QUY HO CH ĐNG Đ NÂNG CAO NĂNG L C GI IỬ Ụ Ạ Ộ Ề Ự Ả
QUY T M T S V N Đ V DÃY CON B NG NGÔN NG L PẾ Ộ Ố Ấ Ề Ề Ằ Ữ Ậ
TRÌNH C++
THU C MÔN: TIN H CỘ Ọ
Nhóm tác gi : ảHoàng Xuân Th ng - Tr ng THPT Lê Vi t Thu tắ ườ ế ậ
Nguy n ễĐình L i - Tr ng THPT Lê Vi t Thu tợ ườ ế ậ
T b môn: ổ ộ Toán - Tin
Năm th c hi n: 2021-2022ự ệ
I. PH N M ĐUẦ Ở Ầ
1.1 Lý do ch n đ tàiọ ề
Trong qua trinh gi ng d y phát tri n năng l c cho hoc sinh khá gioi ả ạ ể ự
th ng găp rât nhiêu bai toan vê day con. Đây la dang bai tâp khó th ng xu t ườ ươ ấ
hi n trong cac đê thi hoc sinh gioi môn Tin h c. R t nhi u h c sinh khi g p d ng ệ ọ ấ ề ọ ặ ạ
bài t p d ng này thì khó tìm đc cách gi i t i u nên đi m không cao. Nguyênậ ạ ượ ả ố ư ể
nhân có th nhi u nh ng trong đo co hai nguyên nhân c ban la: ch ng trình ể ề ư ơ ươ
cho k t qu output sai hoăc ch ng trình cho k t qu output đúng v i các bế ả ươ ế ả ơ ộ
input có d liêu nho nh ng v i nh ng b input co d liêu l n thì ch ng trình ư ư ớ ữ ộ ư ơ ươ
ch y quá th i gian quy đnh là 1giây/1test (m c dù k t qu output v n đúng).ạ ờ ị ặ ế ả ẫ
Trên th c t đã có m t s tài li u đ c p đn các bài t p v dãy con,ự ế ộ ố ệ ề ậ ế ậ ề
nh ng các tài li u này m i ch đa ra thu t toán và ch ng trình gi i m t s bàiư ệ ớ ỉ ư ậ ươ ả ộ ố
t p c th làm ví d minh h a cho m t k thu t l p trình nào đó khi nghiên c uậ ụ ể ụ ọ ộ ỹ ậ ậ ứ
mà ch a khái quát d ng, ch a phân tích sâu cách t duy, cách l a ch n và cài đtư ạ ư ư ự ọ ặ
ch ng trình t i u. Các ch ng trình mà m t s tài li u đa ra r t khó hi u vàươ ố ư ươ ộ ố ệ ư ấ ể
ph c t p không phù h p năng l c h c sinh Tr ng THPT Lê Vi t Thu t. Khiứ ạ ợ ự ọ ườ ế ậ
nghiên c u các tài li u này, không ch h c sinh mà ngay c giáo ch a có kinhứ ệ ỉ ọ ả ư
nghi m cũng r t khó khăn?ệ ấ
T nh ng ly do trên, chúng tôi ch n nghiên c u đ tài: ư ư ọ ứ ề ‘‘S d ng quyử ụ
ho ch đng đ nâng cao năng l c gi i quy t m t s v n đ v dãy conạ ộ ề ự ả ế ộ ố ấ ề ề
b ng ngôn ng l p trình C++ằ ữ ậ ’’.
1.2. Muc đich nghiên c u " ư
V i mong mu n s d ng quy ho ch đng nâng cao năng l c gi i quy tớ ố ử ụ ạ ộ ự ả ế
m t s v n đ v dãy con và hi u bi t sâu s c h n cách gi i các bài t p d ngộ ố ấ ề ề ể ế ắ ơ ả ậ ạ
này, chúng tôi đã dày công nghiên c u, phân d ng các bài t p dãy con, trăn tr đứ ạ ậ ở ể
tìm ra nhi u cách làm khác nhau, đánh giá đ ph c t p, đo th i gian th c hi nề ộ ứ ạ ờ ự ệ
ch ng trình, đ so sánh tìm ra ch ng trình t i u nh t và d hi u nh t trongươ ể ươ ố ư ấ ễ ể ấ
các ch ng trình đã đa ra. T đó nâng cao ch t l ng b i d ng h c sinh gi iươ ư ừ ấ ượ ồ ưỡ ọ ỏ
môn Tin h c.ọ
1.3. Đôi t ng nghiên c u ươ" ư
Sang kiên kinh nghiêm co đôi t ng nghiên c u la ươ ư
- M t s bài toán v dãy con liên ti pộ ố ề ế
- M t s bài toán v dãy con không liên ti pộ ố ề ế
Đc nghiên c u nhi u cách làm, xét trên nhi u ph ng di n ượ ứ ở ề ề ươ ệ (trong đó
nh n m nh ph ng pháp quy ho ch đng)ấ ạ ươ ạ ộ nh : đ ph c t p, k t qu output,ư ộ ứ ạ ế ả
th i gian th c hi n ch ng trình.ờ ự ệ ươ
1.4. Ph ng phap nghiên c u ươ ư
3
Đê trinh bay sang kiên kinh nghiêm nay, chúng tôi đa s dung phôi kêt h p ư ơ
nhiêu ph ng phap nh : nghiên c u tai liêu, thuyêt trinh, quan sát, đi u tra c ươ ư ư ề ơ
b n, th c nghiêm so sanh, phân tich kêt qua th c nghiêm, … phu h p v i môn ả ư ư ơ ơ
hoc thuôc linh v c Tin hoc, Toán h c. ư ọ
Trong t ng ph n chúng tôi s p x p và trình bày các bài t p t d đn khó,ừ ầ ắ ế ậ ừ ễ ế
đng th i thông qua t ng bài t p chúng tôi c g ng phân tích nh m đa ra m tồ ờ ừ ậ ố ắ ằ ư ộ
s đnh h ng l i gi i bài toán đ rèn luy n cho h c sinh có kinh nghi m, kố ị ướ ờ ả ể ệ ọ ệ ỹ
năng v n d ng m t s bài toán t ng t nhau, h ng t i s phát tri n năng l cậ ụ ộ ố ươ ự ướ ớ ự ể ự
cho h c sinh. ọ
II . NÔI DUNG NGHIÊN C U" Ư
2.1. C s ly luânơ ơ$ "
Nêu hoc sinh bi t v n d ng ph ng pháp quy ho ch đng vào vi c gi i ế ậ ụ ươ ạ ộ ệ ả
quy t các bài toán v dãy con nói riêng và các bài t p lâp trinh nói chung thi ch t ế ề ậ ấ
l ng h c sinh gi i s đc nâng cao.ượ ọ ỏ ẽ ượ
2.2. Th c tr ng tr c khi nghiên c uự ạ ướ ứ
Các năm h c tr c chúng tôi cũng đã tr c ti p gi ng d y cho đi tuy n h cọ ướ ự ế ả ạ ộ ể ọ
sinh gi i các c p v chuyên đ dãy con, tuy nhiên vi c d y chuyên đ này chỏ ấ ề ề ệ ạ ề ủ
y u d a trên nh ng kiên th c c b n c a sách giáo khoa, tài li u tham kh oế ự ữ ứ ơ ả ủ ệ ả
ch a chú tr ng nhi u đn vi c nghiên c u ki n th c Toán h c đ v n d ngư ọ ề ế ệ ứ ế ứ ọ ể ậ ụ
gi i quy t các bài toán.ả ế
Chính vì v y nên các em ch y u ch bi t gi i quy t các bài toán mà th y, cô đãậ ủ ế ỉ ế ả ế ầ
d y mà không hi u b n ch t th t c a bài toán, khi g p các bài toán cùng d ngạ ể ả ấ ậ ủ ặ ạ
nh ng có khác chút ít thì g p ph i r t nhi u khó khăn.ư ặ ả ấ ề
K t qu c a th c tr ng: ế ả ủ ự ạ Trên c s nhi u năm đc phân công d yơ ở ề ượ ạ
kh i l p 11,ố ớ tr ng THPT ườ Lê Vi t Thu tế ậ , chúng tôi đã l u l i k t qu h c t pư ạ ế ả ọ ậ
và s ti n b c a h c sinh m i năm h c m t s l p đ có s đi chi u vàự ế ộ ủ ọ ở ỗ ọ ở ộ ố ớ ể ự ố ế
rút kinh nghi m.ệ
- B ng s li u k t qu đt đcả ố ệ ế ả ạ ượ khi ch a ưth c hi n đ tài:ự ệ ề năm h c 2019 - 2020ọ
STT L pớSĩ sốGi iỏKháTrung bình Không đt yêuạ
c uầ
1 11T135 3% 29% 57% 11%
2 11A140 13% 63% 25%
3 11A238 6% 50% 44%
- Khi th c nghi m qua các đi t ng h c sinh đã nêu trên, đa s các em cònự ệ ố ượ ọ ố
lúng túng tr c nh ng bài toán l p trình c b n.ướ ữ ậ ơ ả Ph n l nầ ớ các em còn ch a h ngư ứ
thú v i các bài toán l p trình đc bi t là v i ngôn ng pascal.ớ ậ ặ ệ ớ ữ
4
Vì v y trong quá trình gi ng d y chúng tôi đúc rút ra m t s kinh nghi mậ ả ạ ộ ố ệ
đ giúp các h c sinh ti p c n n i dung này d dàng h n, t o nhi u đam mê choể ọ ế ậ ộ ễ ơ ạ ề
h c sinh. Đ rèn năng l c và k năng l p trình cho h c sinh khá, gi i môn Tinọ ể ự ỹ ậ ọ ỏ
h c, có r t nhi u cách mà giáo viên có th áp d ng đi v i các đi t ng h cọ ấ ề ể ụ ố ớ ố ượ ọ
sinh khác nhau. Thông th ng khi cho m t bài toán tin h c có d ng t ng tườ ộ ọ ạ ươ ự
ho c d ng m r ng t m t bài toán c b n nào đó trong sách giáo khoa, ho cặ ạ ở ộ ừ ộ ơ ả ặ
m t bài toán c b n nào đó mà các em bi t thì các em có th xây d ng và cóộ ơ ả ế ể ự
h ng thú đ xây d ng thu t toán cho bài toán đt ra. Vì v y giáo viên có thứ ể ự ậ ặ ậ ể
ch n các bài t p c b n t đó m r ng và phát tri n đ rèn luy n k năng l pọ ậ ơ ả ừ ở ộ ể ể ệ ỹ ậ
trình cho h c sinh. Dĩ nhiên cách làm này không m i v i giáo viên nh ng cáchọ ớ ớ ư
ch n các bài toán c b n nh th nào đ h c sinh có th v n d ng và gây đcọ ơ ả ư ế ể ọ ể ậ ụ ượ
h ng thú cho h c sinh đó l i là đi u đáng quan tâm. Và chúng tôi đã hoàn toànư ọ ạ ề
thay th ngôn ng l p trình pascal b ng ngôn ng l p trình C++ và ngôn ng l pế ữ ậ ằ ứ ậ ữ ậ
trình Python đ t o thu n l i cho các em trong vi c cài đt ch ng trình.ể ạ ậ ợ ệ ặ ươ
2.3. Các bi n pháp s d ng đ gi i quy t v n đệ ử ụ ể ả ế ấ ề
2.3.1. C s lý thuy tơ ở ế
Khi nào thì chúng ta c n đn quy ho ch đng? Đó là m t câu h i r t khóầ ế ạ ộ ộ ỏ ấ
tr l i. Không có m t công th c nào cho các bài toán nh v y.ả ờ ộ ứ ư ậ
Tuy nhiên, có m t s tính ch t c a bài toán mà b n có th nghĩ đn quy ho chộ ố ấ ủ ạ ể ế ạ
đng. D i đây là hai tính ch t n i b t nh t trong s chúng:ộ ướ ấ ổ ậ ấ ố
Bài toán có các bài toán con g i nhauố
Bài toán có c u trúc con t i uấ ố ư
Th ng thì m t bài toán có đ c hai tính ch t này, chúng ta có th dùngườ ộ ủ ả ấ ể
quy ho ch đng đc. M t câu h i r t thú v là không dùng quy ho ch đng cóạ ộ ượ ộ ỏ ấ ị ạ ộ
đc không? Câu tr l i là có, nh ng n u b n đi thi code thì k t qu không cao.ượ ả ờ ư ế ạ ế ả
a. Dãy con liên ti pế
Dãy con liên ti p là dãy g m các ph n t liên ti p thu c m t dãy cho tr c.ế ồ ầ ử ế ộ ộ ướ
Ví d :ụ Cho dãy A g m 4 s nguyên {5,3,4,-4}. Dãy s {4}; {3,4}; {5,3,4};ồ ố ố
{5,3,4,-4}; … đc g i là các dãy con liên ti p c a dãy A.ượ ọ ế ủ
b. Dãy con không liên ti pế
Dãy con có th ch n không liên ti p là dãy thu đc sau khi xóa m t s ph n tể ọ ế ượ ộ ố ầ ử
(có th không xóa ph n t nào) c a m t dãy cho tr c và gi nguyên th t cácể ầ ử ủ ộ ướ ữ ứ ự
ph n t còn l i trong dãy.ầ ử ạ
Ví d :ụ Cho dãy B g m 6 s nguyên {3,5,-8,7,24,4}. Dãy s {3}; {3,5}; {-8,7};ồ ố ố
{7,24,4}; {3,1,2,-6,9}; … đc g i là các dãy con có th ch n không liên ti pượ ọ ể ọ ế
c a dãy A.ủ
c. Mô hình v dãy conề
5
