SKKN: Hướng dẫn học sinh lựa chọn thuật toán tối ưu khi lập trình giải bài toán trên máy tính

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

Ề

Ế

THÔNG TIN CHUNG V  SÁNG KI N

1. Tên sáng ki n:ế

ướ ự ọ ọ ẫ ậ ố ư H ng d n h c sinh l a ch n thu t toán t ậ i  u khi l p trình gi ả   i

bài toán trên máy tính.

ự ụ ế 2. Lĩnh v c áp d ng sáng ki n:

ạ ậ ụ ả ọ Áp d ng trong gi ng d y l p trình môn tin h c 11.

ụ ờ ế   3. Th i gian áp d ng sáng ki n:

ừ ế T  ngày 20, tháng 09, năm 2014 đ n ngày 20, tháng 4, năm 2016.

4. Tác gi : ả

ễ ọ ị ươ H  và tên: Nguy n Th  Ph ng Ngân.

Năm sinh: 1986.

ườ ể ậ ườ ỹ ơ      N i th ng trú: Khu T p th  giáo viên tr ng THPT M  Tho.

ư ạ ử ộ ọ Trình đ  chuyên môn: c  nhân s  ph m tin h c.

ứ ụ ạ ọ Ch c v  công tác: Giáo viên d y môn Tin h c.

ệ ơ ườ ỹ N i làm vi c: Tr ng THPT M  Tho.

ệ ạ       Đi n tho i: 0975061791.

ơ ị ế ụ 5. Đ n v  áp d ng sáng ki n:

ị ườ ỹ ơ       Tên đ n v : Tr ng THPT M  Tho.

ỉ ị ị Đ a ch : xã Yên Chính – Ý Yên – Nam Đ nh.

ườ

ỹ

1

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

Ụ

Ụ

M C L C

2 Trang ..................................................................................................................................

Trang

ướ ự ọ ọ ề ẫ ậ ố ư ậ Đ  tài: H ng d n h c sinh l a ch n thu t toán t i  u khi l p trình

ả gi i bài toán trên máy tính.

ế ề ệ ạ ả I. Đi u ki n, hoàn c nh t o ra sáng ki n

ế ớ ệ ể ẽ ạ ọ Hi n nay trên th  gi ứ   i, tin h c ngày càng phát tri n m nh m , có  ng

ộ ự ự ủ ủ ế ể ầ ộ ụ d ng r ng rãi trong h u h t các lĩnh v c c a xã h i, s  phát tri n c a tin

ượ ằ ờ ứ ỗ ề ầ ọ h c đ c tính b ng gi , c  m i gi ờ ạ  l ả i có thêm phiên b n ph n m m tin

ớ ượ ạ ề ấ ầ ọ ượ h c đ ữ c nâng c p hay có nh ng ph n m m m i đ c t o ra. Ở ệ  Vi t Nam

ườ

ỹ

2

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

ặ ợ ề ở ậ ọ ọ ắ cũng v y, tin h c có m t tr  giúp trong m i ngành ngh , ọ ơ    kh p m i n i,

ừ ổ ế ị ế ớ ấ ả ọ ườ t thành th  đ n nông thôn và ph  bi n v i t t c  m i ng ườ ừ i t ng i già

ẻ ừ ữ ữ ế ườ ế đ n tr , t nh ng công ­ nhân viên đ n nh ng ng ề ấ ầ   i nông dân đ u r t c n

ủ ầ ọ ọ ở ộ ế ự ợ đ n s  tr  giúp c a tin h c.  Ngày nay, tin h c đã tr  thành m t ph n không

ộ ố ủ ế ể ỗ th  thi u trong cu c s ng c a m i chúng ta.

ử ộ ị ườ ở ề ứ ự ể     L ch s  phát tri n xã h i loài ng i đang n n văn minh th  ba. S  hình

ỗ ề ủ ụ ề ể ắ ớ ộ thành và phát tri n c a m i n n văn minh g n li n v i m t công c  lao

ơ ướ ư ẳ ớ ố ớ ề ạ ộ đ ng m i, ch ng h n nh  máy h i n c – đ i v i n n văn minh công

ệ ử ệ ớ ề ố nghi p, máy tính đi n t ­ đ i  v i n n văn minh thông tin. Máy tính chính

ụ ợ ứ ự ể ể ầ ọ là công c  tr  giúp cho s  phát tri n Tin h c, có th  đáp  ng nhu c u tính

ử ư ữ ệ ế ộ ả toán, l u tr , tìm ki m,.., và x  lý thông tin m t cách có hi u qu .

ộ ử ỉ ệ ư ố Máy tính có t c đ  x  lý nhanh (hàng t  l nh trên 1 giây) nh ng nó cũng

ớ ụ ư ế ạ ấ ả có   gi i   h n.   T t   c   các   máy   tìm   ki m   (ví   d   nh   google,   yahoo   hay

ề ượ ậ ạ ệ ủ ằ ộ gmail…) đ u đ ữ ậ   c l p trình b ng các đo n l nh c a m t Ngôn ng  l p

ử ụ ư ậ ố ư ố ấ trình nào đó nh ng máy nào s  d ng thu t toán t i  u (t t nh t ) thì tìm

ượ ẽ ượ ả ườ ế ki m đ c nhanh, chính xác và s  đ c đông đ o ng ự i dùng l a ch n s ọ ử

d ng.ụ

ể ề ậ ậ ớ ộ ộ V i m t bài toán cũng v y, m t bài toán có th  có nhi u thu t toán đ ể

ả ư ự ậ ọ ố ư ấ ố gi i nh ng ta nên l a ch n thu t toán t ậ   i  u (có s  phép tính ít nh t). V y

ệ ự ư ớ ế ậ ả ọ ộ ỏ ộ vi c l a ch n m t thu t toán đ a t i k t qu  nhanh là m t đòi h i th c t ự ế

ượ ặ ệ ế ươ ầ c n đ c quan tâm đ c bi t. Do đó, trong khi vi t ch ng trình ta nên tìm

ế ươ ự ệ ố cách vi t sao cho ch ng trình th c hi n càng ít phép toán càng t ấ   t. Xu t

ư ề ướ ự ẫ phát t ừ ự ế  th c t đó tôi   đ a ra đ  tài: ọ   ọ “H ng d n h c sinh l a ch n

ậ ố ư ả ằ ị nh m đ nh thu t toán t ậ i  u khi l p trình gi i bài toán trên máy tính”

ườ

ỹ

3

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

ướ ọ ế ự ậ ọ ố ư h ng cho các em h c sinh bi t phân tích, l a ch n thu t toán t i  u tr ướ   c

ậ ả khi l p trình gi i bài toán trên máy tính.

II. Mô t ả ả  gi i pháp

ạ ự 1. Th c tr ng

ấ ầ ố ớ ự ế ủ ậ ọ ọ ộ ố Nh n th y t m quan tr ng c a Tin h c đ i v i th c t ọ    cu c s ng, m i

ề ừ ự ụ ạ ọ lĩnh v c, ngành ngh , t ộ  năm h c 2007­ 2008 B  giáo d c và đào t o đã

ọ ọ ườ ư đ a môn Tin h c thành môn h c chính th c ứ ở ấ ả  t t c  các tr ọ   ng Trung h c

ố ớ ổ ọ ỗ ượ ạ ươ ơ ở c  s , Trung h c ph  thông. M i kh i l p đ c biên so n ch ng trình t ừ

ế ụ ể ừ ự ể ề ấ ằ ọ ế ề ơ ả c  b n đ n c  th  t ng v n đ  nh m giúp h c sinh có s  hi u bi t v  Tin

ự ư ữ ọ ớ ọ ừ ọ h c, có s  t duy, logic gi a Tin h c v i các môn h c khác, t đó giúp các

ậ ụ ự ế em v n d ng vào th c t .

ươ ọ ậ ạ ọ Trong ch ọ   ng trình Tin h c 11 đi sâu vào d y h c l p trình, các em h c

ể ượ ứ ề ậ ơ ở ữ ệ sinh đã hi u đ ế c nh ng khái ni m c  s , ki n th c v  l p trình, đã có th ể

ứ ể ậ ụ ế ả ậ v n d ng ki n th c đ  l p trình gi i các bài toán trên máy tính. Tuy nhiên

ấ ả ậ ậ ươ các em l p trình còn mang tính ch t c m tính, l p trình sao cho ch ng trình

ượ ứ ư ế ự ậ ọ ố ư ạ ch y đ c ch  ch a bi t phân tích, l a ch n thu t toán t i  u đ  gi ể ả   i

ế ướ ự ế ư ề ướ ọ quy t bài toán. Tr c th c t đó tôi đ a ra đ  tài: ẫ “H ng d n h c sinh

ọ ậ ố ư ả ự l a ch n thu t toán t ậ i  u khi l p trình gi i bài toán trên máy tính”

ằ ị ướ ế ậ ố ư nh m đ nh h ng cho các em  bi t thu t toán t ả ự   i  u là gì, vì sao ph i l a

ọ ố ư ể ừ ế ự ậ ọ ậ ch n thu t toán t i  u, đ  t đó các em bi t phân tích, l a ch n thu t toán

ướ ậ ả tr c khi l p trình gi i bài toán trên máy tính.

ả 2. Các gi ọ i pháp tr ng tâm

ụ ầ 2.1. M c đích, yêu c u

ụ ệ ề ầ ổ ồ ­ Đ  tài này đi sâu vào m c đích trao đ i cùng đ ng nghi p, các th y cô

ệ ự ọ ượ ủ ố ư giáo vai trò c a vi c l a ch n đ ậ c thu t toán t i  u.

ườ

ỹ

4

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

ớ ạ ọ ậ ả ộ ­ Giúp các em h c sinh nh  l i quy trình khi l p trình gi i m t bài toán trên

ặ ệ ướ ự ậ ọ ả ọ máy tính, đ c bi t là b c l a ch n thu t toán gi ấ i bài toán r t quan tr ng.

ể ượ ọ ở ­ Giúp các em h c sinh hi u đ ậ c thu t toán ự    đây là cái gì và vì sao nên l a

ọ ố ư ể ả ừ ướ ộ ậ ch n thu t toán t i  u đ  gi i bài toán, t ứ  đó đ ng tr ọ   c m t bài toán h c

ế ậ ườ ấ ự ể ề ợ ọ sinh bi t nh n xét, phân tích các tr ậ   ng h p đ  đ  xu t, l a ch n thu t

ố ư ả ươ ơ toán  t i  u gi i bài toán sao cho ch ạ ng trình ch y nhanh h n.

ộ ố ơ ả ư ắ ế ế ậ ọ ­ Thông qua m t s  thu t toán c  b n (nh  s p x p, tìm ki m,…) h c sinh

ế ậ ụ ể ả ể ứ ạ ữ ế ơ bi t v n d ng đ  có th  gi i quy t nh ng bài toán ph c t p h n.

ộ 2.2. N i dung

ắ ạ ướ ậ ả 2.2.1. Nh c l i các b c l p trình gi i bài toán trên máy tính

ườ ả ọ ậ ng khi l p trình gi i bài toán trên máy tính h c sinh hay b ị Thông th

ắ ế ươ ỏ ướ ả ầ m c sai l m là vi t ch ng trình luôn mà b  qua các b c gi i bài toán trên

ậ ươ ư ế ể ạ ả máy tính, vì v y có khi ch ng trình đã ch y nh ng sai k t qu  vì hi u sai

ư ặ ậ ả ề đ , ho c thu t toán ch a kh  thi…

ắ ọ ạ ậ ậ ậ ứ         Vì v y khi d y l p trình giáo viên nh c h c sinh không nên ngay l p t c

ế ươ ớ ạ ướ ả vi t ch ng trình mà nên nh  l i các b c gi ệ   i bài toán trên máy tính. Vi c

ả ườ ượ ế ướ gi i bài toán trên máy tính th ng đ c ti n hành qua 5 b c sau:

ướ ị + B c 1: Xác đ nh bài toán;

ướ ự ặ ọ ế ế + B c 2: L a ch n ho c thi ậ t k  thu t toán;

ướ ế ươ + B c 3: Vi t ch ng trình;

ướ ệ ỉ + B c 4: Hi u ch nh;

ướ ế ệ + B c 5: Vi t tài li u.

ướ ả ướ ự ặ Trong 5 b c gi i bài toán trên máy tính thì b ọ c l a ch n ho c thi ế ế  t k

ặ ậ ệ ấ ể ể ề ọ thu t toán đ c bi t r t quan tr ng đ  các em có th  phân tích đ  bài, tìm ra

ướ ả ậ ợ h ng gi i, thu t toán phù h p.

ườ

ỹ

5

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

ộ ố ệ 2.2.2. M t s  khái ni m

ậ ệ 2.2.2.1. Khái ni m thu t toán

ậ 2.2.2.1.1. Thu t toán là gì

ể ả ậ ữ ạ ộ ộ 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 thao tác  y t ấ ừ

ậ ượ ủ ầ Input c a bài toán, ta nh n đ c Output c n tìm.

ấ ủ ậ 2.2.2.1.2. Các tính ch t c a thu t toán

ộ ố ữ ả ế ạ ầ ự ừ ậ ệ      ­ Tính d ng: Thu t toán ph i k t thúc sau m t s  h u h n l n th c hi n

các thao tác.

ự ệ ặ ậ ộ ị ế      ­ Tính xác đ nh: Sau khi th c hi n m t thao tác thì ho c là thu t toán k t

ể ượ ặ ị ự ệ ế ộ thúc ho c là có đúng m t thao tác xác đ nh đ  đ c th c hi n ti p theo.

ế ắ ả ậ ượ ậ     ­ Tính đúng đ n: Sau khi thu t toán k t thúc, ta ph i nh n đ c Output

ầ c n tìm.

ọ ậ ố ư ả ự 2.2.2.1.3. Vì sao ph i l a ch n thu t toán t i  u

ả ự ọ ậ ố ư a. Vì sao ph i l a ch n thu t toán t i  u

ự ượ ậ ộ ộ ươ Sau khi đã xây d ng đ c m t thu t toán và m t ch ng trình t ươ   ng

ứ ặ ượ ứ ặ ậ ộ ượ ng, m c dù đã đ c cài đ t theo m t thu t toán đúng và đáp  ng đ c các

ấ ủ ư ế ậ ả ố ố   ể tính ch t c a thu t toán nh ng có th  không cho k t qu  mong mu n đ i

ộ ộ ữ ệ ề ặ ặ ỏ ờ ớ v i m t b  d  li u nào đó vì ho c là nó đòi h i quá nhi u th i gian, ho c là

ớ ể ư ủ ộ ữ ữ ệ ủ ế ươ không có đ  b  nh  đ  l u gi d  li u và các bi n c a ch ng trình. Vì

ể ư ầ ậ ậ ố ư ậ v y ta c n phân tích thu t toán đ  đ a ra thu t toán t i  u.

ể ậ ị ố ư ứ b. Căn c  vào đâu đ  xác đ nh thu t toán là t i  u

ộ ứ ể ậ ậ ớ ộ ỉ V i m t bài toán, không ch  có m t thu t toán, v y căn c  vào đâu đ  có

ể ượ ứ ể ậ ơ th  nói đ ậ c thu t toán này nhanh h n thu t toán kia? Ta có th  căn c  vào

ớ ầ ờ ế ể ự ệ ề ậ ộ th i gian và b  nh  c n thi t đ  th c hi n thu t toán. Trong đ  tài này ta

ườ

ỹ

6

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

ự ệ ệ ế ậ ờ ờ ẽ s  quan tâm đ n th i gian th c hi n thu t toán. Vi c đánh giá th i gian

ệ ủ ẫ ớ ự ậ ề ờ ứ ạ ệ ộ ộ th c hi n c a thu t toán d n t i m t khái ni m “đ  ph c t p v  th i gian

ậ ượ ứ ườ ủ c a thu t toán” đã đ c ch ng minh và th ng đ ượ ọ ắ c g i t ộ ứ ạ   t là đ  ph c t p

ứ ạ ủ ệ ậ ậ ỏ ộ ủ c a thu t toán, kí hi u là O(..). Đ  ph c t p c a thu t toán càng nh  thì

ậ ả ạ thu t toán càng ch y nhanh và kh  thi.

ế ố ụ ự ề ệ ấ ậ ộ ờ ộ Th i gian th c hi n m t thu t toán ph  thu c vào r t nhi u y u t ư    nh :

ướ ữ ệ ữ ệ ự ư ủ ể ố ợ kích th ọ c c a d  li u đ a vào, l a ch n, b  trí ki u d  li u có h p lý

không…

ẽ ế ự ệ ể ậ ậ ờ ố ệ     V y đ  tính toán th i gian th c hi n thu t toán ta s  đ m s  câu l nh mà

ộ ố ườ ự ệ ụ ể ể ế ợ ặ nó th c hi n, ho c trong m t s  tr ng h p có th  đ m c  th  phép tính

ự ể ệ ặ ậ ỏ ạ   ố ọ s  h c, so sánh, gán…mà thu t toán đòi h i th c hi n ho c có th  ch y

ự ươ ụ ể ữ ậ ử ằ ộ ế tr c ti p ch ệ   ng trình b ng m t ngôn ng  l p trình c  th  và th  nghi m

ờ ộ ố ộ ữ ệ ấ ồ ả ử ế ệ ớ ế   nó nh  m t s  b  d  li u nào đ y r i so sánh k t qu  th  nghi m v i k t

ả ế qu  mà ta đã bi t.

ậ ữ c. Ngôn ng  thu t toán

ữ ể ả ữ ậ ậ ọ ­ Ngôn ng  dùng đ  miêu t thu t toán g i là ngôn ng  thu t toán.

ườ ượ ả ằ ộ ử ộ ậ    ­ Thu t toán th ng đ c mô t ẽ ự   ệ  b ng m t dãy các l nh. B  x  lý s  th c

ộ ậ ự ệ ệ ặ ệ ấ ị ừ ế hi n các l nh đó theo m t tr t t nh t đ nh cho đ n khi g p l nh d ng thì

ế k t thúc.

ữ ồ ậ    ­ Ngôn ng  thu t toán bao g m:

ữ ệ ướ + Ngôn ng  li ừ t kê t ng b c;

ố ơ ồ    + S  đ  kh i;

ữ ậ + Ngôn ng  l p trình

ử ụ ữ ệ ề ướ ư      ­   Trong đ  tài này tôi  u tiên s  d ng ngôn ng  li ừ t kê t ng b c và

ữ ậ ngôn ng  l p trình Pascal.

ườ

ỹ

7

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

ộ ố ơ ả ườ ậ 2.2.3. M t s  thu t toán c  b n th ng dùng

ắ ế ậ 2.2.3.1. Thu t toán s p x p

2.2.3.1.1. Bài toán

1, a2,…,

ố ươ ố ồ ng N và dãy A g m N s  nguyên: a * Bài toán: Cho s  nguyên d

ố ạ ứ ế ắ ả ướ ớ   c không l n aN. S p x p  dãy A thành dãy không gi m (t c là s  h ng tr

ơ ố ạ h n s  h ng sau).

* Ví d :ụ  Cho N=6, dãy A: 3 2 1 4 6 3

ế ắ => Dãy sau khi s p x p: 1 2 3 3 4 6

ậ 2.2.3.1.2. Thu t toán

ả ạ ượ ọ ế ọ ậ          Trong quá trình h c t p và gi ng d y tôi đã đ c h c và bi ấ   t có r t

ươ ể ự ư ắ ế ế ắ ẳ ạ ọ ề nhi u ph ắ   ng pháp s p x p (ch ng h n nh  s p x p ki u l a ch n, s p

ế ể ế ể ể ắ ầ ắ ạ ố ắ   ế x p ki u thêm d n, s p x p ki u phân đo n, s p x p ki u vun đ ng, s p

ể ậ ườ ầ ự ự ế ế ế x p ki u hòa nh p hai đ ắ ng tr c ti p, s p x p tu n t ế   ổ ắ , tráo đ i, s p x p

ươ ổ ọ nhanh Quick sort…). Tuy nhiên trong ch ư   ng trình tin h c ph  thông tôi  u

ươ ế ế ắ ắ ằ ử ụ tiên s  d ng ph ổ ng pháp s p x p b ng tráo đ i và s p x p nhanh Quick­

ấ ươ ổ ơ ế ằ ả ắ ậ sort. Tôi nh n th y: ph ễ ể   ng pháp s p x p b ng tráo đ i đ n gi n d  hi u

ố ượ ự ệ ờ ớ ọ v i h c sinh, s  l ng phép tính toán, chi phí th i gian th c hi n cũng

ữ ệ ư ớ ươ ế ậ không quá cao, tuy nhiên n u t p d  li u đ a vào l n thì ph ng pháp này

ươ ế ắ ả ộ ộ ạ b c l ế  h n ch ; còn ph ộ   ng pháp s p x p nhanh Quick sort thì qu  là m t

ệ ờ ế ắ ậ ấ ờ thu t toán s p x p tuy t v i, có chi phí th i gian th p.

ư ề ế ế ắ ắ ằ   ậ      Trong đ  tài này tôi đ a ra hai thu t toán s p x p đó là: s p x p b ng

ể ộ ế ắ ổ ả ự tráo đ i và s p x p nhanh Quick sort đ  đ c gi ử ụ    có s  so sánh và s  d ng

ườ ạ linh ho t trong tr ợ ụ ể ng h p c  th .

ắ ế ổ ậ ằ 2.2.3.1.2.1. Thu t toán s p x p b ng tráo đ i

ườ

ỹ

8

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

ưở ươ ỗ ặ ố ạ ứ ề ề ớ V i m i c p s  h ng đ ng li n k  trong dãy, * Ý t ng ph ng pháp:

ơ ố ệ ổ ế ố ướ ớ n u s  tr ỗ c l n h n s  sau ta đ i ch  chúng cho nhau. Vi c đó đ ượ ặ   c l p

ạ ự ổ ữ ế ỗ l i cho đ n khi không có s  đ i ch  nào n a.

ậ  * Thu t toán:

Procedure sapxeptraodoi;

Var i, j, tg: integer;

begin

For i:=1 to n­1 do

For j:= n downto i+1 do

If a[j]< a[j­1] then

Begin

Tg:=a[j];

A[j]:=a[j­1];

A[j­1]:=tg;

End;

End;

ỗ ầ ử ụ ậ ặ ệ    Thu t toán trên s  d ng 2 vòng l p  for… => m i l n duy t i ậ * Nh n xét:

ấ ẩ ị ớ ự ệ ể ề ả ố ph i th c hi n n­1 phép so sánh đ  tìm ra giá tr  l n nh t đ y v  cu i dãy.

n

(*

)1

ậ ố ầ ế ộ V y s  phép toán c n thi t là: (n­1)+(n­2)+…+1= ứ ạ    => Đ  ph c t p

(cid:0)n 2

2).

ỉ ỡ ậ ấ ủ c a thu t toán x p x  c  O(n

ắ ế ậ 2.2.3.1.2.2. Thu t toán s p x p nhanh Qick­sort

ưở ươ * Ý t ng ph ng pháp:

ể ắ ướ ầ ử ộ ẫ ế Đ  s p x p dãy tr ọ c tiên ta ch n m t ph n t ng u nhiên trong dãy làm

ầ ử ố ỏ ơ ả ượ ố ị ế ị ọ “ch t”. M i ph n t có giá tr  nh  h n “ch t” ph i đ c x p vào v  trí

ườ

ỹ

9

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

ướ ầ ử ầ ố ọ ị ớ ố tr c “ch t” (đ u dãy); m i ph n t ơ  có giá tr  l n h n “ch t”  ph i đ ả ượ   c

ế ầ ắ ố ố ị ượ ế x p vào v  trí sau “ch t”   (cu i dãy). Khi đó dãy c n s p x p đ c phân

ầ ử ạ ạ ộ ồ ố ị thành hai đo n: m t đo n g m các ph n t ộ   ỏ ơ  có giá tr  nh  h n “ch t”, m t

ầ ử ạ ồ ứ ế ụ ắ ế ặ ị ớ ố ơ đo n g m các ph n t có giá tr  l n h n “ch t”. C  ti p t c s p x p l p đi

ư ậ ẽ ạ ớ ố ượ ặ ạ l p l i nh  v y v i các đo n con cu i cùng ta s  thu đ c dãy đã đ ượ ắ   c s p

ầ ề ế x p theo chi u tăng d n.

ậ  * Thu t toán:

procedure qs(l,h:longint);

var i,j,k:longint;

begin

if l>=h then exit;

i:=l; j:=h;

k:=a[random(h­l+1)+l];

repeat

while a[i]

while a[j]>k do dec(j);

if i<=j then

begin

if i

inc(i); dec(j);

end;

until i>j;

qs(l,j); qs(i,h);

end;

ộ ứ ạ ỡ ậ Thu t toán Qick­sort có đ  ph c t p c  ~ O(nlogn) ậ    * Nh n xét:

ườ

ỹ

10

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

ậ 2.2.3.1.3. Nh n xét chung

ổ ọ ễ ế ậ ấ ắ ậ So sánh hai thu t toán trên ta th y thu t toán s p x p n i b t tuy d  cài

2) còn thu t toán Qick­sort ch  có đ  ph c ứ

ứ ạ ỡ ư ậ ộ ỉ ộ ặ đ t nh ng có đ  ph c t p c  O(n

ự ủ ệ ỡ ờ ơ   ạ t p c   O(nlogn), có nghĩa là th i gian th c hi n c a Qick­sort nhanh h n

ụ ể ừ ự ề ậ ọ ấ r t nhi u. V y tùy vào t ng bài toán c  th  mà ta nên l a ch n ph ươ   ng

3) thì không nh tấ

ế ậ ữ ệ ư ế ắ ợ ỏ pháp s p x p phù h p. N u t p d  li u đ a vào nh  (<=10

ế ả ử ụ ế ậ ữ ệ ư ớ thi ử ụ   t ph i s  d ng Qick­sort còn n u t p d  li u đ a vào l n thì s  d ng

ả ậ ộ ả ệ ờ thu t toán Qick­sort qu  là m t gi i pháp tuy t v i.

ế ậ 2.2.3.2. Thu t toán tìm ki m

2.2.3.2.1. Bài toán tìm ki mế

ế ượ ư ể ồ Bài toán tìm ki m đ c phát bi u nh  sau: Cho dãy A g m N s ố

ộ ố ầ ế t có hay không nguyên khác nhau: a1, a2,…, aN và m t s  nguyên k. C n bi

i = k. N u có hãy cho bi

ỉ ố ế ế ch  s  i  (1<=i<=N) mà a ỉ ố t ch  s  đó.

ụ ồ ố * Ví d : Cho  N=6, dãy A g m các s : 4, 6, 3, 9, 2, 15

ố ạ ớ ị ằ ậ +  V i k=9, trong dãy trên có s  h ng a ỉ ố ầ   4   có giá tr  b ng k. V y ch  s  c n

tìm là i=4.

ố ạ ị ằ ớ +  V i k=5 thì không có s  h ng nào trong dãy A có giá tr  b ng k.

ầ ự ụ ế ậ ế * Trong m c này ta xét hai thu t toán: tìm ki m tu n t và tìm ki m nh ị

phân.

ầ ự ế ậ 2.2.3.2.1.1. Thu t toán tìm ki m tu n t

ị * Xác đ nh bài toán:

ố ồ ộ ố ­ Input: dãy a g m N s  nguyên khác nhau a1, a2,…, aN và m t s  nguyên k.

ỉ ố ằ ị ặ ­ Output: v  trí (vt) b ng ch  s  i mà a ố ạ   i = k ho c thông báo không có s  h ng

ị ằ ủ nào c a dãy A có giá tr  b ng k.

ườ

ỹ

11

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

1 thì v  trí là 1, n u k

ưở ướ ế ế ị Tr c h t ta so sánh k v i a ế ớ 1 n u k = a * Ý t ng:

2 thì v  trí c a k là 2, còn tr

ế ủ ị ườ ợ   ng h p <>a1 ta so sánh ti p k v i a ế ớ 2. N u k = a

ế ượ ế ụ ế c ti p t c cho đ n khi k <>a2  thì so sánh ti p k v i a ớ 3… Quá trình trên đ

i (i<=n) thì v  trí là i, tr

i mà i>n thì k không có m tặ

ị ườ ợ ế n u k=a ng h p k <> a

trong dãy A.

ả ậ * Gi i thu t TIM_KIEM_TUAN_TU:

for i:= 1 to n do

if a[i]=k then

begin

vt:=i;

break;

end;

if vt>0 then write(f2,'da tim thay tai vi tri:',vt)

else write(f2,'khong tim thay');

ậ  * Nh n xét:

ầ ự ổ ể ế ậ ả ỹ ế      Tìm ki m tu n t ấ ơ  là k  thu t tìm ki m r t đ n gi n và c  đi n, trong

ử ụ ể ệ ậ ấ thu t toán  ta s  d ng thêm câu l nh break đ  sau khi đã tìm th y khóa k có

ế ặ ỏ ươ ề trong dãy thì thoát luôn ra kh i vòng l p và k t thúc ch ng trình, đi u này

ể ố ượ ả giúp gi m đi đáng k  s  l ng phép toán.

ớ ả ậ ườ ợ ố ấ ấ     Ta th y v i gi i thu t trên, tr ng h p t ằ   ấ t nh t là tìm th y khóa k n m

ầ ườ ợ ỉ ầ ngay đ u dãy thì ch  c n 1 phép so sánh; tr ng h p trung bình là khóa k

ữ ầ ườ ấ ấ ợ ằ ở ị n m v  trí gi a dãy c n phép so sánh, tr ng h p x u nh t là tìm

1(cid:0)n 2

ằ ở ấ ự ầ ố ờ th y khóa k n m ệ    cu i dãy c n n+1 phép so sánh => Th i gian th c hi n

ả ậ ủ c a gi i thu t trên là ~ O(n).

ườ

ỹ

12

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

ế ậ ị 2.2.3.2.1.2. Thu t toán tìm ki m nh  phân

ị * Xác đ nh bài toán:

ố ồ ượ ắ   c s p ­ Input: dãy a g m N s  nguyên khác nhau a1, a2,…, aN (dãy A đã đ

ứ ự ộ ố ầ theo th  t tăng d n) và m t s  nguyên k.

ỉ ố ằ ị ặ ­ Output: v  trí (vt) b ng ch  s  i mà a ố ạ   i = k ho c thông báo không có s  h ng

ị ằ ủ nào c a dãy A có giá tr  b ng k.

* Ví d : ụ

ầ Cho dãy A tăng d n:  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18. Tìm  s ố

ể ả ể ử ụ ậ k=8 có trong dãy A không? Đ  gi i bài toán này ta có th  s  d ng thu t toán

ế ị tìm ki m nh  phân.

ưở * Ý t ng:

Giua

ớ ố ạ ở ữ So sánh khóa k v i s  h ng a gi a dãy, trong đó Giua= [(n+1)/2]. Khi

ả ườ ộ đó x y ra m t trong ba tr ợ ng h p:

Giua thì Giua là ch  s  c n tìm. K t thúc vi c tìm ki m.

ỉ ố ầ ệ ế ế ế     + N u k = a

Giua  thì vi c tìm ki m k trên dãy g m các s  h ng a

Giua+1,

ố ạ ệ ế ồ ế        +   N u k > a

aGiua+2,…, aN;

Giua thì vi c tìm ki m k s  th c hi n trên dãy g m các s   a

ẽ ự ế ệ ệ ồ ế     + N u k < a ố 1,

a2,…, aGiua­1

.       Trong tr

ườ ộ ế ợ ế ệ ng h p m t n u k = a ơ   ế Giua thì vi c tìm ki m k t thúc quá đ n

ế ả ả ườ ư ế ợ gi n. còn n u không thì c  hai tr ề ng h p hai và ba đ u đ a đ n bài toán

ầ ử ế ả ơ ớ ượ tìm ki m trên b ng không l n h n [n/2] ph n t . Quá trình trên đ ự   c th c

ệ ớ ệ ầ ử ỉ ớ hi n cho t ả i khi b ng li t kê ch  còn 1 ph n t và so sánh k v i chính s ố

ệ ẹ ế ế ạ ạ h ng này. Vi c tìm ki m này giúp thu h p nhanh ph m vi tìm ki m. Ta có

ể ả ư ế ậ ị th  mô t thu t toán tìm ki m nh  phân nh  sau:

ả ậ * Gi i thu t TIM_KIEM_NHI_PHAN:

ườ

ỹ

13

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

i:=1;j:=n;

while i

begin

giua:=trunc ((i+j)/2);

if k>a[giua] then i:=giua+1

else j:=giua;

end;

if a[i]=k then vt:=i

else vt:=0;

if vt>0 then writeln('da tim thay tai vi tri:',vt)

else write('khong tim thay');

ậ * Nh n xét:

Giua thì

ả ậ ườ ợ ố ấ ấ Trong gi i thu t trên tr ng h p t t nh t là tìm th y khóa k = a

ỉ ầ ế ệ ế ơ ế   ả vi c tìm ki m k t thúc quá đ n gi n (ch  c n 1 phép so sánh). Còn n u

ườ ấ ợ ườ ượ ờ không tr ấ ng h p x u nh t ng ứ i ta cũng ch ng minh đ ự   c th i gian th c

2n).

ả ậ ệ ủ hi n c a gi i thu t trên là ~ O(log

ậ 2.2.3.2.2 Nh n xét chung

ầ ự ế ậ ớ ậ ị So v i thu t toán tìm ki m tu n t ự   ế , thu t toán tìm ki m nh  phân th c

ầ ử ế ệ ả ớ ơ ậ hi n tìm ki m trên b ng không l n h n [n/2] ph n t . V y trong tr ườ   ng

ệ ượ ắ ứ ự ế ậ ị ả ợ h p b ng li t kê đã đ c s p th  t thì thu t toán tìm ki m nh  phân t ố   t

ầ ự ấ ề ế ậ ườ ợ ơ h n thu t toán tìm ki m tu n t r t nhi u, còn trong tr ng h p dãy khóa

ư ượ ắ ả ể ế ế ế ắ ờ ch a đ c s p x p thì th i gian chi phí cho s p x p cũng ph i k  đ n. Vì

ừ ườ ắ ự ề ậ ợ ọ ậ v y tùy t ng tr ng h p đ  bài ra ta nên cân nh c l a ch n thu t toán sao

ự ể ệ ấ ợ cho  phù h p đ  chi phí th c hi n là ít nh t.

ộ ố ụ ứ 2.2.4. M t s  ví d  minh ch ng

ườ

ỹ

14

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

2.2.4.1. Ví d  1 ụ

ả ổ (SGK trang 51): Gi i bài toán c

ừ ừ V a gà v a chó

ạ Bó l i cho tròn

ươ Ba m i sáu con

ẵ ộ M t trăm chân ch n

ạ ỏ ỗ H i có bao nhiêu con m i lo i?

ự ọ ậ * L a ch n thu t toán cho bài toán:

ấ ầ ể ễ ổ ọ ớ Bài toán c  trên r t g n gũi v i các em h c sinh, các em có th  d  dàng

ể ả ụ ọ ế ả ấ áp d ng toán h c đ  gi ề i ra k t qu . Có r t nhi u cách khác nhau đ  gi ể ả   i

ự ệ ả ộ ơ ố ươ bài toán này. M t cách đ n gi n và s  phép toán th c hi n cũng t ố   ng đ i

ọ ố ể ễ ư ọ ố ít, h c sinh có th  d  dàng đ a ra là: G i s  gà là g; s  chó là c. Khi đó ta s ẽ

ằ ạ ố ừ ự ế có s  chó n m trong ph m vi t ể ễ  1 đ n 25 và có th  d  dàng xây d ng đ ượ   c

ươ ư ch ng trình nh  sau:

Program bai_toan_co_1;

uses crt;

var g,c: integer;

begin

clrscr;

for c:=1 to 25 do

begin

g:=36­c;

if ((4*c+2*g)=100) then

write('So ga la: ',g,' So cho la: ',c);

ườ

ỹ

15

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

end;

end.

ấ ổ ố Ta th y t ng s  gà và chó là 36 và t ng ổ ố s  chân là 100. Gi ả ử  s ậ * Nh n xét:

ấ ả ố ố ố ể t t c  là chó, thì s  con t i đa là 100/4 = 25 (con); t i thi u là 36 / 4 = 9

ỉ ầ ử ụ ư ậ ặ ừ (con). Nh  v y chúng ta ch  c n s  d ng vòng l p for t 9­>25. Cách này

ẽ ố ư ơ s  t i  u h n.

ươ Ch ng trình minh h aọ :

Program bai_toan_co_2;

uses crt;

var g,c: integer;

begin

clrscr;

for c:=9 to 25 do

begin

g:=36­c;

if ((4*c+2*g)=100) then

write('So ga la: ',g,' So cho la: ',c);

end;

end.

2.2.4.2. Ví dụ 2

ầ ử ả ồ ế ươ ạ ả . Hãy vi t ch ng trình t o m ng B[1..n], Cho m ng A g m n ph n t

ầ ử ầ ủ ủ ậ ổ trong đó b[i] là t ng c a i ph n t đ u tiên c a A. ( Bài 2­ ự   Bài t p và th c

hành 4­ SGK trang 66)

ị * Xác đ nh bài toán:

ả ồ + Input: m ng A g m n ph n t ầ ử ;

ườ

ỹ

16

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

ầ ử ầ ủ ạ ả ổ + Output: t o m ng b[1..n], trong đó b[i] là t ng c a i ph n t ủ    đ u tiên c a

a;

ể ả ể ả ể ế ề ậ ấ * Đ  gi i quy t 1 bài toán có th  có r t nhi u thu t toán đ  gi i. Gi ả ử   s

ể ử ụ ạ ầ ươ ể ả tho t đ u có th  s  d ng ch ng trình sau (có trong SGK) đ  gi ế   i quy t

bài toán này:

program subsum1;

const nmax=100;

type myarray= array[1..nmax] of integer;

var a,b:myarray;

n,i,j:integer;

begin

randomize;

write ('nhap n');

readln(n);

{ Tao ngau nhien mang gom n so nguyen}

for i:=1 to n do a[i]:=random(300)­random(300);

for i:=1 to n do write(a[i]:5);

writeln;

{ Bat dau tao b}

for i:=1 to n do

begin

b[i]:=0;

for j:=1 to i do b[i]:=a[i]+a[j];

end;

{ Ket thuc tao b}

ườ

ỹ

17

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

for i:=1 to n do write(b[i]:6);

readln

end.

ử ươ ạ ộ ố ộ ẫ ớ ­ Ch y th  ch ng trình v i m t s  b  test ng u nhiên ta có:

3

103  226  ­37

103  329  292

4

­106  ­47  ­212  48

­106  ­153  ­365  ­317

9

­136 ­122 ­207  ­63  95  152  60  55  ­156

­136  ­258  ­465  ­528  ­433  ­281  ­221  ­166  ­322

n M ng aả M ng bả

ừ ạ ả ử ụ ấ ặ * Quan sát t ồ    đo n{ Bat dau tao b} ta th y ph i s  d ng 2 vòng l p for l ng

nhau for i:=1 to n do

begin

b[i]:=0;

for j:=1 to i do b[i]:=a[i]+a[j];

end;

ử ụ ự ế ậ ả * N u s  d ng thu t toán trên thì máy tính ph i th c hi n ệ n(n+1)/2phép

c ng.ộ

* Trong bài toán này ta th y:ấ

b[1]=a[1]

b[i]=b[i­1]+a[i] , 1

ạ ươ ừ ế Do đó, ta thay đo n ch ng trình t chú thích { Bat dau tao b} đ n {Ket thuc

ệ ở tao b} b i hai l nh sau:

ườ

ỹ

18

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

b[1]:=a[1];

for i:= 2 to n do b[i]:=b[i­1]+a[i];

ự ệ ả ớ ỉ * V i hai l nh này, máy ch  ph i th c hi n ệ n­1 phép c ng.ộ

ươ ư ọ Ta có ch ng trình minh h a khi thay nh  sau:

program subsum2;

const nmax=100;

type myarray= array[1..nmax] of integer;

var a,b:myarray;

n,i,j:integer;

begin

randomize;

write ('nhap n');

readln(n);

{ Tao ngau nhien mang gom n so nguyen}

for i:=1 to n do a[i]:=random(300)­random(300);

for i:=1 to n do write(a[i]:5);

writeln;

b[1]:=a[1];

for i:= 2 to n do b[i]:=b[i­1]+a[i];

for i:=1 to n do write(b[i]:6);

readln

end.

ạ ạ ươ ộ ố ộ ẫ ớ * Ch y l i ch ng trình v i m t s  b  test ng u nhiên ta có:

ườ

ỹ

19

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

M ng aả M ng bả n

219  ­7  61

3

219  212  273

31  ­130  147  169

31  ­99   48  217

4

9

160  ­52  ­149  113  ­161  244  91  166  ­133 160  108  ­41  72  ­89  155  246  412  279

ố ượ ả ệ ươ B ng so sánh s  l ự ng phép toán th c hi n trong 2 ch ng trình trên:

n 3 4 9 subsum1 6 10 45 subsum2 2 3 8

ế ử ụ ể ả ả N u s  d ng cách 1 đ  gi ự   i bài toán này thì máy ph i th c ậ * Nh n xét:

2), trong khi

ứ ạ ủ ậ ộ ộ hi n ệ n(n+1)/2phép c ng => đ  ph c t p c a thu t toán ~ O(n

ự ả ứ ộ ộ ỉ ử ụ s  d ng cách 2 thì máy ch  ph i th c hi n ứ ạ   ệ n­1 phép c ng, t c đ  ph c t p

ư ậ ậ ờ ệ ủ c a thu t toán ~ O(n). Vì v y nh  vi c phân tích nh  trên ta có th  ti ể ế   t

ượ ộ ượ ể ươ ơ ệ ki m đ c m t l ng tính toán đáng k  giúp ch ạ ng trình ch y nhanh h n.

ề ọ ỏ ỉ ọ ị i t nh nam đ nh năm h c 2015 – 2016) 2.2.4.3. Ví dụ 3 (Đ  thi h c sinh gi

ệ ấ ự ệ ẻ ở ị ướ c công dân S  công an Nam Đ nh th c hi n công vi c c p th  căn c

ở ế ậ ỗ ườ ườ ứ năm 2016. M i ngày S  ti p nh n N ng i dân, ng i th  i m t t ờ ấ i th i gian

ẻ ấ ế ằ ườ (phút) hoàn thành c p th . Bi ở ấ t r ng S  c p cho ng i dân theo th  t ứ ự ầ    l n

ượ ệ ườ ớ ế ườ ế l t, xong vi c ng i này m i đ n ng i ti p theo.

ứ ự ế ầ ườ ờ ổ ờ Yêu c u: Em hãy x p th  t cho N ng i dân sao cho t ng th i gian ch  và

ẻ ủ ấ ườ ấ hoàn thành c p th  c a N ng i là ít nh t.

ữ ệ ệ D  li u: vào cho trong t p CANCUOC.INP

ườ

ỹ

20

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

4) cho bi

ố ự ườ ­ Dòng 1 là s  t nhiên N (N<=10 ế ố ượ t s  l ng ng i dân.

i (ti <=109) là s  phút hoàn thành c p th

ố ươ ấ ố ­ Dòng 2 là N s  nguyên d ng t ẻ

ườ ở ấ ỗ ố cho ng i dân i. M i s  cách nhau b i d u cách.

ệ ế ả ổ ờ ờ K t qu  ra ghi trong t p CANCUOC.OUT là t ng th i gian ch  và hoàn

ẻ ủ ấ ườ ấ thành c p th  c a N ng i là ít nh t.

ị * Xác đ nh bài toán:

+ Input:

4) cho bi

ố ự ườ ­ Dòng 1 là s  t nhiên N (N<=10 ế ố ượ t s  l ng ng i dân.

i (ti <=109) là s  phút hoàn thành c p ấ

ố ươ ố ­ Dòng 2 là N s  nguyên d ng t

ẻ ườ ở ấ ỗ ố th  cho ng i dân i. M i s  cách nhau b i d u cách.

+ Output:

ứ ự ườ ổ ờ ờ ế         X p th  t cho N ng i dân sao cho t ng th i gian ch  và hoàn thành

ườ ấ ẻ ủ ấ c p th  c a N ng i là ít nh t.

ưở * Ý t ng:

1..AN

ọ ồ ố ươ ­ G i dãy g m N s  nguyên d ng là dãy A

1..AN theo chi u tăng d n

ướ ế ế ề ầ ­ Tr ắ c h t ta đi s p x p dãy A

ễ ượ ­ Ta d  dàng tính đ c:

1 = A[1]

ẻ ủ ấ ờ ườ + Th i gian hoàn thành c p th  c a ng ứ i th  1 là t

2 = t1 + A[2]

ẻ ủ ấ ờ ườ + Th i gian hoàn thành c p th  c a ng ứ i th  2 là t

3 = t2 + A[3]

ẻ ủ ấ ờ ườ + Th i gian hoàn thành c p th  c a ng ứ i th  3 là t

…

n = tn­1 + A[n]

ẻ ủ ấ ờ ườ + Th i gian hoàn thành c p th  c a ng ứ i th  n là t

1 +t2 +..+tn

ẻ ủ ấ ổ ờ ờ ườ => T ng th i gian ch  và hoàn thành c p th  c a N ng i là t

ự ọ ậ * L a ch n thu t toán:

ườ

ỹ

21

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

4  => t p d  li u đ a vào ữ ệ

ề ườ ư ậ ­ Vì đ  bài cho bi ế ố ượ t s  l ng ng i dân N <=10

ử ụ ể ắ ế ậ ớ l n => Ta nên s  d ng thu t toán Qick­sort đ  s p x p (cách này đ t đ ạ ượ   c

ố ể đi m t i đa).

ấ ờ ổ ­ Sau đó ta đi tính t ng th i gian ít nh t.

ươ ọ * Ch ng trình minh h a:

const fi='CANCUOC.INP';

fo='CANCUOC.OUT';

var n:longint;

a:array[1..10001]of longint;

f1,f2:text;

procedure inp;

begin

assign(f1,fi);

assign(f2,fo);

reset(f1);

rewrite(f2);

end;

procedure out;

begin

close(f1); close(f2);

end;

procedure swap(var x,y:longint);

var tg:longint;

begin

tg:=x; x:=y; y:=tg;

ườ

ỹ

22

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

end;

procedure qs(l,h:longint);

var i,j,k:longint;

begin

if l>=h then exit;

i:=l; j:=h;

k:=a[random(h­l+1)+l];

repeat

while a[i]

while a[j]>k do dec(j);

if i<=j then

begin

if i

inc(i); dec(j);

end;

until i>j;

qs(l,j); qs(i,h);

end;

procedure optimiz;

var i:longint; s,t:qword;

begin

readln(f1,n);

for i:=1 to n do read(f1,a[i]);

qs(1,n);

t:=0; s:=0;

ườ

ỹ

23

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

for i:=1 to n do

begin

inc(t,a[i]);

inc(s,t);

end;

write(f2,s);

end;

begin

inp;

optimiz;

out;

end.

ệ ế ả ạ III. Hi u qu  do sáng ki n đem l i

ệ ả ế 1. Hi u qu  kinh t

ự ậ ọ ố ư ỗ ế ượ L a ch n thu t toán t i  u trong m i bài toán giúp ti ệ t ki m đ ộ   c m t

ượ ể ươ ạ ơ ế l ng tính toán đáng k , làm cho ch ng trình ch y nhanh h n, ti ệ   t ki m

ớ ộ b  nh , tài nguyên máy tính.

ả ề ặ ệ ộ  2. Hi u qu  v  m t xã h i

ố ớ ọ ọ ạ a. Đ i v i h c sinh h c đ i trà

ọ ậ ạ ả ồ Trong quá trình d y h c l p trình tin 11, tôi luôn l ng ghép, gi ng gi ả   i,

ể ọ ư ể ậ ọ ượ phân tích thu t toán cho h c sinh hi u đ  h c sinh đ a ra đ ậ c thu t toán

ố ư ấ ượ ầ ụ t i  u, góp ph n nâng cao ch t l ng giáo d c.

ự ả ạ ọ ớ ọ ọ     Năm h c 2015­ 2016 tôi đã l a ch n 4 l p h c sinh và gi ng d y theo 2

ướ h ng:

ụ ế ệ ộ

­ M t là: Không áp d ng sáng ki n kinh nghi m

ườ

ỹ

24

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

ụ ế ệ

­ Hai là: Có áp d ng sáng ki n kinh nghi m

ể ạ ượ Trong quá trình d y, thông qua các bài ki m tra tôi đánh giá đ c nh ư

sau:

ụ ụ ế ế Không   áp   d ng   sáng   ki n   kinh Có   áp   d ng   sáng   ki n   kinh

ọ ọ nghi mệ ố ớ + L p 11A4(sĩ s  40): 10 h c sinh nghi mệ ố ớ + L p 11A3(sĩ  s  40): 34 h c sinh

ấ ượ ấ ượ ề (~25%) đ  xu t đ ậ c thu t toán t ố   i ề (~85%) đ  xu t đ ậ c thu t toán t ố   i

ư ạ ọ ư ạ ọ u; còn l i 30 h c sinh (~75%) ch ỉ u; còn l ư   i 8 h c sinh (~15%) ch a

ề ậ ế ự ậ ọ ấ tìm cách đ  xu t thu t toán và vi ế   t bi t nên l a ch n thu t toán nào sao

ươ ươ ươ ự ệ ch ng trình sao cho ch ng trình cho ch ng  trình th c hi n càng  ít

ượ ượ ạ ch y đ ư c và đ a ra đ ế c k t qu ả phép toán càng t t.ố

ư ề ầ nh  đ  bài yêu c u.

ớ ọ ớ ọ ố + L p 11A5 (sĩ s  37): 8 h c sinh ố + L p 11A6 (sĩ s  39): 30 h c sinh

ấ ượ ề ề ấ ượ (~21,6%) đ  xu t đ ậ c thu t toán (~76,9%)   đ   xu t   đ ậ c   thu t   toán

ố ư ạ ọ ố ư ạ ọ t i  u; còn l i 29 h c sinh (~78,4%) t i  u; còn l i 9 h c sinh (~23,1%)

ề ấ ậ ỉ ế ự ậ ch  tìm cách đ  xu t thu t toán và ư ch a   bi ọ t   nên   l a   ch n   thu t   toán

ế ươ ươ ự vi t ch ng  trình sao  cho ch ươ   ng nào sao cho ch ệ   ng trình th c hi n

ạ ượ trình ch y đ ư c và đ a ra đ ượ ế   c k t càng ít phép toán càng t t.ố

ả ư ề ầ qu  nh  đ  bài yêu c u.

ướ ộ ắ ố ượ ứ => Đ ng tr c m t bài toán các em => Đa s  các em n m đ c vì sao

ế ự ả ự ậ ọ ư ch a bi ọ   t cách phân tích l a ch n ầ c n ph i l a ch n thu t toán t ố ư   i  u.

ậ ố ư ể ừ ứ ướ ộ thu t toán t ư i  u, ch a hi u đ ượ   c T  đó đ ng tr c m t bài toán các

ả ự ầ ậ ọ ế ự vì sao c n ph i l a ch n thu t toán em   bi ọ   t   cách   phân   tích   l a   ch n

ố ư ả ậ ố ấ t ậ i   u   khi   l p   trình   gi i   bài   toán thu t toán t t nh t sao cho ch ươ   ng

ự ệ trên máy tính. trình th c hi n càng ít phép toán càng

t t.ố

ườ

ỹ

25

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

ố ớ ồ ưỡ ọ ỏ b. Đ i v i công tác b i d ng h c sinh gi i

ừ ổ ọ ữ ầ ả ả Ngay t nh ng bu i h c đ u tiên tôi đã phân tích, gi ng gi i cho các em

ậ ố ư ự ầ ế ủ ệ ự ậ ọ ố ư thu t toán t i  u là gì, s  c n thi t c a vi c l a ch n thu t toán t i  u khi

ả ơ ả ư ậ ầ ậ l p trình gi ả   i bài toán trên máy tính; đ a ra các thu t toán c  b n c n ph i

ữ ế ế ể ắ ả ậ ắ n m v ng: s p x p m ng, tìm ki m.. đ  các em phân tích tìm ra thu t toán

ố ư ể ượ ệ ự ủ ậ ọ ố ư ề t i  u, hi u đ c vai trò c a vi c l a ch n thu t toán t ạ i  u, t o ti n đ ề

ư ả ể ạ ế ứ ạ ả ố ế ậ cho các em t duy gi i quy t các bài t p ph c t p đ  đ t k t qu  t ấ t nh t.

ề ấ ế ị IV. Đ  xu t, ki n ngh :

ữ ề ậ ố ư ả ư ậ Nh ng phân tích v  thu t toán t i  u và gi i pháp thu t toán tôi đ a ra

ữ ể ế ơ ả ủ ậ trên đây là nh ng hi u bi t và thu t toán c  b n c a cá nhân tôi. Trong quá

ậ ụ ả ế ự ệ ả ạ ấ ệ trình gi ng d y, th c hành tôi đã v n d ng và th y hi u qu , ti ờ   t ki m th i

ớ ơ ạ ộ ọ ế ậ ụ gian ch y, b  nh  h n giúp các em h c sinh bi t v n d ng và phân tích

ậ ướ ươ ỉ thu t toán kĩ càng tr ậ c khi l p ch ng trình trên máy. Tuy nhiên nó ch  là

ủ ế ấ ề ế ẫ ặ sáng ki n c a cá nhân tôi, t t nhiên v n còn nhi u thi u sót, ho c có th ể

ư ẳ ữ ệ ặ ậ ố ớ ồ đ i v i đ ng nghi p nó ch a h n là nh ng  phân tích hay ho c thu t toán

ẳ ố ư ậ ậ ượ ề ư ủ c a tôi ch a h n đã t ấ i  u vì v y tôi r t mong nh n đ ế   c nhi u ý ki n

ể ậ ậ ả ầ ơ ớ   đóng góp đ  thu t toán và l p trình ngày càng đ n gi n và g n gũi v i

chúng ta.

ạ ả ề ế ặ V. Cam k t không sao chép ho c vi ph m b n quy n

ủ ế ệ Tôi xin cam đoan đây là sáng ki n kinh nghi m c a cá nhân tôi, trong quá

ự ế ề ả ạ ả trình gi ng d y b n thân đúc k t thành, không h  có s  sao chép hay vi

ả ạ ề ủ ấ ứ ph m b n quy n c a b t c  công trình nào.

Ơ Ả Ế Ơ Ị    C  QUAN Đ N V TÁC GI  SÁNG KI N

ườ

ỹ

26

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

Ụ Ế ÁP D NG SÁNG KI N

.................................................................

.................................................................

.................................................................

.................................................................

ễ ị .................................................................                               Nguy n Th  Ph ươ   ng

Ngân

Ụ Ụ PH  L C

ụ ệ ả Danh m c các tài li u tham kh o:

ườ

ỹ

27

Tr

ng THPT M  Tho

ị ươ

ễ

ổ

Giáo viên: Nguy n Th  Ph

ng Ngân

T : Lý – Tin ­ KTCN

ụ ọ 1. SGK tin h c 10_NXB Giáo d c;

ụ ọ 2. SGK tin h c 11_NXB Giáo d c;

ờ ạ ễ ễ ứ 3. Toán r i r c_ Nguy n Đ c Nghĩa – Nguy n Tô Thành;

ữ ệ ấ ả ậ

4. C u trúc d  li u và gi

ỗ i thu t_Đ  Xuân Lôi;

ệ

5. Tài li u giáo khoa chuyên Tin_Lê Minh Hoàng.

ườ

ỹ

28

Tr

ng THPT M  Tho