Tài liệu Kinh nghiệm lựa chọn và cài đặt chương trình tối ưu khi giải một số dạng bài tập tìm kiếm, sắp xếp nhằm nâng cao chất lượng học sinh giỏi môn tin ở trường thpt

1 Đề tài: KINH NGHIỆM LỰA CHỌN VÀ CÀI ĐẶT CHƯƠNG TRÌNH TỐI ƯU KHI GIẢI MỘT SỐ DẠNG BÀI TẬP TÌM KIẾM, SẮP XẾP NHẰM NÂNG CAO CHẤT LƯỢNG HỌC SINH GIỎI MÔN TIN HỌC Ở TRƯỜNG THPT. 1. Mở đầu 1.1. Lí do chọn đề tài. 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. 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 ). 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). 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: “KINH NGHIỆM LỰA CHỌN VÀ CÀI ĐẶT CHƯƠNG TRÌNH TỐI ƯU KHI GIẢI MỘT SỐ DẠNG BÀI TẬP TÌM KIẾM, SẮP XẾP NHẰM NÂNG CAO CHẤT LƯỢNG HỌC SINH GIỎI MÔN TIN HỌC Ở TRƯỜNG THPT” nhằm định 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. 1.2. Mục đích nghiên cứu: 2 Đề tài này nghiên cứu nhằm giúp học sinh giải quyết tốt các bài toán sắpp xếp, tìm kiếm từ đó đôi mới cách tư duy lâ ̣p trình, để khi đứng trước mô ̣t bài toán cần giải quyết ngoài viê ̣c tìm ra thuâ ̣t toán để cài đặt chương trình thì học sinh sẽ biết cách so sánh, đánh giá hiệu quả của thời gian thực hiện chương trình (hay còn gọi là độ phức tạp của thuật toán) và lựa chọn được chương trình phù hợp nhằm nâng cao chất lượng học sinh giỏi 1.3. Đối tượng nghiên cứu: Sáng kiến kinh nghiê ̣m có đối tượng nghiên cứu là các bài toán sắpp xếp, tìm kiếm, được nghiên cứu ở nhiều cách làm, xét trên nhiều phương diện 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 Để trình bày sáng kiến kinh nghiê ̣m này, tôi đã sử dụng phối kết hợp nhiều phương pháp như: nghiên cứu tài liê ̣u, thuyết trình, quan sát, điều tra cơ bản, thực nghiê ̣m so sánh, phân tích kết quả thực nghiê ̣m, … phù hợp với môn học thuô ̣c lĩnh vực Tin học. 2. NỘI DUNG NGHIÊN CƯU 2.1. Cơ sở l uu ̣n Căn cứ vào mục tiêu của môn Tin học, là phải cung cấp những tri thức cơ bản, làm nền tảng để học sinh có thể tiếp tục đi sâu vào tìm hiểu và xây dựng khoa học Tin học hoặc tiếp thu những tri thức của các lĩnh vực kĩ thuật công nghệ tiên tiến, nhất là các lĩnh vực của công nghệ thông tin. Môn Tin học, cũng như mọi môn học khác, căn cứ vào mục tiêu trên để xác định ra nhiệm vụ cụ thể của môn học, tô chức hoạt động đào tạo góp phần thực hiện mục tiêu giáo dục mà Đảng và nhà nước đề ra. Nếu học sinh thực hiê ̣n tốt viê ̣c lựa chọn và cài đặt chương trình tối ưu khi giải các bài tâ ̣p sắpp xếp, tìm kiếm nói riêng và các bài tập lâ ̣p trình nói chung thì chất lượng học sinh giỏi sẽ được nâng cao. 2.2. Thực trạng 3 Những năm đầu tôi dạy bồi dưỡng học sinh giỏi chưa chú trọng nhiều đến cải tiến chương trình tối ưu hơn để chương trình chạy nhanh hơn và chủ yếu là định hướng cho học sinh tìm ra được thuâ ̣t toán (cách làm) để chương trình cho ra được kết quả mà thôi. Chính vì vậy khi giải quyết các bài toán cơ bản nói riêng và các bài tập lập trình pascal khác nói chung, học sinh và ngay cả giáo viên thường chỉ làm việc với các bộ input có dữ liệu nhỏ dễ nhìn thấy kết quả output và thường không xét đến trường hợp input đặc biệt hay các input có dữ liệu lớn. Dẫn đến bị mất điểm trong bài thi học sinh giỏi. Đối với thi học sinh giỏi, dù kết quả output của 2 thí sinh có giống hệt nhau với cùng một bộ input, nhưng việc chênh lệch về thời gian quyết định thí sinh có thể chiến thắpng hay thất bại (yêu cầu thời gian xử lí chương trình không quá 1 giây/1 test). Trong các kì thi học sinh giỏi gần đây, với cấu trúc đề 5 câu tương ứng với số điểm 6, 5, ,,3,2 trong đó chỉ có không quá 50% các dữ liệu input là nhỏ vừa tầm thì việc thí sinh dù có làm hết cả , câu trong đề thì nguy cơ thất bại vẫn rất cao. Bảng điểm các lần thi khảo sát chất lượng học sinh giỏi về chuyên đề số học (do tôi tự tô chức) năm học 2018 – 2019 khi chưa thực hiện đề tài: Họ tên Phạm Minh Đức Võ Lê Phương Điểm lần 1 2/10 3/10 Điểm lần 2 3/10 3/10 Điểm lần 3 2/10 ,/10 Điểm lần , 3/10 ,/10 Do đó kết quả học sinh giỏi năm 2018- 2019 chưa được như mong muốn, có 2 em học sinh tham gia thi học sinh giỏi Tin của trường thất bại không có em nào đạt giải (mă ̣c dù khi đi thi về các em rất phấn khởi vì nghỉ mình làm bài tốt, đúng vâ ̣y bài làm các em đều cho kết quả đúng trong khoảng thời gian cho phép nhỏ hơn 1 giây nhưng với bô ̣ input có dữ liê ̣u nhỏ còn bô ̣ input có dữ liê ̣u lớn thì bài làm vẫn cho kết quả đúng nhưng thời gian chạy chương trình quá 1giây, nghĩa là bô ̣ test có dữ liê ̣u lớn các em bị mất điểm). Vấn đề đă ̣t ra, là làm thế nào để lấy được điểm với các bộ input có dữ liê ̣u lớn. Muốn vậy cần phải lựa chọn và cài đặt được chương trình hiệu quả (tối ưu). Chương trình hiệu quả là chương trình giải quyết được những bộ input có dữ liệu lớn, chính xác, dung lượng sử dụng bộ nhớ nhỏ, thời gian thực chương trình ngắpn,... Nhưng trong phạm vi sáng kiến kinh nghiệm của mình, tôi chỉ nghiên cứu về tiêu chí thời gian thực hiê ̣n chương trình để lựa chọn chương trình tối ưu, đây là tiêu chí quan trọng nhất và được người ta quan tâm nhiều. Ngoài ra, tôi cũng ưu , tiên lựa chọn chương trình ngắpn gọn, dễ hiểu phù hợp với năng lực học sinh trường tôi. Thời gian thực hiện chương trình không chỉ phụ thuộc vào thuật toán mà còn phụ thuộc vào cấu hình máy tính, kĩ xảo người lập trình, kích thước và tính chất của dữ liệu vào,...Để cụ thể và tường minh hơn tôi có sử dụng phần mềm Themis để đo thời gian thực hiện của các chương trình với các bộ test cụ thể (có file test kèm theo). Các kết quả được tôi thử nghiệm trên máy tính laptop ASUS, Ram 2GB, Processor AMDE-,50 APU 1.65HZ. 2.3. Cac giải phap. 2.3.1 Kiến thức trọng tum +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 ,: 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. + Thuật toan à 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ắpp 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. + Cac tính chất của thuật toan - Tính dừng: Thuật toán phải kết thúc sau một số hữu hạ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 đắpn: Sau khi thuật toán kết thúc, ta nhận được Output cần tìm. + Vì sao phải ựa chọn thuật toan tối ưu 5 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. + Căn cứ vào đuu để xac định thuật toan à 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 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ắpt 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. + Ngôn ngữ thuật toan - 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; 6 + 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. 2.3.2. Một số thuật toan sắp xếp, tìm kiếm 2.3.2.1 Thuật toan sắp xếp *Bài toan: Cho số nguyên dương N và dãy A gồm N số nguyên: a 1, a2,…, aN. Sắpp xếp dãy A thành dãy không giảm (tức là số hạng trước không lớn hơn số hạng sau). * Ví dụ: Cho N=10, dãy A: 5 7 8 1 2 3 10 9 0 5 => Dãy sau khi sắpp xếp: 0 1 2 3 5 5 7 8 9 10 * Thuật toan Có rất nhiều thuật toán sắpp xếp như sắpp xếp: lựa chọn, thêm dần, phân đoạn, vun đống, hòa nhập hai đường trực tiếp, tuần tự, tráo đôi, sắpp xếp nhanh Quick sort… Tuy nhiên trong quá trình dạy học tôi giới thiệu cho học sinh 2 thuật toán: tráo đôi và Quick sort. Thuật toán sắpp xếp tráo đôi dễ hiểu nhưng có một số hạn chế, còn quick sort có thời gian thực hiện ít Trong đề tài này tôi đưa ra hai thuật toán sắpp xếp đó là: sắpp xếp bằng tráo đôi và sắpp 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ể. 7 2.3.2.1.1 Thuật toan sắp xếp bằng trao đổi Ý tưởng phương phap: Với mỗi cặp số hạng đứng liền kề trong dãy, 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 toan: 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; Nhận xét: Thuật toán trên sử dụng 2 vòng lặp for… => mỗi lần duyệt i 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. Vậy số phép toán cần thiết là: (n-1)+(n-2)+…+1= n * ( n  1) 2 => Độ phức tạp của thuật toán xấp xỉ cỡ O(n2). 2.3.2.1.2 Thuật toan sắp xếp nhanh Quick-sort Ý tưởng phương phap: Ý tưởng: Chọn một phần tử làm chốt (ở đây ta chọn phần tử ở vị trí giữa). Từ trái sang tìm phần tử có vị trí i lớn hơn hoặc bằng phần tử chốt, từ phải sang tìm phần tử có vị trí j bé hơn hoặc bằng phần tử chốt. Nếu i <= j thì đôi chỗ hai phần tử. Làm cho đến khi i > j. Lúc này sẽ chia ra được 2 nhóm cần sắpp xếp. Làm tương tự như vậy với mỗi nhóm cho đến khi đã sắpp xếp hết dãy. 8 procedure quicksort(l,r: longint); var i,j,tg,mid: longint; begin i:=l; j:=r; mid:= a[(l+r) div 2]; repeat while a[i]< mid do inc(i); while a[j] > mid do dec(j); if i<=j then begin tg:=a[i]; a[i]:=a[j]; a[j]:=tg; inc(i); dec(j); end; until i> j; if il then quicksort(l,j); end; Độ phức tạp thuật toán là O(NlogN) * Nhận xét chung So sánh hai thuật toán trên ta thấy thuật toán sắpp xếp nôi bọt tuy dễ cài đặt nhưng có độ phức tạp cỡ O(n2) còn thuật toán Quick-sort chỉ có độ phức tạp cỡ O(nlogn), có nghĩa là thời gian thực hiện của Quick-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 pháp sắpp xếp phù hợp. Nếu tập dữ liệu đưa vào nhỏ (<=103) thì không nhất thiết phải sử dụng Quick-sort còn nếu tập dữ liệu đưa vào lớn thì sử dụng thuật toán Quick-sort quả là một giải pháp tuyệt vời. 2.3.2.1.3 Thuật toan tìm kiếm * Bài toan 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ố nguyên khác nhau: a1, a2,…, aN và một số nguyên k. Cần biết có hay không chỉ số i (1<=i<=N) mà ai = k. Nếu có hãy cho biết chỉ số đó. * Ví dụ: Cho N=6, dãy A gồm các số: ,, 6, 3, 9, 2, 15 9 + Với k=9, trong dãy trên có số hạng a , có giá trị bằng k. Vậy chỉ số cần tìm là i=,. + 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.3.2.1.3.1 Thuật toan tìm kiếm tuần tự Xac định bài toan: - 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. Ý tưởng: Trước hết ta so sánh k với a1 nếu k = a1 thì vị trí là 1, nếu k <>a1 ta so sánh tiếp k với a2. Nếu k = a2 thì vị trí của k là 2, còn trường hợp k <>a 2 thì so sánh tiếp k với a3… Quá trình trên được tiếp tục cho đến khi nếu k=a i (i<=n) thì vị trí là i, trường hợp k <> ai mà i>n thì k không có mặt 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. 10 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 n 1 2 phép so sánh, trường hợp xấu nhất là tìm 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). 2.3.2.1.3.2 Thuật toan tìm kiếm nhị phun Xac định bài toan: - Input: dãy a gồm N số nguyên khác nhau a1, a2,…, aN (dãy A đã được sắpp 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: 5 6 12 15 17 18 19. Tìm số k=18 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: So sánh khóa k với số hạng a Giua ở giữa dãy, trong đó Giua= [(n+1)/2]. Khi đó xảy ra một trong ba trường hợp: + Nếu k = aGiua thì Giua là chỉ số cần tìm. Kết thúc việc tìm kiếm. + Nếu k > aGiua thì việc tìm kiếm k trên dãy gồm các số hạng aGiua+1, aGiua+2,…, aN; + Nếu k < aGiua thì việc tìm kiếm k sẽ thực hiện trên dãy gồm các số a1, 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: 11 function binary_search(A, n, T) is L := 0 R := n − 1 whi e L ≤ R do Giua := floor((L + R) / 2) if A[Giua] < T then L := Giua + 1 e se if A[Giua] > T then R := Giua - 1 e se: return Giua return không_thành_công Nhận xét: Trong giải thuật trên trường hợp tốt nhất là tìm thấy khóa k = a Giua thì 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 hiện của giải thuật trên là ~ O(log2n). * 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ắpp 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ắpp xếp thì thời gian chi phí cho sắpp 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ắpc lựa chọn thuật toán sao cho phù hợp để chi phí thực hiện là ít nhất. 2.3.3. Một số ví dụ minh chứng Bài toan 1: cho dãy số A a1,a2,...an có n phần tử. hãy sắpp xếp dãy số A theo chiều tăng dần Yêu cầu: Sắpp xếp dãy A tăng dần thời gian chạy 1s Dữ liệu: Vào file DAYSO.inp - Dòng đầu tiên số nguyên n với n<=10, 12 - Dòng thứ 2: các phần tử của dãy số A (ai<109) Kết quả: ghi ra tệp DAYSO.out đã sắpp xếp tăng dần Cách 1: Dùng thuật toán sắpp xếp tráo đôi (thuật toán BAI1A phụ lục) Cách 2: Dùng thuật toán sắpp xếp quicksort (thuật toán BAI1B phụ lục) Kết quả chạy trên phần mêm Thuật toan sắp xếp trao đổi 32 mi iseconds thuật toan sắp xếp quicksort 16 mi iseconds , Nhận xét: với bài toán n<=10 có thể sử dụng được thuật toán sắpp xếp tráo đôi Bài toan 2: cho dãy số A a1,a2,...an có n phần tử. hãy sắpp xếp dãy số A theo chiều tăng dần Yêu cầu: sắpp xếp dãy A tăng dần thời gian chạy 1s Dữ liệu: Vào file DAYSO.inp - Dòng đầu tiên số nguyên n với n<=105 - Dòng thứ 2: các phần tử của dãy số A Kết quả: ghi ra tệp DAYSO.out đã sắpp xếp tăng dần Cách 1: Dùng thuật toán sắpp xếp tráo đôi (thuật toán BAI2A phụ lục) Cách 2: Dùng thuật toán sắpp xếp quicksort (thuật toán BAI2B phụ lục) Kết quả chạy trên phần mềm Thuật toan sắp xếp trao đổi 43087 mi iseconds Thuật toan sắp xếp quicksort 78 mi iseconds Nhận xét: với bài toán n<=105 và thời gian chạy 1s không thể sử dụng được thuật toán sắpp xếp tráo đôi, phải dùng thuật toán sắpp xếp quicksort Bài toan 3: Cho một dãy số a1,a2,...an có n<=10, phần tử. Hãy đếm số lần xuất hiện của từng phần tử trong mảng. (với ai <109) Yêu cầu: đếm số lần xuất hiện của từng phần tử trong mảng thời gian chạy 1s Dữ liệu: Vào file DAYSO.inp - Dòng đầu tiên số nguyên n với n<=10, - Dòng thứ 2: các phần tử của dãy số A (ai<109) 13 Kết quả: ghi ra tệp DAYSO.out tần số xuất hiện của các số trong dãy A Mỗi số ghi 1 dòng Cach1 : Ý tưởng sắp xếp dãy A, sau đó duyệt cac phần từ từ 1 đến n nếu a[i] và a[i+1] khac nhau thì in ra tần số, con không dem =dem+1 Với cách n<=10, tiến hành sắpp xếp mảng theo chiều tăng dần. Sử dụng sắpp xếp tráo đôi (thuật toan BAI3A phụ ục) Kết quả chạy trên phần mêm Thuật toan sắp xếp trao đổi 437 mi iseconds Nhận xét: thời gian chạy ít hơn 1 giây Bài toan 4: Cho một dãy số a1,a2,...an có n<=105 phần tử. Hãy đếm số lần xuất hiện của từng phần tử trong mảng. (với ai <109) Yêu cầu: đếm số lần xuất hiện của từng phần tử trong mảng thời gian chạy 1 giây Dữ liệu: Vào file DAYSO.inp - Dòng đầu tiên số nguyên n với n<=105 - Dòng thứ 2: các phần tử của dãy số A (ai<109) Kết quả: ghi ra tệp DAYSO.out tần số xuất hiện của các số trong dãy A Mỗi số ghi 1 dòng +Thuật toán : do n<=105 nên ta dùng sắpp xếp Quick-sort (thuật toan BAI3B phụ ục) Thuật toan sắp xếp Quick-sort 47 mi iseconds Bài toan 5: Cho một dãy số a1,a2,...an có n<=105 phần tử và giá trị X. Hãy tìm xem dãy số A có giá trị X không?, dãy chưa sắpp xêp. (với ai <109) Yêu cầu: Tìm xem dãy số A có giá trị X không, thời gian chạy 1 giây Dữ liệu: Vào file DAYSO.inp  Dòng 1: số X cần tìm  Dòng số 2 số nguyên n với n<=105  Dòng thứ 2: các phần tử của dãy số A (ai<109) Kết quả: ghi ra tệp DAYSO.out nếu tìm thấy ghi vị trí trong A, không thấy ghi số 0 Cách 1: Tìm kiếm tuần tự (thuật toan BAI5A phụ ục) Cách 2: Tìm kiếm nhị phân (thuật toan BAI5B phụ ục) 1, Kết quả chạy trên phần mêm Thuật toan tìm kiếm tuần tự 31 mi iseconds Thuật toan tìm kiếm nhị phun 94 mi iseconds Nhận xét: nếu dãy A chưa sắpp xếp thì sắpp xếp tuần tự nhanh hơn Bài toan 6: Cho một dãy số a1,a2,...an có n<=106 phần tử và giá trị X. Hãy tìm xem dãy số A có giá trị X không?, dãy đã sắpp xêp. (với ai <109) Yêu cầu: Tìm xem dãy số A có giá trị X không, thời gian chạy 1 giây Dữ liệu: Vào file DAYSO.inp  Dòng 1: số X cần tìm  Dòng số 2 số nguyên n với n<=105  Dòng thứ 2: các phần tử của dãy số A (ai<109) Kết quả: ghi ra tệp DAYSO.out nếu tìm thấy ghi vị trí trong A, không thấy ghi số 0 Cách 1: Thuật toán tìm kiếm tuần tự (thuật toán BAI6A phụ lục) Cách 2: Thuật toán tìm kiếm nhị phân (thuật toán BAI6B phụ lục) Thuật toan tìm kiếm tuần tự 296 mi iseconds Thuật toan tìm kiếm nhị phun 265 mi iseconds Nhận xét: nếu dữ liệu rất lớn và dãy số A đã sắpp xếp thì thuật toán tìm kiếm nhị phân nhanh hơn Bài toan 7: Trong một bữa tiệc, có N người tham dự. Người thứ i có chiều cao là Hi. Người tô chức bữa tiệc muốn đếm xem ông có thể ghép được bao nhiêu cặp từ N người này. Ông là một người khá vui tính, vì không muốn để cho các cặp đôi trông quá chênh lệch về chiều cao, ông đã đưa ra 1 yêu cầu: Người thứ i và người thứ j (i ≠ j) có thể ghép cặp được với nhau nếu như thỏa mãn điều kiện sau: 90% * Hj ≤ Hi ≤ Hj. Nếu có cặp người thứ i đã ghép với người thứ j thì đảo vị trí ghép của 2 người này, thì đây cũng chỉ tính là 1 cách ghép (ví dụ: nếu có cách ghép người thứ 2 với người thứ 3 thì cũng giống như ghép người thứ 3 với người thứ 2) 15 Với số lượng người tham dự nhỏ ông có thể dễ dàng tính ra được số cặp có thể ghép, nhưng bữa tiệc có rất nhiều người và việc tính toán của ông trở nên khó khăn hơn. Yêu cầu: Hãy giúp ông tính số cặp có thể ghép được. Dữ liệu: Vào từ file văn bản BAI7.INP gồm: - Dòng đầu tiên chứa số nguyên dương N là số người tham dự bữa tiệc. (N ≤ 105) - Dòng thứ 2 chứa N số nguyên dương Hi là độ cao của N người. (Hi ≤ 109) 16 Kết quả: Ghi ra file văn bản BAI7.OUT gồm một dòng duy nhất là kết quả của bài toán. Ví dụ : BAI7.INP BAI7.OUT 6 100 89 90 101 91 99 11 Thuật toán: + Sắpp xếp tăng dần theo chiều cao + Duyệt từ i từ 1 đến n-1 với mỗi vị trí i thì ta chặt nhị phân để tìm người có vị trí j xa nhất mà thỏa mãn 9*h[j] <= 10*h[i]. Nếu j > i thì ta được thêm số cặp là j-i. (thuật toan BAI7 phụ ục) 2.4. Hiệu quả của sang kiến kinh nghiệm Với cách làm như vậy đã rèn luyê ̣n kỹ năng lâ ̣p trình cho các học sinh tham gia học đội tuyển, các em cũng có thói quen tối ưu hóa thuâ ̣t toán và cài đă ̣t chương trình phù hợp, để ý đến về thời gian chạy chương trình hơn (không chỉ quan tâm đến đáp số như trước đây). Qua các lần thi khảo sát chất lượng học sinh giỏi về chuyên đề sắpp xếp, tìm kiếm năm học 2019 - 2020 chất lượng học sinh dần dần tiến bộ (nhận thấy thông qua điểm lần sau thường cao hơn lần trước, mặc dù mức độ đề khó tăng dần). Họ tên Phạm Minh Đức Nguyễn Lan Anh Điểm lần 1 5/10 6/10 Điểm lần 2 8/10 7/10 Điểm lần 3 10/10 8/10 Điểm lần , 9/10 8/10 Như vậy rõ ràng việc giúp học sinh lựa chọn và cài đặt thuâ ̣t toán tối ưu, hiệu quả đem lại là rất rõ rệt, tránh được việc học sinh mất điểm vì những lí do đáng tiếc trong kì thi học sinh giỏi THPT môn Tin học. 17 3. KẾT LUẬN VÀ KIẾN NGHI 3.1. Kết uận Kinh nghiệm trên sẽ là vốn tích lũy của bản thân tôi trong những năm ôn luyện đội tuyển tiếp theo. Đồng thời, có thể là tài liệu tham khảo cho những giáo viên trẻ còn thiếu kinh nghiệm trong bồi dưỡng học sinh giỏi. Do thời gian có hạn và kinh nghiê ̣m chưa nhiều nên đề tài không tránh khỏi những thiếu sót, kính mong sự đóng góp ý kiến của các đồng nghiê ̣p để đề tài được hoàn thiện hơn. 3.2. Kiến nghị Đối với tô chuyên môn, cần phân dạng bài tập cho học sinh khi giảng dạy. Ra nhiều dạng đề đúng với cấu trúc đề do Sở giáo dục Thanh Hóa quy định để đưa vào ngân hàng đề làm phong phú nguồn tài liệu bồi dưỡng học sinh giỏi của nhà trường. Mong Ban giám hiệu nhà trường luôn duy trì việc tô chức các kì thi khảo sát chất lượng học sinh giỏi môn Tin để học sinh có cơ hội thử sức với các kì thi. Trên đây chỉ là những kiến nghị mang tính chủ quan của tôi, nhưng cũng rất mong được các cấp có thẩm quyền xem xét và sự góp ý của các đồng nghiệp. XÁC NHẬN CỦA THỦ TRƯỞNG ĐƠN VỊ Thanh Hóa, ngày 10 tháng 05 năm 2020 Tôi xin cam đoan đây là SKKN của mình viết, không sao chép nội dung của người khác. Giáo viên Trịnh Anh Tài 18 19