Ngày sáng kiến được áp dụng
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 đóng vai trò quan trọng trong lập trình, và để trở thành lập trình viên giỏi, học sinh cần phải học thuật toán một cách cẩn thận và chuyên sâu Dưới đây là một số giải pháp mà 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.
Phương pháp thuyết trình là một giải pháp hiệu quả trong dạy học, trong đó lời nói của giáo viên đóng vai trò chủ đạo Ưu điểm nổi bật của phương pháp này là khả năng truyền tải một khối lượng lớn kiến thức tin học đến với người học.
Phương pháp thuyết trình hiện nay còn hạn chế, khiến học sinh trở nên thụ động trong việc tiếp nhận và lưu giữ kiến thức Phương pháp này chủ yếu chỉ dừng lại ở việc tái hiện lại kiến thức mà chưa khuyến khích sự thông hiểu và vận dụng của học sinh Hơn nữa, học sinh chỉ được rèn luyện kỹ năng ghi nhớ mà thiếu đi khả 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 trong tương lai của các em.
Phương pháp vấn đáp là một giải pháp hiệu quả trong dạy học, nơi giáo viên đưa ra câu hỏi và học sinh trả lời, khuyến khích tranh luận giữa học sinh và giáo viên Phương pháp này không chỉ giúp học sinh tiếp thu kiến thức một cách sâu sắc mà còn phát triển kỹ năng tư duy phản biện và giao tiếp.
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
Khi áp dụng phương pháp này, giáo viên cần chuẩn bị một hệ thống bài tập với nhiều mức độ nhận thức khác nhau Tuy nhiên, thời gian ôn tập cho mỗi chủ đề thường ngắn, trong khi lượng kiến thức cần truyền tải lại lớn, khiến giáo viên khó có thể kiểm tra toàn diện kiến thức đã tiếp thu và 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:
Hai giải pháp trên cho thấy rằng việc nắm vững kiến thức thuật toán chủ yếu chỉ là ghi nhớ thụ động và học thuộc các thuật toán cơ bản trong sách giáo khoa Tin Học 10 Điều này dẫn đến tình trạng học sinh lớp 11 gặp khó khăn trong việc học lập trình, khiến môn học trở nên khó hiểu và khó thực hành, ngay cả đối với những học sinh giỏi được chọn vào đội tuyển Tin học.
Trong quá trình ôn luyện đội tuyển học sinh giỏi năm 2019 – 2020, tôi đã áp dụng nhiều phương pháp mới như hoạt động nhóm, khám phá và nghiên cứu trường hợp nhằm tạo hứng thú học lập trình cho học sinh Tuy nhiên, những phương pháp này không mang lại hiệu quả như mong đợi, khi đội tuyển chỉ đạt được một giải khuyến khích và một 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
Tôi đã quyết định nghiên cứu chuyên đề “Ứng dụng thuật toán trong lập trình” nhằm áp dụng vào quá trình giảng dạy đội tuyển trong năm học 2020 – 2021.
6 Mục đích của giải pháp sáng kiế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 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 Đồng thời, các nội dung này giúp 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 kiến thức cơ bản về thuật toán giúp học sinh hiểu rõ và ghi nhớ các thuật toán thiết yếu, từ đó có khả năng áp dụng chúng vào việc 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.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
Khái niệm thuật toán là một dãy hữu hạn các thao tác được sắp xếp theo trình tự xác định Mục đích của thuật toán là từ đầu vào (input) thực hiện các thao tác để đạt được đầu ra (output) mong muốn.
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:
• : 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
+ 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
- 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ố
• 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
Bước 1 Nhập N và dãy a1,…, aN;
Bước 3 Nếu i > N thì đưa ra giá trị Max rồi kết thúc;
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;
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 phụ thuộc vào thời gian thực hiện của hai câu lệnh thành phần, được ký hiệu là f(n) và g(n) Thời gian thực hiện tổng thể của câu lệnh If sẽ được xác định dựa trên các hàm này.
If sẽ được tính theo quy tắc max nên sẽ là O(max(f(n), g(n)))
Thời gian thực hiện của câu lệnh lặp được tính theo quy tắc nhân, cụ thể là O(k(n)F(n)), trong đó k(n) đại diện cho số lần lặp và F(n) là thời gian thực hiện của câu lệnh trong mỗi 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)
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) và lệnh lặp (5) đều có số lần lặp là n, do đó thời gian thực hiện của cả hai lệnh này đều là O(n).
(4) có số lần lặp là n, như vậy thời gian thực hiện là O(n 2 )
Vậy thời gian thực hiện đoạn chương trình trên là: max(O(1), O(n), O(n 2 )) = O(n 2 )
Kết luận, mỗi bài toán có thể được giải quyết bằng nhiều thuật toán, nhưng mỗi thuật toán chỉ phù hợp với một bài toán cụ thể Sự khác biệt giữa các học sinh nằm ở khả năng lựa chọn thuật toán phù hợp Thuật toán có độ phức tạp thấp giúp nâng cao khả năng lập trình của học sinh Để phát triển sâu và xa trong lĩnh vực lập trình, học sinh cần chú trọng học tốt phần thuật toán, vì đây là nền tảng quyết định cho khả năng lập trình trong tương lai.
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
Sự cần thiết phải áp dụng giải pháp sáng kiến
Hai giải pháp trên chỉ giúp học sinh lưu giữ kiến thức thuật toán một cách thụ động và ghi nhớ máy móc, chủ yếu dừng lại ở các thuật toán cơ bản trong sách giáo khoa Tin Học 10 Kết quả là, khi bước vào lớp 11, nhiều học sinh cảm thấy môn lập trình trở nên khó khăn, cả về lý thuyết lẫn thực hành, ngay cả với những học sinh xuất sắc được chọn vào đội tuyển Tin học.
Trong quá trình ôn luyện đội tuyển học sinh giỏi năm 2019 – 2020, tôi đã áp dụng các phương pháp mới như hoạt động nhóm, khám phá và nghiên cứu trường hợp nhằm tạo hứng thú học lập trình cho học sinh Tuy nhiên, những phương pháp này không mang lại hiệu quả như mong đợi, khi đội tuyển chỉ đạt được 01 giải khuyến khích và 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
Trong năm học 2020 – 2021, tôi quyết định nghiên cứu chuyên đề "Ứng dụng thuật toán trong lập trình" và áp dụng kiến thức này vào quá trình giảng dạy đội tuyển.
Mục đích của giải pháp
- 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 phân chia theo mức độ, giáo viên có thể đánh giá hiệu quả học tập của học sinh Đồng thời, các nội dung này giúp 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 kiến thức cơ bản về thuật toán giúp học sinh hiểu, nhớ và áp dụng các thuật toán cơ bản vào việc 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.
Nội dung
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
Khái niệm thuật toán là một 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, nhằm mục đích chuyển đổi input thành output mong muốn sau khi thực hiện toàn bộ các thao tác đó.
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:
• : 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
+ 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
- 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ố
• 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
Bước 1 Nhập N và dãy a1,…, aN;
Bước 3 Nếu i > N thì đưa ra giá trị Max rồi kết thúc;
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;
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ủa câu lệnh điều kiện If được xác định dựa trên thời gian thực hiện của hai câu lệnh thành phần, ký hiệu là f(n) và g(n).
If sẽ được tính theo quy tắc max nên sẽ là O(max(f(n), g(n)))
Thời gian thực hiện của câu lệnh lặp được xác định theo quy tắc nhân, cụ thể là O(k(n)F(n)), trong đó k(n) đại diện cho số lần lặp và F(n) là thời gian thực hiện của câu lệnh trong mỗi 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)
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) và lệnh lặp (5) đều có số lần lặp là n, do đó thời gian thực hiện của cả hai lệnh này đều là O(n).
(4) có số lần lặp là n, như vậy thời gian thực hiện là O(n 2 )
Vậy thời gian thực hiện đoạn chương trình trên là: max(O(1), O(n), O(n 2 )) = O(n 2 )
Kết luận, mỗi bài toán có thể giải quyết bằng nhiều thuật toán, nhưng mỗi thuật toán chỉ áp dụng cho một bài toán cụ thể Sự khác biệt giữa các học sinh nằm ở khả năng lựa chọn thuật toán phù hợp Thuật toán với độ phức tạp thấp giúp nâng cao kỹ năng lập trình của học sinh Để tiến xa trong lĩnh vực lập trình, việc học tốt thuật toán là rất cần thiết, vì đây là nền tảng quan trọng quyết định khả năng lập trình trong tương lai của các em.
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: Thiết lập hệ thống bài tập ứng dụng cho từng thuật toán cơ bản đã được đề cập ở bước 1, thể hiện qua phiếu bài tập trong mỗi buổi học.
Bước 3: Nghiên cứu các thuật toán tối ưu như sắp xếp nhanh, tìm kiếm nhị phân, quay lui và quy hoạch động, đồng thời thực hành với các bài tập có độ khó cao để nâng cao kỹ năng.
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
Năm 2020 – 2021: 1 giải 3, 1 giải khuyến khích.
Thuyết minh về phạm vi áp dụng sáng kiến
Sáng kiến kinh nghiệm nhằm 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 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 và nâng cao, cùng với các bài tập ở mức vận dụng hoặc vận dụng cao.
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 đề không chỉ giúp học sinh vượt qua khó khăn trong học tập mà còn hỗ trợ họ trong cuộc sống hàng ngày Đây là một tiêu chí quan trọng mà các công ty lớn thường xem xét trong quá trình phỏng vấn xin việc.
Mạng lưới truyền thông và các sản phẩm công nghệ sơ khai do học sinh phát triển đã góp phần thay đổi quan điểm của phụ huynh về môn tin học Điều này đã nâng cao niềm tin của phụ huynh vào khả năng của con em, giá trị của môn học cũng như uy tín của nhà trường.
* 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
Yên Dũng, ngày 5 tháng 4 năm 2021
I MỘT SỐ THUẬT TOÁN CƠ BẢ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ố
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 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
Chia hết không ? Không Không Không Không Chia hết không?
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)
2 Sắp xếp tráo đổi: (EXCHANGE SORT)
- 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.5 Độ phức tạp thuật toán: O(N 2 )
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)
- 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
Tìm kiếm tuần tự là một kỹ thuật đơn giản, bắt đầu từ bản ghi đầu tiên và so sánh khoá tìm kiếm với các khoá trong danh sách cho đến khi tìm thấy bản ghi mong muốn hoặc duyệt hết danh sách Hàm tìm kiếm tuần tự kiểm tra xem trong dãy khoá k[1 n] có khoá nào bằng X không; nếu có, nó trả về chỉ số của khoá đó, ngược lại, trả về 0 Một khoá phụ k[n+1] được sử dụng và gán giá trị bằng X để hỗ trợ quá trình tìm kiếm.
3.4 Cài đặt function SequentialSearch(X: TKey): Integer; var i: Integer; begin i := 1; while (i 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, quá trình tìm kiếm thành công và kết thúc Ngược lại, nếu trong quá trình tìm kiếm mà đoạn tìm kiếm trở nên rỗng (tức là L > R), thì tìm kiếm sẽ thất bại.
* Code của ngôn ngữ lập trình PASCAL
Function TK_NhiPhan(K: Key): integer; var L, R, Giua: integer;
Để tìm kiếm một giá trị K trong mảng A, ta sử dụng phương pháp tìm kiếm nhị phân Đầu tiên, tính chỉ số giữa Giua bằng công thức Giua := (L + R) div 2 Nếu A[Giua] bằng K, ta trả về vị trí Giua Nếu A[Giua] nhỏ hơn K, ta cập nhật L thành Giua + 1; ngược lại, R được cập nhật thành Giua - 1 Nếu không tìm thấy K, hàm sẽ trả về 0.
1.3 Độ phức tạp thuật toán
Thuật toán tìm kiếm nhị phân có độ phức tạp tính toán tốt nhất là O(1) và xấu nhất là O(lgN) Tuy nhiên, cần lưu ý rằng trước khi áp dụng phương pháp này, dãy khóa phải được sắp xếp, do đó, thời gian chi phí cho việc sắp xếp cũng cần được tính đến.
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
Bài toán này có thể giải theo 2 cách sau:
Để giải bài toán hiệu quả, bạn có thể sử dụng phương pháp với hai vòng lặp lồng nhau nhằm tìm tất cả các tổng của các đoạn con Đồng thời, cách này cũng giúp xác định đoạn con có tổng cụ thể mà bạn đang tìm kiếm.
>= S và có số phần tử ít nhất Độ phức tạp là O(N 2 )
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:
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