Đề thi chọn HSG môn Tin học huyện Đạ Tẻh năm 2020 kèm lời giải

1. ĐỀ THI

Cấu trúc đề thi:

          Lưu ý: Dấu * được thay thế bởi pas, cpp hoặc py của ngôn ngữ lập trình được sử dụng tương ứng là Pascal, C++ hoặc Python

Câu 1: (6 điểm) Ước chung lớn nhất

          Cho hai số tự nhiên N, M (1 < N, M < 10⁹). Viết chương trình tìm ước chung lớn nhất của hai số N và M?

          Dữ liệu vào từ file: UCLN.INP

          – Dòng đầu tiên ghi hai số N và M cách nhau một khoảng trắng.

          Kết quả ra file: UCLN.OUT

          – Dòng đầu tiên ghi ước chung lớn nhất tìm được.

          Ví dụ:

Câu 2: (7 điểm) Điếm các số nguyên tố

          Cho dãy số nguyên gồm N phần tử A_i (0 < N < 10³, 0 < A_i < 10⁶). Viết chương trình đếm xem trong dãy số đã cho có bao nhiêu phần tử là số nguyên tố?

Dữ liệu vào từ file: NGUYENTO.INP

– Dòng đầu tiên ghi số N

– Dòng thứ hai ghi N số nguyên, các số cách nhau một khoảng trắng

Kết quả ra file: NGUYENTO.OUT

– Dòng đầu tiên ghi kết quả đếm được.

Ví dụ:

Câu 3: (7 điểm) Dãy theo quy luật

          Quy ước: Ứng với mỗi số tự nhiên x (0 < x < 10⁶), ta có số tự nhiên f(x) bằng tổng bình phương các chữ số của x.

Chằng hạn: x = 12 thì f(x) = 1² + 2² = 5

Từ x ta xây dựng dãy X_n theo quy ước như sau:

X₁ = x; X₂ = f(X₁); X₃ = f(X₂); …; X_n = f(X_n+1)  (với 1 <= i <= n < 10²)

Viết chương trình in ra dãy (X_n)?

Dữ liệu vào từ file: DAYXN.INP

– Dòng đầu tiên ghi số tự nhiên x và n, cách nhau một khoảng trắng.

Kết quả ra file: DAYXN.OUT

– Dòng đầu tiên ghi n phần tử đầu tiên của dãy, các số cách nhau một khoảng trắng.

Ví dụ:

———— Hết ———–

2. HƯỚNG DẪN GIẢI

Câu 1: Ước chung lớn nhất

def UCLN(a,b):
    while a != b:
        if a > b: a = a - b
        else: b = b - a
    return a
f_in = open("UCLN.INP","r"); f_out = open("UCLN.OUT","w");
line = f_in.readline()
a_line = line.split()
f_out.write(str(UCLN(int(a_line[0]),int(a_line[1]))))
f_in.close(); f_out.close();

Câu 2: Đếm các số nguyên tố

def is_prime(n):
    if n < 2: return False
    else:
        m = math.sqrt(n); i = 2;
        while (n%i != 0) and (i<m): i = i + 1
        if i>m: return True
        else: return False

import math
f_in = open("NGUYENTO.INP","r"); f_out = open("NGUYENTO.OUT","w");
n = int(f_in.readline())
line = f_in.readline(); text_a_line = line.split();

dem = 0
for i in range(0,n):
    if is_prime(int(text_a_line[i])) == True: dem = dem + 1
f_out.write(str(dem))
f_in.close(); f_out.close();

Câu 3: Dãy theo quy luật

def f(x):
    st = str(x); s = 0;
    for i in range(0,len(st)): s = s + int(st[i])**2
    return s

f_in = open("DAYXN.INP","r"); f_out = open("DAYXN.OUT","w");
line = f_in.readline(); text_a_line = line.split();
x, n = int(text_a_line[0]), int(text_a_line[1])

f_out.write(str(x))
for i in range(0,n-1):
    f_out.write(" " + str(f(x)))
    x = f(x)
f_in.close(); f_out.close();