Giúp học sinh cài đặt chương trình tối ưu khi giải một số bài tập có sử dụng thuật toán sắp xếp bằng ngôn ngữ lập trình pascal và c++ nhằm nâng cao chất lượng học sinh giỏi môn tin học ở trường THPT

SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁTRƯỜNG THPT ĐẶNG THAI MAI SÁNG KIẾN KINH NGHIỆM GIÚP HỌC SINH CÀI ĐẶT CHƯƠNG TRÌNH TỐI ƯU KHI GIẢI MỘT SỐ BÀI TẬP CÓ SỬ DỤNG THUẬT TOÁN SẮP XẾP BẰNG NGÔN

SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ

TRƯỜNG THPT ĐẶNG THAI MAI

SÁNG KIẾN KINH NGHIỆM

GIÚP HỌC SINH CÀI ĐẶT CHƯƠNG TRÌNH TỐI ƯU KHI GIẢI MỘT SỐ BÀI TẬP CÓ SỬ DỤNG THUẬT TOÁN SẮP XẾP BẰNG NGÔN NGỮ LẬP TRÌNH PASCAL VÀ C++ NHẰM NÂNG CAO CHẤT LƯỢNG HỌC SINH GIỎI

MÔN TIN HỌC Ở TRƯỜNG THPT

Người thực hiện: Hoàng Thị Mai Chức vụ: Giáo viên

SKKN thuộc lĩnh vực: Tin học

THANH HÓA NĂM 2020

MỤC LỤC

1 Mở đầu 1

1.1 Lý do chọn đề tài 1

1.2 Mục đích nghiên cứu 1

1.3 Đối tượng nghiên cứu 2

1.4 Phương pháp nghiên cứu 2

2 Nội dung sáng kiến kinh nghiệm 2

2.1 Cơ sở lí luận 2

2.2 Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm 3

2.2.1 Đặc điểm tình hình nhà trường 3

2.2.2 Thực trạng trước khi nghiên cứu 3

2.3 Giải pháp đã sử dụng để giải quyết vấn đề 4

2.3.1 Cơ sở lý thuyết 4

2.3.1.1 Bài toán sắp xếp 4

2.3.1.2 Thuật toán sắp xếp lựa chọn 4

2.3.1.3 Thuật toán sắp xếp nhanh 5

2.3.1.4 Thuật toán sắp xếp bằng phương pháp đếm phân phối 6

2.3.2 Biện pháp cài đặt chương trình tối ưu khi giải một số bài tập có sử dụng thuật toán sắp xếp 6

2.3.2.1 Bài tập ví dụ có sử dụng thuật toán sắp xếp 7

2.3.2.2 Bài tập áp dụng 11

2.3.2.2.1 Một số bài tập sử dụng thuật toán sắp xếp nhanh 11

2.3.2.2.2 Một số bài tập sử dụng thuật toán đếm phân phối 16

2.4 Hiệu quả sáng kiến kinh nghiệm 19

3 Kết luận và kiến nghị 19

3.1 Kết luận 19

3.1 Kiến nghị 20

1 Mở đầu

1.1 Lý do chọn đề tài

Trong quá trình giảng dạy cũng như bồi dưỡng học sinh giỏi, tôi gặp rấtnhiều các bài tập có sử dụng thuật toán sắp xếp Có thể thấy sắp xếp đóng vai tròrất quan trọng trong cuộc sống nói chung và tin học nói riêng Theo D.Knuth thì40% thời gian tính toán của máy tính là dành cho việc sắp xếp Do đặc điểm dữliệu như số thực hay số nguyên, kí tự hay xâu, kích thước nhỏ hay lớn, lưu trữ ở

bộ nhớ trong hay bộ nhớ ngoài, mà người ta có nhiều thuật toán sắp xếp khácnhau Trong số đó, sắp xếp lựa chọn, sắp xếp nhanh, sắp xếp bằng phương phápđếm phân phối là những thuật toán hay, dễ cài đặt, được ứng dụng nhiều khi giảicác bài toán Tin học Mỗi thuật toán sắp xếp có những ưu điểm và nhược điểmriêng Khi học sinh gặp dạng bài tập này, mặc dù việc đoán nhận lớp giải thuậtsắp xếp không phải quá khó nhưng học sinh lại nóng vội bắt tay ngay vào việcviết chương trình hoặc chủ quan không để ý đến đặc điểm, giới hạn dữ liệu đềbài ra, dẫn đến việc sử dụng một số giải thuật sắp xếp không phù hợp và chưatối ưu đối với yêu cầu dữ liệu vào của đề ra Do vậy, trong các kì thi học sinhgiỏi các em có thể đạt một số điểm nhất định, nhưng kết quả không cao, khôngtương xứng với khả năng và công sức bỏ ra

Với mong muốn giúp học sinh giải quyết tốt hơn các bài tập có sử dụngthuật toán sắp xếp và hiểu biết sâu sắc hơn cách giải bài tập dạng này Tôi đãnghiên cứu tìm ra các ưu điểm và nhược điểm nổi bật của 3 thuật toán sắp xếp,đánh giá độ phức tạp, đo thời gian thực hiện chương trình để so sánh và đưa racách giải phù hợp, có hiệu quả nhất của từng thuật toán sắp xếp đối với từngkiểu dữ liệu khác nhau Qua đó, phát triển tư duy lập trình cho học sinh và dầnnâng cao chất lượng học sinh giỏi môn Tin học

Hơn nữa, ngày nay các ứng dụng công nghệ thông tin ngày càng pháttriển Các ngôn ngữ lập trình phát triển rất nhanh đáp ứng nhu cầu dạy và họchiện đại Hiện tại, ngôn ngữ lập trình pascal đang được sử dụng trong dạy họclập trình ở lớp 11 đã trở nên lạc hậu, tính ứng dụng thực tế không cao cùng với

tâm lí xem môn Tin là môn học phụ nên không thu hút được sự yêu thích tìm tòi khám phá của học sinh, dẫn đến việc học trở nên đối phó Do vậy, việc lựa chọn

một ngôn ngữ lập trình phù hợp, đáp ứng được nhu cầu phát triển ngày càng caocủa nền giáo dục hiện đại là rất cần thiết Nên tôi đã trăn trở nghiên cứu tìm hiểuthêm ngôn ngữ lập trình C++ (đây là ngôn ngữ thú vị, dễ học, tương đồng vớiPascal, chương trình thực hiện nhanh) để chuyển thể một số bài tập có sử dụngthuật toán sắp xếp từ ngôn ngữ lập trình pascal sang ngôn ngữ C++ Đồng thờikiểm tra và so sánh thời gian thực hiện chương trình giữa hai ngôn ngữ

Từ những lý do trên tôi đã mạnh dạn trình bày sáng kiến kinh nghiệm:

“Giúp học sinh cài đặt chương trình tối ưu khi giải một số bài tập có sử dụng thuật toán sắp xếp bằng ngôn ngữ lập trình Pascal và C++ nhằm nâng cao chất lượng học sinh giỏi môn Tin học ở trường THPT”.

1.2 Mục đích nghiên cứu

Đề 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 tập có sử

dụng thuật toán sắp xếp, để khi đứng trước một bài toán cần giải quyết ngoàiviệc tìm ra giải thuật để 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ứctạp của thuật toán) và lựa chọn được thuật toán phù hợp Đồng thời giúp họcsinh lựa chọn ngôn ngữ lập trình phù hợp với năng lực bản thân, xu thế thời đạinhằm nâng cao chất lượng học sinh giỏi Từ đó giúp học sinh dần làm quen vớingôn ngữ lập trình mới C++.

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 thuật toán sắp xếpgồm: sắp xếp lựa chọn, sắp xếp nhanh, sắp xếp bằng phương pháp đếm phânphối Các bài toán có sử dụng thuật toán sắp xếp, được nghiên cứu và so sánh ởnhiều cách làm mỗi cách tương ứng dùng một giải thuật sắp, xét trên cácphương diện như: độ phức tạp, kết quả output, thời gian thực hiện chương trình.Cách làm tối ưu nhất được cài đặt chương trình bằng ngôn ngữ lập trình Pascal

và C++

1.4 Phương pháp 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ợpnhiề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ônhọc thuộc lĩnh vực Tin học

2 Nội dung sáng kiến kinh nghiệm

2.1 Cơ sở lý luận

Nghị quyết hội nghị Trung ương VIII khóa XI đề ra mục tiêu: “Đối vớigiáo dục phổ thông tập trung phát triển trí tuệ, thể chất, hình thành phẩm chất,năng lực công dân, phát hiện và bồi dưỡng năng khiếu, định hướng nghề nghiệpcho học sinh Nâng cao chất lượng giáo dục toàn diện, chú trọng giáo dục lýtưởng truyền thống đạo đức, lối sống, ngoại ngữ, tin học, năng lực và kỹ năngthực hành, vận dụng kiến thức vào thực tiễn, phát triển khả năng sáng tạo và tựhọc, khuyến khích học tập suốt đời".[1]

Yêu cầu cấp bách hiện nay của toàn ngành giáo dục, là xây dựng phươngpháp dạy học hiện đại, đáp ứng được yêu cầu phát triển ngày càng cao của nềngiáo dục hiện đại Toàn ngành đang ra sức phấn đấu xây dựng chương trình sáchgiáo khoa mới, đổi mới phương pháp dạy học theo định hướng hình thành vàphát triển năng lực

Mục tiêu của môn Tin học trong chương trình giáo dục phổ thông là giúphọc sinh hình thành và phát triển năng lực Tin học

Đối với môn Tin họ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, đổi mới phương pháp dạy học nhằm góp phần thực hiện tốtmục tiêu của ngành giáo dục trong giai đoạn mới

Nếu học sinh có thói quen và kỹ năng tốt khi thiết kế và cài đặt chươngtrình tối ưu để giải lớp bài tập sắp xếp nói riêng và các bài tập lập trình nóichung thì chất lượng học sinh giỏi sẽ rất khả quan và đạt kết quả cao trong các

kì thi HSG

2.2 Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm

2.2.1 Đặc điểm tình hình nhà trường

Trường THPT Đặng Thai Mai được thành lập ngày: 20/08/2001, theoquyết định số: 2109/QĐ-UB của Chủ tịch UBND Tỉnh Thanh Hoá Trường nằmngay trên đường quốc lộ 1A, thuộc km 12 từ thành phố Thanh Hóa xuống phíaNam, thuộc địa bàn xã Quảng Bình, huyện Quảng Xương, tỉnh Thanh Hóa, nơi

đa số phụ huynh học sinh làm nông nghiệp và khai thác, đánh bắt hải sản Điềukiện kinh tế còn gặp nhiều khó khăn Các em học sinh ít có điều kiện tiếp xúcvới máy tính ở nhà Chất lượng đầu vào của học sinh thấp, chủ yếu là học sinhtrung bình, yếu

Năm học 2017 - 2018 trường có 27 lớp và 1 phòng học thực hành Tin học

có mạng Internet, có lắp đặt máy chiếu Hiện nay, năm học 2019 - 2020 nhàtrường đã tăng lên 31 lớp, nhưng vẫn chỉ có một phòng thực hành Tin học đượclắp đặt máy chiếu, không kết nối Internet Cơ sở vật chất chưa đảm bảo cho việchọc bộ môn Tin học của nhà trường

Môn Tin học là môn học đặc thù có nhiều kiến thức khó Đặc biệt là lậptrình pascal ở lớp 11 (đây là kiến thức thi học sinh giỏi tỉnh môn Tin học) đượcđánh giá là khó và lạc hậu Hơn nữa, môn học được học sinh, phụ huynh, nhàtrường mặc định là môn phụ, phụ huynh không khuyến khích ủng hộ con yêuthích đam mê môn học, thậm chí nhiều phụ huynh còn cấm con tham gia độituyển học sinh giỏi môn Tin học, tạo áp lực cho giáo viên và nhà trường để conđược ra khỏi đội tuyển tập trung vào học các môn ôn thi đại học nên việc lựachọn và bồi dưỡng học sinh giỏi là vô cùng khó khăn Thực trạng trên dẫn tớitâm lý học sinh chán học nên chất lượng học sinh giỏi không cao

2.2.2 Thực trạng trước khi nghiên cứu

Năm 2014 – 2015 tôi được phân công là giáo viên chính bồi dưỡng họcsinh giỏi tỉnh môn Tin học Rút kinh nghiệm từ các năm trước đây khi bồidưỡng học sinh giỏi, tôi đã chú trọng nhiều hơn đến cải tiến chương trình tối ưutuy nhiên hiệu quả mang lại chưa cao

Đối với lớp bài tập có sử dụng giải thuật sắp xếp, đây là dạng bài tập

không quá khó, là phần học sinh có thể ghi điểm Tuy nhiên, phần vì giáo viên

chưa có phương pháp giảng dạy phù hợp đối với lớp bài tập này, phần vì họcsinh chủ quan không chú ý đến đặc điểm dữ liệu, giới hạn dữ liệu, không nắmđược đặc trưng nổi bật của từng thuật toán sắp xếp nên khi học sinh gặp dạngbài tập này thường chỉ dừng lại ở bước đoán nhận có sử dụng thuật toán sắp xếprồi nóng vội viết chương trình ngay Vì vậy, chương trình thường không hiệuquả dẫn tới kết quả thi học sinh giỏi không cao, không tương xứng với năng lực

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 đề dãycon (do tôi tự tổ chức) năm học 2014 – 2015 khi chưa thực hiện đề tài:

Do đó kết quả học sinh giỏi năm 2014 - 2015 có đạt một số kết quả nhấtđịnh, nhưng không cao (1 giải ba, 1 giải khuyến khích).

Bởi vậy, để học sinh đạt được kết quả cao trong kỳ thi học sinh giỏi Tỉnhcần phải rèn luyện cho các em tuân thủ tốt các bước thiết kế và cài đặt chươngtrình tối ưu, điều này không dễ chút nào, đòi hỏi giáo viên phải kiên nhẫn, duytrì uốn nắn ngay từ khi các em bắt đầu với những bài toán đơn giản và trong suốtquá trình học cho đến khi các em đi thi

Trong phạm vi sáng kiến kinh nghiệm của mình, tôi chỉ tập trung nghiêncứu 3 thuật toán: sắp xếp lựa chọn, sắp xếp nhanh và sắp xếp bằng phương phápđếm phân phối Mặt khác, tôi nghiên cứu và cài đặt song song hai ngôn ngữ lậptrình là Pascal và C++ để giúp học sinh tiếp cận với ngôn ngữ lập trình mới.Đồng thời, tôi có sử dụng phần mềm Themis để đo và so sánh thời gian thựchiện chương trình giữa hai ngôn ngữ nhằm giúp học sinh thấy được việc lựachọn ngôn ngữ lập trình phù hợp cũng là yếu tố khá quan trọng trong lập trình

2.3 Giải pháp đã sử dụng để giải quyết vấn đề

2.3.1 Cơ sở lý thuyết

2.3.1.1 Bài toán sắp xếp

Để không mất tính tổng quát, ta sẽ trình bày các thuật toán sắp xếp cho bài

toán sau: Cho dãy gồm n số nguyên a 1 , a 2, , a n Hãy sắp xếp thành dãy tăng không ngặt (dãy không giảm).

Tùy thuộc vào đặc điểm dữ liệu để ta lựa chọn thuật toán sắp xếp hợp lý

2.3.1.2 Thuật toán sắp xếp lựa chọn

Ý tưởng:

- So sánh cặp số a1 với a2, nếu số sau nhỏ hơn số trước thì đổi chỗ hai số

đó cho nhau Làm tương tự với các cặp số a1 với a3, , a1 với an Khi đó phần tửnhỏ nhất sẽ đưa lên đầu dãy (tức a1)

- Thực hiện lặp lại với các cặp số: a2 với a3; a2 với a4; ; a2 với an; ; an-1với an

if (a[i] > a[j]) {

tg = a[i];

a[i] = a[j];

a[j] = tg;

}

Độ phức tạp thuật toán là: O(n 2 )

Đánh giá ưu điểm, nhược điểm:

Ưu điểm:

- Code đơn giản, dễ hiểu

- Sắp xếp được với giá trị phần tử là kiểu số nguyên, kiểu số thực, kiểu kí

tự, kiểu xâu.

- Sắp xếp được với phần tử có miền giá trị lớn |ai| ≤ 1018 (nếu ai là kiểuxâu, sắp xếp được xâu có độ dài rất lớn chỉ phụ thuộc vào dung lượng bộ nhớtrong)

Nhược điểm:

- Độ phức tạp của thuật toán lớn O(n2)

- Chạy không đủ nhanh (quá 1 giây) với dữ liệu lớn, chỉ áp dụng với sốphần tử n < 104

2.3.1.3 Thuật toán sắp xếp nhanh

Ý 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áisang 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ìmphầ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ắp xếp Làmtương tự như vậy với mỗi nhóm cho đến khi đã sắp xếp hết dãy

while a[i]<x do inc(i);

while x<a[j] do dec(j);

x = a[(l + r) / 2];

i = l;

j = r;

do {

while (a[i] < x) i++;

while (a[j] > x) j ;

if (i <= j) {

tg = a[i];

a[i] = a[j]; a[j] = tg;

i++;

j ;

} }

while (i <= j)

if (l < j) qsort(a, l, j);

if (i < r) qsort(a, i, r); }

Độ phức tạp trung bình của thuật toán là: O(nlogn)

Đánh giá ưu điểm, nhược điểm:

Ưu điểm:

- Thời gian thực hiện nhanh Áp dụng với số phần tử n ≤ 10 6

- Sắp xếp được với các phần tử là kiểu số nguyên, kiểu số thực, kiểu kí tự,kiểu xâu

- Sắp xếp được các phần tử với miền giá trị lớn |a i | ≤ 10 18 (nếu ai là kiểu

xâu, sắp xếp được các xâu có độ dài rất lớn chỉ phụ thuộc vào dung lượng bộnhớ trong).

Nhược điểm:

- Chạy chậm (quá 1 giây) với số phần tử n > 10 6

.

- Không ổn định, tùy thuộc vào cách chia thành 2 phần, nếu chia không tốt

độ phức tạp trong trường hợp xấu nhất có thể là O(n2) (trường hợp này hiếm khixảy ra)

2.3.1.4 Thuật toán sắp xếp bằng phương pháp đếm phân phối

Ý tưởng:

- Khởi tạo giá trị ban đầu cho mảng dem

- Dùng mảng dem để đếm số lần xuất hiện của số a[i] trong dãy

- Duyệt i từ giá trị nhỏ nhất (gtmin) của các a[i] đến giá trị lớn nhất(gtmax) của các a]i] Duyệt j từ 1 đến dem[i] rồi in ra i

Mô phỏng thuật toán bằng Pascal và C++:

{in day so}

for i:= gtmin to gtmax do

Độ phức tạp của thuật toán là: O(max(n,gtmax)).

Đánh giá ưu điểm, nhược điểm:

Ưu điểm:

- Code đơn giản

- Độ phức tạp phụ thuộc miền giá trị

- Áp dụng được với dãy có số phần tử lớn n ≤ 108

Nhược điểm:

- Chỉ sắp xếp được các phần tử số nguyên hoặc kí tự

- Phải biết miền giá trị của số nguyên

- Miền giá trị > 107 sẽ không thể tạo được mảng dem để lưu trữ (nghĩa làchỉ áp dụng được với miền giá trị |ai| ≤ 107)

2.3.2 Biện pháp cài đặt chương trình tối ưu khi giải một số bài tập có sử dụng thuật toán sắp xếp

Khi phát vấn một bài tập mới mà tôi yêu cầu học sinh làm theo các trình

tự sau:

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

Bước 2: Xác định đặc điểm dữ liệu (như số phần tử n, kiểu phần tử là số thực hay số nguyên, kí tự hay xâu, ).

Bước 3: Lập bảng so sánh giữa các thuật toán (gồm đánh giá độ phức tạp, thời gian thực hiện).

Bước 4: Nhận xét và lựa chọn thuật toán hiệu quả nhất.

Bước 5: Cài đặt thuật toán đã lựa chọn bằng ngôn ngữ Pascal và C++.

Bước 6: Sử dụng Themis-chấm bài tự động để chấm code (với 10 bộ test

gửi kèm đĩa CD) bằng ngôn ngữ lập trình Pascal và C++ Từ đó nhận thấy tính

hiệu quả giữa hai ngôn ngữ

Bước 7: Lập trình giải các bài tập có sử dụng thuật toán sắp xếp với thuật

toán hiệu quả nhất bằng ngôn ngữ lập trình Pascal và C++

2.3.2.1 Bài tập ví dụ có sử dụng thuật toán sắp xếp

Bài tập: Cho một dãy số nguyên a 1 , a 2, , a n Hãy đếm số lượng giá trị khácnhau trong dãy và đưa ra số lần lặp của giá trị xuất hiện nhiều nhất

Dữ liệu vào: File BAI1.INP gồm 2 dòng:

+ Dòng đầu số nguyên dương N.

+ Dòng thứ hai gồm dãy số nguyên a 1 , a 2, , a n

Dữ liệu ra: File BAI1.OUT gồm 2 dòng:

+ Dòng đầu tiên ghi số lượng giá trị khác nhau trong dãy

+ Dòng thứ 2 ghi số lần lặp của giá trị xuất hiện nhiều nhất

Trường hợp 1: Giả sử số phần tử của dãy n <= 10 6 và giá trị các phần tử là

để lưu trữ

Thời gian Quá 1giây Đạt yêu cầu Không thực hiện được

Từ bảng trên, ta thấy để giải quyết tối ưu bài toán trên với giới hạn dữ liệu ai

nguyên, |a i | ≤ 10 9 , n ≤ 10 6 , tôi định hướng học sinh chọn thuật toán sắp xếp

nhanh Cách này học sinh có thể lấy được 100% số điểm.

Ý tưởng:

B1: Sắp xếp dãy số tăng dần (các số bằng nhau đứng liên tiếp nhau) B2: Khởi tạo d:=1 (số phần tử khác nhau), dd:=1 (số phần tử liên tiếp bằng nhau) và dmax:=1 (số lần lặp của giá trị xuất hiện nhiều nhất) Duyệt i từ

phần tử thứ 2 đến n, nếu 2 số đứng cạnh nhau mà bằng nhau thì tăng dd, ngược lại khác nhau thì tăng d, đồng thời tìm dmax.

while a[i]<x do inc(i);

while x<a[j] do dec(j);

x = a[(l + r) / 2];

i = l; j = r;

do { while (a[i] < x) i++; while (a[j] > x) j ;

if (i <= j)

{

tg = a[i];a[i] = a[j]; a[j] = tg; i++; j ; }

} while (i <= j);

if (l < j) qsort(a, l, j);

if (i < r) qsort(a, i, r); }

int main() { ifstream fi("BAI1.INP"); ofstream fo("BAI1.OUT");

fi >> n;

//cap phat mang dong long* a = new long[n+1]; for (i = 1; i <= n; i++)

fi >> a[i];

qsort(a,1, n);

d = 1; dd = 1; dmax = 1; for (i = 2; i <= n; i++) {

if (a[i]==a[i-1]) dd++; else

{

if (dd>dmax) dmax = dd;

d++; dd = 1;

} }

fo << d << endl << dmax; //tra lai vung nho dong delete[] a;

fi.close();

fo.close();

return 0;

}

Chú ý: Cách này áp dụng được cả trong trường hợp phần tử của dãy là

kiểu số thực hoặc kiểu kí tự hoặc kiểu xâu Nếu n <= 10 3 thì ta thay thủ tục sắpxếp nhanh bằng thủ tục sắp xếp chọn vẫn lấy được 100% số điểm

Sử dụng phần mềm Themis Ta đo thời gian thực hiện chương trình giữa 2 ngôn ngữ Pascal và C++ ở mỗi test cụ thể như sau: (file code và test kèm CD)

Độ phức

tạp

Test0 1 (giây)

Test0 2 (giây)

Test0 3 (giây)

Test0 4 (giây)

Test0 5 (giây)

Test0 6 (giây)

Test0 7 (giây)

Test0 8 (giây)

Test0 9 (giây)

Test1 0 (giây)

Pascal 0(nlogn) 0.018 0.019 0.018 0.044 0.021 0.019 0.019 0.329 0.332 0.409

Từ bảng trên, ta dễ dàng nhận thấy cùng một thuật toán nhưng sử dụngngôn ngữ lập trình C++ để cài đặt thì thời gian thực hiện nhanh hơn khi cài đặtbằng ngôn ngữ lập trình Pascal

Trường hợp 2: Giả sử số phần tử của dãy n <= 10 7 và giá trị các phần tử là

nguyên |a i | <= 10 6

Bảng so sánh (số phần tử n <= 10 7 và giá trị phần tử nguyên |a i | <= 10 6 )

So sánh (Selection sort) Sắp xếp chọn Sắp xếp nhanh (Quicksort) Sắp xếp đếm phân phối (Counting sort)

Độ phức

tạp O(1014) O(107log107) O(107)

Thời gian Quá 1giây Quá 1 giây Đạt yêu cầu

Từ bảng trên, ta thấy để giải quyết tối ưu bài toán trên với giới hạn dữ liệu ai

nguyên, |a i | <= 10 6 , n <= 10 7 , tôi định hướng học sinh chọn thuật toán đếm

phân phối Cách này học sinh có thể lấy được 100% số điểm.

Ý tưởng:

B1: Khởi tạo: dem[i]:=0; nmax:=10 7 ; d:=0; dmax:=0; (mảng dem với dem[i] là số lần xuất hiện số nguyên i, i=-nmax nmax)

B2: Đọc các phần tử a[i] của dãy A và thực hiện đếm phân phối các giá

trị a[i] trong dãy A: dem[a[i]]:=dem[a[i]]+1, đồng thời tìm giá trị lớn nhất max

của dãy A