Sáng kiến kinh nghiệm THPT: Phân tích, vận dụng các thuật toán sắp xếp để giải quyết một số bài toán viết bằng NNLT C++

Chia sẻ: Hương Hoa Cỏ Mới | Ngày: | Loại File: PDF | Số trang:39

Thêm vào BST

Báo xấu

27
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích chính của sáng kiến là nghiên cứu, phân tích và vận dụng các thuật toán sắp xếp dành cho đối tượng HSG khối THPT. Việc lĩnh hội được sáng kiến sẽ giúp học sinh: Mô tả đúng khái niệm, bản chất và mục đích của việc sắp xếp. Trình bày và thực hiện cài đặt một cách chính xác các thuật toán sắp xếp. Đánh giá đúng về các thuật toán sắp xếp và tìm ra thuật toán sắp xếp phù hợp cho từng bài toán. Giúp các em học giỏi môn Tin Học đạt kết quả cao. Tạo ra nguồn tài liệu tham khảo về thuật toán hỗ trợ cho học sinh, giáo viên dạy Tin học bậc THPT. Sử dụng NNLT C++ trong chương trình giáo dục phổ thông mới.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sáng kiến kinh nghiệm THPT: Phân tích, vận dụng các thuật toán sắp xếp để giải quyết một số bài toán viết bằng NNLT C++

SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN SÁNG KIẾN KINH NGHIỆM ĐỀ TÀI PHÂN TÍCH, VẬN DỤNG CÁC THUẬT TOÁN SẮP XẾP ĐỂ GIẢI QUYẾT MỘT SỐ BÀI TOÁN VIẾT BẰNG NNLT C++ SKKN thuộc lĩnh vực: Tin học Nghệ An năm 2021
1. MỞ ĐẦU 1.1. Lý do chọn đề tài Chúng ta biết rằng để có kết quả cao trong kì thi tuyển chọn học sinh giỏi môn tin học nói chung thì phải có vốn kiến thức về thuật toán để giải được các bài toán khó, hoặc những bài toán dữ liệu vào lớn, sau đó học sinh lựa chọn NNLT để lập trình dựa vào thuật toán đã tìm được và giải bài toán theo yêu cầu. Trong quá trình dạy bồi dưỡng học sinh giỏi tôi gặp rất nhiều bài toán có sử dụng giải thuật sắp xếp. Đây là dạng bài tập không khó nhưng học sinh thường hay chủ quan nên không chạy được hết các test lớn. Nguyên nhân cơ bản là học sinh không áp dụng phương pháp phù hợp cho bài toán đó. Với mong muốn giúp học sinh giải quyết tốt hơn các bài tập sắp xếp dãy số, tôi đã dày công nghiên cứu các thuật toán sắp xếp và phân tích để áp dụng vào từng dạng toán phù hợp. Mặt khác, theo chương trình mới của Bộ Giáo Dục khuyến khích giáo viên dạy NNLT mới thay Pascal nên tôi viết chương trình bằng NNLT C++ để làm tài liệu tham khảo mới cho giáo viên và học sinh. Từ những lý do trên tôi đã mạnh dạn trình bày sáng kiến kinh nghiệm: “Phân tích, vận dụng các thuật toán sắp xếp để giải quyết một số bài toán viết bằng NNLT C++”. 1.2. Mục đích nghiên cứu Mục đích chính của sáng kiến là nghiên cứu, phân tích và vận dụng các thuật toán sắp xếp dành cho đối tượng HSG khối THPT. Việc lĩnh hội được sáng kiến sẽ giúp học sinh: - Mô tả đúng khái niệm, bản chất và mục đích của việc sắp xếp - Trình bày và thực hiện cài đặt một cách chính xác các thuật toán sắp xếp. - Đánh giá đúng về các thuật toán sắp xếp và tìm ra thuật toán sắp xếp phù hợp cho từng bài toán. - Giúp các em học giỏi môn Tin Học đạt kết quả cao - Tạo ra nguồn tài liệu tham khảo về thuật toán hỗ trợ cho học sinh, giáo viên dạy Tin học bậc THPT - Sử dụng NNLT C++ trong chương trình giáo dục phổ thông mới. 2
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ếp và viết một số chương trình có sử dụng các thuật toán sắp xếp bằng NNLT C++. 1.4. Phương pháp nghiên cứu Để trình bày sáng kiến kinh nghiệm này, chúng 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, vận dụng… phù hợp với môn học thuộc lĩnh vực Tin học. 3
2. NỘI DUNG NGHIÊN CỨU 2.1. Cơ sở lý luận 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 toán sắp xếp 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. Học sinh dần được làm quen với NNLT C++. 2.2. Thực trạng 2.2.1 Thực trạng trước khi nghiên cứu Đố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ắng 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). Lý do khi vận dụng các thuật toán thì thường học sinh chỉ chọn những thuật toán quen thuộc mà ít khi phân tích bài toán để tìm ra thuật toán phù hợp hơn. 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ắn,... 2.3. Các biện pháp sử dụng để giải quyết vấn đề 2.3.1. Giới thiệu về bài toán sắp xếp 2.3.1.1. Khái niệm Sắp xếp là quá trình xử lý một danh sách các phần tử (hoặc các mẫu tin) để đặt chúng theo một thứ tự, thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thông tin lưu trữ tại mỗi phần tử. Ví dụ: cho trước một dãy số a1, a2,..., an được lưu trữ trong cấu trúc dữ liệu mảng. Sắp xếp dãy số a1, a2,..., an là thực hiện việc bố trí lại các phần tử sao cho được dãy mới có thứ tự tăng dần (hoặc giảm dần). Hai thao tác so sánh và gán là các thao tác cơ bản của hầu hết các thuật toán sắp xếp. Bài toán sắp xếp xuất hiện trong bất kỳ lĩnh vực nào của tin học. Khi xây dựng một bài toán sắp xếp, cần tìm cách giảm thiểu những phép so sánh và đổi chỗ không cần thiết để tăng hiệu quả của thuật toán. Trong đề tài này tôi giới thiệu một số giải thuật sắp xếp từ đơn giản đến phức tạp có thể áp dụng thích hợp cho việc sắp xếp. 4
2.3.1.2. Mục đích của sắp xếp Mục đích của việc sắp xếp chính là giúp chúng ta có cái nhìn tổng quan hơn về những dữ liệu mà ta có, dễ dàng tìm kiếm những phần tử đứng thứ nhất về một tiêu chí nào đó.... 2.3.2. Một thuật toán sắp xếp cơ bản 2.3.1.1. Sắp xếp nổi bọt (Bubble Sort) 2.3.1.1.1. Ý tưởng của thuật toán Sắp xếp nổi bọt là thuật toán đơn giản nhất, ý tưởng thuật toán này như sau: Duyệt qua danh sách, làm cho các phần tử lớn nhất hoặc nhỏ nhất về cuối danh sách, tiếp tục làm phần tử lớn hơn hoặc nhỏ hơn cận kề đó dịch chuyển về cuối... cứ như thế cho đến hết danh sách. 2.3.1.1.2. Nội dung và cài đặt chương trình Các bước thực hiện giải thuật: 1. Gán i 0 2. Gán j 0 3. Nếu A[j] > A[j+1] thì đổi chỗ A[j] và A[j+1] 4. Nếu j < n-j-1: 4.1: Đúng thì j=j+1 và quay lại bước 3 4.2: Sai thì sang bước 5 5. Nếu i < n-1: 5.1: Đúng thì i=i+1 và quay lại Bước 2 5.2: Sai thì dừng lại Cài đặt trong C++: #include #include #include using namespace std; int a[100001]; int n,tg; int main() { clock_t begin=clock(); 5
ifstream fi("bubble.inp"); ofstream fo("bubble.out"); fi>>n; for (int i=0;i>a[i]; for (int i=0;i
nhỏ nhất đó với phần tử đang duyệt và cứ tiếp tục như vậy. 2.3.1.2.2. Nội dung và cài đặt chương trình Các bước thực hiện giải thuật: B1: i 0 B2: j i+1; min A[i] B3: Nếu j < n B3.1: Nếu A[j] < A[min] thì min j B3.2: j j+1 B3.3: Quay lại B3 B4: Đổi chỗ A[min] và A[i] cho nhau B5: Nếu i < n-1 thì i i+1 và quay lại B2 B6: Dừng lại. Cài đặt trong C++ #include #include #include using namespace std; int a[100001]; int n,tg,mi; int main() { clock_t begin=clock(); ifstream fi("select.inp"); ofstream fo("select.out"); //doc mang fi>>n; for (int i=0;i>a[i]; //sap xep for (int i=0;i
mi=i; for (int j=i+1;j
phải 1 vị trí và chèn phần tử i+1 vào vị trí đó. 2.3.1.3.2. Nội dung và cài đặt chương trình Các bước thực hiện của thuật toán: B1: i 1 B2: x A[i]; pos i-1 B3: Nếu Pos >= 0 và A[pos] > x: B3.1:A[Pos+1] A[Pos] B3.2: Pos Pos-1; B3.3: Quay lại B3 B4: A[Pos+1] x B5: Nếu i < n thì i i+1 và quay lại B2 B6: Dừng lại. Cài đặt thuật toán trong C++: #include #include #include using namespace std; int a[100001]; int n,tg,pos,x; int main() { clock_t begin=clock(); ifstream fi("insert.inp"); ofstream fo("insert.out"); //doc mang fi>>n; for (int i=0;i>a[i]; //sap xep for (int i=1;i
{ x=a[i]; pos=i-1; while (pos>=0 && a[pos]>x) { a[pos+1]=a[pos]; pos--; } a[pos+1]=x; } //in ket qua for (int i=0;i
Giải thuật này sử dụng giải thuật sắp xếp chọn trên các phần tử có khoảng cách xa nhau, sau đó sắp xếp các phần tử có khoảng cách hẹp hơn. 2.3.1.4.2. Nội dung và cài đặt chương trình Cài đặt C++: #include #include #include using namespace std; int a[100001]; int n; void shellsort(int a[],int n) { int k; for (int i=n/2;i>0;i=i/2) { for (int j=i;j=0;k=k-i) { if (a[k+i]>=a[k]) break; else { swap(a[k],a[k+1]); } } } } } int main() { 11
clock_t begin=clock(); ifstream fi("shell.inp"); ofstream fo("shell.out"); fi>>n; for (int i=0;i>a[i]; shellsort(a,n); for (int i=0;i
thi của thuật toán. Phần tử được chọn làm chốt tối ưu nhất là phần tử trung vị, phần tử này làm cho số phần tử nhỏ hơn trong dãy bằng hoặc xấp xỉ số phần tử lớn hơn trong dãy. Tuy nhiên, việc tìm kiếm này rất tốn kém, phải có thuật toán tìm kiếm riêng, từ đó làm giảm hiệu suất của thuật toán tìm kiếm nhanh, do đó, để đơn giản, người ta sử dụng phần tử chính giữa làm chốt. Cài đặt C++: #include #include #include using namespace std; int a[100001]; int n; void swap(int &a,int &b) { int tg=a; a=b; b=tg; } void QuickSort(int a[],int left, int right) { int i=left, j=right; int pivot=a[(left+right)/2]; while (i
j--; } } if (leftn; for (int i=0;i>a[i]; QuickSort(a,0,n-1); for (int i=0;i
mới sắp xếp xong. Lúc đó độ phức tạp của Quick Sort là O(n2). Vì vậy thời gian thực hiện giải thuật Quick Sort trung bình là O(nlogn). 2.3.1.6. Sắp xếp bằng phép đếm phân phối (Counting Sort) 2.3.1.6.1. Ý tưởng của thuật toán Counting sort là một thuật toán sắp xếp cực nhanh một mảng các phần tử mà mỗi phần tử là các số nguyên không âm; hoặc là một danh sách các ký tự được ánh xạ về dạng số để sort theo bảng chữ cái. Counting sort là một thuật toán sắp xếp các con số nguyên không âm, không dựa vào so sánh. 2.3.1.6.2. Nội dung và cài đặt chương trình Cài đặt C++: #include #include using namespace std; int a[100001]; int n; void counting_sort(int a[],int n) { int output[n]; int max=a[0]; int min=a[0]; for (int i=1;imax) max=a[i]; else if(a[i]
for (int i=1;ia[i]; counting_sort(a,n); //in ket qua for (int i=0;i
+ Mảng 1 các phần tử đã được sắp xếp + Mảng 2 các phần tử chưa được sắp xếp Trong mảng chưa được sắp xếp, các phần tử lớn nhất sẽ được tách ra và đưa vào mảng đã được sắp xếp. Điều cải tiến ở Heap Sort so với Selection Sort ở việc sử dụng cấu trúc dữ liệu heap thay vì tìm kiếm tuyến tính để tìm ra phần tử lớn nhất. 2.3.1.7.2. Nội dung và cài đặt chương trình Cài đặt trong C++: #include #include #include using namespace std; int a[100001]; int n; void swap(int &a, int &b) { int tg=a; a=b; b=tg; } void ImplHeap(int a[], int n, int i) { int root=i; int l=2*i+1; int r=2*i+2; if (la[root]) root=l; if (ra[root]) root=r; if (root!=i) { swap(a[i],a[root]); 17
ImplHeap(a,n,root); } } void ImplHeapSort(int a[],int n) { for(int i=(n/2)-1;i>=0;i--) ImplHeap(a,n,i); for (int i=n-1;i>=0;i--) { swap(a[0],a[i]); ImplHeap(a,i,0); } } int main() { clock_t begin=clock(); ifstream fi("Heap.inp"); ofstream fo("Heap.out"); //doc mang fi>>n; for (int i=0;i>a[i]; //sap xep int n=sizeof(a)/sizeof(a[0]); ImplHeapSort(a,n); //in ket qua for (int i=0;i
fo
int n2=right-mid; int* L=new int[n1]; int* R=new int[n2]; for (int ii=0;ii