Ph n 1: ĐĂT VÂN ĐÊ ầ
Kinh th a quy ưthây cô giao!
Ti n sĩ tri u Lê, Thân Nhân Trung đã nói “Hi n tài là nguyên khíế ề ề
c a qu c gia, nguyên khí th nh thì th n c m nh mà h ng th nh, nguyênủ ố ị ế ướ ạ ư ị
khí suy thì th n c y u mà th p hèn”. Vì th các b c đ v ng thánhế ướ ế ấ ế ậ ế ươ
minh luôn coi vi c giáo d c nhân tài, kén ch n k sĩ, vun tr ng nguyênệ ụ ọ ẻ ồ
khí qu c gia làm công vi c hàng đu..., câu nói b t h c a Thân Nhânố ệ ầ ấ ủ ủ
Trung đã cho th y t th i xa x a các th h ông cha đã r t coi tr ng nhânấ ừ ờ ư ế ệ ấ ọ
tài và coi nh ng nhân tài là t ng lai c a đt n c. V i c ng v là m tữ ươ ủ ấ ướ ớ ươ ị ộ
giáo viên chuyên ngành Tin h c tr c ti p gi ng d y, tôi th y đc nh ngọ ự ế ả ạ ấ ượ ữ
nhi m v quan tr ng ph i làm đu tiên đó là làm th nào đ h c sinhệ ụ ọ ả ầ ế ể ọ
thích h c và h c gi i môn Tin. Trong th i đi ngày nay, Tin h c có vaiọ ọ ỏ ờ ạ ọ
trò và v trí đc bi t quan tr ng trong khoa h c kĩ thu t và đi s ng, giúpị ặ ệ ọ ọ ậ ờ ố
con ng i ti p thu m t cách d dàng các môn khoa h c khác có hi uườ ế ộ ễ ọ ệ
qu .ả
Có th nói phát hi n và b i d ng HSG là m t trong nh ng ho tể ệ ồ ưỡ ộ ữ ạ
đng chuyên môn chính trong năm h c c a tr ng. B n thân qua thamộ ọ ủ ườ ả
kh o các đ thi HSG c a t nh và qu c gia đã th y h u h t các đ thi đuả ề ủ ỉ ố ấ ầ ế ề ề
có các bài toán t i u. Đ gi i các bài toán tôi u thì có nhi u ph ngố ư ể ả ư ề ươ
pháp gi i, trong đó ng d ng thu t toán quay lui đ gi i bài toán t i uả ứ ụ ậ ể ả ố ư
cũng là m t ph ng pháp đc nhi u ng i s d ng. Đo cung chinh la ộ ươ ượ ề ườ ử ụ
ly do đê tôi viêt đê tai !“Thu t toán quay lui và ng d ng gi i bài toánậ ứ ụ ả
t i u”.ố ư
Tôi rât mong đc s gop y cua quy thây cô đê đê tai ngay cang ươ" ư" ! !
đc hoan thiên h n.ươ" " ơ
Xin chân thanh cam n! ơ
Trang 1
Phân 2: NH NG BIÊN PHAP GIAI QUYÊT VÂN ĐÊ Ư
I. C S LÝ LU N C A V N ĐƠ Ở Ậ Ủ Ấ Ề:
Cũng nh trình bày trên bài toán t i u là m t trong nh ng bàiư ở ố ư ộ ữ
toán th ng g p trong các k thi h c sinh gi i.ườ ặ ỳ ọ ỏ
Công vi c khó khăn đây là làm th nào đ các em có th hi uệ ở ế ể ể ể
đc thu t toán và có th ng d ng vào gi i các bài toán liên quan.ượ ậ ể ứ ụ ả
Xu t phát t th c ti n nh v y, tôi đã đa ra m t s b c giúp choấ ừ ự ễ ư ậ ư ộ ố ướ
các em có th hi u đc thu t toán và ng d ng đ gi i các bài toánể ể ượ ậ ứ ụ ể ả
cùng lo i:ạ
-Ý t ng c a thu t toán.ưở ủ ậ
- Thu t toán.ậ
-ng d ng thu t toán gi i các bài toán đn gi n.Ứ ụ ậ ả ơ ả
-ng d ng thu t toán quay lui có đánh giá c n gi i m t s bàiỨ ụ ậ ậ ả ộ ố
toán ph c t p.ứ ạ
-ng d ng thu t toán gi i bài toán trong các đ thi h c sinh gi i.Ứ ụ ậ ả ề ọ ỏ
II. TH C TR NG C A V N Đ:Ự Ạ Ủ Ấ Ề
1) Th c tr ng v c p qu n lýự ạ ề ấ ả
*) u đi m:Ư ể
- Đã quan tâm vào công tác phát tri n mũi nh n.ể ọ
- Có s phân công nhi m v cho t ng giáo viên tr c ti pự ệ ụ ừ ự ế
gi ng d y, giám sát và ki m tra quá trình th c hi n c a giáo viên.ả ạ ể ự ệ ủ
- Đng viên tinh th n cũng nh t o m i đi u ki n thu n l iộ ầ ư ạ ọ ề ệ ậ ợ
nh t đ giáo viên th c hi n nhi m v .ấ ể ự ệ ệ ụ
*) H n ch :ạ ế
Khi phân công nhi m v thì ch a xác đnh m t chi n l cệ ụ ư ị ộ ế ượ
lâu dài, đó là ch t p trung phát hi n và b i d ng h c sinh l p 11ỉ ậ ệ ỗ ưỡ ọ ớ
Trang 2
mà không phát hi n và b i d ng ngay t khi các em đang h c l pệ ồ ưỡ ừ ọ ớ
10.
2) Th c tr ng v giáo viênự ạ ề
*) u đi m:Ư ể
- Đc đào t o v chuyên môn c b n, có s c kh e, s c tr ,ượ ạ ề ơ ả ứ ỏ ứ ẻ
có lòng nhi t tình trong công vi c. Luôn luôn h c t p trau d i triệ ệ ọ ậ ồ
th c, nh m ph c v t t nh t cho s nghi p giáo d c.ứ ằ ụ ụ ố ấ ự ệ ụ
- Trong quá trình gi ng d y, tuy g p nhi u khó khăn nh ngả ạ ặ ề ư
ph n l n các th y cô giáo đu đt ch “tâm” lên hàng đu, đây làầ ớ ầ ề ặ ữ ầ
m t trong nh ng thu n l i góp ph n vào s thành công c a ngànhộ ữ ậ ợ ầ ự ủ
giáo d c.ụ
- Có s đu t vào nghiên c u khi đc giao nhi m v .ự ầ ư ứ ượ ệ ụ
*) H n ch :ạ ế
M t s giáo viên không có tâm huy t, ch a t p trung vàoộ ố ế ư ậ
công tác chuyên môn nên ki n th c v ôn luy n h c sinh gi i cònế ứ ề ệ ọ ỏ
h n ch . Vi c b i d ng HSG ch t p trung cho s ít giáo viênạ ế ệ ồ ưỡ ỉ ậ ố
trong t .ổ
3) Th c tr ng v h c sinh ự ạ ề ọ
*) u đi m:Ư ể
- Các em HS ngoan, c n cù ch u khó, có ý th c v n lênầ ị ứ ươ
trong h c t p.ọ ậ
- Có trách nhi m v i vi c h c t p, trong quá trình h c t pệ ớ ệ ọ ậ ọ ậ
hăng say phát bi u, đóng góp nên s thành công c a bài gi ng.ể ự ủ ả
*) H n ch :ạ ế
- Ki n th c c b n v l p trình còn r t nhi u h n ch , chế ứ ơ ả ề ậ ấ ề ạ ế ỉ
có s ít em h c sinh trên đa bàn th tr n, m i đc ti p c n v iố ọ ị ị ấ ớ ượ ế ậ ớ
l p trình ch ng trình l p 8 – THCS.ậ ở ươ ớ
Trang 3
- Đa s các em h c t t môn Tin h c thì l i h c t t các mônố ọ ố ọ ạ ọ ố
khoa h c t nhiên (Toán, Lí, Hóa), nên đã theo tham gia b i d ngọ ự ồ ưỡ
các b môn đó.ở ộ
- Tin h c là môn mà không có trong các k thi t t nghi pọ ỳ ố ệ
cũng nh đi h c hàng năm, nên các em cũng không m n mà v iư ạ ọ ặ ớ
vi c tham gia h c và b i d ng HSG.ệ ọ ồ ưỡ
4) Th c tr ng v c s v t ch tự ạ ề ơ ở ậ ấ
*) u đi m:Ư ể
- Có đ c s v t ch t đ ph c v cho l p h c.ủ ơ ở ậ ấ ể ụ ụ ớ ọ
- Có các ph ng ti n ph c v cho m c đích gi ng d y , VD:ươ ệ ụ ụ ụ ả ạ
B ng t , máy chi u, máy tính...ả ừ ế
*) H n ch :ạ ế
- Thi u tài li u và sách tham kh o.ế ệ ả
- M t s h c sinh không có đ kinh phí mua máy tính cá ộ ố ọ ủ
nhân ph c v cho m c đích ôn t p t i nhà.ụ ụ ụ ậ ạ
III. CÁC BI N PHÁP ĐÃ TI N HÀNH Đ GI I QUY T V N ĐỆ Ế Ể Ả Ế Ấ Ề:
1. Thu t toán quay luiậ: Gi thi t m t c u hình c n tìm đc mô t b iả ế ộ ấ ầ ượ ả ở
m t b ph n g m n thành ph n aộ ộ ậ ồ ầ 1, a2,...an. Gi s tìm đc i - 1 thànhả ử ượ
ph n aầ1, a2, ai-1, ta tìm thành ph n th i b ng cách duy t t t c các khầ ứ ằ ệ ấ ả ả
năng có th c a aể ủ i. V i m i kh năng j ki m tra xem nó có ch p nh nớ ỗ ả ể ấ ậ
đc không. X y ra hai tr ng h p:ượ ả ườ ợ
- Ch p nh n đc thì xác đnh aấ ậ ượ ị i theo j và ki m tra xem i = n ch a, n u iể ư ế
= n thì ta ghi nh n m t c u hình, còn n u i <n ta ti n hành xác đnh aậ ộ ấ ế ế ị i+1.
- N u th t t c các kh năng mà không có kh năng nào ch p nh n ế ử ấ ả ả ả ấ ậ
đc thì quay l i b c tr c xác đnh l i aượ ạ ướ ướ ị ạ i-1.
Trang 4
N i dung c a thu t toán này r t phù h p v i vi c g i đ quy. Ta có th ộ ủ ậ ấ ợ ớ ệ ọ ệ ủ
t c đ quy sau đây:ụ ệ
Procedure Try (i:tinteger);
Var j:integer;
Begin
For j:=1 to n do
if ch p nh n j ấ ậ then
Begin
xác nh n ai theo jậ
if i=n then <Ghi nh n m t c u hình>ậ ộ ấ
Else try(i+1);
End;
End;
2. ng d ng thu t toán quay lui gi i m t s bài toán c b n:Ứ ụ ậ ả ộ ố ơ ả
Bài 1: Hãy vi t ch ng trình li t kê t t c các dãy nh phân có đ dài n.ế ươ ệ ấ ả ị ộ
Bài 2: Hãy vi t ch ng trình li t kê các hoán v c a {1,2,...,n}ế ươ ệ ị ủ
Bài 3: Hãy vi t ch ng trình li t kê các t h p ch p m c a {1,2,...,n}ế ươ ệ ổ ợ ậ ủ
Bài 4: Li t kê t t c các cách s p x p nh ng con h u trên bàn c NxN ệ ấ ả ắ ế ữ ậ ờ
sao cho chúng không ăn đc nhauượ .
Bài 5: Hãy vi t ch ng trình li t kê t t c các chu trình Haminton c aế ươ ệ ấ ả ủ
đn đ th vô h ng. (ơ ồ ị ướ Chu trình b t đu t đnh v nào đó qua t t c cácắ ầ ừ ỉ ấ ả
đnh còn l i, m i đnh đúng m t l n r i quay tr v đnh v đc g i làỉ ạ ỗ ỉ ộ ầ ồ ở ề ỉ ượ ọ
chu trình Hamilton).
(*Bài 1: Hãy vi t ch ng trình li t kê t t c các dãy nh phân có đ ế ươ ệ ấ ả ị ộ
dài n.*)
Trang 5