Giải đề thi học sinh giỏi tin lớp 12-Lâm Đồng (Phần 2)

Tên kỳ thi

Kỳ thì chọn học sinh giỏi cấp tỉnh lớp 12, năm học 2021 – 2022. Sở Giáo dục và Đào tạo Lâm Đồng.

Ngày thi

Ngày: 07/01/2022.

Đề bài

Câu 2: Tên file bài làm: FIB2.*
Xâu Fibonacci thường được sử dụng để rèn luyện kỹ năng xử lý khi giới thiệu các giải thuật xử lý xâu. Xét dãy xâu F₀, F₁, F₂, … xây dựng theo quy tắc sau:

• F₀ = ‘a’
• F₁ = ‘b’
• F_n = F_{n – 2} + F_{n – 1}

Yêu cầu: Cho hai số nguyên n và k (0 ≤ k ≤ 45, k không vượt quá độ dài xâu F_n). Hãy xác định số lượng ký tự a xuất hiện trong k ký tự đầu tiên của xâu F_n
Dữ liệu vào: từ file văn bản FIB2.INP

• Dòng đầu ghi số nguyên T là số test cần xử lý (1 ≤ T ≤ 100)
• Mỗi dòng trong T dòng sau ghi hai số n và k cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra file văn bản FIB2.OUT

• Ứng với mỗi test trên một dòng dưới dạng một số nguyên.

Hướng dẫn làm bài

Thầy sử dụng ngôn ngữ lập trình Python nên thầy sẽ có hướng tiếp cận của Python. Các em làm bài bằng C/C++ thì có thể có cách trình bày khác thầy.
Bài này có 2 giai đoạn:

• • Giai đoạn 1:

Xác định dãy Fibonacci.

• Giai đoạn 2:

Đếm số lần xuất hiện ‘a’ trong k ký tự đầu tiên của dãy Fibinacci vừa tìm được (mỗi trường hợp sẽ có một dãy Fibonacci khác nhau).

Code tham khảo

# Xây dựng hàm
"""
Hàm khởi tạo Fibo
"""
def Fibo(n):
    if n == 0:
        return "a"
    elif n == 1:
        return "b"
    else:
        return Fibo(n - 2) + Fibo(n - 1)


"""
Hàm đếm số lượng ký tự a
"""
def Count_a(fibo, k):
    count = 0
    for i in range(k):
        if fibo[i] == 'a':
            count += 1
    return count


# ===main===
if __name__ == '__main__':
    # Mở file
    f_i = open("FIB2.INP", mode="r")
    f_o = open("FIB2.OUT", mode="w")

    # Đọc số lượng các trường hợp
    n = int(f_i.readline())
    # Đọc lần lượt từng dòng của từng trường hợp
    for i in range(n):
        line = f_i.readline()
        lst = line.split(" ")
        # Xác định n, k và dãy Fibo
        n = int(lst[0])
        k = int(lst[1])
        fibo = Fibo(n)

        # Xác định số lượng a thỏa mãn
        count_a = Count_a(fibo, k)

        # Hiển thị ra màn hình
        print("Day Fibo tai F", n, " la: ", fibo, " - Số lượng a thoa man la: ", count_a, sep="")

        # In ra tệp đầu ra
        f_o.writelines(str(count_a) + "\n")

    # Đóng tệp
    f_i.close()
    f_o.close()

Tham khảo

Cùng trong một đề này, bài 1