Sáng kiến kinh nghiệm THPT: Rèn kĩ năng lập trình cho học sinh giỏi thông qua khai thác tư duy một số thuật toán

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

Thêm vào BST

Báo xấu

45
lượt xem 4
download

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

Mục tiêu nghiên cứu của sáng kiến kinh nghiệm là thông qua hệ thống kiến thức và bài tập được phân chia theo mức độ giáo viên có thể đánh giá kết quả học tập của học sinh. Qua các nội dung giáo viên rèn luyện tư duy logic và kĩ năng giải quyết vấn đề cho học sinh. Thay đổi thực trạng của đội tuyển, khắc phục nhược điểm của giải pháp cũ, góp phần nâng cao chất lượng đội tuyển. Hệ thống lại kiến thức cơ bản về thuật toán từ đó giúp học sinh có thể hiểu, nhớ và vận dụng các thuật toán cơ bản vào giải quyết các bài toán khó. Biết cách tính độ phức tạp thuật toán từ đó biết cách lựa chọn thuật toán tối ưu. Phát triển tư duy logic và hình thành kĩ năng giải quyết vấn đề. Tiếp cận với một số thuật toán tối ưu trong lập trình. Tạo hứng thú học lập trình cho học sinh.

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: Rèn kĩ năng lập trình cho học sinh giỏi thông qua khai thác tư duy một số thuật toán

SỞ GIÁO DỤC VÀ ĐÀO TẠO BẮC GIANG TRƯỜNG THPT YÊN DŨNG SỐ 2 -----------&&&------------- THUYẾT MINH MÔ TẢ GIẢI PHÁP VÀ KẾT QUẢ THỰC HIỆN SÁNG KIẾN “ Rèn kĩ năng lập trình cho học sinh giỏi thông qua khai thác tư duy một số thuật toán” Người thực hiện: Trần Thị Thơm Giáo viên môn: Tin Học Đơn vị: Trường THPT Yên Dũng số 2. Yên Dũng, tháng 4 năm 2021
2 CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập – Tự do – Hạnh phúc THUYẾT MINH MÔ TẢ GIẢI PHÁP VÀ KẾT QUẢ THỰC HIỆN SÁNG KIẾN 1. Tên sáng kiến: “Rèn kĩ năng lập trình cho học sinh giỏi thông qua khai thác tư duy một số thuật toán’’ 2. Ngày sáng kiến được áp dụng lần đầu hoặc áp dụng thử : 09/2020 3. Các thông tin cần bảo mật: không có. 4. Mô tả các giải pháp cũ thường làm : Thuật toán là nội dung quan trọng trong lập trình. Một học sinh không học thuật toán vẫn có khả năng lập trình, nhưng nếu muốn là một lập trình viên giỏi thì học sinh đó phải học thuật toán thật cẩn thận và chuyên xâu. Sau đây là một số giải pháp vẫn được các thầy cô nhóm Tin – Trường THPT Yên Dũng số 2 áp dụng trong quá trình giảng dạy thuật toán. 4.1. Giải pháp 1: Sử dụng phương pháp thuyết trình Đây là phương pháp dạy học mà phượng tiện cơ bản dùng để thực hiện là lời nói của giáo viên. Vì vậy, ưu điểm lớn nhất của phương pháp này là có thể truyền tải một lượng lớn kiến thức tin học đến với người học. Tuy nhiên, phương pháp thuyết trình còn hạn chế là làm cho học sinh thụ động trong việc tiếp nhận và lưu giữ lại kiến thức. Đặc biệt là với phương pháp này chỉ dừng lại ở việc tái hiện lại các kiến thức trong nhận thức của học sinh. Vì vậy, phương pháp này chưa hướng tới mức độ thông hiểu đặc biệt là vận dụng của học sinh. Đồng thời, học sinh chỉ rèn luyện kĩ năng ghi nhớ còn học sinh chưa được rèn luyện kĩ năng phân tích, tổng hợp và tư duy logic. Dẫn đến hạn chế khả năng lập trình sau này của học sinh.
3 4.2 Giải pháp 2: Sử dụng phương pháp vấn đáp Đây là phương pháp dạy học mà ở đó giáo viên sẽ là người đưa ra các câu hỏi và học sinh sẽ trả lời, học sinh có thể cùng nhau tranh luận hoặc tranh luận với giáo viên, từ đó giúp học sinh tiếp thu được kiến thức của bài giảng. Với phương pháp này, giáo viên tạo ra hứng thú, kích thích tư duy, làm việc độc lập hoặc làm việc theo nhóm của học sinh. Tuy nhiên, khi sử dụng phương pháp này, giáo viên cần phải chuẩn bị hệ thống bài tập ở các mức độ nhận thức. Nhưng do thời lượng dành cho một chủ đề ôn tập ngắn trong khi lượng kiến thức cần truyền tải cho học sinh nhiều nên giáo viên không thể kiểm tra hết được kiến thức thu nhận cũng như sự chuẩn bị của học sinh. 5. Sự cần thiết phải áp dụng giải pháp sáng kiến: Vậy với 2 giải pháp trên thì nội dung kiến thức thuật toán hầu như chỉ là lưu giữ thụ động, ghi nhớ một cách máy móc (học thuộc) và chỉ dừng lại ở các thuật toán cơ bản trong sách giáo khoa Tin Học 10. Dẫn đến tình trạng khi học lập trình lớp 11 học sinh thường thấy môn học này rất khó (khó hiểu, khó làm) kể cả đối với học sinh giỏi được chọn vào đội tuyển Tin học 11. Trong quá trình ôn luyện đội tuyển học sinh giỏi năm 2019 – 2020 tôi đã vận dụng các phương pháp mới với mục đích tạo hứng thú học lập trình cho học sinh: phương pháp hoạt động nhóm, phương pháp khám phá, phương pháp nghiên cứu trường hợp nhưng không hiệu quả. Cụ thể năm 2019 – 2020 đội tuyển học sinh giỏi của trường đạt thành tích không tốt: 01 em giải khuyến khích, 01 em không có giải. Nguyên nhân quan trọng là các em đội tuyển rất yếu về thuật toán. Xuất phát từ vấn đề đó tôi mạnh dạn chọn nghiên cứu chuyên đề “Ứng dụng thuật toán trong lập trình” và áp dụng vào trong quá trình giảng dạy đội tuyển trong năm học 2020 – 2021.
4 6. Mục đích của giải pháp sáng kiến 6.1 Đối với giáo viên: - Với sáng kiến kinh nghiệm ‘Ứng dụng thuật toán trong lập trình’, giáo viên tiếp tục củng cố nâng cao chuyên môn của bản thân. - Thông qua hệ thống kiến thức và bài tập được phân chia theo mức độ giáo viên có thể đánh giá kết quả học tập của học sinh. Qua các nội dung giáo viên rèn luyện tư duy logic và kĩ năng giải quyết vấn đề cho học sinh. - Thay đổi thực trạng của đội tuyển, khắc phục nhược điểm của giải pháp cũ, góp phần nâng cao chất lượng đội tuyển. 6.2 Đối với học sinh: - Hệ thống lại kiến thức cơ bản về thuật toán từ đó giúp học sinh có thể hiểu, nhớ và vận dụng các thuật toán cơ bản vào giải quyết các bài toán khó. - Biết cách tính độ phức tạp thuật toán từ đó biết cách lựa chọn thuật toán tối ưu. - Phát triển tư duy logic và hình thành kĩ năng giải quyết vấn đề. - Tiếp cận với một số thuật toán tối ưu trong lập trình. - Tạo hứng thú học lập trình cho học sinh. 7. Nội dung: 7.1 Thuyết minh giải pháp mới hoặc cải tiến - Tên giải pháp: Rèn kĩ năng lập trình cho học sinh giỏi thông qua khai thác tư duy một số thuật toán. - Nội dung: 7.1.1 Thuật toán Khái niệm: là dãy hữu hạn các thao tác được sắp 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 ta nhận được output cần tìm. Phân loại : + Thuật toán dưới dạng liệt kê + Thuật toán dưới dạng sơ đồ khối:
5 • : Thể hiện thao tác nhập xuất dữ liệu. • : Thể hiện thao tác tính toán. • : Thể hiện thao tác so sánh. • : Chỉ chiều thực hiện thao tác. Các bước xây dựng thuật toán: + Xác định bài toán: Xác định input và output. + Ý tưởng giải quyết bài toán. + Viết thuật toán. + Xác định độ phức tạp thuật toán. Ví dụ: Tìm giá trị lớn nhất của dãy số gồm N số nguyên a1, a2, ..., aN. + Xác định bài toán - Input: Số nguyên dương N và dãy N số nguyên a1,..., aN. - Output: Giá trị lớn nhất Max của dãy số. + Ý tưởng: • Khởi tạo giá trị Max = a1; • Lần lượt với i từ 2 đến N, so sánh giá trị số hạng ai với giá trị Max, nếu ai > Max thì Max nhận giá trị mới là ai. + Thuật toán: Liệt kê : Bước 1. Nhập N và dãy a1,…, aN; Bước 2. Max := a1, i := 2; Bước 3. Nếu i > N thì đưa ra giá trị Max rồi kết thúc; Bước 4. Bước 4.1. Nếu ai > Max thì Max := ai; Bước 4.2. i := i + 1 rồi quay lại bước 3;
6 Sơ đồ khối Độ phức tạp thuật toán: Tính độ phức tạp thuật toán: + Thời gian thực hiện một lệnh đơn không phụ thuộc vào kích thước dữ liệu nên sẽ là O(1). + Thời gian thực hiện một câu lệnh hợp thành sẽ được tính theo quy tắc cộng và quy tắc max. + Thời gian thực hiện câu lệnh điều kiện If: Giả sử thời gian thực hiện hai câu lệnh thành phần dạng đủ là f(n) và g(n) thì thời gian thực hiện của câu lệnh If sẽ được tính theo quy tắc max nên sẽ là O(max(f(n), g(n))).
7 + Thời gian thực hiện câu lệnh lặp sẽ áp dụng theo quy tắc nhân, nghĩa là O(k(n)F(n)) nếu k(n) là số lần lặp và f(n) là thời gian thực hiện câu lệnh trong vòng lặp. + Hàm và thủ tục là một chương trình độc lập nên về nguyên tắc có thể áp dụng các quy tắc trên để đánh giá thời gian thực hiện. Ví dụ 1: Thuật toán tìm giá trị lớn nhất có độ phúc tạp : O(N) Ví dụ 2: (1) S:= 0; (2) for i:= 1 to n do (3) S:= S + A[i]; (4) for i:= 1 to n do (5) For j:= 1 to n do (6) S:= S +1; Thời gian thực hiện chương trình phụ thuộc vào n: + Các lệnh (1), (3), (6) có thời gian thực hiện là O(1). + Lệnh lặp (2) có số lần lặp là n, như vậy thời gian thực hiện lệnh (2) là O(n) + Lệnh lặp (5) có số lần lặp là n, như vậy thời gian thực hiện là O(n). Lệnh lặp (4) có số lần lặp là n, như vậy thời gian thực hiện là O(n2) Vậy thời gian thực hiện đoạn chương trình trên là: max(O(1), O(n), O(n2)) = O(n2) Kết luận: Một bài toán sẽ có nhiều thuật toán, nhưng một thuật toán chỉ giải quyết được 1 bài toán. Đứng trước một bài toán học sinh sẽ hơn nhau ở việc lựa chọn thuật toán cho bài toán. Thuật toán có độ phức tạp càng nhỏ thì khả năng lập trình của học sinh càng tốt. Nếu học sinh muốn tiến sâu và tiến xa trong lập trình thì cần và rất cần học tốt phần thuật toán. Đây là hành trang đầu đời và có tính quyết định tới khả năng lập trình của học sinh trong tương lai.
8 7.1.2 Áp dụng thuật toán vào giải quyết các bài toán cơ bản và bài toán nâng cao trong lập trình pascal Tin học 11. (Phụ lục I) - Các bước tiến hành giải pháp: Bước 1: Hệ thống lại toàn bộ kiến thức cơ bản về thuật toán, đặc biết chú ý tới các thuật toán cơ bản đã học trong chương trình lớp 10. Bước 2: Xây dựng hệ thống bài tập mức độ vận dụng đối với từng thuật toán cơ bản trong bước 1.(thể hiện dưới dạng phiếu bài tập trong từng buổi học). Bước 3: Tìm hiểu một số thuật toán tối ưu (sắp xếp nhanh, tìm kiếm nhị phân, quay lui, quy hoạch động) và hệ thống bài tập mức độ vận dụng cao. Trong quá trình tiến hành giải pháp + bước 1: học sinh thuần túy là viết thuật toán, + bước 2: ngoài viết thuật toán học sinh bắt đầu lập trình trên máy, + bước 3: học sinh chủ yếu lập trình dựa trên ý tưởng thuật toán giải quyết bài toán. - Kết quả khi thực hiện giải pháp: + Sản phẩm được tạo ra từ giải pháp: (Phụ lục II) + Bảng số liệu đánh giá kết quả trước và sau khi thực hiện giải pháp : Kết quả thi học sinh giỏi văn hóa cấp tỉnh.
9 Năm 2019 – 2020: 1 giải khuyến khích. Năm 2020 – 2021: 1 giải 3, 1 giải khuyến khích.
10 7.2 Thuyết minh về phạm vi áp dụng sáng kiến Sáng kiến kinh nghiệm đề cập đến việc góp phần nâng cao hiệu quả ôn luyện đội tuyển văn hóa cấp tỉnh môn Tin học 11 cho đối tượng học sinh trường Trung học phổ thông Yên Dũng số 2 thông qua việc xây dựng hệ thống các thuật toán cơ bản, nâng cao và hệ thống các bài tập ở mức vận dụng hoặc vận dụng cao. 7.3. Thuyết minh về lợi ích kinh tế, xã hội của sáng kiến - Tạo tiền đề vững chắc cho học sinh khi bước vào ngành công nghệ. - Hình thành kĩ năng giải quyết vấn đề giúp học sinh giải quyết các vấn đề không chỉ trong học tập mà còn cả trong cuộc sống. Đây là một tiêu chí quan trọng được các công ti lớn sử dụng khi phỏng vấn xin việc. - Thông qua mạng lưới truyền thông và các sản phẩm công nghệ sơ khai của học sinh đã từng bước thay đổi quan điểm của phụ huynh về môn tin học. Từ đó niềm tin của phụ huynh vào con em, vào môn học và vào nhà trường ngày càng được nâng cao. * Cam kết : Chúng tôi cam đoan những điều khai trên đây là đúng sự thật và không sao chép hoặc vi phạm bản quyền KT. HIỆU TRƯỞNG Yên Dũng, ngày 5 tháng 4 năm 2021 PHÓ HIỆU TRƯỞNG Tác giả sáng kiến (Chữ ký, dấu) (Chữ ký) Lê Đình Khương Trần Thị Thơm
11 PHỤ LỤC I I. MỘT SỐ THUẬT TOÁN CƠ BẢN: 1. Kiểm tra nguyên tố . 1.1 Xác định bài toán - Input: N là là một số nguyên dương. - Output: "N là số nguyên tố " hoặc "N không là số nguyên tố ". 1.2. Ý tưởng: Ta nhắc lại định nghĩa: Một số nguyên dương N là số nguyên tố nếu nó có đúng hai ước khác nhau là và chính nó. Từ định nghĩa đó, ta suy ra - Nếu N = 1 thì N không là số nguyên tố; - Nếu 1 < N < 4 thì N là số nguyên tố; - Nếu N > 4 và không có ước số trong phạm vi từ 2 đến phần nguyên căn bậc hai của N thì N là số nguyên tố. 1.3. Thuật toán Liệt kê Bước 1: Nhập số nguyên dương N; Bước 2: Nếu N = 1 thì thông báo N không nguyên tố rồi kết thúc; Bước 3: Nếu N < 4 thì thông báo N nguyên tố rồi kết thúc; Bước 4: i ← 2; Bước 5: Nếu i > [√𝑁] thì thông báo N là sô nguyên tố rồi kết thúc. Bước 6: Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết thúc; Bước 7: i ← i + 1 rồi quay lại bước 5.
12 Sơ đồ khối: 1.4. Ví dụ mô phỏng: Với N= 29 2 3 4 5 6 2 3 29/2 29/3 29/4 29/5 45/2 45/3 Chia hết Chia hết Không Chia Không Không Không Không không ? không? hết 29 là số nguyên tố 45 không là số nguyên tố 1.5. Độ phức tạp thuật toán: O(√𝑁 ) 1.6. Bài tập vận dụng: (phiếu học tập 1 – Phụ lục II)
13 2. Sắp xếp tráo đổi: (EXCHANGE SORT) 2.1. Xác bài toán: - Input: Dãy A gồm N số nguyên a1, a2, …, aN. - Output: Dãy A đước sắp xếp lại thành dãy không giảm. 2.2. Ý tưởng: Với mỗi cặp số hạ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 sảy ra nữa. 2.3. Thuật toán:
14 2.4. Ví dụ mô phỏng: 2.5. Độ phức tạp thuật toán: O(N2) 2.6. Bài tập vận dụng: (Phiếu bài tập 3 – phụ lục II) 3. Tìm kiếm tuần tự: (SEQUENTIAL SEARCH) 3.1. Xác định bài toán: - Input: Dãy A gồm N số nguyên a1, a2, …, aN và khóa k. - Output: Chỉ số i mà ai = 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. 3.2. Ý tưởng: Tìm kiếm tuần tự là một kỹ thuật tìm kiếm đơn giản. Nội dung của nó như sau: Bắt đầu từ bản ghi đầu tiên, lần lượt so sánh khoá tìm kiếm với khoá tương ứng của các bản ghi trong danh sách, cho tới khi tìm thấy bản ghi mong muốn hoặc đã duyệt hết danh sách mà chưa thấy {Tìm kiếm tuần tự trên dãy khoá k[1..n]; hàm này thử tìm xem trong dãy có khoá nào = X không, nếu thấy nó trả về chỉ số của khoá ấy, nếu không thấy nó trả về 0. Có sử dụng một khoá phụ k[n+1] được gán giá trị = X}
15 3.3. Thuật toán: 3.4. Cài đặt function SequentialSearch(X: TKey): Integer; var i: Integer; begin i := 1; while (i
16 3.5. Ví dụ mô phỏng 3.6. Bài tập vận dụng: (Phiếu bài tập 3 – Phụ lục II) II. MỘT SỐ THUẬT TOÁN TỐI ƯU VÀ BÀI TẬP VẬN DỤNG: 1. Tìm kiếm nhị phân (BINARY SEARCH) Phương pháp tìm kiếm nhị phân được áp dụng trên mảng đã sắp thứ tự. Tức là A[1] ≤ A[2] ≤ ... ≤ A[n] 1.1 Ý tưởng: Giả sử cần tìm K trong đoạn A[L ... R] (L đoạn A[Giua] với Giua = (L + R) div 2 • Nếu A[Giua] < K nghĩa là đoạn A[L ... Giua] chứa toàn khóa < K. khi đó ta tiến hành tìm kiếm K trên đoạn A[Giua+1 ... R] • Nếu A[Giua] > X nghĩa là đoạn A[L ... Giua] chứa toàn khóa > K. khi đó ta tiến hành tìm kiếm K trên đoạn A[R ... Giua - 1] • Nếu A[Giua] = K thì tìm kiếm thành công (kết thúc quá trình tìm kiếm). Quá trình tìm kiếm sẽ thất bại nếu một bước nào đó đoạn tìm kiếm là rỗng tức là L > R 1.2 .Cài đặt * Code của ngôn ngữ lập trình PASCAL Function TK_NhiPhan(K: Key): integer; var L, R, Giua: integer; Begin L :=1; R := N; While (L
17 Begin Giua := (L + R) div 2; if A[Giua] = K then exit(Giua); {tìm thấy K thì trả ra vị trí của nó} if A[Giua]< K then L := Giua + 1 else R := Giua – 1; end; exit(0); {không tìm thấy x thì trả ra kết quả bằng 0} End; 1.3. Độ phức tạp thuật toán. Người ta chứng minh được độ phức tạp tính toán của thuật toán tìm kiếm nhị phân trong trường hợp tốt nhất là O(1), trong trường hợp xấu nhất là O(lgN). Tuy nhiên không nên quên rằng trước khi sử dụng phương pháp tìm kiếm nhị phân thì dãy khóa phải được sắp xếp, tức là thời gian chi phí cho việc sắp xếp phải được tính đến. 1.4. Bài tập vận dụng Bài 1. Dãy con (Đề thi HSG tỉnh Bắc Giang năm 2019 – 2020) Cho một dãy số nguyên dương a1, a2, ..., aN (10 < N < 100.000), ai ≤ 10.000 với mọi i=1..N và một số nguyên dương S (S < 100.000.000). Yêu cầu: Tìm độ dài nhỏ nhất của dãy con chứa các phần tử liên tiếp của dãy mà có tổng các phần tử lớn hơn hoặc bằng S. Dữ liệu vào: Đọc từ file SUB.INP gồm 2 dòng, dòng 1 chứa N và S ở dòng đầu. Dòng 2 chứa các phần tử của dãy. Dữ liệu ra: Kết quả ghi vào file SUB.OUT, chứa độ dài của dãy con tìm được.
18 Ví dụ : SUB.INP SUB.OUT 10 15 2 5 1 3 5 10 7 4 9 2 8 * Hướng dẫn giải: Bài toán này có thể giải theo 2 cách sau: Cách 1: dễ dàng giải bài toán với 1 cách làm trâu bò là xét 2 vòng lặp lồng nhau để tìm tất cả các tổng của các đoạn con đồng thời kết hợp tìm đoạn con có tổng >= S và có số phần tử ít nhất. Độ phức tạp là O(N2) Cách 2: Sử dụng phương pháp tìm kiếm nhị phân để giải bài toán: Gọi T[i] là tổng của các số A[1] đến A[i] (mảng tiền tố). Vì A[i] là các số dương => Dãy T là dãy tăng dần. Khi đó ta sẽ tiến hành tìm kiếm nhị phân trên dãy T như sau: * Xét T[i]: d = 1, c = i-1, g = (d + c) div 2 Nếu T[i] – T[g] >= S thì kq = min(kq, i – g) và tìm kq tiếp tục ở đoạn bên phải T[g] Nếu T[i] – T[g] < S thì tìm kq ở đoạn bên trái T[g]. Độ phức tạp là O(NlogN). Bài 2: Đếm tam giác (Đề thi tin học trẻ tỉnh Bắc Giang năm 2019 – 2020) Cho 3 dãy số dương A, B, C cùng có N phần tử. Hãy đếm xem có bao nhiêu bộ 3 số A[i], B[j] và C[k] mà 3 số này là 3 cạnh của 1 tam giác. Dữ liệu vào: từ file TRIANGLE.INP với cấu trúc: - Dòng đầu chứa số nguyên n (n
19 - Dòng thứ hai chứa các số A1, A2, ..., An. - Dòng thứ ba chứa các số B1, B2, ..., Bn. - Dòng thứ tư chứa các số C1, C2, ..., Cn. Các số Ai, Bi, Ci đều không vượt quá 104 và được ghi cách nhau bởi dấu cách. Dữ liệu ra: file văn bản TRIANGLE.OUT gồm một số S duy nhất là số lượng bộ ba số tìm được. TRIANGLE.IN TRIANGLE.OU TRIANGLE.IN TRIANGLE.OU P T P T 2 2 3 8 23 231 31 449 47 852 * Hướng dẫn: Chúng ta có thể giải bài này bằng 2 cách như sau: Cách 1: Bài toán được giải một cách dễ dàng bằng phương pháp vét cạn: dùng 3 vòng lặp lồng nhau để xét từng bộ ba số (ai, bj, ck). Độ phức tạp là O(N3). Cách 2: Ta có cách giải với độ phức tạp là O(N2*logN) như sau: Trước hết ta giải bài toán phụ như sau: Cho dãy không giảm A, và hai số x < y. Hãy sử dụng phương pháp tìm kiếm nhị phân để đếm xem có bao nhiêu số A[i] thỏa mã x < A[i] < y. Bài 3: Love in war (liw.pas) – Đề thi HSG cụm Yên Dũng năm 2019 – 2020 Nếu như nói đến chiến tranh là nói đến sự khốc liệt, sự mất mát, những đau khổ, những hy sinh lớn lao thì khi nói đến tình yêu ta nghĩ tới sự êm dịu, ngọt ngào, hạnh phúc. Chiến tranh có thể hủy diệt mọi thứ trên đường nó đi qua, những con người có thể bị bao thương tật, biến dạng hình thể trong chiến tranh, song tình yêu như một
20 sức mạnh không thể giập vùi, tình yêu ấy đã giúp bao anh lính bộ đội cụ Hồ đã chắc tay súng để bảo vệ tổ quốc và có niền tin vào một ngày mai đất nước độc lập thống nhất, tình yêu bị kìm nén ấy sẽ lại bùng cháy và thăng hoa cùng dân tộc. Những con người đấy phần đông là thanh niên, khi đó tại các trường đại học khi có lệnh tổng động viên nhiều sinh viên cả nam nữ gác bút nghiên đi theo tiếng gọi của lịch sử. Trường đại học hồi đó quản lý sinh viên bằng mã sinh viên, hai sinh viên khác nhau sẽ có 2 mã khác nhau. Trong khi học tập các cặp nam nữ sinh viên đã nảy sinh những tình cảm đẹp giành cho nhau. Các cặp nam nữ sinh viên nói trên ghi lại mã sinh viên của nhau trước khi lên đường nhập ngũ để ngày giải phóng họ dễ tìm lại nhau trong trường đại học. Năm 1975, khi chiến tranh kết thúc, đất nước hoàn toàn giải phóng, những sinh viên năm nào người đã ngã xuống trên mặt trận, một số may mắn còn lại và có điều kiện quay về trường tiếp tục học tập. Biết rằng có n sinh viên nam và m sinh viên nữ đã trở về trường. n sinh viên nam, trong hoàn cảnh chiến tranh khốc liệt, họ đã để thất lạc mã số của những người sinh viên nữ và chỉ nhớ được mã sinh viên của chính họ: b1, b2, b3, … bn; m sinh viên nữ vẫn giữ lại được mã sinh viên của mình: g1, g2, g3,….,gm và của các sinh viên nam mà họ đã dành tình cảm thời sinh viên trước đó: y1, y2, y3,….,ym (gi giữ yi). Cặp sinh viên bi và gj sẽ tìm được nhau nếu yj = b i. Yêu cầu: Em hãy thống kê xem có bao nhiêu cặp sinh viên nam nữ trong số trên có thể tìm được nhau và chỉ ra các cặp sinh viên đó. Dữ liệu vào: tệp LIW.INP gồm: - Dòng 1: n m - Dòng 2: mã sinh viên nam b1, b2, b3, … bn - Dòng 3: mã sinh viên nữ g1, g2, g3,….,gm - Dòng 4: mã các sinh viên nam mà sinh viên nữ đã dành tình cảm thời sinh viên trước đó: y1, y2, y3,….,ym (gi giữ yi). Dữ liệu ra: tệp LIW.OUT gồm: