Đề cương ôn tập Học kì 2 Tin học 10 năm 2024–2025 trường THPT Chuyên Lương Văn Chánh (Đắk Lắk)

Sở Giáo dục và Đào tạo Phú Yên ĐỀ CƯƠNG ÔN TẬP HỌC KỲ II Trường THPT Chuyên Lương Văn Chánh Năm học: 2024 - 2025 Tổ Tin học Môn: Tin - Lớp: 10 Chương trình: Chuyên

I. NỘI DUNG ÔN TẬP

1. Chuyên đề: Quy hoạch động:

+ Hiểu cách nhận diện được bài toán có thể giải bằng kỹ thuật Quy hoạch động;

+ Biết và giải thích được các bước cần thực hiện khi xây dựng thuật toán theo kỹ thuật quy hoạch động;

+Thiết kế được thuật toán theo kỹ thuật Quy hoạch động cho một số bài toán đơn giản;

+ Viết được chương trình có sử dụng kỹ thuật Quy hoạch động cho một vài bài toán điển hình.

2. Chuyên đề sắp xếp và tìm kiếm:

- Biết được tầm quan trọng của các thuật toán sắp xếp

- Biết ba thuật toán sắp xếp phổ biến: sắp xếp đơn giản, QuickSort, MergeSort

- Cách sử dụng các thuật toán sắp xếp trong thư viện chuẩn;

- Vận dụng các thuật toán tìm kiếm tuần tự và thuật toán tìm kiếm nhị phân để giải một số bài toán điển hình.

3. Chuyên đề đồ thị:

- Biết được các khái niệm cơ bản liên quan đến mô hình đồ thị: đỉnh, cạnh/cung, đường đi, chu trình, tính liên thông, thành phần liên thông, cây khung, trọng số, ma trận trọng số.

- Biết cách thể hiện đồ thị khi lập trình.

- Biết được thuật toán duyệt đồ thị BFS và DFS, thuật toán tìm đường đi ngắn nhất Dijkstra, Floyd, thuật toán tìm cây khung nhỏ nhất Prim và Kruskal

- Cài đặt được các cách biểu diễn đồ thị

- Vận dụng được các thuật toán duyệt BFS và DFS, thuật toán tìm đường đi ngắn nhất Dijkstra, Floyd, thuật toán tìm cây khung nhỏ nhất Prim và Kruskal để giải một số bài toán và cài đặt được trên máy tính.

II. MỘT SỐ BÀI TẬP THAM KHẢO

Bài 1. Hoán vị

Trong một cuốn sách cổ có ghi lại rất nhiều các con số bí ẩn mà chúng có mối liên hệ với số 30. Sau một thời gian nghiên cứu, các chuyên gia đã tìm được cách giải mã các số đó: hoán vị các chữ số của số bí ẩn để thu được một bội số lớn nhất của 30.

Yêu cầu: Hãy viết chương trình để giúp các chuyên gia giải mã các số bí ẩn đó.

Dữ liệu vào: Gồm một dòng duy nhất chứa số nguyên dương ??, với ?? có tối đa 10 chữ số là số cần giải mã.

Kết quả: Gồm một số nguyên duy nhất là số lớn nhất chia hết cho 30 tìm được bằng cách hoán vị các chữ số của ??. Nếu không tìm thấy thì đưa ra −1.

Ví dụ:

Input Output 1002 2100 12498567859 -1 Bài 2: Chọn quà

Để khích lệ tinh thần học tập của học sinh cô giáo chủ nhiệm tổ chức chương trình tặng quà cho học sinh của lớp. Cô giáo chuẩn bị n hộp quà được đánh số thứ tự từ 1 đến n. Trên hộp quà thứ i có dán nhãn ai và trong đó có món quà giá trị wi. Cô giáo yêu cầu học sinh có thể chọn một hoặc nhiều hộp quà theo thứ tự từ hộp thứ 1 đến hộp thứ n, hộp quà chọn sau phải có nhãn lớn hơn hộp quà chọn trước, tức là:

൜ ??????< ??????< ⋯< ?????? ??≤ ????< ????< ⋯< ????≤??

Yêu cầu: Em hãy chọn cho mình các món quà như yêu cầu của cô giáo để có tổng giá trị lớn nhất.

Dữ liệu: Vào từ file văn bản GIFRTS.INP trong đó:

- Dòng 1 chứa số nguyên ?? (?? ≤ 103)

- n dòng tiếp theo, mỗi dòng ghi hai số nguyên dương ??i và wi (∀??: ??i ≤ 109, wi ≤ 106) tương ứng là nhãn và giá trị món quà trong hộp quà thứ i.

Các số trên một dòng được ghi cách nhau bởi dấu cách

Kết quả: Ghi ra file văn bản GIFRTS.OUT một số nguyên duy nhất là tổng giá trị các món quà được chọn

Ví dụ:

GIFRTS.INP GIFRTS.OUT Giải thích

5

5 15

3 5

4 7

5 1

2 8

15 Chọn hộp quà thứ 1

5

4 10

1 3

5 15

3 10

4 12

25 Có thể chọn hộp quà thứ 1, 3. Hoặc có thể chọn hộp quà thứ 2, 4, 5