Luyện thi HSG pascal

SỞ GIÁO DỤC VÀ ĐÀO TẠO

HÀ TĨNH

 

 (Đề thi có 2 trang)

KỲ THI CHỌN HỌC SINH GIỎI TỈNH CẤP THPT

NĂM HỌC 2012 - 2013

MÔN THI: TIN HỌC - LỚP 10

Thời gian: 180 phút (Không kể thời gian giao đề)

   Ký   hiệu

Thành viên

hiệu

Thành viên

TIN 3

Việt

3

Việt

TOAN 2

Tuấn

2

Tuấn

TIN 3

Thái

Do lỗi in ấn →

3

Thái

TIN 3

Anh

3

Anh

TOAN 2

Chính

2

Chính

SỞ GIÁO DỤC VÀ ĐÀO TẠO

HÀ TĨNH

KỲ THI CHỌN HỌC SINH GIỎI TỈNH CẤP THPT NĂM HỌC 2012 - 2013

HƯỚNG DẪN CHẤM THI

Môn thi: Tin học 10

Gợi ý đáp án

Thang điểm

Câu 1

6.0

- Xác định bài toán:

     Input: Hai số a, b (10 ≤ a ≤ b ≤ 10⁴)

     Output: Số lượng số thân thiện thuộc đoạn [a,b]

0.5

- Ý tưởng: Dùng 1 biến dem để lưu số lượng số thân thiện

          Xét lần lượt các số tự nhiên i từ a tới b

 Với mỗi số i xác định số tự nhiên j là đảo ngược của i

  Nếu UCLN(i,j)= 1 thì tăng biến dem lên 1

           Kết quả bài toán là dem

1.0

- Thuật toán:

Bước 1. Nhập hai số a và b;

Bước 2. i!a; dem ! 0;

Bước 3. Nếu i>b thì chuyển đến bước 13;

Bước 4. k!i, Songuoc!0;

Bước 5. Nếu k = 0 thì chuyển đến bước 8;

Bước 6. Songuoc!Songuoc*10+k mod 10;

Bước 7. k ! k div 10; rồi quay lại bước 5

Bước 8. k ! i;

Bước 9. Nếu k = Songuoc thì chuyển đến bước 11;

Bước 10. Nếu k > Songuoc thì  k ! k - Songuoc

     Ngược lại Songuoc ! Songuoc – k, rồi quay lại bước 9;

Bước 11. Nếu k=1 thì dem ! dem+1;

Bước 12. i!i+1 và quay lại bước 3;

Bước 13. Đưa ra kết quả dem rồi kết thúc.

4.5

Theo yêu cầu đề bài cho thấy các bước giải rất rõ ràng nên trong thuật toán có thể chia nhỏ từng phần để cho điểm.

Bước 1: Nhập dữ liệu: 0,5 điểm

Bước 2, bước 3, bước 12 thể hiện vòng lặp: 1 điểm

Bước 4 tới bước 7 tính số đảo ngược: 1 điểm

Bước 8 tới bước 11 xác định UCLN: 1,5 điểm

Bước 13: Đưa ra kết quả: 0,5 điểm

Câu 2.

7.0

- Xác định bài toán:

      Input: N và dãy A gồm N số tự nhiên

     Output: Số tự nhiên nhỏ nhất không xuất hiện trong dãy A

0.5

- Ý tưởng:

Nhận xét: Số tự nhiên nhỏ nhất luôn nằm trong đoạn từ 0 tới N.

Do vậy dùng dãy B[0..N] để đánh dấu những số đã có trong dãy A nằm trong đoạn từ 0 tới N. Ban đầu đánh dấu tất cả các phần tử của dãy B có giá trị là False. Tiếp theo đánh dấu trong dãy B những phần tử có trong dãy A như sau:

Xét i: 1 tới N, nếu A_i<=N thì đánh dấu B[A_i]ßTrue

      Tìm số tự nhiên đầu tiên j trong dãy B mà Bj=False, với j: 0 tới N

1.5

- Thuật toán:

Bước 1. Nhập N và dãy A₁, A₂,...,A_N;

Bước 2. i!0;

Bước 3. Nếu i>N thì chuyển đến bước 6;

Bước 4. B_i!False;

Bước 5. i!i+1; rồi quay lại bước 3;

Bước 6. i!1;

Bước 7. Nếu i>N thì và chuyển đến bước 10;

Bước 8. Nếu A_i<=N thì B[A_i]!true;

Bước 9. i!i+1 và quay lại bước 7;

Bước 10. j!0;

Bước 11. Nếu B_j=false thì thông báo j, rồi kết thúc;

Bước 12. j!j+1 và quay lại bước 11;

         

5.0

Câu 3.

7.0

- Xác định bài toán:

     Input: N và dãy A gồm N số nguyên dương lưu số thành viên

     Output: Số lượng nhóm đề tài

0.5

- Ý tưởng:

Xét lần lượng từng học sinh:1 .. N

  Ứng với từng học sinh đánh dấu các học sinh cùng nhóm, đồng thời tăng biến dem lên 1.

 Kết quả bài toán là dem

1.5

- Thuật toán:

Bước 1. Nhập N và dãy A₁, A₂,...,A_N;

Bước 2. i!1; dem ! 0;

Bước 3. Nếu i>N thì chuyển đến bước 11;

Bước 4: Nếu A_i<=0 thì chuyển sang bước thứ 10;

Bước 5. dem ! dem+1;

Bước 6. K!A_i;  j ! i; d ! 0;

Bước 7. Nếu (j>N) hoặc (d=K) thì và chuyển đến bước 10;

Bước 8. Nếu A_j=k thì A_j ! -K; d ! d+1;

Bước 9. j!j+1 và quay lại bước 7;

Bước 10. i!i+1 và quay lại bước 3

Bước 11. Đưa ra kết quả dem  rồi kết thúc.

5.0