Phần II. Tự luận (3 điểm)

Ví dụ về đoạn chương trình:

n = int(input())

sum = 0

for i in range(0, n):

sum = sum + i

print(sum)

Vòng lặp từ 0 đến n → thời gian thực hiện chương trình là T(n) = n + 3. Độ phức tạp của T(n) là O(n) theo quy tắc lấy max.

Trình bày thuật toán:

Bước 1. Nhập hai số nguyên dương a và b.

Bước 2. Tìm ước chung lớn nhất (UCLN) của a và b.

Bước 3. Duyệt qua các số từ 1 đến UCLN để tìm ra các ước là chẵn.

Bước 4. In danh sách các ước chung chẵn.

[1] Chuyển mô tả thành chương trình:

a = int(input())

b = int(input())

list = []

ucln = UCLN(a, b) → Làm mịn tại bước [2]

for i in range(1, ucln+1):

Kiểm tra i có thỏa mãn thì thêm vào danh sách → Làm mịn tại [3]

Hiển thị danh sách.

[2] Làm mịn cách tính ước chung lớn nhất:

Ý tưởng: UCLN của hai số a và b cũng là UCLN của b và phần dư của a chia cho b.

num1 = a, num2 = b.

Lặp đến khi num2 = 0:

Thực hiện phép chia để tìm ucln. → Làm mịn tại bước [4].

Trả về ước chung lớn nhất của a và b.

[3] Làm mịn thao tác kiểm tra số chẵn:

if ucln % i == 0 and ucln % 2 == 0:

list.append(i)

[4] Làm mịn dần thao tác chia giá trị:

Bước 1: Nếu b bằng 0, thì a là UCLN và thuật toán kết thúc.

Bước 2: Nếu b khác 0, hãy chia a cho b và lấy số dư r.

Bước 3: Gán b cho a và r cho b.

Bước 4: Quay lại Bước 1.

Hoàn thiện chương mô tả thuật toán:

a = int(input())

b = int(input())

list = []

num1 = a, num2 = b.

while num2 != 0:

if b == 0:thì a là ucln và thuật toán kết thúc.

Nếu b khác 0, hãy chia a cho b và lấy số dư r.

Gán b cho a và r cho b.

Quay lại.

for i in range(1, ucln+1):

if ucln % i == 0 and ucln % 2 == 0:

list.append(i)

Hiển thị danh sách.