SKKN Phát triển tư duy thuật toán cho học sinh THCS thông qua việc khai thác một số bài toán cơ bản trong môn Tin học

Nội dung tóm tắt: SKKN Phát triển tư duy thuật toán cho học sinh THCS thông qua việc khai thác một số bài toán cơ bản trong môn Tin học

1. toán cơ bản 1. Tuy nhiên các em sẽ gặp khó khăn về thuật giải với n số. Như vậy giáo viên đã tạo cho học sinh một tình huống có vấn đề mà học sinh cần phải tư duy để vượt qua khó khăn này. Để giảm mức độ khó giáo viên yêu cầu học sinh nêu ý tưởng: Tìm ước chung lớn nhất của 3 số, khi học sinh làm được giáo viên tiếp tục yêu cầu học sinh tìm ước chung lớn nhất của 4 số, 5 số Lúc này học sinh sẽ rút ra thuật giải tổng quát của bài toán tìm ước chung của N số như sau: Gọi U1 là ước chung lớn nhất của a1 và a2. Bước tiếp theo tìm ước lớn nhất của U1 với a3, gọi U2 là ước chung lớn nhất của U1 và a3. Tiếp tục tìm ước chung của U2 với a4 Tìm ước chung lớn nhất của Un-2 với n. Cuối cùng ta được ước chung của dãy gồm n phần tử là Un-1. Chương trình tham khảo: const fi='uclnmax.inp'; fo='uclnnax.out'; var i,ucmax,n:longint; u:array[1 100000] of longint; function UCLN(a,b:longint):longint; var x,y,r: longint; Begin x:= b; y:= a; while y <> 0 do begin r:= x mod y; x:= y; y:= r; end; ucln:=x; end; BEGIN assign(input,fi); reset(input); readln(n); for i:=1 to n do read(u[i]); assign(output,fo); rewrite(output); ucmax:=ucln(u[1],u[2]); for i:=3 to n do ucmax:=ucln(ucmax,u[i]); write(ucmax); close(input); close(output); END. 5
2. Nhận xét: Từ bài toán tổng quát (bài 1.1), dựa trên thuật toán của bài toán cơ bản đã biết (bài toán 1) giáo viên đã rèn cho học sinh khả năng đặc biệt hóa, khái quát hóa thuật toán, quy bài toán lạ về bài toán quen thuộc cơ bản, bài toán quen thuộc. Rèn luyện được cho học sinh kỹ năng này sẽ là tiền đề giúp các em học tốt phương pháp quy hoạch động, đệ quy.  Từ bài toán cơ bản đã biết, vận dụng phép tương tự hóa để giải quyết một số bài toán tương tự mở rộng, bài toán thực tiễn. Từ bài toán cơ bản tìm ước chung lớn nhất của 2 số nguyên a và b, giáo viên tiếp tục đưa ra một số bài toán mở rộng tương tự, bài toán thực tiễn để học sinh có thể vận dụng các kiến thức, kỹ năng từ bài toán cơ bản để giải quyết một số bài toán tương tự mở rộng, các bài toán ứng dụng trong thực tiễn, từ đó hình thành tư duy sáng tạo cho các em thông qua việc khai thác một chuỗi các bài tập có liên quan logic với nhau. Sau đây chúng tôi xin giới thiệu một số bài toán tương tự mở rộng và một số bài toán thực tiễn, các bài toán này đều được phát triển từ bài toán gốc “tìm ước chung lớn nhất của 2 số nguyên dương”. Lớp các bài toán này được đính kèm bên dưới phần phụ lục của sáng kiến. Tính mới và sáng tạo của giải pháp 1: Giải pháp này giúp học sinh rèn luyện kỹ năng quy lạ về quen, đưa nặng về nhẹ, chuyển đổi các bài toán phức tạp cồng kềnh thành những bài toán cơ ban đã biết. Với giải pháp mới này, giáo viên đã giúp học sinh tiết kiệm được thời gian để hình thành tư duy thuật toán thông qua lớp bài toán có kiến thức liền mạch, logic với nhau. Giải pháp 2. Rèn luyện cho học sinh khả năng phân tích, tổng hợp, vận dụng các kiến thức, kỹ năng đã có để giải quyết bài toán theo nhiều thuật giải khác nhau từ đó lựa chọn ra thuật giải tối ưu. Đứng trước một bài toán mới lạ phải học sinh phải linh hoạt, mềm dẻo đưa ra nhiều thuật giải khác nhau, không dập khuân, máy móc từ đó phân tích lựa chọn ra thuật giải tối ưu nhất cho bài toán. Rèn luyện được khả năng này giúp học sinh hình thành tư duy một cách sáng tạo, phát hiện ra vấn đề mới của thuật toán. Đây là một trong những kỹ năng quan trọng nhất trong lập trình. Ví dụ minh họa: Bài 2. Kiểm tra tính nguyên tố của một số nguyên. Cho một số nguyên N (với N≤1012). Hãy kiểm tra N có phải là số nguyên tố hay không? Ví dụ: N=11 là số nguyên tố, N=100 không phải là số nguyên tố. Giới hạn thời gian bài toán là 1s. Đối với bài toán 2 học sinh thường mắc những sai lầm sau: + Thứ nhất: Dùng thuật toán vét cạn để giải quyết bài toán một cách đơn thuần, không quan tâm đến giới hạn dữ liệu đầu bài (N≤1012), thời gian chạy chương trình nên dẫn đến thuật toán không tối ưu. Thuật toán vét cạn sau chỉ đảm bảo giới hạn dữ liệu (N≤106). 6
3. Function KTNT(N:longint):Boolean; Begin KTNT:=False; For i:=2 to n -1 do If N mod i =0 then Begin KTNT:=true; Break; End; End. + Thứ hai: Giáo viên dạy cho học sinh công nhận luôn thuật toán tối ưu (thuật toán đảm bảo chạy được giới hạn dữ liệu đề bài và thời gian nhỏ hơn 1 giây) mà không cần giải thích tại sao phải dùng thuật toán này? Điều này dẫn đến học sinh không hiểu được bản chất thực của thuật toán, do đó không phát huy được tư duy sáng tạo, không khơi dạy được niềm đam mê, hứng thú trong bộ môn tin học. Function KTNT(N:longint):Boolean; Begin KTNT:=False; For i:=2 to trunc(sqrt(n)) do If N mod i =0 then Begin KTNT:=true; Break; End; End. Để khắc phục những lỗi trên giáo viên cần xây dựng các tình huống có vấn đề để học sinh có thể phân tích, lựa chọn thuật giải tối ưu cho bài toán như sau: 6 6 12 + Giáo viên xây dựng 2 bộ test N≤10 và 10 106 học sinh sẽ phát hiện chương trình sẽ chạy thời gian quá 1s không đảm bảo giới hạn về thời gian chạy. Như vậy đây là một tình huống có vấn đề mà học sinh cần tuy duy sáng tạo, phân tích, tổng hợp các kiến thức đã học để đưa ra cách giải khác để giải quyết bài toán. Đến đây giáo viên có thể yêu cầu học sinh nhắc lại và lấy ví dụ về tính chất kiểm tra ước trong toán học mà các em đã được biết trong chương trình toán học lớp 6 như sau: “ Mỗi hợp số n có ít nhất một ước số nguyên tố nhỏ hơn hoặc bằng n ”. Sau khi học sinh biết được tính chất này sẽ tư duy thuật giải mới và cải tiến 12 12 6 thuật toán cũ từ giới hạn N≤10 về giới hạn N≤ 10 =10 . Bài toán đã được giải 7
4. quyết một cách tối ưu theo cách For i:=2 to trunc(sqrt(n)) do Nhận xét: Với bài toán trên giáo viên đã rèn cho học sinh khả năng phân tích bài toán, đưa ra nhiều cách giải từ đó lựa chọn ra thuật giải tối ưu, điều này giúp học sinh hình thành kỹ năng phát hiện vấn đề, đưa ra thuật toán tối ưu một cách nhanh nhất khi gặp một bài toán khác tương tự như tính tổng, đếm các số nguyên tố trong một dãy số cho trước Bài 3. Cho số nguyên dương n (n≤1000). Đếm ước nguyên tố của n!. Ví dụ: N=3 thì N!=3! có 4 ước số là 1; 2; 3; 6. Giới hạn thời gian bài toán là 1s. Đối với bài toán này một trong những sai lầm lớn nhất của của giáo viên và học sinh là tính n!, sau đó duyệt trong đoạn từ [1;n!] để thực hiện kiểm tra nguyên tố và đếm, cách này là không khả thi về mặt dữ liệu và thời gian, vì khi tính n! sẽ dẫn đến lỗi tràn dữ liệu với n>20. Tương tự như trên giáo viên cần xây dựng các tình huống cho học sinh phân tích lựa chọn thuật giải như sau: Giáo viên xây dựng bộ test N≤20 và n>20 + Với N>20 học sinh sẽ phát hiện ra lỗi tràn dữ liệu nếu sử dụng thuật tính N!. Khi đó học sinh cần phải tư duy, vận dụng các kiến thức đã có để giải quyết vấn đề trên bằng một thuật giải khác hoặc giáo viên có thể cho học sinh phân tích một số ví dụ để rút ra kết luận “mọi ước nguyên tố của N! đều nhỏ hơn hoặc bằng N” nên chỉ cần duyệt từ khoảng [2;N] để kiểm tra và đếm các số nguyên tố, thuật toán này hoàn toán khả thi về dữ liệu và thời gian. Qua các tình huống và cách phân tích thuật giải bài toán 4 , học sinh sẽ lựa chọn cách tối ưu nhất. Chương trình thuật toán tham khảo: Function Demnt(N:integer):integer; Var i:integer; Begin For i:=2 to N do If KTNT(i) then Inc(Demnt); End; Tương tự như vậy giáo viên có thể khai thác một số lớp các các bài toán có cùng cách giải được khai thác từ bài toán cơ bản để rèn luyện tư duy sáng tạo của học sinh. Sau đây chúng tôi xin giới thiệu lớp bài toán sử dụng thuật toán cơ bản “Phân tích một số nguyên dương thành tích các thừa số nguyên tố ” để tiếp tục rèn luyện cho học sinh khả năng phân tích, tổng hợp thuật toán từ đó lựa chọn thuật giải tối ưu. Lớp các bài toán này được đính kèm bên dưới phần phụ lục của sáng kiến. Tính mới, tính sáng tạo của giải pháp 2. Tính mới và tính sáng tạo của giải pháp 2 được thấy rõ trong việc rèn luyện để hình thành tư duy phân tích, tổng hợp cho học sinh bằng cách đưa ra nhiều thuật giải, từ đó lựa chọn thuật giải tối ưu nhất của bài toán. 8
5. Giải pháp giúp giáo viên và học sinh hiểu rõ được bản chất của thuật toán, khắc phục được việc chỉ giải bài toán một cách đơn giản là chạy được chương trình hoặc công nhận thuật giải mà không biết thuật toán đã tối ưu hay chưa? Khi học sinh hình thành được tư duy sáng tạo trong thuật toán sẽ giúp các em thích giải quyết những bài toán ở mức độ cao hơn từ đó tạo hứng thú, ham thích học bộ môn lập trình cho các em. 3. Hiệu quả của sáng kiến. 3.1. Hiệu quả kinh tế Trong các năm học 2015-2016, 2016-2017 ; 2017-2018, tỉ lệ học sinh đạt giải rất cao so với các huyện khác trong tỉnh, luôn duy trì đứng thứ nhất toàn đoàn trong suốt 4 năm liên tiếp. Qua đó thể hiện việc áp dụng sáng kiến là khả thi rất cao. Đây chính là tiền đề để các em có động lực vào các lớp chuyên tin, các lớp năng khiếu lập trình. Qua học tập theo phương pháp trên giúp học sinh có kiến thức chuyên sâu, tư duy sáng tạo về lập trình, đây chính là nền tảng vững chắc về chi thức để các em định hướng nghề nghiệp trong tương lai. Đây chính là hiệu quả về mặt tri thức, chất xám của xã hội. Giúp giáo viên và học sinh giảm bớt thời gian học tập và nghiên cứu. Đây chính là hiệu quả về kinh tế về mặt thời gian và tri thức đối với học sinh và giáo viên. 3.2. Hiệu quả xã hội A. Hiệu quả trong công tác bồi dưỡng đội tuyển học sinh giỏi Việc áp dụng sáng kiến vào công tác bồi dưỡng đội tuyển học sinh giỏi đã đạt được những thành tích cao và được thể hiện qua bảng số liệu sau: Số HS Số HS Tỉ lệ % Số lượng giải Năm học Dự thi Đạt giải đạt giải Nhất Nhì Ba KK 2015-2016 06 06 100% 01 05 0 0 2016-2017 07 07 100% 01 05 01 0 2017-2018 09 09 100% 0 03 05 01 B. Hiệu quả trong việc nâng cao trình độ chuyên môn nghiệp vụ, bồi dưỡng tình cảm nghề nghiệp cho đội ngũ giáo viên trong ngành giáo dục, nâng cao uy tín của giáo viên trong công giảng dạy cũng như của ngành giáo dục Trong các năm học chất lượng đại trà luôn đạt và vượt chỉ tiêu về tỉ lệ học sinh khá giỏi, đặc biệt trong ba năm liên tiếp đội tuyển tin học của thành phố Ninh Bình do tôi phụ trách luôn xếp thứ nhất toàn tỉnh, tỉ lệ học sinh đạt giải luôn đạt tỉ lệ cao nhất tỉnh, hàng năm luôn có học sinh của trường đạt giải tin học trẻ cấp thành phố, cấp tỉnh. Đây chính là kết quả khẳng định chất lượng giảng dạy của đội ngũ giáo viên giảng dạy bộ môn tin học trong nhà trường THCS Ninh Phong và của thành phố Ninh 9
6. Bình, từ đó nâng cao uy tín của ngành giáo dục thành phố Ninh Bình trong công tác giảng dạy, đặc biệt là trong công tác giảng dạy đại trà, bồi dưỡng học sinh giỏi. Qua đó cũng làm cho xã hội, các phụ huynh yên tâm, tin tưởng tuyệt đối vào đội ngũ giáo viên, cũng như ngành giáo dục trong rèn luyện, đào tạo ra những con người có tài đức vẹn toàn để xây dựng quê hương giàu đẹp. C. Hiệu quả trong việc rèn luyện kĩ năng học tập và bồi dưỡng tình cảm của học sinh đối với môn tin học. Qua thực tiễn và nghiên cứu tôi nhận thấy rằng áp dụng sáng kiến vào dạy học theo định hướng khai thác và phát triển bài toán là một cách làm hay, phù hợp với xu thế chung, góp phần vào việc đổi mới phương pháp dạy học, rèn luyện kiến thức, kĩ năng, óc sáng tạo và bồi dưỡng năng lực tư duy cho học sinh và ngoài ra còn gây hứng thú, ham thích học bộ môn tin cho các em. 4. ĐIỀU KIỆN VÀ KHẢ NĂNG ÁP DỤNG 4.1. Khả năng áp dụng sáng kiến * Đối nhà trường: Năm học 2015-2016 có 01 em đạt giải nhì cấp tỉnh; 01 em đạt giải nhì trong cuộc thi tin học trẻ không chuyên cấp tỉnh, tỉ lệ đạt giải là 100%. - Năm học 2016-2017 có 02 em được đi thi tỉnh và đạt 01 giải nhì, 01 giải 3, tỉ lệ đạt giải 100%. - Năm học 2016-2017 có 01 em tham ra thi tin học trẻ không chuyên cấp tỉnh và đạt giải nhất và được chọn đi thi tin học trẻ toàn quốc. - Hằng năm chất lượng dạy học đại trà luôn luôn đạt và vượt chỉ tiêu. * Đối với đội tuyển tin học thành phố Ninh Bình Năm học 2015-2016 đội tuyển tin thành phố Ninh Bình xếp thứ nhất toàn tỉnh, trong 06 em tham gia đội tuyển đạt giải 100%, trong đó có 01 giải nhất và 05 giải nhì. Năm học 2016-2017 đội tuyển tin thành phố Ninh Bình xếp thứ nhất toàn tỉnh, trong 07 em tham gia đội tuyển đạt giải 100%, trong đó có 01 giải nhất và 05 giải nhì, 01 giải 3. Năm học 2017-2018 đội tuyển tin có 09 em dự thi tỉ lệ đạt giải là 100%, toàn đoàn đứng thứ nhất tỉnh, trong đó có 03 giải nhì, 05 em giải ba, 01 em giải khuyến khích. * Sáng kiến được áp dụng trong thử nghiệm trong năm đầu tiên 2015-2016 trong công tác dạy học đại trà và công tác bồi dưỡng học sinh giỏi cấp trường, cấp thành phố, cấp tỉnh đối với bộ môn lập trình tin học và một số bài toán trong chương trình bảng tính excel (tin học 7) và sau đó được áp dụng liên tiếp trong các năm học 2016- 2017; 2017-2018 và đã đạt được những hiệu quả nhất định trong dạy và học như chúng tôi đã trình bày ở trên. Các giáo viên tin dạy chương trình lập trình ở các nhà trường và cấp học khác hoàn toàn có thể áp dụng sáng kiến này trong công tác giảng dạy đại trà, bồi dưỡng học sinh giỏi để rèn luyện tư duy sáng tạo cho học sinh để nâng cao chất lượng giáo 10
7. dục. Giải pháp nêu trong sáng kiến hoàn toàn phù hợp với việc đổi mới phương pháp dạy học theo đinh hướng năng lực học sinh nên sáng kiến có thể áp dụng cho bộ môn toán học trong chương trình giáo dục phổ thông. 4.2. Điều kiện áp dụng sáng kiến Tuy vậy để áp dụng được sáng kiến ta cần đảm bảo các yêu cầu sau: Giáo viên phải nhiệt huyết, yêu nghề, yêu thích bộ môn lập trình tin học. Giáo viên phải có kiến thức tổng hợp chuyên sâu về bộ môn lập trình để có thể khai thác, phát triển các bài toán cơ bản thành các dạng, lớp bài toán nâng cao để rèn luyện tư duy cho học sinh. Học sinh phải có kiến thức cơ bản về ngôn ngữ lập trình, nắm được một số thuật toán cơ bản trong lập trình tin học. Danh sách những người đã tham gia áp dụng sáng kiến thử. Trình độ Nội dung Năm Chức STT Họ và tên Nơi công tác chuyên công việc sinh danh môn hỗ trợ Áp dụng Trường THCS Giáo sáng kiến 1 Lê Xuân Ngưu 1985 Ninh Phong -TP Đại Học viên vào giảng Ninh Bình dạy Áp dụng Trường THCS Giáo sáng kiến 2 Đoàn Duy Thường 1984 Trương Hán Siêu Thạc Sĩ Viên vào giảng - TP Ninh Bình dạy Chúng tôi xin cam đoan mọi thông tin nêu trong đơn là trung thực, đúng sự thật và hoàn toàn chịu trách nhiệm trước pháp luật. 11
8. TP. Ninh Bình, ngày 05 tháng 09 năm 2018 NGƯỜI NỘP ĐƠN TÁC GIẢ ĐỒNG TÁC GIẢ Lưu Thị Thuỷ Lê Xuân Ngưu Trần Văn Trường TRƯỜNG THCS NINH PHONG PHÒNG GDĐT THÀNH PHỐ NINH BÌNH XÁC NHẬN XÁC NHẬN Sáng kiến “Phát triển tư duy thuật toán cho học sinh thcs thông qua việc khai thác một số bài toán cơ bản trong môn tin học” đã được áp dụng và mang lại hiệu quả thiết thực tại trường THCS Ninh phong từ năm học 2015-2016 KT. HIỆU TRƯỞNG (Kí, đóng dấu) 12
9. PHỤ LỤC I. Vận dụng bài toán cơ bản “ Tìm ước chung lớn nhất của hai số nguyên dương” để phát triển và giải một số bài toán mở rộng, bài toán thực tiễn. A. Một số bài toán mở rộng Bài 1. Cho hai số nguyên dương a và b. Hãy kiểm tra hai số a, b có phải là 2 số nguyên tố cùng nhau không? Ví dụ a=3; b=10 là hai số nguyên tố cùng nhau. Bài 2. Cho hai số nguyên dương a và b. Tìm bội chung nhỏ nhất của 2 số nguyên dương a và b. Ví dụ a=2; b=10 bội chung nhỏ nhất là 10. Bài 3. Cho phân số a (b≠0) . Hãy rút gọn phân số trên? Ví dụ a=2; b=10 là thì b phân số rút gọn là 1 . 5 X X X Bài 4. Cho dãy gồm N phân số 1 , 2 , , n . Y1 Y2 Yn Yêu cầu: Đếm xem có bao nhiêu phân số tối giản. Dữ liệu vào: Từ tệp PSTG.INP gồm N + 1 dòng: 3 + + Dòng đầu ghi số N (với N < 10 , N Z ). + N dòng tiếp theo mỗi dòng ghi hai số Xi, Yi ghi cách nhau một dấu cách là tử X i 3 + số và mẫu số của phân số (với 1 ≤ Xi, Yi ≤ 10 , Xi, Yi Z ). Yi Dữ liệu ra: Là tệp PSTG.OUT ghi số lượng các phân số tối giản. Ví dụ: PSTG.INP PSTG.OUT 3 2 2 3 2 4 8 3 B. Một số bài toán thực tiễn. Bài 5. Để kỷ niệm ngày Quốc tế phụ nữ 8-3, công ty bánh kẹo Kinh Đô muốn tặng mỗi nữ nhân viên một phần quà là các loại bánh kẹo. Công ty đã chuẩn bị N loại bánh kẹo khác nhau. Mỗi loại có số gói khác nhau. Em hãy giúp Công ty chia số bánh kẹo đó thành những phần quà giống nhau sao cho số lượng phần quà là nhiều nhất. Dữ liệu vào: File văn bản CHIAQUA.INP gồm 2 dòng, dòng đầu chứa số nguyên dương N là số loại bánh kẹo, dòng thứ hai chứa N số nguyên dương a1, a2, , an. (ai là số gói bánh kẹo của loại thứ i). Dữ liệu ra: File văn bản CHIAQUA.OUT chứa 1 số nguyên là kết quả tìm được. Ví dụ 1: 13
10. CHIAQUA.INP CHIAQUA.OUT 2 2 6 4 Bài 6. Trong cuộc thi giải toán qua mạng internet mỗi học sinh đều có số điểm tích lũy riêng của mình. Số điểm tích lũy của mỗi học sinh là một số nguyên dương K (0 < K ≤ 2 109). Đội tuyển của trường THCS Tài Năng có N học sinh tham gia dự thi (2 ≤ N ≤ 100). Tại buổi gặp mặt trước kỳ thi cấp tỉnh, thầy hiệu trưởng quyết định thưởng cho các học sinh trong đội tuyển Q triệu đồng, biết rằng điểm tích lũy của mỗi học sinh đều chia hết cho Q. Yêu cầu: Hãy tìm số nguyên dương Q lớn nhất. Dữ liệu vào: Cho trong file văn bản PT.INP có cấu trúc như sau: - Dòng 1: Ghi số nguyên dương N là số lượng học sinh. - Dòng 2: Ghi N số nguyên dương lần lượt là điểm tích lũy của N học sinh, các số được ghi cách nhau ít nhất một dấu cách. Dữ liệu ra: Ghi ra file văn bản PT.OUT theo cấu trúc như sau: - Dòng 1: Ghi số nguyên dương Q tìm được. Ví dụ: PT.INP PT.OUT 5 3 15 24 45 36 27 Bài 7. Trong một màn pháo hoa chào đón năm mới 2016 có N loại pháo hoa. Mỗi loại pháo hoa có màu sắc và hình dạng khác nhau sẽ được bắn lên theo những chu kỳ khác nhau. Tính từ khi bắt đầu màn pháo hoa, loại pháo hoa thứ i sẽ được bắn lên vào những giây chia hết cho i. Tuấn là một khán giả do điều kiện thời gian hạn hẹp chỉ có M giây để chiêm ngưỡng màn pháo hoa này, cậu ta muốn nhìn thấy càng nhiều loại pháo hoa được bắn lên cùng một lúc càng tốt. Bạn hãy tính xem Tuấn phải đợi ít nhất bao nhiêu giây trong thời gian cho phép của mình để đạt được điều cậu ta mong muốn. Dữ liệu vào: Trong tệp PHAOHOA.INP ghi hai số nguyên dương N, M (0<N,M<60000) Dữ liệu ra: tệp PHAOHOA.OUT ghi số giây nhỏ nhất mà Tuấn phải đợi. Ví dụ : PHAOHOA.INP PHAOHOA.OUT 5 25 12 Bài 8. Nhân kỷ niệm 1050 nhà Nhà nước Đại Cổ Việt, người ta trang trí một dây đèn nháp nháy tại khu vực quảng trường Đinh Tiên Hoàng Đế. Dây đèn này gồm có N bóng nối tiếp, được đánh số thứ tự từ 1 tới N và được điều khiển theo nguyên tắc: Bắt đầu từ thời điểm 0 tất cả các bóng đèn đều ở trạng thái tắt, bóng thứ I lóe sáng 14
11. vào các thời điểm Ti ; 2xTi; 3xTi (với i=1, 2, N). Nếu đứng theo dõi sẽ thấy thời điểm tất cả các bóng đèn đều sáng. Ví dụ: Nếu có 2 đèn mà T1=4 thì tại các thời điểm 4, 8, 12, 20 bóng 1 sẽ sáng, T2=6 thì các thời điểm 6, 12, 24, 30 bóng đèn 2 sẽ sáng. Như vậy thời điểm 12 là thời điểm sớm nhất mà cả 2 bóng đèn đều cùng lóe sáng. Cho biết số lượng đèn N và các giá trị Ti, hãy xác định thời điểm sớm nhất mà tất cả N bóng đèn đều sáng. Dữ liệu vào: Trong tệp Dennhay.inp gồm có 2 dòng: Dòng đầu chứ số nguyên dương N (2<N<30). Dòng thứ 2 chứa N số nguyên dương T1; T2; T3 Tn (Ti<106). Dữ liệu ra: Trong tệp dennhat.out ghi 1 số duy nhất là thời điểm sớm nhất mà cả N bóng đều sáng. Ví dụ: DENNHAY.INP DENNHAY.OUT 2 12 4 6 Nhận xét: Tất cả các bài toán trên đều vận dụng thuật toán tìm ước chung lớn nhất (bài toán cơ bản). II. Một số bài toán cơ bản nâng cao được phát triển từ thuật toán “Phân tích một số nguyên dương thành tích các thừa số nguyên tố ”. Bài toán 1. Cho số nguyên dương N (N<1012). Hãy phân tích N thành tích các thừa số nguyên tố. Ví dụ: n=100, phân tích n thành tích các thừa số nguyên tố ta sẽ được n=100=22.52 Bài toán 2. Cho số nguyên dương N (N<1012). Đếm số ước nguyên dương của N. Ví dụ N=10 có 4 ước là 1; 2; 5; 10. Dữ liệu vào: Trong tệp count.inp ghi số nguyên dương N. Dữ liệu ra: Trong tệp count.out ghi số nguyên không âm là số lượng ước nguyên dương của N. Bài 3. Cho số nguyên dương N (N<109). Tìm một số nguyên dương K nhỏ nhất để N!xK là một số chính phương. Ví dụ N=4 thì số nguyên dương nhỏ nhất là K=6 vì N!x6=24.6=144 là một số chính phương. Bài 4. Cho số nguyên dương n (n≤1000). Tìm số chữ số 0 tận cùng của N!. Ví dụ: 14! = 87178291200 có 2 chữ số 0 tận cùng, 15! = 1307674368000 có 3 chữ số 0 tận cùng. Bài 5. Với mọi số nguyên dương x ta luôn biến đổi được x thành tích a. b (với a, b là các số nguyên dương). Việc biến đổi như vậy gọi là đưa thừa số ra ngoài dấu căn. Yêu cầu: Cho trước số nguyên dương x (1≤x ≤ 1014). Hỏi trong các cách biến 15
12. đổi x thành tích a. b (với a, b là các số nguyên dương) thì số a lớn nhất là số nào? Ví dụ: Với x = 72 ta có x = 72 =1. 72 =2. 18 =3. 8 =6. 2 . Khi đó số a lớn nhất là 6. Dữ liệu vào: Trong tệp cbh.inp ghi một số nguyên dương x (x≤1014). Dữ liệu ra: Trong tệp cbh.out số a lớn nhất cần tìm. Ví dụ: CBH.INP CBH.OUT 72 6 Hết 16