Sáng kiến kinh nghiệm THPT: Mở rộng bài toán cơ sở trong Tin học

Ở

S GIÁO D C VÀ ĐÀO T O THANH HÓA

Ạ Ỉ Ơ

Ụ ƯỜ TR

NG THPT B M S N

Ế

Ệ

SÁNG KI N KINH NGHI M

Ở Ộ

Ộ Ố

Ơ Ở

M R NG M T S BÀI TOÁN C S TRONG TIN H CỌ

ệ ạ ặ i th c hi n: Đ ng Văn M nh

ườ ự ứ ụ

ơ ị ỉ ơ ng THPT B m S n

ườ ự ộ Ng Ch c v : Giáo viên Đ n v công tác: Tr ọ SKKN thu c lĩnh v c: Tin h c

Ặ Ấ Ề I. Đ T V N Đ

ệ ắ ế ả ộ t, k t lu n và cách gi i m t bài toán c s r t

Vi c n m v ng gi ọ ậ ở ộ ạ

ự ả

ạ i các bài toán cùng d ng ho c m r ng. ứ ủ ọ ả ậ c cách gi ả ừ ế ữ ế thi ừ ạ ệ quan tr ng trong vi c nh n d ng, m r ng ph m vi bài toán t ặ ị xác đ nh, xây d ng đ Cũng t ơ ở ấ ọ đó h c sinh ở ộ nghiên c u c a h c sinh. ượ đó khuy n khích kh năng t ự ọ ự h c, t

ệ ọ ị

Trong tin h c vi c xác đ nh chính xác bài toán( Input, Output) và thu t ả ọ ơ ở i m t bài toán c s nào đó cũng giúp h c sinh trong vi c nh n d ng,

ượ ự ặ ượ ộ ộ ố ị ậ ậ ệ ạ ậ c thu t toán c ho c xây d ng đ

toán gi ở ộ m r ng m t s bài toán và xác đ nh đ ả gi i các bài toán đó.

ọ ươ ọ ớ Th c t

ầ ế ậ

ở ộ ủ ạ ớ

ợ ớ ể ấ

ố ữ ụ ằ

ứ ử ố ự ọ ế c ki n th c trong Sách Giáo Khoa và x lý t

ượ ố ọ ớ ậ ọ ự ế ng trình tin h c l p 11 , đa ph n các em h c sinh khi h c ch ậ ự ỡ ề ấ ỡ đ u r t b ng và y u khi xây d ng thu t toán cho các bài toán. chính vì v y, ở ộ ệ các bài toán m r ng ph m vi c a m t SKKN này tôi xin trích gi i thi u ố s bài toán tiêu bi u trong sách giáo khoa, r t phù h p v i đa s các em ắ có l c h c trung bình và khá nh m m c đích giúp các em n m v ng đ t các bài toán trong cu n “Bài t p Tin h c l p 11”.

Ộ II. N I DUNG.

ự ể ậ ố ủ ố c a s nguyên d ươ ng

Bài toán 1. Xây d ng thu t toán ki m tra tính nguyên t N.

ị Xác đ nh bài toán.

ươ ố +/ Input: S nguyên d ng N

ặ ố ố ố ố +/ Output: Thông báo “ N là s nguyên t ” ho c “N không là s nguyên t ”

ậ Thu t toán:

ậ ố ươ B1. Nh p s nguyên d ng N

ạ

ố ố B2. N u t n t là s nguyên t " ng ế ồ ạ ướ ủ c c a N trong ph m vi [2, N div 2] thì thông báo”N không i ượ ạ ố c l ố i thông báo “ N là s nguyên t ”

ế B3. K t thúc.

ể ở ộ ơ ở ừ T bài toán c s này chúng ta có th m r ng ra các bài toán sau:

Bài toán 1.1

ố ươ ươ ng M và dãy s nguyên d ng a1, a2, …, aM. Tính và đ a

ố ế ố ố ố có trong dãy. N u không có s nguyên t ư ố

ư ố Cho s nguyên d ổ ra màn hình t ng các s nguyên t nào thì đ a ra màn hình s 0.

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

ươ ố ươ ố +/ Input: S nguyên d ng M và dãy s nguyên d ng a1, a2, …, aM.

ổ ố ố ặ ố +/ Output: T ng các s nguyên t có trong dãy ho c s 0.

ể ượ ở ộ

ỗ

ự ố

ặ ố ố ơ ở c xem là m r ng c a bài toán c s nêu trên ơ ng N trong bài toán c ệ c th c hi n m t cách thì

ổ ủ Rõ ràng bài toán này có th đ M) nh s nguyên d ươ ư ố ế n u chúng ta xem m i ai ( i:1 ượ ề ộ ố ổ ấ ở s . V n đ tính t ng các s nguyên t có trong dãy đ ộ ế ổ ả ấ ơ r t đ n gi n là khai báo thêm bi n t ng và khi g p m t ai là s nguyên t ộ c ng ai vào cho t ng.

ậ Thu t toán:

ậ ố ươ ố ươ B1. Nh p s nguyên d ng M và dãy các s nguyên d ng a1, a2, …, aM.

t ng ổ  0;

ệ ừ ế ế ố ố B2. Duy t t a1 đ n aM n u ai (i=1;M) là s nguyên t thì t ng ổ  t ng +ai ổ

ồ ế ư ổ B3. Đ a t ng ra màn hình r i k t thúc.

Bài toán 1.2

ố ố ươ

ố ế ố ế ư ng a1, a2, …, aM. Đ m và đ a có trong dãy. N u không có s nguyên

ng M và dãy s nguyên d ố ng các s nguyên t ố ư Cho s nguyên d ra màn hình s l ố t ươ ố ượ nào thì đ a ra màn hình s 0.

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

ươ ố ươ ố +/ Input: S nguyên d ng M và dãy s nguyên d ng a1, a2, …, aM.

ố ượ ố ặ ố +/ Output: S l ố ng các s nguyên t có trong dãy ho c s 0.

ể ượ ơ ở ở ộ

ủ c xem là m r ng c a bài toán c s nêu ươ ng N trong bài toán ự ỗ ố ượ ề ế c th c hi n

ượ ộ ế ặ

ả ế ố ơ Rõ ràng bài toán này cũng có th đ M) nh s nguyên d ư ố ế trên n u chúng ta xem m i ai ( i:1 ơ ở ấ ệ ố ố có trong dãy đ c s . V n đ đ m s l ng các s nguyên t ấ ơ ố ế ộ m t cách r t đ n gi n là khai báo thêm bi n đ m và khi g p m t ai là s ị thì tăng đ m thêm 1 đ n v . nguyên t

ậ Thu t toán:

ậ ố ươ ố ươ B1. Nh p s nguyên d ng M và dãy các s nguyên d ng a1, a2, …, aM.

đ m ế  0;

ệ ừ ế ế ố ố ế B2. Duy t t a1 đ n aM n u ai (i=1;M) là s nguyên t thì đ m ế  đ m +1

ư ế ồ ế B3. Đ a đ m ra màn hình r i k t thúc.

Bài toán 1.3

ố ươ ư ng a1, a2, …, aM. Đ a ra màn

ứ ự ế ậ ố ng M và dãy s nguyên d ố có trong dãy theo th t

ố ươ Cho s nguyên d ố ố đã nh p. N u không có s hình các s nguyên t ố ố nào thông báo ra màn hình “Trong dãy không có s nguyên t ”. nguyên t

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

ươ ố ươ ố +/ Input: S nguyên d ng M và dãy s nguyên d ng a1, a2, …, aM.

ố ố ứ ự ậ +/ Output: các s nguyên t có trong dãy theo th t ặ đã nh p ho c thông báo.

ấ ả ể ượ

ị ơ ở

ậ ế ấ ng ai (v i i nh n giá tr t

ề ư ố

ậ ặ ố

ả ơ

ế ố ố ượ nào” đ ầ  0 v i gi ớ ệ ừ a1 đ n aM n u ai

ư ố ố ồ ơ ị

ế ạ

ở ộ ừ ế T k t qu xác đ nh bài toán ta th y bài toán này có th đ c xem là m r ng ể ủ ề ủ ố c a bài toán c s nêu trên vì v n đ ch ch t trong bài này cũng là ki m tra ố ả ị ừ ớ ươ ỗ ố 1 đ n M) có ph i lá s nguyên m i s nguyên d ố ứ ố ấ có trong dãy theo th hay không? V n đ đ a ra màn hình các s nguyên t t ự ố ự c th c đã nh p ho c thông báo “trong dãy không có s nguyên t t ế ả ử ử ụ ư ệ s hi n đ n gi n nh sau. Ta s d ng bi n kt:byte. Ban đ u kt ế ằ nào sau đó ta du t t r ng trong dãy không có s nguyên t ờ ố thì đ a ai ra màn hình đ ng th i tăng kt lên 1 đ n v . Cu i là s nguyên t ể ố cùng ta ki m tra l i kt = 0? N u đúng thì thông báo “ trong dãy không có s ố nào” nguyên t

ậ Thu t toán:

ậ ố ươ ố ươ B1. Nh p s nguyên d ng M và dãy các s nguyên d ng a1, a2, …, aM.

kt  0;

ệ ừ ế ế ố ố B2. Duy t t a1 đ n aM n u ai (i=1;M) là s nguyên t thì:

ư 2.1 Đ a ai ra màn hình;

ơ ị 2.2 Tăng kt lên 1 đ n v :inc(kt)

ế ố ố B3. N u kt=0 thì thông báo “trong dãy không có s nguyên t nào”

ế B3. K t thúc.

ư ể ề ỉ Chúng ta có th xét thêm bài toán sau( đ thi hsg t nh H ng Yên).

ậ ả L p trình gi i bài toán sau:

ầ ử ả ố ồ ấ ả ầ ử , hãy tìm t t c các ph n t ố là s

ủ ố ổ ộ Cho m t m ng s nguyên g m 30 ph n t nguyên t và tính t ng c a chúng.

ậ ừ ể ặ ẳ

ư ạ

ạ ộ ủ bàn phím to đ c a 2 đi m M, N trong m t ph ng. Tính Bài toán 2. Nh p t ế ộ và đ a ra màn hình đ dài đo n MN. N u chúng trùng nhau thì thông báo “M ớ trùng v i N”.

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

ố ố +/ Input: B n s x1,y1,x2,y2

ạ ặ ộ ớ +/ Output: Đ dài đo n MN ho c thông báo “M trùng v i N”

: ậ Thu t toán

ậ ố B1. Nh p 4 s x1, y1, x2, y2; d 0;

x 2(

x )1

y 2(

y )1

(cid:0) (cid:0) (cid:0) B2. d 

ế ớ ượ ạ ư ồ i đ a d ra màn hình r i c l

B3. N u d=0 thì thông báo “M trùng v i N”, ng ế k t thúc.

ạ ộ ủ ỉ

ủ ủ ậ ẳ ệ ặ ộ

ậ ừ ự bàn phím to đ c a các đ nh c a Bài toán 2.1 Xây d ng thu t toán nh p t ư m t tam giác trong m t ph ng. Tính và đ a ra màn hình chu vi, di n tích c a tam giác đó.

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

ố +/ Input: Các s x1, y1, x2, y2, x3, y3.

ệ +/ Output: Chu vi, di n tích tam giác

ệ bài

ấ ơ ở ủ ộ ạ ộ ứ ế ể ạ ừ ấ Ta th y vi c tính chu vi c a tam giác trong bài toán này xu t phát t t to đ các đi m. toán c s đã nêu t c là tính đ dài các c nh khi bi

: ậ Thu t toán

ậ ố B1. Nh p 6 s x1, y1, x2, y2, x3, y3;

(cid:0) (cid:0) (cid:0) B2. a 

x 2(

x )1

y 2(

y )1

(cid:0) (cid:0) (cid:0) b 

x 3(

x )1

y 3(

y )1

(cid:0) (cid:0) (cid:0) c 

x

y

x 3(

)2

y 3(

)2

(cid:0) (cid:0) (cid:0) p a+b+c; s

p

c

(2/

2/

pa )(

2/

pb )(

2/

)

ồ ế ư b3. Đ a p, s ra màn hình r i k t thúc.

ạ ộ ủ ậ ừ ủ ậ ỉ bàn phím to đ c a các đ nh c a

ư ủ ộ ỉ ự Bài toán 2.2 Xây d ng thu t toán nh p t m t đa giác N đ nh. Tính và đ a ra màn hình chu vi c a đa giác đó.

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

ặ ố ị ừ ậ ớ +/ Input: Các c p s (xi, yi), v i i nh n giá tr t ế 1 đ n N.

ủ +/ Output: Chu vi c a đa giác.

ả ượ ộ

ở c m ộ ự ấ ự ể ấ ừ ễ bài toán c s 2 nêu trên vì th c ch t đây cũng là bài toán tính đ dài ọ t to đ các đi m. T đó h c sinh d dàng xây d ng

ẳ ể ả ậ ừ ế ị T k t qu xác đ nh bài toán ta th y đây cũng là m t bài toán đ ừ ơ ở ộ r ng t ế ạ các đo n th ng khi bi thu t toán đ gi ạ ộ i bài toán này.

ậ Thu t toán:

ạ ộ ủ ậ ỉ B1. Nh p to đ c a N đ nh;

ạ ộ B2. Tính đ dài các các c nh, tính chu vi;

ồ ế ư B3. Đ a chu vi ra màn hình, r i k t thúc.

ể ở ộ ủ ỉ Ta có th m r ng bài toán tính chu vi c a đa giác N đ nh trong không

gian.

ự ế ậ ằ ố

ư ộ ố Bài toán 3. Xây d ng thu t toán tìm max trong 2 s a, b. N u chúng b ng nhau thì đ a ra màn hình m t trong hai s đó.

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

ố +/ Input: Hai s a, b.

ủ ố +/ Output: Max c a hai s a, b.

ậ Thu t toán:

ậ B1. Nh p a, b

B2. Max  a;

ế B3. N u Max < b thì Max b

ồ ế ư B4. Đ a Max ra màn hình r i k t thúc.

ừ ệ ể ở ộ ủ ủ ố

ố T vi c tìm max c a 2 s ta có th m r ng bài toán tìm max c a N s trong bài toán sau:

ủ ự ậ ố Bài toán 3.1 Xây d ng thu t toán tìm max c a N s nguyên a1, a2, …, aN.

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

ươ ố ố +/ Input: S nguyên d ng N và dãy s nguyên a1, a2, …, aN

ố ủ +/ Output: Max c a dãy s đã cho.

ậ ơ ở ủ ư ầ

ạ ớ ẽ i tìm max c a max v i a3, quá trình s

c 1 s đó là max. Sau đó ta l ế ế ố ễ ủ ớ ủ ằ B ng quy lu t nh trong bài toán c s , ban đ u ta tìm max c a a1, a2 ta ẽ ượ s đ ượ đ c ti p di n cho đ n khi tìm max c a max v i aN.

ậ Thu t toán:

ậ ố ươ ố B1. Nh p s nguyên d ng N và dãy s nguyên a1, a2, …, aN

B2. Max a1; i 2;

ế B3. N u i>N thì sang B5

ế ạ B4. N u ai>max thì max  ai, ii+1, quay l i B3.

ồ ế ư B5. Đ a Max ra màn hình r i k t thúc.

ơ ở ự ễ ọ ượ ậ c thu t

ớ ủ Ngoài ra, v i bài toán c s này h c sinh d dàng xây d ng đ ố ủ ố toán tìm min c a 2 s , Tìm min c a N s .

ệ ủ ố ầ ự ậ ấ ự “ch” trong xâu

Bài toán 4. Xây d ng thu t toán tìm s l n xu t hi n c a kí t s

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

ự +/ Input: Kí t “ch” và xâu s

ệ ủ ố ầ ấ ự +/ Output: S l n xu t hi n c a kí t “ch” trong xâu s.

: ậ Thu t toán

ậ ự B1. Nh p xâu s và kí t ch; dem 0;

ệ ừ ầ ế ế ế ế ố ơ ị đ u đ n cu i xâu s, n u s[i]=ch thì tăng bi n đ m lên 1 đ n v

B2. Duy t t dem dem+1

ồ ế ư B3. Đ a dem ra màn hình r i k t thúc.

Ta xét bài toán sau:

ệ ủ ầ ố ự ậ ấ ỗ ự trong

Bài toán 4.1. Xây d ng thu t toán tính t n s xu t hi n c a m i kí t xâu s.

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

+/ Input: Xâu s

ệ ủ ố ầ ỗ ự ấ +/ Output: S l n xu t hi n c a m i kí t trong xâu s.

ộ ấ

ở ộ ố ầ ể ệ ủ ơ

ấ ố ầ đây là có th có nhi u h n m t kí t ậ

ơ ở ề ệ ắ ự ở ộ c m r ng ệ ủ ẽ

ằ ượ ố ầ

ơ ở ậ c thu t toán ệ ấ c tìm s l n xu t hi n ượ ố ầ c s l n

ệ ủ ệ ủ ự ấ

ự ế ể ự ư ượ ch a đ “ch” trong bài toán c s . Khi tìm đ ố ầ ư ở đây là làm th nào đ b qua các kí t

ấ

i bài toán 4.1 b ng cách xem m i kí t ư ự ự ồ r i thì đ a kí t ề ả ệ ấ ượ ầ ố ố ầ ơ ấ ả

c tìm s l n xu t hi n trong xâu s. V n đ này có nhi u cách gi ế ố ầ ự ế ệ ế ấ đó cùng s l n xu t hi n c a nó ra ể ỏ đã ề ế ả i quy t ệ ấ c t n s xu t hi n. cũng k t

ự ấ Rõ ràng ta th y đây cũng là bài toán tìm s l n xu t hi n c a m t kí t ự ầ ề ượ trong xâu. V n đ đ c n ả ữ ấ ph i tìm s l n xu t hi n c a chúng trong xâu s. Vi c n m v ng thu t toán ọ ả i bài toán c s nêu trên s giúp h c sinh có th xây d ng đ gi ỗ ể ả đ gi ủ c a chúng trong xâu s nh kí t ỗ xu t hi n c a m i kí t ộ ấ màn hình. M t v n đ n y sinh ề ượ đ ự ư đã tìm đ nh ng cách đ n gi n nh t là xoá h t các kí t ệ ủ ấ Khi xoá h t xâu thì công vi c tìm s l n xu t hi n c a các kí t thúc.

ậ Thu t toán:

ậ B1. Nh p xâu s;

ự ệ ư ế B2. Trong khi ch a h t xâu th c hi n:

ệ ủ ố ầ ự ấ Tìm s l n xu t hi n c a kí t s[1] trong xâu;

ư ự ệ ủ ố ầ ấ Đ a kí t s[1] cùng s l n xu t hi n c a nó ra màn hình

ự Xoá các kí t s[1] trong xâu

ế B3. K t thúc.

ậ ự ấ ệ ấ xu t hi n ít nh t trong xâu ự Bài toán 4.2 . Xây d ng thu t toán tìm kí t

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

+/ Input: Xâu s

ự ấ ệ +/ Output: Kí t ấ xu t hi n ít nh t trong xâu s .

ấ ề ơ ở bài toán c s 4 vì v n đ chính

ượ ấ c phát tri n t ệ ủ

ấ ế ự ố ầ trong xâu. Tuy nhiên nó đ ệ ủ ỗ

ấ ả ệ ở ượ ự ạ l ơ ố ầ ứ ộ ự ẽ ơ ấ

ở ộ ẽ ử ụ

đây cũng là c nâng cao ể ả i ph i ki m đó có ph i xu t hi n ít nh t không? S đ n gi n h n n u ta xem ậ ậ ấ ế ộ ầ ự ệ

ố ầ

ế

ệ ủ ấ ự ế ạ

ẽ ả ạ i so sánh v i min. N u min l m h n s l n xu t hi n c a kí t c bài ấ ơ ố ầ i min và minchar, cu i cùng ta s gi i quy t đ

ể ừ Bài toán này đ ộ đi tìm s l n xu t hi n c a m t kí t ơ h n m t m c đó là sau khi đ m s l n xu t hi n c a m i kí t ả tra xem kí t ế ủ đây là bài toán m r ng c a bài toán 4.1. Th t v y, ta s s d ng m t bi n ự ấ ả ể ể ư xu t hi n ít nh t trong xâu và ban đ u gi ki u kí t (minchar) đ l u kí t ệ ủ ấ ự ấ ế ằ ít nh t trong xâu là(min=length(s)), thi t r ng s l n xu t hi n c a kí t ượ ố ầ ỗ ầ ự ộ c s l n xu t hi n c a m t kí t minchar=s[1] . Sau đó m i l n đ m đ ệ ủ ớ ớ trong xâu ta l ế ượ ố ừ ế v a đ m thì ta gán l toán

ậ Thu t toán:

ậ B1. Nh p xâu s; minchar=s[1]; min=length(s)

ự ệ ư ế B2. Trong khi ch a h t xâu th c hi n:

ệ ủ ố ầ ự ấ Tìm s l n xu t hi n c a kí t s[1] trong xâu;

ượ ự ế ệ ớ ớ ơ ố ầ So sánh s l n tìm đ c đó v i min. N u min l n h n thì th c hi n:

ệ ủ ị ớ ố ầ ậ ấ ự ừ ế ượ Min nh n giá tr m i là s l n xu t hi n c a kí t v a đ m đ c;

Minchar:=s[1]

ự Xoá các kí t s[1] trong xâu

ư ế B3. Đ a minchar và min ra màn hình và k t thúc.

ậ ự ấ ệ ấ ề xu t hi n nhi u nh t trong xâu ự Bài toán 4.3 . Xây d ng thu t toán tìm kí t

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

+/ Input: Xâu s

ự ấ ệ ề ấ +/ Output: Kí t xu t hi n nhi u nh t trong xâu s .

ươ ươ ủ ậ ả ng đ ng c a bài toán 4.2. Thu t toán gi i bài toán

ấ Ta th y đây là bài toán t ư này nh sau:

ậ Thu t toán

ậ B1. Nh p xâu s; maxchar=s[1]; max=0;

ự ệ ư ế B2. Trong khi ch a h t xâu th c hi n:

ệ ủ ố ầ ự ấ Tìm s l n xu t hi n c a kí t s[1] trong xâu;

ượ ự ế ệ ớ ơ ớ ố ầ So sánh s l n tìm đ c đó v i max. N u max l n h n thì th c hi n:

ệ ủ ị ớ ố ầ ậ ấ ự ừ ế ượ Max nh n giá tr m i là s l n xu t hi n c a kí t v a đ m đ c;

Maxchar:=s[1]

ự Xoá các kí t s[1] trong xâu

ư ế B3. Đ a maxchar và max ra màn hình và k t thúc.

ả ủ ự ậ ạ ộ ướ c. Bài toán 5. Xây d ng thu t toán t o xâu đ o c a m t xâu cho tr

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

+/ Input: Xâu s;

ả ủ +/ Output: Xâu đ o c a xâu s.

ậ Thu t toán:

ở ạ ậ B1. Nh p xâu s, kh i t o xâu x ’’; i length(s)

ế B2. N u i < 1 thì sang B4

ạ B3. x  x+s[i]; i i1, quay l i B2;

ồ ế ư B4. Đ a x ra màn hình r i k t thúc.

ự ả

ộ ả ủ ướ ằ ố ứ ể ậ Bài toán 5.1. Xây d ng thu t toán ki m tra xem m t xâu cho tr c có ph i là ố ứ xâu đ i x ng không? Xâu đ i x ng là xâu mà xâu đ o c a nó b ng chính nó.

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

+/ Input: Xâu s;

ố ứ ế ậ ả ặ ả

+/ Output: K t lu n “xâu s có ph i xâu đ i x ng” ho c “xâu s không ph i xâu ố ứ đ i x ng”.

ệ ố ứ ậ ở c m

ễ ỉ ầ ạ ấ ả ủ ượ ớ ồ

ừ bài toán 5 và chúng ta ch c n t o xâu đ o c a s r i so sánh v i chính ẽ ế ừ T khái ni m xâu đ i x ng, ta d dàng nh n th y bài toán này đ ộ r ng t ả nó là s cho k t qu .

: ậ Thu t toán

ậ B1. Nh p xâu s

ả ủ ạ B2.T o xâu đ o c a s

ế ằ

ả ủ ế ế ớ ố ứ ố ứ ả ả B3. So sánh s v i xâu đ o c a s. N u chúng b ng nhau thì thông báo “xâu s có ằ ph i xâu đ i x ng”, n u chúng không b ng nhau thì thông báo “xâu s không ph i xâu đ i x ng”. K t thúc.

ự ộ ướ ả c có ph i là

ậ ướ ả ủ ộ Bài toán 5.2. Xây d ng thu t toán ki m tra xem m t xâu cho tr xâu đ o c a m t xâu cho tr ể c khác không?

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

+/ Input: Xâu s, x;

ả ủ ế ặ

ậ ả ủ ả +/ Output: K t lu n “xâu s, x là hai xâu đ o c a nhau” ho c “xâu s, x không ph i là hai xâu đ o c a nhau”.

ễ ế ệ ả ự ệ i quy t nó d dàng đ c th c hi n khi

ậ Đây cũng là bài toán mà vi c gi ả ủ ạ ượ t o đ ượ c xâu đ o c a hai xâu đã cho. Sau đây là thu t toán.

: ậ Thu t toán

ậ B1. Nh p xâu s, x

ả ủ ả ủ ạ B2.T o xâu đ o c a s, xâu đ o c a x

ớ ả ủ ộ ặ ế ớ

ả ủ ả ủ i thì

ả ủ ế ả ấ B3. So sánh s v i xâu đ o c a x, x v i xâu đ o c a s. N u có ít nh t m t c p ượ ạ ằ b ng nhau thì thông báo “xâu s, x là hai xâu đ o c a nhau” ,ng c l thông báo “xâu s, x không ph i là hai xâu đ o c a nhau”. K t thúc.

Bài toán 5.3 (Bài 4.42 sbt tin 11).

ố ộ ướ i ta xâu N viên đá quý kích th

ố ộ ầ ế ể

ườ ị

ộ

ả

ở ầ ố ừ trái sang luôn có màu ầ ứ i t

ủ ồ

ặ ườ ổ Ng c gi ng nhau th nh m t vòng đeo c , ố ừ ỗ ộ m i viên có m t màu trong s các màu đánh s t 1 đ n 9. Đ tăng tính đ c ị ắ ứ đáo cho vòng trang s c quý này, ng i ta đ nh l p khoá đeo vào v trí sao cho ệ ộ ụ ấ ượ c m t dây đá quý có tính ch t: không ph thu c vào vi c khi m vòng ta đ ỗ ộ ề ượ ầ c m t chu i c m đ u dây nào bên tay ph i và đ u kia bên tay trái, ta đ u đ ộ ụ ứ ạ j không ph thu c h t gi ng nhau, t c là viên đá th ố ị ị ầ vào cách c m. Cho sâu s g m các màu c a các viên đá quý, hãy xác đ nh s v trí đ t khoá.

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

+/ Input: Xâu s

ặ ố ị +/ Output: S v trí đ t khoá

ẳ ạ ữ ị ẽ ặ

ị ứ ứ ứ ặ ị ị ứ Ch ng h n: Cho s=’222222335533’, ta s có 2 v trí đ t khoá là gi a v trí th ữ ị 3 và v trí th 4 ho c gi a v trí th 9 và v trí th 10.

ậ Thu t toán:

ấ ừ ặ ặ

ẽ ắ ố ứ

ấ ủ ấ ố ứ ạ ẳ ộ ỗ tính ch t c a cách đ t khoá, m i cách đ t khoá s cho ta m t Ta th y t ẽ ố ộ xâu đá quý có tính ch t đ i x ng khi đó ta s c m t xâu màu s c đ i x ng ươ ứ t ng ng. Ch ng h n:

ố ứ ữ ị ứ ặ c xâu đ i x ng

ứ ữ ị ố ứ Ở ị ặ ượ v trí đ t khoá gi a v trí th 3 và th 4 ta đ ứ v trí đ t khoá gi a v trí th 9 và 10 ta có xâu đ i x ng

Ở ị 222335533222; 533222222335.

ấ

ặ ự ằ

ệ ộ ủ ớ

ế

ặ ơ

ả ậ ố ị ệ ế ố ứ ề ả ậ V y xét v b n ch t đây cũng là bài toán xâu đ i x ng. Vi c đ m s v ạ ừ ầ ố ế ượ c th c hi n b ng cách sau: Cho i ch y t trí đ t khoá đ đ u xâu đ n cu i ỗ ể ớ xâu s( i:1>L, v i L là đ dài c a xâu s). V i m i i ta ki m tra xem xâu ố ứ ả s1=copy(s,i,Li+1)+copy(s,1,i1) có ph i là xâu đ i x ng không? N u đúng thì ượ ố ị ẽ ố ị ế tăng đ m lên 1 đ n v . Cu i cùng ta s tìm đ c s v trí đ t khoá. Sau đây là i bài toán này. thu t toán gi

ậ ộ B1. Nh p xâu s, dem 0; i1; L đ dài xâu s;

ư ế B2. N u i> L thì đ a dem ra màn hình, sang B4

ằ ỗ B3. s1’’ ( s1 gán b ng xâu r ng);

s1copy(s,i,Li+1)+copy(s,1,i1).

ố ứ ế ạ N u s1 là xâu đ i x ng thì dem dem+1; ii+1, quay l i B2.

ế B4. K t thúc.

ự ậ Bài toán 6. Xây d ng thu t toán tính N!.

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

ươ ố +/ Input: S nguyên d ng N

+/ Output: N!.

ậ Thu t toán:

ậ ố ươ B1. Nh p s nguyên d ng N; gt 1; i2;

ế ướ B2. N u i> N thì sang b c 4

B3. gtgt*i, ii+1, quay l i B2ạ

ồ ế ư B4. Đ a gt ra màn hình r i k t thúc.

ể ở ộ ơ ở ừ T bài toán c s trên ta có th m r ng các bài toán sau:

ẵ ố

ậ ọ ớ ậ ư ố ng trình đ a ra màn hình s hoán v

ố nhiên N. L p ch (N<10).

nhiên N

ị ủ ố ề Bài toán 6.1 (Đ thi hsg tin h c l p 12 thành ph Đà N ng năm 20012002) ị ươ ộ ố ự Nh p vào m t s t ủ c a N s 1,2,3,...,N. ị Xác đ nh bài toán: ố ự +/ Input: S t ố +/ Output: S hoán v c a N s

ậ

ị ủ ầ ử

ứ ầ ử ơ ở ố ừ ị 1, 2, 3, ..., N, ta có s hoán v ậ đó là N!. V y đây chính là bài toán c s đã cho. T đó thu t

ể ả Thu t toán: ố Theo công th c tính s hoán v c a N ph n t ủ c a N ph n t toán đ gi ậ i bài toán này là:

ậ ố ươ B1. Nh p s nguyên d ng N; shv 1; i2;

ế ướ B2. N u i> N thì sang b c 4

B3. shvshv*i, ii+1, quay l i B2ạ

ồ ế ư B4. Đ a shv ra màn hình r i k t thúc.

ề ọ ố ỉ Bài toán 6.2.(Đ thi tin h c kh i THPT t nh An Giang)

ộ ỗ ộ ượ ọ ự ự ủ ế ỗ M t chu i con s1 có đ dài k đ c g i là chu i con th c s c a s n u:

ự ượ ậ ự ủ ừ ỗ ỏ ấ c l p nên t đ t

các kí t ỗ ự ộ ồ Nó g m k kí t ự ố ả c các kí t ằ c a chu i s b ng cách rút b t gi ng nhau trong chu i và không thêm m t kí t nào khác.

ự ậ ự Trong s1 các kí t là tuân theo tr t t đã có trong s.

ự ự ủ ố ớ ế ượ ậ ừ ế ng trình tìm s dãy con th c s c a s v i k=2, bi t s đ c nh p t

ươ Vi t ch bàn phím.

ụ Ví d s=’HOI THI TIN HOC TRE TINH AN GIANG’

ế ự ố ự Sau khi rút h t các kí t gi ng nhau và không thêm kí t nào ta có s=’CRE’.

ự ự ớ ừ ố T đó ta có s dãy con th c s v i k=2 là 3(CR,CE, RE)

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

ố +/ Input: Xâu s và s k( k=2)

ự ự ủ ố +/ Output: S dãy con th c s c a s.

ậ Thu t toán:

ọ ố ạ ự ố i trong xâu s sau khi đã rút các kí t gi ng nhau và

ạ ẳ ụ nào. Ch ng h n trong ví d trên ta có L=3. Trong s1 k kí

ả ừ c a nó t

ổ ợ

i( RC, EC, ER). Nh v y đây chính là bài toán tính t ầ ử ẽ ượ ễ ộ trái qua ph i (CR, CE, RE) mà không l y ư ậ . Bài toán này s đ

ượ ạ

c các giá tr sau: L!; k!; (Lk)!. Tóm l ừ ề ậ ở ậ ả ấ h p c tính m t cách d dàng sau khi i đây là bài toán tính ư i bài toán này nh ị trên. T đó ta có thu t toán gi

ự Ta g i L là s kí t còn l ự ộ không thêm m t kí t ự ượ ấ ứ ự ủ đ t c l y theo th t ứ ự ượ ạ ng th t c l ủ ậ ch p k c a L ph n t chúng ta tính đ ừ giai th a mà ta đã đ c p sau:

ậ ố B1. Nh p xâu s và s k

ử ự ố B2. X lí xâu s( xoá các kí t gi ng nhau)

B3. Tính L!, k!, (Lk)!

L ! kLk (!

B4. Tính (cid:0)

ư ế ồ ế ả B5. Đ a k t qu ra màn hình r i k t thúc.

ự ế ụ ấ ẹ Th c t cho th y, khi tôi áp d ng các bài toán “nh nhàng” và “v a ừ

ề ấ ứ ọ ế ớ t lên l p s c”ứ này. các em h c sinh đ u r t thích thú, hào h ng trong các ti

ạ ứ ỏ ủ ộ ấ ớ ề ủ c a tôi. đi u này đã mang l i s c lan t a c a b môn r t l n, giúp cho

ườ ạ ườ ọ ề ứ ớ ươ ọ ớ . ng i d y và ng i h c đ u h ng thú v i ch ng trình Tin h c l p 11

ơ ở ể ả ọ ỉ ể ở ộ Ngoài ra h c sinh có th m r ng bài toán c s 6 đ gi i các bài toán ch nh

ổ ợ ươ ả ợ h p và t h p khác trong ch ng trình gi ớ i tích l p 11.

ự ự ượ ứ ắ ậ ồ Sau khi t mình xây d ng đ c thu t toán r i, ngay t c kh c các em đã

ể ế ươ ả ữ ậ ế có th vi t ch ng trình gi ằ i quy t các bài toán đó b ng ngôn ng l p trình

ộ Pascal m t cách nhanh chóng và chính xác.

ả ạ ế ọ ừ ồ ụ ụ ớ K t qu t i 3 l p tôi ph trách trong năm h c v a r i, sau khi áp d ng

ứ ộ ở ớ ữ ể ằ ậ ấ SKKN này, v i m c đ các bài ki m tra l p trình b ng ngôn ng Pascal l y

ừ ụ ể ư t đây, các em đã làm tôi hài lòng. C th nh sau:

ỷ ệ ạ ạ T l HS đ t lo i khá tr ở L pớ Ban lên

11B1 ơ ả C b n 68,42%

ự 11B5 T nhiên 70,2%

ự 11B9 T nhiên 88,64%

Ậ Ế III. K T LU N.

ậ ả ộ

ộ

SKKN này tôi ch nêu minh ho

ữ ở ộ ả ở ộ ạ ừ ỉ ẫ ậ

ắ ọ ả ượ ự ậ ơ ả ẽ i m t bài toán c b n s ệ đó rèn luy n ạ m t ộ m t s bài toán c s và cách d n d t h c sinh nh n i các bài toán ơ ở đó xây d ng đ c thu t toán gi

ệ ắ Vi c n m v ng input, output và thu t toán gi ớ ọ giúp h c sinh m r ng các l p bài toán m t cách linh ho t t ọ ượ ỹ đ i toán cho h c sinh. c k năng gi ừ ộ ố ố s bài toán m r ng t ể ừ ở ộ ạ d ng, m r ng bài toán đ t ở ộ m r ng.

ổ ở ộ

ọ ọ ữ

ạ ế ề ố ượ ắ ự ự ư

ể

ể ượ ơ ở ư ự ễ c gi

ả ằ ẫ ộ

ự ng xây d ng thuât toán duy nh t đ đ m b o tính lôgic_M r ng bài toán.

ỗ ạ ả ạ ầ ỉ ở ộ ữ ậ ượ ễ ớ

c di n đ t g n v i ngôn ng l p trình ớ ề ớ ọ ậ ẽ ầ ơ ợ ớ ỉ Trong khuôn kh SKKN, các bài toán m r ng nêu ra ch phù h p v i ứ ế các h c sinh trung bình và khá, giúp h c sinh n m v ng ki n th c SGK ọ ể . H c sinh có ng và cũng ch a th c s tiêu bi u và còn h n ch v s l ể ậ ụ ặ th tìm thêm các bài toán khác đ v n d ng trong th c ti n. M t khác các bài ở ộ ậ ữ toán c s cũng nh các bài toán m r ng có th đ i b ng nh ng thu t ớ toán khác. Tuy nhiên trong đè tài này, v i m i d ng toán tôi v n ch nêu m t ấ ể ả ướ h Các thu t toán nêu trong đ tài đ Pascal s g n gũi h n v i h c sinh l p 11.

ắ ằ ế ế ẫ

ề ư ọ ề ế ệ

Tôi tin ch c r ng đ tài này v n còn nhi u khi m khuy t, kính mong ề ồ đ ng nghi p cũng nh h c sinh cho nhi u ý ki n đóng góp. Tôi xin chân thành ả ơ c m n!