Cấu trúc dữ liệu cơ bản

Danh sách bài tập

Note: Đề bài được tạo bằng pipeline scrape từ web trường (Moodle PHP) về, và reformat từng bài bằng Gemini 2.0 Flash (sửa lại markdown, nếu có ảnh, dịch ra latex hoặc sử dụng ASCII để minh họa). Để AI tự code rồi tự check trên Mimgo thì chắc cũng được nhưng mà thôi 🥴.

3.1. Mật khẩu hợp lệ

Một mật khẩu của một tài khoản trên trang web môn học được coi là hợp lệ nếu có đủ các yếu tố sau:

1. Độ dài từ 8 đến 100 ký tự.
2. Có chữ cái in hoa.
3. Có chữ cái thường.
4. Có số.
5. Có ký tự đặc biệt là một trong các ký tự sau: ~!@#$%^&*.

• Viết chương trình nhập vào một mật khẩu, kiểm tra xem mật khẩu đó có hợp lệ theo quy tắc ở trên hay không?
• Hoàn thành hàm checkPassword(s), hàm này trả về True nếu mật khẩu là hợp lệ, trả lại False nếu mật khẩu không hợp lệ.

def checkPassword(s):
    if not (8 <= len(s) <= 100):
        return False
    has_upper = any(c.isupper() for c in s)
    has_lower = any(c.islower() for c in s)
    has_digit = any(c.isdigit() for c in s)
    has_special = any(c in "~!@#$%^&*" for c in s)
    return has_upper and has_lower and has_digit and has_special

3.2 Tính phương sai

Viết chương trình tính giá trị trung bình phương sai, độ lệch chuẩn của  một danh sách các số thực:

• Giá trị trung bình là trung bình cộng của các giá trị trong danh sách.
• Phương sai tính bằng công thức:

\[\delta = \frac{1}{n} \sum_{i=1}^n (x_i - e)^2\]

• Trong đó $e$ là giá trị trung bình, $x_i$ là giá trị thứ $i$ của danh sách.
• Độ lệch chuẩn được tính bằng căn bậc 2 của phương sai.

import math

def mean(s):
    return sum(s) / len(s)

def variance(s):
    e = mean(s)
    return sum((x - e) ** 2 for x in s) / len(s)

def standarddeviation(s):
    return math.sqrt(variance(s))

3.3 Góc giữa hai vector

Viết chương trình tính góc giữa 2 vector:

• Hoàn thiện hàm cosineb2v(u,v), hàm này trả về giá trị cosine của góc giữa hai vector u và v theo công thức sau:

\[\cos(u, v) = \frac{(u \cdot v)}{\|u\| \times \|v\|}\]

• Trong đó $(u \cdot v) = u_1 v_1 + u_2 v_2$ và $ u = (u_1, u_2), v = (v_1, v_2) $. Nếu vector có nhiều hơn hai thành phần, tiếp tục thêm + $u_3v_3 + u_4v_4$…

\[\| u \| = \sqrt{u_1^2 + u_2^2}\]

import math

def cosineb2v(u, v):
    dot_product = sum(ux * vx for ux, vx in zip(u, v))
    norm_u = math.sqrt(sum(ux ** 2 for ux in u))
    norm_v = math.sqrt(sum(vx ** 2 for vx in v))
    if norm_u == 0 or norm_v == 0:
        return 0
    return dot_product / (norm_u * norm_v)

3.4 Sắp xếp chẵn lẻ

Hoàn thiện hàm customSort(a):

• Hàm thực hiện sắp xếp các phần tử trong danh sách a theo thứ tự như sau:
• Các phần tử chẵn bên trái, lẻ bên phải, các số chẵn tăng dần, các số lẻ sắp xếp giảm dần
• Kết quả trả về là 1 danh sách được sắp xếp theo thứ tự trên

Ví dụ:

• a = [1,2,3,4,5,6,7,8,9,10]

Kết quả trả về là:

• [2,4,6,8,10,9,7,5,3,1]

def customSort(a):
    even = sorted([x for x in a if x % 2 == 0])
    odd = sorted([x for x in a if x % 2 != 0], reverse=True)
    return even + odd

3.5 Cộng 2 số nguyên

Cho 2 số nguyên a, b được biểu diễn bởi 2 danh sách. Ví dụ:

• a = [1,2,4,5]
• b = [7,8,9]

Thực hiện phép cộng 2 số a, b trên 2 danh sách theo quy tắc cộng thông thường. kết quả trả về là 1 danh sách biểu diễn tổng a+b:

• c = [2,0,3,4]

def addNum(a, b):
    a = a[::-1]
    b = b[::-1]
    max_len = max(len(a), len(b))
    result = []
    carry = 0

    for i in range(max_len):
        digit_a = a[i] if i < len(a) else 0
        digit_b = b[i] if i < len(b) else 0
        total = digit_a + digit_b + carry
        result.append(total % 10)
        carry = total // 10

    if carry:
        result.append(carry)

    return result[::-1]

3.6 Nhân số nguyên lớn

Giống như bài cộng số nguyên 3.5, ở bài này chúng ta cần viết chương trình thực hiện nhân 2 số nguyên, trong đó mỗi số được lưu trong 1 danh sách. Ví dụ:

• a = [1,2,3,4]
• b = [4,5,6]

Để thực hiện phép nhân, ta lấy từng giá trị của b (từ phải sang trái) nhân với các phần tử của a theo cách tính phép nhân thông thường. Với mỗi số hạng lùi dần về phía bên trái của b, ta thêm 1 số 0 vào danh sách kết quả.

• 6 x a = 6 x [1,2,3,4] = [7,4,0,4]
• 5 x a = 5 x [1,2,3,4] = [6,1,7,0], thêm 1 số 0 vào kết quả [6,1,7,0,0]
• 4 x a = 4 x [1,2,3,4] =[4,9,3,6] thêm 2 số 0 vào kết quả [4,9,3,6,0,0]

Giờ kết quả của phép nhân là việc cộng các mảng kết quả của các phép nhân trung gian ở trên. Khi đó chúng ta quay trở lại bài toán phép cộng số nguyên trên mảng (bài 3.5)

def multiNum(a, b):
    def multiply_single(a, digit):
        a = a[::-1]
        carry = 0
        result = []
        for x in a:
            product = x * digit + carry
            result.append(product % 10)
            carry = product // 10
        if carry:
            result.append(carry)
        return result[::-1]

    def addNum(x, y):
        x = x[::-1]
        y = y[::-1]
        max_len = max(len(x), len(y))
        result = []
        carry = 0
        for i in range(max_len):
            xi = x[i] if i < len(x) else 0
            yi = y[i] if i < len(y) else 0
            s = xi + yi + carry
            result.append(s % 10)
            carry = s // 10
        if carry:
            result.append(carry)
        return result[::-1]

    result = [0]
    b = b[::-1]
    for i in range(len(b)):
        product = multiply_single(a, b[i])
        product += [0] * i
        result = addNum(result, product)

    return result