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 THPT: Một số kỹ thuật lập trình nâng cao giúp đạt hiệu quả cao trong bồi dưỡng học sinh giỏi các cấp

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:97

Thêm vào BST
Báo xấu
20
lượt xem 10
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à giới thiệu đến giáo viên và học sinh một số kỹ thuật lập trình nâng cao dành cho đối tượng HSG các cấp khối THPT; 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.

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: Một số kỹ thuật lập trình nâng cao giúp đạt hiệu quả cao trong bồi dưỡng học sinh giỏi các cấp

  1. SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN SÁNG KIẾN KINH NGHIỆM ĐỀ TÀI MỘT SỐ KỸ THUẬT LẬP TRÌNH NÂNG CAO GIÚP ĐẠT HIỆU QUẢ CAO TRONG BỒI DƯỠNG HỌC SINH GIỎI CÁC CẤP Lĩnh vực: Tin học Tác giả: Nguyễn Thị Luận Tổ: Toán – Tin Năm thực hiện: 2021 - 2023 Số ĐT: 0989868255 Email: nguyenluan.dc5@gmail.com NGHỆ AN, NĂM 2023
  2. MỤC LỤC Trang 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 1.5. Phạm vi nghiên cứu ……………………………………………………...2 2. NỘI DUNG NGHIÊN CỨU ………………………………………………….2 2.1. Cơ sở lý luận .................................................................................. .……..2 2.1.1. Khái niệm về kỹ thuật lập trình …………………………………….….2 2.1.2. Vai trò của kỹ thuật lập trình …………………………………………..2 2.2. Thực trạng ……………………………………...………………………...2 2.3. Các kỹ thuật lập trình nâng cao ………………………………………….3 2.3.1. Kỹ thuật mảng đánh dấu ……………………………………………….3 2.3.1.1. Bài toán 1 - Số nhỏ nhất ……………………………………………...3 2.3.1.2. Bài toán 2 – Sàng nguyên tố ………………………………………....5 2.3.2. Kỹ thuật mảng đếm ……………………………………………...….….7 2.3.2.1 – Bài toán 1 - Tần số xuất hiện ……………………………………….7 2.3.2.2. Bài toán 2 – Hai lớp học ……………………………………………..9 2.3.2.3. Bài toán 3 – Sắp xếp đếm phân phối ………………………………..10 2.3.3. Kỹ thuật quay lui ……………………………………………………...11 2.3.3.1. Bài toán 1 – In ra tất cả các hoán vị của n số tự nhiên đầu tiên …….13 2.3.3.2. Bài toán 2 – Liệt kê các dãy nhị phân độ dài N ………………...14 2.3.5. Kĩ thuật tham lam (greedy) …………………………………………...14 2.3.5.1. Bài toán 1 – Tìm đường đi ngắn nhất ………………………………15 2.3.5.2 Bài toán 2 – Xếp lịch ………………………………………………..17 2.3.4. Kỹ thuật quy hoạch động ……………………………………………..19 2.3.4.1. Bài toán 1 – Bài toán kinh điển tìm số Fibonaci thứ n ……………..20 2.3.4.2. Bài toán 2 – Vali …………………………………………………....21 2.4. Đánh giá các kỹ thuật …………………………………………………...22 2.4.1. Đánh giá các kỹ thuật thông qua thời gian thực hiện …………………22
  3. 2.4.1.1. Bài toán – Sàng nguyên tố ……………………………………….…23 2.4.1.2. Bài toán 2 – Dãy con liên tiếp ………………………………………24 2.4.1.3. Bài toán 3 - Trò chơi con số may mắn ……………………………...25 2.4.1.4. Bài toán 4 - Dãy nguyên tố …………………………………………27 2.4.1.5. Bài toán 5 – Liệt kê các hoán vị …………………………………….28 2.4.2. Đánh giá ưu điểm và hạn chế của các kĩ thuật ……………………......29 2.4.2.1. Kỹ thuật mảng đếm ………………………………………………....30 2.4.2.2. Kỹ thuật mảng đánh dấu …………………………………………...30 2.4.2.3. Kỹ thuật quay lui …………………………………………………....30 2.4.2.4. Kỹ thuật tham lam …………………………………………………..31 2.4.2.5. Kỹ thuật quy hoạch động …………………………………………...31 2.5. Bài toán áp dụng ………………………………………………………..32 2.5.1. Bài toán 1 – DỰ BÁO THỜI TIẾT…………………………………...32 2.5.2. Bài toán 2 - LẬP TRÌNH ……………………………………………..33 2.5.3. Bài toán 3 – PALIN …………………………………………………..34 2.5.4. Bài toán 4 – QUÂN HẬU ………………………………………….....35 2.5.5. Bài toán 5 – TÌM SỐ ………………………………………………….36 2.5.6. Bài toán 6 - BEAUTY ………………………………………………...36 2.5.7. Bài toán 7 – DUY NHẤT ĐẦU TIÊN ………………………………..37 2.5.8. Bài toán 8 – SỐ HOÀN HẢO …………………………………….......38 2.5.9. Bài toán 9 – BỐ TRÍ PHÒNG HỌP ……………………………….…38 2.5.10. Bài toán 10 – BÁN SÁCH …………………………………………..39 2.5.11. Bài toán 11 – PHÂN HẠNG NGỌC TRAI …………………………40 2.5.12. Bài toán 12 – XẾP GẠCH ………………………………………..…41 2.5.13. Bài toán 13 – PHÂN TÍCH MỘT SỐ BẰNG TỔNG CÁC SỐ …….41 2.5.14. Bài toán 14 – DÃY CON ĐƠN ĐIỆU TĂNG DÀI NHẤT ……...…42 2.6. Kinh nghiệm bồi dưỡng HSG ……………………………………….….43 2.7. Kết quả đạt được ………………………………………………….....….44 2.7.1. Kết quả thực nghiệm ………………………………………………….44 2.7.2. Kết quả khảo sát sự cấp thiết và tính khả thi của các kỹ thuật lập trình nâng cao ……………………………………………………………………..45 2.7.2.1. Mục đích khảo sát ……………………………………………….….45
  4. 2.7.2.2. Nội dung và phương pháp khảo sát ………………………………...45 2.7.2.2.1. Nội dung khảo sát ……………………………………………..….45 2.7.2.2.2. Phương pháp khảo sát và thang đánh giá …………………………45 2.7.2.3. Đối tượng khảo sát ……………………………………………….…46 2.7.2.4. Kết quả khảo sát về sự cấp thiết và tính khả thi của các giải pháp đã đề xuất …………………………………………………………………………..47 2.7.2.4.1. Sự cấp thiết của các giải pháp đã đề xuất …………………………47 2.7.2.4.2. Tính khả thi của các giải pháp đề xuất ………………..…………48 2.7.3. Kết quả đạt được trong công tác bồi dưỡng HSG …………………….48 3. KẾT LUẬN VÀ KIẾN NGHỊ ……………………………………….……..49 3.1. Kết luận …………………………………………………………………49 3.2. Kiến nghị ………………………………………………………….…….50 TÀI LIỆU THAM KHẢO ………………………………………………..……51 PHỤ LỤC 1 …………………………………………………………………......52 1. Kỹ thuật mảng đánh dấu ………………………………………………….52 1.1. Bài toán 1- Số nhỏ nhất …………………………………………………52 1.2. Bài toán 2 – Sàng nguyên tố ……………………………………………52 2. Kỹ thuật mảng đếm ……………………………………………………….53 2.1. Bài toán 1 – Tần số xuất hiện …………………………………………...53 2.2. Bài toán 2 – Hai lớp học ………………………………………………..54 2.3. Bài toán 3 – Sắp xếp đếm phân phối …………………………………....55 3. Kĩ thuật quay lui …………………………………………………………..56 3.1. Bài toán 1: In ra tất cả các hoán vị của n số tự nhiên đầu tiên (0
  5. PHỤ LỤC 2 …………………………………………………………………..…66 1. Bài toán 1: SÀNG SỐ NGUYÊN TỐ …………………………………….66 2. Bài toán 2: DÃY CON LIÊN TIẾP ……………………………………....67 3. Bài toán 3: TRÒ CHƠI CON SỐ MAY MẮN …………………………...68 4. Bài toán 4: DÃY NGUYÊN TỐ ………………………………………….69 5. Bài toán 5: LIỆT KÊ CÁC HOÁN VỊ ……………………………………71 PHỤ LỤC 3 ……………………………………………………………………..73 1. Bài toán 1: DỰ BÁO THỜI TIẾT ………………………………………..73 2. Bài toán 2: LẬP TRÌNH ………………………………………………….75 3. Bài toán 3: PALIN ………………………………………………………..76 4. Bài toán 4: QUÂN HẬU ………………………………………………....78 5. Bài toán 5: TÌM SỐ ……………………………………………………....79 6. Bài toán 6: BEAUTY ……………………………………………………..80 7. Bài toán 7: DUY NHẤT ĐẦU TIÊN …………………………………….81 8. Bài toán 8: SỐ HOÀN HẢO …………………………………………..….82 9. Bài toán 9: BỐ TRÍ PHÒNG HỌP ……………………………………….83 10. Bài toán 10: BÁN SÁCH ………………………………………………..85 11. Bài toán 11: PHÂN HẠNG NGỌC TRAI ……………………………....85 12. Bài toán 12: XẾP GẠCH ……………………………………….…….…86 13. Bài toán 13: PHÂN TÍCH MỘT SỐ THÀNH TỔNG CÁC SỐ ………..87 14. Bài toán 14 – DÃY CON ĐƠN ĐIỆU TĂNG DÀI NHẤT ………….…88 PHỤ LỤC 4 ……………………………………………………………………..90
  6. DANH MỤC TỪ VIẾT TẮT TT Từ viết tắt Nghĩa từ viết tắt 1 NNLT Ngôn ngữ lập trình 2 THPT Trung học phổ thông 3 HSG Học sinh giỏi 4 QHĐ Quy hoạch động 5 HS Học sinh
  7. 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 tốt về thuật toán để giải được các bài toán từ mức độ cơ bản đến nâng cao, 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. Điều này lại chỉ được hình thành sau khi người học được tiếp xúc với một hệ thống các bài toán đi từ cơ bản đến nâng cao được tổ chức cẩn thận, chặt chẽ. Hệ thống này giúp xây dựng được các thói quen tư duy cơ bản và nâng cao cũng như các kỹ thuật cơ bản và kỹ thuật nâng cao trong lập trình. Với các kỹ thuật cơ bản như cờ hiệu, lính canh, ghi nhớ, duy trì mảng sắp xếp, đệ quy, chia đệ trị mà tôi đã trình bày trong SKKN năm trước đã giúp các quý thầy cô và các em học sinh có được kiến thức và tư duy cơ bản cũng như có cái nhìn tổng quan về ưu điểm và hạn chế của các kĩ thuật. Tuy nhiên, khi tham gia kì thi HSG các cấp có nhiều bài toán nâng cao đòi hỏi phải sử dụng đến các kỹ thuật nâng cao hơn mà các kỹ thuật cơ bản không cho được thuật toán tối ưu. Với mong muốn giúp các em giải các bài toán nâng cao trong Tin học theo hướng tối ưu nhất, qua quá trình bồi dưỡng học sinh giỏi, tôi đã phát hiện, đúc rút ra được một số kỹ thuật lập trình nâng cao, rất quan trọng giúp đạt hiệu quả cao trong kì thi HSG các cấp như cấp trường, cấp huyện, cấp tỉnh, cấp Quốc gia. Mặt khác, theo tôi thấy hiện tại chưa có tài liệu nào viết về các kỹ thuật lập trình nâng cao và ứng dụng của chúng một cách đầy đủ để làm tài liệu tham khảo mới cho giáo viên và học sinh. Ngoài ra, theo công văn mới của Sở về thi HSG cấp tỉnh sẽ không dùng NNLT Pascal nữa 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 quyết định trình bày sáng kiến kinh nghiệm: “Một số kỹ thuật lập trình nâng cao giúp đạt hiệu quả cao trong bồi dưỡng học sinh giỏi các cấp”. 1.2. Mục đích nghiên cứu Mục đích chính của sáng kiến là giới thiệu đến giáo viên và học sinh một số kỹ thuật lập trình nâng cao dành cho đối tượng HSG các cấp khối THPT. - 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++ là ngôn ngữ có ưu thế mạnh trong thực hiện chương trình nhanh, phù hợp với thi HSG các cấp. 1
  8. 1.3. Đối tượng nghiên cứu - Giáo viên và học sinh tham gia bồi dưỡng HSG Tin học. - Tổng hợp lại một số kỹ thuật nâng cao giúp học sinh phát triển tư duy lập trình thông qua hệ thống các bài tập được phân loại kỹ lưỡng. 1.4. Phương pháp nghiên cứu - Phương pháp điều tra, nghiên cứu tài liệu. - Phương pháp phân tích, tổng hợp. - Phương pháp khảo sát thực tiễn. - Phương pháp tổng kết kinh nghiệm. 1.5. Phạm vi nghiên cứu Phạm vi nghiên cứu: Một số kỹ thuật nâng cao để tăng tốc chương trình giúp đạt hiệu quả cao trong bồi dưỡng HSG các cấp môn Tin học. 2. NỘI DUNG NGHIÊN CỨU 2.1. Cơ sở lý luận 2.1.1. Khái niệm về kỹ thuật lập trình Kỹ thuật lập trình là kỹ thuật thực thi một giải pháp phần mềm (cấu trúc dữ liệu + giải thuật) dựa trên nền tảng một phương pháp luận (methodology) và một hoặc nhiều ngôn ngữ lập trình phù hợp với yêu cầu đặc thù của ứng dụng. 2.1.2. Vai trò của kỹ thuật lập trình Trẻ em là thế hệ của tương lai, trẻ em cũng cần học các kỹ năng giúp cho trẻ có thể làm được những điều mới chứ không hoàn toàn đi theo những gì đã được dạy trong quá khứ. Theo nhiều chuyên gia, lập trình là một trong những kỹ năng quan trọng trẻ nên được trang bị từ sớm để giúp trẻ phát triển tư duy tính toán và các kỹ năng tư duy phản biện, kỹ năng trình bày, kỹ năng quản lý thời gian, làm việc nhóm.... và quan trọng hơn hết là được thỏa sức sáng tạo “thế giới trong mơ” của mình một cách sinh động trên máy tính. Tư duy tính toán (Computational Thinking) là cách tư duy sao cho không những giải quyết được vấn đề mà còn có thể đưa vào máy tính cách giải quyết vấn đề. Nhờ đó, vấn đề sẽ được máy tính xử lý một cách chính xác, nhanh chóng và có thể tự động hoàn toàn. Tư duy tính toán là nền tảng của Trí tuệ nhân tạo, Học máy và nhiều công nghệ khác của tương lai. Khi được phát triển kỹ năng này từ sớm, trẻ sẽ biết cách tiếp cận giải quyết vấn đề từng bước một cách logic và dần biết được cách giải quyết các vấn đề lớn, phức tạp. 2.2. Thực trạng Trên thực tế đã có một số tài liệu đề cập đến những kỹ thuật để tăng tốc chương trình, tuy nhiên chưa đi sâu vào phân tích cách tư duy, cách lựa chọn và cài đặt chương trình tối ưu, đặc biệt việc tổng hợp lại các kỹ thuật từ cơ bản đến nâng 2
  9. cao giúp học sinh có thể so sánh các cách giải, các kết quả, độ phức tạp còn rất ít, hệ thống bài tập cũng không nhiều. Trong quá trình ôn luyện đội tuyển, học sinh được dạy một số kỹ thuật cơ bản như kĩ thuật cờ hiệu, lính canh, ghi nhớ, duy trì mảng sắp xếp, đệ quy,… để giải các bài toán ở mức độ cơ bản và mức độ khá. Nhưng nếu chỉ dừng lại ở đó hay không biết kết hợp với những kỹ thuật nâng cao khác sẽ không đạt được sự tối ưu cao nhất và kết quả tốt nhất. Các kỹ thuật được giới thiệu trong sáng kiến đều là những kỹ thuật nâng cao đem lại một hiệu quả rất đáng kể trong việc giảm độ phức tạp thuật toán, tiến tới một thuật toán tối ưu nhất. Học sinh dần được làm quen với NNLT C++. 2.3. Các kỹ thuật lập trình nâng cao 2.3.1. Kỹ thuật mảng đánh dấu - Là kỹ thuật sử dụng một mảng để đánh dấu trạng thái (true/fasle hoặc 0/1) cho tập số tự nhiên {0, 1, 2, ... , n − 1}. - Mục đích chính: đánh dấu trạng thái của các số trong một tập số tự nhiên. Sau đó, dựa vào trạng thái của phần tử có chỉ mục tương ứng để kiểm tra một tính chất nào đó. - Xét một số bài toán cụ thể như sau: 2.3.1.1. Bài toán 1 - Số nhỏ nhất Cho N số nguyên dương A = (a1 , a2, … , aN) (1 ≤ N ≤ 108 và 1 ≤ ai ≤ 106). Hãy tìm số nguyên dương nhỏ nhất không xuất hiện trong A. Input • Dòng đầu tiên chứa số nguyên N • Dòng thứ hai chứa N số tự nhiên Output • Số tự nhiên nhỏ nhất không xuất hiện trong A Ví dụ Input Output 8 4 67125326 a. Ý tưởng thuật toán Bài này có nhiều cách làm. Ở đây tôi xin đề cập một kỹ thuật tuy đơn giản nhưng rất hay và có thể áp dụng cho nhiều bài tập, đó là kỹ thuật mảng đánh dấu trạng thái. Tôi sử dụng mảng một chiều A để lưu N số nguyên dương a1, a2 , ..., aN. int A[100000000], B[1000000]; 3
  10. Tôi sẽ sử dụng mảng B để đánh dấu sự xuất hiện của các phần tử trong mảng A. Vì các số ai trong mảng A có giá trị 1 ≤ ai ≤ 106 nên kích thước của mảng B tối thiểu là 106. Tôi đánh dấu: B[i] = 1 nếu số i xuất hiện trong mảng A và B[i]=0 nếu i không xuất hiện trong A. Khi đó ta có đoạn chương trình đánh dấu đơn giản như sau: memset(B,0,sizeof(B)); fi >> N; for (int i =1; i > A[i]; // Đọc ra phần tử thứ i trong mảng A B[A[i]] = 1; // Đánh dấu phần tử A[i] có xuất hiện trong mảng A } Sau khi đã đánh dấu thì việc tìm số nào chưa xuất hiện trở nên rất đơn giản. Duyệt từ đầu mảng đến cuối mảng B: Gặp số nào mà B[i]=0 thì dừng lại; và i chính là số nguyên dương đầu tiên chưa xuất hiện trong mảng A. Ta có đoạn code như sau: i=1; while (B[i]= =1 ) i++; Minh họa từng bước quá trình đánh dấu: 67125326 Kết quả chạy từng bước quá trình đánh dấu - Ban đầu B[i] = 0 với mọi i (1≤i ≤ 106) 0 0 0 0 0 0 0 0…0 - Lần 1: - Lần 5 + Đọc ra A[1]=6 + Đọc ra A[5]=5 + Đánh dấu B[6] = 1 + Đánh dấu B[5] = 1 0 0 0 0 0 1 0 0 …0 1 1 0 0 1 1 1 0…0 - Lần 2: - Lần 6 + Đọc ra A[2]=7 + Đọc ra A[6]=3 + Đánh dấu B[7] = 1 + Đánh dấu B[3] = 1 0 0 0 0 0 1 1 0…0 1 1 1 0 1 1 1 0…0 4
  11. - Lần 3: - Lần 7 + Đọc ra A[3]=1 + Đọc ra A[7]=2 + Đánh dấu B[1] = 1 + Đánh dấu B[2] = 1 1 0 0 0 0 1 1 0…0 1 1 1 0 1 1 1 0…0 - Lần 4: - Lần 8 + Đọc ra A[4]=2 + Đọc ra A[8]=6 + Đánh dấu B[2] = 1 + Đánh dấu B[6] = 1 1 1 0 0 0 1 1 0…0 1 1 1 0 1 1 1 0…0 - Sau khi đánh dấu thì ta thấy B[4] = 0 nên 4 là số nhỏ nhất chưa xuất hiện trong A. b. Nội dung và cài đặt chương trình - Các bước thực hiện giải thuật: Bước 1. Đọc giá trị N từ tệp; Bước 2. Khởi tạo các phần tử trong mảng B đều bằng 0; Bước 3. Cho i lần lượt nhận các giá trị từ 1 đến N, thực hiện lặp lại: Bước 3.1. Đọc phần tử A[i] từ tệp; Bước 3.2. B[A[i]]= 1; Bước 4. i ← 0; Bước 5. i ← i + 1; Bước 6. Nếu B[i] = 0 thì ghi ra tệp giá trị i rồi kết thúc thuật toán; Bước 7. Nếu B[i] = 1 thì quay lại bước 5. - Cài đặt chương trình: Phần phụ lục 1 (sonhonhat.cpp) 2.3.1.2. Bài toán 2 – Sàng nguyên tố Cho số nguyên N (1 ≤ N ≤ 106 ). Viết chương trình liệt kê các số nguyên tố nhỏ hơn N. Input : • Dòng duy nhất chứa số nguyên N Output : • Dòng thứ nhất ghi số M là số lượng số nguyên tố tìm được • Dòng thứ hai ghi dãy gồm M số nguyên tố nhỏ hơn N. 5
  12. Ví dụ: Input Output 10 4 2357 20 8 2 3 5 7 11 13 17 19 a. Ý tưởng thuật toán - Tạo mảng đánh dấu snt để đánh dấu cho tất cả các phần tử có giá trị từ 2 đến N -1 và mặc định tất cả đều là số nguyên tố (quy ước có giá trị bằng 1). - Xét số nguyên tố nhỏ nhất đầu tiên – giả sử x, đánh dấu tất cả các bội số của x là: 2x, 3x, 4x,…nằm trong đoạn [x, N) không phải số nguyên tố (quy ước có giá trị bằng 0). - Tìm số tiếp theo được đánh dấu là số nguyên tố trong đoạn [x, N). Nếu không còn số nào, thoát chương trình. Nếu còn, gán nó cho x và lặp lại bước 2. - Khi kết thúc giải thuật, các số không bị đánh dấu bằng 0 là các số nguyên tố - Đoạn chương trình con thể hiện mảng đánh dấu như sau: void sangnt() { int i,j; //Đánh dấu các số từ 2 đến N là nguyên tố for (i=2; i
  13. Bước 6.1. dem ← dem +1; Bước 6.2. j ← 2*i; Bước 6.3. Nếu j ≥ N thì chuyển đến bước 7; Bước 6.4. snt[j] ← 0; Bước 6.5. j ← j + i rồi quay lại bước 6.3; Bước 7. i ← i + 1 rồi quay lại bước 5; Bước 8. Ghi giá trị biến dem ra tệp; Bước 9. i ← 1; Bước 10. Nếu i ≥ N thì kết thúc thuật toán; Bước 11. Nếu snt[i] = 1 thì ghi giá trị i ra tệp; Bước 12. i ← i + 1 rồi quay lại bước 10. - Cài đặt chương trình: Phần phụ lục 1 (sangsonguyento.cpp) 2.3.2. Kỹ thuật mảng đếm - Là kỹ thuật dùng một mảng đếm để lưu trữ số lần xuất hiện của từng số trong dãy cho trước tại chỉ mục tương ứng của chúng. Ban đầu, khởi tạo mảng đếm này có tất cả các phần tử đều bằng 0. Khi duyệt các số trong dãy, gặp số nào thì phần tử có chỉ mục tương ứng trong mảng đếm sẽ tăng lên 1 đơn vị. - Mục đích chính là đếm số lần xuất hiện của các số trong một dãy số cho trước. - Xét một số bài toán cụ thể sau: 2.3.2.1 – Bài toán 1 - Tần số xuất hiện Nhập vào một số nguyên dương N (N ≤ 1000), tiếp theo là N số nguyên dương lần lượt là các phần tử của một dãy số có giá trị không lớn hơn 32000. Hãy đếm tần số (số lần xuất hiện) của các số trong dãy và in nó ra màn hình dưới dạng sau: a1 – t 1 a2 – t2 ………… aN - t N Trong đó t1 là số lần xuất hiện của số a1, t2 là số lần xuất hiện của a2, … Và a1, a2, …, aN không trùng nhau và được sắp xếp tăng dần. Ví dụ: Input Output 6 2–2 422565 4–1 5–2 6–1 7
  14. a. Ý tưởng thuật toán: Với bài này ta sẽ sử dụng mảng đếm: - Tạo mảng t với mục đích: t[i] sẽ lưu số lần xuất hiện của phần tử có giá trị là i. - Khởi tạo các phần tử của mảng t bằng 0. - Đọc các số trong dãy a: đọc đến phần tử a[i] nào thì ta tăng t[a[i]] lên 1 đơn vị. Giá trị của a[i] sẽ được xem là một chỉ số trong dãy t. Lưu ý: Với kỹ thuật mảng đếm này chỉ áp dụng được khi a[i] có thể làm chỉ số của dãy t. Đoạn lệnh chương trình con sau thể hiện mảng đếm t: int t[32001], a[1001]; void doctep() { ifstream fi(“lophoc.inp”); memset(t, 0, sizeof(t)); fi>>N; for(int i=1; i>a[i]; t[a[i]]++; }} b. Nội dung và cài đặt chương trình - Các bước thực hiện giải thuật: Bước 1. Đọc giá trị N từ tệp; Bước 2. Khởi tạo các phần tử của mảng t bằng 0 Bước 3. Max ← 0; Bước 4. Cho i lần lượt nhận các giá trị từ 1 đến N, thực hiện lặp lại: Bước 4.1. Đọc phần tử a[i] từ tệp; Bước 4.2. t[a[i]]← t[a[i]] + 1; Bước 4.3. Nếu Max < a[i] thì Max ← a[i]; Bước 5. Cho i lần lượt nhận các giá trị từ 1 đến Max, thực hiện lặp lại: Bước 5.1. Nếu t[i] > 0 thì ghi giá trị a[i] và t[a[i]] ra tệp trên mỗi dòng; Bước 6. Kết thúc thuật toán. - Cài đặt chương trình: Phần phụ lục 1 (tanso.cpp) 8
  15. 2.3.2.2. Bài toán 2 – Hai lớp học Tico dạy và tổ chức thi cho hai lớp học: lớp Công nghệ Thông tin có N sinh viên có kết quả thi là a1, a2, …, aN và lớp Điện tử có M sinh viên có kết quả thi là b1, b2…, bM. Sau khi chấm bài xong Tico muốn biết xem có bao nhiêu cặp hai bạn học mỗi bạn một lớp mà có điểm bằng nhau. Input - Dòng đầu ghi 2 số nguyên dương N, M (1
  16. for (int i=1; i>x; b[x]++; } fi.close(); } b. Nội dung và cài đặt chương trình - Các bước thực hiện của giải thuật: Bước 1. Đọc giá trị N, M từ tệp; Bước 2. Khởi tạo các phần tử của mảng a và b đều bằng 0; Bước 3. Thực hiện lặp lại N lần thao tác sau: Bước 3.1. Đọc giá trị x từ tệp; Bước 3.2. a[x] ← a[x] + 1; Bước 4. Thực hiện lặp lại M lần thao tác sau: Bước 4.1. Đọc giá trị x từ tệp; Bước 4.2. b[x]← b[x] + 1; Bước 5. dem ← 0; Bước 6. Cho i lần lượt nhận các giá trị từ 0 đến 105, thực hiện lặp lại: Bước 6.1. dem ← dem + a[i]*b[i]; Bước 7. Ghi giá trị dem ra tệp rồi kết thúc thuật toán. - Cài đặt chương trình: Phần phụ lục 1 (lophoc.cpp) 2.3.2.3. Bài toán 3 – Sắp xếp đếm phân phối Cho n số nguyên dương được lưu trữ trong tệp Sort.inp (ai ≤ 5000, n ≤ 109). Hãy lập trình sắp xếp dãy số này và ghi kết quả vào tệp Sort.out. Ví dụ: Sort.inp Sort.out 14 11222333334456 11323325464233 a. Ý tưởng thuật toán: Đọc qua một lượt từ phần tử a[1] đến a[n] và dùng mảng b đếm số lần xuất hiện của mỗi phần tử. Phần tử b[i] dùng để lưu số lần xuất hiện của số i trong dãy a. 10
  17. Sau đây là mô phỏng thuật toán với ví dụ test trên: Giá trị: 1 2 3 4 5 6 b: 2 3 5 2 1 1 Sau đó ta dựa trên mảng b này để viết ra các số thành một danh sách. Giá trị i Kết quả danh sách Giải thích i=1 11 b[1] = 2: ta viết i ra 2 lần. i=2 11222 b[2] = 3: ta viết i ra 3 lần. i=3 1122233333 b[3] = 5: ta viết i ra 5 lần. i=4 112223333344 b[4] = 2: ta viết i ra 2 lần. i=5 1122233333445 b[5] = 1: ta viết i ra 1 lần. i=6 11222333334456 b[6] = 1: ta viết i ra 1 lần. Kết quả duyệt từ đầu đến cuối mảng b, ta được danh sách sắp xếp a. Nội dung và cài đặt chương trình - Các bước thực hiện thuật toán: Bước 1. Đọc giá trị n từ tệp; Bước 2. Khởi tạo các phần tử của mảng b đều bằng 0; Bước 3. Thực hiện lặp lại n lần thao tác sau: Bước 3.1. Đọc giá trị x từ tệp; Bước 3.2. b[x] ← b[x] + 1; Bước 4. n ← 0; Bước 5. Cho i lần lượt nhận các giá trị từ 1 đến 5000, thực hiện lặp lại: Bước 5.1. Cho j lần lượt nhận các giá trị từ 1 đến b[i], thực hiện lặp lại: Bước 5.1.1. a[n] ← i; Bước 5.1.2. n ← n + 1; Bước 6. Ghi mảng a ra tệp rồi kết thúc thuật toán. Trong ví dụ trên, ta thấy kích thước của mảng b phụ thuộc vào giá trị của các phần tử trong mảng A. (ở bài toán này là 5000). - Cài đặt chương trình: Phần phụ lục 1 (Sort.cpp) 2.3.3. Kỹ thuật quay lui Kỹ thuật quay lui (Backtracking) là một kỹ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong 11
  18. số các lựa chọn khả dĩ và đệ quy. Người đầu tiên đề ra thuật ngữ này (Backtracking) là nhà toán học người Mỹ D. H. Lehmer vào những năm 1950. Mục đích chính: Kỹ thuật quay lui dùng để giải bài toán liệt kê các cấu hình. Ý tưởng thuật toán: Mỗi cấu hình được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng. Giả sử cấu hình cần liệt kê có dạng x[1..n], khi đó thuật toán quay lui thực hiện qua các bước: 1) Xét tất cả các giá trị x[1] có thể nhận, thử cho x[1] nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho x[1] ta sẽ: 2) Xét tất cả các giá trị x[2] có thể nhận, lại thử cho x[2] nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho x[2] lại xét tiếp các khả năng chọn x[3] … cứ tiếp tục như vậy đến bước …………….. N) Xét tất cả các giá trị x[n] có thể nhận, thử cho x[n] nhận lần lượt các giá trị đó, thông báo cấu hình tìm được . Trên phương diện quy nạp, có thể nói rằng kỹ thuật quay lui liệt kê các cấu hình n phần tử dạng x[1..n] bằng cách thử cho x[1] nhận lần lượt các giá trị có thể. Với mỗi giá trị thử gán cho x[1] bài toán trở thành liệt kê tiếp cấu hình n -1 phần tử x[2..n]. Như vậy, khi thử gán x[1] bằng giá trị thứ nhất trong tập giá trị có thể nhận thì thuật toán sẽ tìm và in ra tất cả các cấu hình mà có x[1] bằng giá trị thứ nhất, sau đó quay lui lại để thử gán x[1] bằng giá trị thứ hai trong tập giá trị có thể nhận và tìm in ra tất cả các cấu hình mà có x[1] bằng giá trị thứ hai, …cứ như vậy thuật toán tiếp tục quay lui để thử hết tất cả các khả năng. Để cài đặt kỹ thuật quay lui, chúng ta sử dụng một chương trình con và gọi đến hàm đó trong chương trình chính. Mô hình của kỹ thuật quay lui sử dụng ngôn ngữ C++ như sau: Void Quay_lui(int i) { for (< mọi giá trị V có thể gán cho x[i] >) {< Thử cho x[i] = V >; if (< x[i] là phần tử cuối cùng trong cấu hình >) < Thông báo cấu hình tìm được >; else { < Ghi nhận việc cho x[i] nhận giá trị V (nếu cần) >; Quay_lui (i + 1); //Gọi đệ quy để chọn tiếp x[i+1] < Nếu cần, bỏ ghi nhận việc thử x[i] = V để thử giá trị khác>; } }} Thuật toán quay lui thường sẽ bắt đầu bằng lời gọi Quay_lui(1). - Xét một số bài toán cụ thể sau: 12
  19. 2.3.3.1. Bài toán 1 – In ra tất cả các hoán vị của n số tự nhiên đầu tiên (0
  20. 2.3.3.2. Bài toán 2 – Liệt kê các dãy nhị phân độ dài N a. Ý tưởng thuật toán Biểu diễn dãy nhị phân có độ dài n dưới dạng a[1..n]. Ta sẽ liệt kê các dãy nhị phân bằng cách thử dùng các giá trị {0,1} gán cho a[i]. Với mỗi giá trị thử gán cho a[i] lại thử các giá trị có thể gán cho a[i+1]... cứ như vậy cho đến khi chọn xong phần tử a[n]. Ở bài này do các phần tử a[i] trong dãy nhị phân có thể lặp lại nên không cần đánh dấu giá trị đã chọn. Chương trình con thể hiện kỹ thuật quay lui như sau: void Quay_lui(int i) // Chương trình con quay lui {for (int j=0;j
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

EXAM.01: Bộ 300+ Đề Thi Thử THPT Quốc Gia 2019
315 tài liệu
1700 lượt tải
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
59=>2