intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Sáng kiến kinh nghiệm: Hướng dẫn học sinh giải bài toán sắp xếp - Tin học 8

Chia sẻ: Nguyễn Thị Lan | Ngày: | Loại File: DOC | Số trang:32

Thêm vào BST
Báo xấu
219
lượt xem 40
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Khi xây dựng một hệ thống quản lý thông tin trên máy tính, bên cạnh các thuật toán tìm kiếm, các thuật toán sắp xếp dữ liệu cũng là một trong các chủ đề được quan tâm hàng đầu. Vậy là thế nào để hướng dẫn học sinh giải bài toán sắp xếp, mời các bạn cùng tham khảo sáng kiến kinh nghiệm "Hướng dẫn học sinh giải bài toán sắp xếp - Tin học 8" dưới đây để hiểu hơn về vấn đề này.

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: Hướng dẫn học sinh giải bài toán sắp xếp - Tin học 8

  1. Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn ThÞ Lan Họ và tên : Nguyễn Thị Lan Chức vụ : Giáo viên Trường : Trung học cơ sở Trần Cao Tên đề tài SKKN: HƯỚNG DẪN HỌC SINH GIẢI BÀI TOÁN SẮP XẾP TIN HỌC 8. Phần I. PHẦN MỞ ĐẦU I. ĐẶT VẤN ĐỀ 1. Lí do chọn đề tài Hiện nay trong hầu hết các lĩnh vực hệ  lưu trữ, quản lý dữ  liệu, thao  tác tìm kiếm thường được thực hiện nhiều nhất để  khai thác thông tin một   cách nhanh chóng và chính xác  (ví dụ như: tra cứu từ điển, tìm sách trong  thư  viện, tra cứu thông tin về  nhân viên trong một cơ quan, tra cứu điểm thi của  một học sinh trong một trường học,…). Để đạt được mục tiêu tìm kiếm một   cách nhanh chóng thì dữ liệu cần phải được sắp xếp sẵn, ngăn nắp, khoa học   theo một trật tự, một hệ thống  nhất định. Khi xây dựng một hệ  thống quản lý thông tin trên máy tính, bên cạnh  các thuật toán tìm kiếm, các thuật toán sắp xếp dữ liệu cũng là một trong các   chủ đề được quan tâm hàng đầu. Trong khi đó, với học sinh bậc THCS, việc lập trình giải quyết các bài   toán, đặc biệt là các bài toán sắp xếp còn rất lúng túng, phương pháp còn  N¨m häc 2014 - 2015 Trang: 3
  2. Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn nghèo nàn, thuật toán còn đ ThÞ ơn điệu, điLan ều này dẫn đến việc giải quyết các bài  toán sắp xếp còn rất nhiều hạn chế.  Xuất phát từ thực trạng của vấn đề trên, sau một thời gian dài tìm hiểu,  nghiên cứu tôi xây dựng chuyên đề: “Hướng dẫn học sinh giải bài toán sắp   xếp” với mong muốn mang lại cho các em một cái nhìn tổng thể về  bài toán  sắp xếp nói chung, các thuật toán sắp xếp nói riêng, từ  đó có thể  tiếp cận  được với các bài toán quản lý thông tin sau này. 2. Đối tượng nghiên cứu và phạm vi nghiên cứu a) Đối tượng nghiên cứu ­ Học sinh lớp 8 trường THCS Trần Cao b) Phạm vi nghiên cứu:  Tìm hiểu và vận dụng các lý thuyết cơ bản về một số phương pháp  sắp xếp như: phương pháp chọn trực tiếp (Selection Sort), chèn trực tiếp  (Insertion Sort), sắp xếp nổi bọt (Bubble Sort), sắp xếp kiểu vun đống (Heap  Sort), sắp xếp nhanh (Quick Sort), sắp xếp với độ dài bước giảm dần (Shell  Sort),… Áp dụng đối với: ­ Phần: Câu lệnh lặp (xác định); Lặp với số lần chưa biết trước; Làm  việc với dãy số; Kiểu dữ liệu mảng.  ­ Bộ môn Tin học lớp 8.  II. PHƯƠNG PHÁP TIẾN HÀNH Chuyên đề chủ yếu sử dụng các phương pháp nghiên cứu sau: ­ Phương pháp nghiên cứu lí luận: Nghiên cứu các vấn đề  mang tính lí  luận có liên quan đến đề  tài (Muốn học tốt lập trình phải có thuật toán tốt,   muốn có thuật toán tốt đòi hỏi học sinh phải tiếp cận với nhiều dạng bài   toán, nhiều cách giải quyết bài toán,...) N¨m häc 2014 - 2015 Trang: 4
  3. Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn ­ Phương pháp đi ThÞ ều tra: V ới phLan ương pháp này tôi tiến hành điều tra học  sinh bằng các phiếu trắc nghiệm (chỉ rõ tính đúng, sai của thuật toán, dự đoán   kết quả của thuật toán), các bài thực hành trên phòng máy để nắm chắc trình   độ nhận thức, kỹ năng thực hành của từng đối tượng học sinh. Trên cơ sở đó  làm nền tảng đối chiếu kết quả trước và sau khi thực hiện chuyên đề. ­ Phương pháp phỏng vấn: Thông qua việc trao đổi trực tiếp thẳng thắn  với học sinh về các biện pháp giúp các em thực hành tốt bộ môn, tôi đã nhận   được những mong muốn, những băn khoăn, ..., và cả  những ý kiến đóng góp  của các em. Cũng từ đây tôi hình thành nên các giải pháp cho chuyên đề. ­ Phương pháp tạo tình huống: Thông qua các bài tập tạo tình huống,  các bài tập có tính chất minh chứng tôi dần dần dẫn các em vào vấn đề  và  hướng dẫn các em tìm cách giải quyết. ­ Phương pháp quan sát, đánh giá, tổng hợp: Thông qua quá trình quan  sát học sinh thực hành, đánh giá, tổng hợp kết quả thực hành giúp tôi có giải   pháp để thực hiện và điều chỉnh chuyên đề của mình cho phù hợp và có hiệu   quả nhất. Phần II.  NỘI DUNG I. MỤC TIÊU CỦA ĐỀ TÀI ­ Trình bày được ý tưởng, thuật giải (thuật toán) của một số phương  pháp sắp xếp thông dụng. ­ Giới thiệu được Code diễn đạt thuật giải. ­ Mô tả được thuật toán của phương pháp bằng ví dụ cụ thể. II. CÁC GIẢI PHÁP THỰC HIỆN Một số thuật toán sắp xếp: 1. Sắp xếp chọn trực tiếp (Selection Sort) N¨m häc 2014 - 2015 Trang: 5
  4. Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan 2. SắNguyÔn p xếp chèn trThÞ ực tiếLan p (Insertion Sort) 3. Sắp xếp nổi bọt (Bubble Sort) 4. Sắp xếp phân hoạch (Quick Sort) 5. Sắp xếp với bước giảm dần (Shell Sort) 6. Sắp xếp vun đống (Heap Sort) 1. Sắp xếp chọn trực tiếp (Selection Sort)  Ý tưởng: ­ Chọn phần tử nhỏ nhất trong n phần tử đầu, đưa phần tử này về vị trí   đầu của dãy. Tiếp tục quá trình với n­1 phần tử  còn lại và bắt đầu từ  vị  trí  thứ 2. Lặp lại quá trình trên cho dãy gồm n­1 phần tử còn lại. ­ Thuật toán thực hiện n­1 lần để lần lượt đưa phần tử nhỏ nhất trong  dãy hiện hành về vị trí dẫn đầu.  Thuật toán: Đầu vào: n – số phần tử mảng a – mảng chứa các phần tử bất kỳ Đầu ra:  a­ mảng đã được sắp xếp tăng dần Bước 1: i = 0 Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n­1] Bước 3: Hoán vị a[i] với a[min] Bước 4:  • nếu i Dừng thuật toán  Cài đặt (code): N¨m häc 2014 - 2015 Trang: 6
  5. Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan … NguyÔn ThÞ Lan Type mang:array[1..20] of integer; Function SelectionSort(a:mang, n:integer): integer; Var i, j, vtmin, tam: integer; Begin Writeln(‘­­­­­­SAP XEP CHON TRUC TIEP­­­­­­’); For i≔1 to n­1 do Begin Vtmin≔i; For j≔i+1 to n do If a[vtmin]>a[j] then vtmin≔j; {Hoan doi vi tri cua a[i] va a[vtmin]} Tam≔a[i]; A[i]≔a[vtmin]; A[vtmin]≔tam; End; Writeln(‘Day so sau khi sap xep la:’); For i≔1 to n do Write(a[i],’     ’); End; …  Ví dụ minh họa: Cho dãy số (mảng a):   12    2 8 5 1 6 4 15 Yêu cầu: Sắp xếp dãy số tăng dần.  Mô tả các bước chạy khi thực hiện thuật toán với dãy trên: N¨m häc 2014 - 2015 Trang: 7
  6. Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn i=0 => j = 1 ÷ ThÞ Lan ổi a[0] và a[4]   7 và vtmin = 4 => Hoán đ N¨m häc 2014 - 2015 Trang: 8
  7. Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn ThÞ Lan 2. Sắp xếp chèn trực tiếp (Insertion Sort)  Ý tưởng:  N¨m häc 2014 - 2015 Trang: 9
  8. Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn Giả sử có dãy a ThÞ Lan 0, a1,…,ai­1 đã được sắp xếp. Ý tưởng của thuật toán là  chèn thêm phần tử mới ai vào vị  trí thích hợp của đoạn a1…ai­1 sao cho được  dãy mới a1…ai đã được sắp xếp Nguyên tắc sắp xếp như  sau: đoạn gồm phần tử  a0 đã được sắp xếp,  thêm a1 vào được a0,a1 đã được sắp xếp, tiếp tục thêm a2 vào được a0, a1, a2 đã  sắp xếp…tiếp tục để thêm an vào để được a0,a1,…,an đã sắp xếp.  Thuật toán: Đầu vào: n – số phần tử mảng a – mảng chứa các phần tử bất kỳ Đầu ra: a­ mảng đã được sắp xếp tăng dần Bước 1: i=1 //giả sử a[0] đã được sắp xếp Bước 2: x=a[i], tìm vị trí pos thích hợp trong đoạn từ a[0] đến a[i­1] để chèn  a[i] vào Bước 3: đổi chỗ các phần tử từ a[pos] đến a[i­1] sang phải một vị trí để được  vị trí chèn a[i] vào Bước 4: chèn a[i] vào vị trí pos tìm được bằng cách gán a[pos]=a[i] Bước 5: i=i+1 Nếu i lặp lại bước 2 Ngược lại => Dừng thuật toán  Cài đặt: … Type mang:array[1..20] of integer; Function  InsertionSort(a:mang, n:integer): integer; Var i, j, pos, x: integer; N¨m häc 2014 - 2015 Trang: 10
  9. Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan Begin NguyÔn ThÞ Lan Writeln(‘­­­­­­SAP XEP CHEN TRUC TIEP­­­­­­’); For  i≔2 to n do  Begin X≔a[i]; {Luu gia tri cua phan tu a[i] de tranh khi de khi roi cho} Pos≔i­1; While (pos >= 1) and (a[pos]>x) do      Begin               A[pos+1]≔a[pos];               Pos≔pos­1;      End; A[pos+1]≔x; {chen x vao day} End; Writeln(‘Day so sau khi sap xep la:’); For i≔1 to n do Write(a[i],’     ’); End;  Ví dụ minh họa:  Cho dãy số a: a = 12 2 8 5 1 6    4 15  Sắp xếp dãy tăng dần Mô tả các bước chạy khi thực hiện thuật toán với dãy trên: N¨m häc 2014 - 2015 Trang: 11
  10. Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn ThÞ Lan N¨m häc 2014 - 2015 Trang: 12
  11. Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn ThÞ Lan 3. Sắp xếp nổi bọt (Bubble Sort) Ý tưởng:  N¨m häc 2014 - 2015 Trang: 13
  12. Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan Xuất phát tNguyÔn ThÞ ừ đầu dãy hay cu Lan ến hành đổi chỗ cặp phần tử kế  ối dãy và ti cận nhau để  đưa phần tử  nhỏ  hơn hoặc lớn hơn về vị trí cao nhất hay thấp   nhất trong dãy. Sau khi đã chuyển vị  tjrí này không xét nữa => Lặp lại quá   trình này khi dãy không còn phần tử nào nữa   Thuật toán:  Bước 1: i = 0 Bước 2: j = n­1  //duyệt từ cuối đến ptử thứ i Trong khi j>i thực hiện nếu a[j] =n­1 => Hết dãy và dừng thuật toán Ngược lại lặp lại bước 2   Cài đặt: … Type mang = array[1..20] of integer; Function BubbleSort(a:mang, n:integer): integer; Var i, j, tg: integer; Begin Writeln(‘­­­­SAP XEP NOI BOT ­­­­’); For i≔1 to n do For j≔n downto i+1 do If a[j]
  13. Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn ThÞ A[j]≔a[j­1]; Lan A[j­1]≔tg; End; End;  Ví dụ minh họa:  Cho dãy số a: a =  2 12 8 5 1 6 4 15  Yêu cầu: Sắp xếp dãy tăng dần N¨m häc 2014 - 2015 Trang: 15
  14. Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn ThÞ Lan N¨m häc 2014 - 2015 Trang: 16
  15. Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn ThÞ Lan N¨m häc 2014 - 2015 Trang: 17
  16. Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn ThÞ Lan 4. Sắp xếp dựa trên phân hoạch – Quick Sort Ý tưởng:  + Phân hoạch dãy a1 a2 …an thành 3 thành phần : ­ Dãy con 1 : Gồm các phần tử a1 …ai có giá trị không lớn hơn x.(x) ­ Dãy con 3: ai,..aj=x + Với x là giá trị của một phần tử tuỷ ý trong dãy ban đầu.  + Sau khi phân hoạch, dãy ban đầu được chia làm 3 phần : ak  x,  vớI k=j..N  Thuật toán: Giải thuật để sắp xếp một dãy al…ar  Bước 1 : Phân hoạch dẫy al…ar  thành các dãy con :  Dãy con 1 : al…aj  x  Bước 2 :   Nếu (l
  17. Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn ThÞ Lan Giải thuật để phân hoạch một dãy al…ar thành 2 dãy con: Bước 1 : Chọn tuỳ ý a[k] làm giá trị mốc l
  18. Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn ThÞ Lan Function QuickSort(a:mang; l,r:integer):integer; Var I, j, x, n:integer; Begin Writeln(‘­­­­­­SAP XEP PHAN HOACH­­­­­­’); X≔a[(l+r) div 2]; I≔l; J≔r; Repeat While a[i]x do dec(j); If (i
  19. Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn ThÞ Lan 1 2 8 5 1 6 4 1 2 E 5 r=8 l=1 4 2 1 5 8 6 1 1 E 2 5 Phân hoạch đoạn  l=1; r=3; x=a[2]=2 4 2 1 5 8 6 1 1 E 2 5 l=1 r=3 1 2 4 5 8 6 1 1 E 2 5 Phân hoạch đoạn  l=5; r=8; x=a[6]=6 1 2 4 5 8 6 1 1 E 2 5 l=5 r=8 1 2 4 5 6 8 1 1 2 5 Phân hoạch đoạn  l=7; r=8; x=a[7]=12 1 2 4 5 6 8 1 1 2 5 l=7 r=8 1 2 4 5 6 8 1 1 N¨m häc 2014 - 2015 2 5 Trang: 21
  20. Híng dÉn häc sinh gi¶i bµi to¸n s¾p xÕp - Tin häc 8. ®Gi¸o ¸n Tin häc 9 NguyÔn ThÞ Lan NguyÔn ThÞ Lan Dừng 5.  Sắp xếp với bước giảm dần (Shell Sort)  Ý tưởng: Dựa trên ý tưởng sắp xếp theo phương pháp chèn ­ Phân chia dãy ban đầu thành những dãy con các phần tử ở cách nhau h vị trí ­ Dãy ban đầu : a1 a2 … an được xem như sự xen kẽ các dãy con sau : ­ Dãy con thứ nhất : a1 ah+1 a2h+1 … ­ Dãy con thứ hai   : a2 ah+2 a2h+2 … ….                          ­ Dãy con thứ h      : ah a2h a3h …  Giải thuật:  Bước 1  :  Chọn k khoảng cách h[1], h[2],…,h[k] và i=1.  Bước 2 : Phân chia dãy ban đầu thành các dãy con cách nhau h[i]  khoảng cách. Sắp xếp từng dãy con bằng phương pháp chèn trực tiếp.  Bước 3 : i=i+1; Nếu i>k : dừng. Nếu i
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2