Dãy số Fibonacci (Đề thi Tin học trẻ)

Bài toán – Dãy số Fibonacci (Dành cho học sinh THCS)

Như các bạn đã biết dãy số Fibonaci là dãy 1, 1, 2, 3, 5, 8, …. Dãy này cho bởi công thức đệ qui sau:

F₁ = 1, F₂ =1, F_n = F_n-1 + F_n-2 với n > 2

Chứng minh khẳng định sau:

Mọi số tự nhiên N đều có thể biểu diễn duy nhất dưới dạng tổng của một số số trong dãy số Fibonaci.

N = a_kF_k + a_k-1F_k-1 + …. a₁F₁

Với biểu diễn như trên ta nói N có biểu diễn Fibonaci là a_ka_k-1…a₂a₁.

Cho trước số tự nhiên N, hãy tìm biểu diễn Fibonaci của số N.

Input:

Tệp văn bản P11.INP bao gồm nhiều dòng. Mỗi dòng ghi một số tự nhiên.

Output:

Tệp P11.OUT ghi kết quả của chương trình: trên mỗi dòng ghi lại biểu diễn Fibonaci của các số tự nhiên tương ứng trong tệp P11.INP.

Lời giải bài toán Dãy số Fibonacci

Để chứng minh khẳng định trên, chúng ta có thể sử dụng phương pháp đệ quy. Dưới đây là cách chứng minh khẳng định đó:

Chứng minh khẳng định: Đầu tiên, chúng ta sẽ chứng minh rằng mọi số tự nhiên N đều có thể biểu diễn dưới dạng tổng của các số trong dãy số Fibonaci.

Để đơn giản, chúng ta sẽ chứng minh với N = 1, 2, 3, và 4.

N = 1: Ta có F1 = 1, vậy 1 có thể được biểu diễn dưới dạng tổng của 1 số trong dãy số Fibonaci, tức là 1 = F1.
N = 2: Ta có F1 = 1, F2 = 1, vậy 2 có thể được biểu diễn dưới dạng tổng của các số trong dãy số Fibonaci, tức là 2 = F2.
N = 3: Ta có F1 = 1, F2 = 1, F3 = 2, vậy 3 có thể được biểu diễn dưới dạng tổng của các số trong dãy số Fibonaci, tức là 3 = F2 + F1.
N = 4: Ta có F1 = 1, F2 = 1, F3 = 2, F4 = 3, vậy 4 có thể được biểu diễn dưới dạng tổng của các số trong dãy số Fibonaci, tức là 4 = F3 + F1.

Vậy, ta có thể suy ra rằng mọi số tự nhiên N đều có thể được biểu diễn dưới dạng tổng của các số trong dãy số Fibonaci.

Tiếp theo, chúng ta sẽ chứng minh rằng biểu diễn của N là duy nhất.

Giả sử tồn tại hai cách biểu diễn khác nhau của N, tức là N = akFk + ak-1Fk-1 + …. a1F1 = bmFm + bm-1Fm-1 + …. b1F1, với ak ≠ bm (với k < m).

Khi đó, ta sẽ có:

akFk + ak-1Fk-1 + …. a1F1 = bmFm + bm-1Fm-1 + …. b1F1

Do đó,

akFk + ak-1Fk-1 + …. a1F1 – bmFm – bm-1Fm-1 – …. b1F1 = 0

Giả sử rằng Fk là số Fibonaci lớn nhất xuất hiện trong biểu diễn của N

Chúng ta sẽ chứng minh bằng phương pháp quy nạp.

Bước cơ sở: Nếu k = 1, tức là N chỉ chứa duy nhất số Fibonaci F1, thì đẳng thức trên trở thành:

akF1 – bmFm – bm-1Fm-1 – …. b1F1 = 0

Do ak và bm không bằng nhau, ta có:

ak – bmFm-1 – bm-1Fm-2 – …. b1 = 0

Điều này dẫn đến mâu thuẫn, vì trái vế là một tổng của các số Fibonaci nhỏ hơn F1, trong khi vế phải là một số duy nhất. Vậy giả sử đúng đối với k = 1.

Bước giả sử: Giả sử đẳng thức trên đúng đối với k = p (p > 1), tức là:

akFk + ak-1Fk-1 + …. a1F1 = bmFm + bm-1Fm-1 + …. b1F1

Bước chứng minh: Chúng ta sẽ chứng minh đẳng thức trên đúng đối với k = p + 1.

Sử dụng công thức đệ qui của dãy số Fibonaci, ta có:

Fp+1 = Fp + Fp-1

Vậy ta có thể viết lại đẳng thức trên dưới dạng:

akFk + ak-1Fk-1 + …. a1F1 = bmFm + bm-1Fm-1 + …. b1F1

= (bm-1 + bm)Fm + bm-1Fm-1 + …. b1F1

= bm-1Fm-1 + bmFm + …. b1F1 + bmFm

= bm-1Fm-1 + (bm + bm-1)Fm + …. b1F1

= bm-1Fm-1 + Fp+1 + …. b1F1

Để đẳng thức trên đúng đối với k = p + 1, ta chỉ cần thay thế Fp+1 bằng biểu diễn đúng của Fp+1 dưới dạng tổng của các số trong dãy số Fibonaci, tức là Fp+1 = Fp + Fp-1, ta được:

akFk + ak-1Fk-1 + …. a1F1 = bm-1Fm-1 + Fp + Fp-1 + …. b1F1

Vậy giả sử đúng đối với k = p + 1.

Từ đó, theo nguyên lý quy nạp, ta có thể kết luận rằng mọi số tự nhiên N đều có thể biểu diễn duy nhất dưới dạng tổng của các số trong dãy số Fibonaci, với biểu diễn như sau: N = akFk + ak-1Fk-1 + …. a1F1, với biểu diễn Fibonaci là akak-1…a2a1.

Tiếp theo, để tìm biểu diễn Fibonaci của số N trong đầu vào, bạn có thể áp dụng thuật toán sau:

Đọc dữ liệu đầu vào từ tệp P11.INP, lấy các số tự nhiên N cần tìm biểu diễn Fibonaci.
Định nghĩa một hàm để tính dãy số Fibonaci đến số hạng thứ cần thiết (số hạng lớn nhất nhỏ hơn hoặc bằng N).
Tìm các hệ số ak tương ứng với dãy số Fibonaci đã tính được trong bước 2.
Ghi kết quả vào tệp P11.OUT theo định dạng yêu cầu.

Cài đặt bài toán Dãy Fibonacci với Python

Dưới đây là một ví dụ về cách thực hiện bằng ngôn ngữ Python:

# Hàm tính dãy số Fibonaci đến số hạng thứ n
def fib(n):
    fib_list = [1, 1]
    while len(fib_list) < n:
        fib_list.append(fib_list[-1] + fib_list[-2])
    return fib_list

# Đọc dữ liệu từ tệp P11.INP
with open("P11.INP", "r") as f_in:
    lines = f_in.readlines()
    for line in lines:
        N = int(line.strip())  # Chuyển đổi đầu vào từ chuỗi sang số nguyên

        # Tìm dãy số Fibonaci đến số hạng thứ cần thiết
        fib_list = fib(N)

        # Tìm hệ số ak tương ứng
        ak = []
        for i in range(len(fib_list)-1, -1, -1):
            if N >= fib_list[i]:
                ak.append(1)
                N -= fib_list[i]
            else:
                ak.append(0)

        # Ghi kết quả vào tệp P11.OUT
        with open("P11.OUT", "a") as f_out:
            f_out.write("".join(str(x) for x in ak[::-1]) + "\n")

Sau khi chạy chương trình, kết quả của biểu diễn Fibonaci của các số N trong đầu vào sẽ được ghi vào tệp P11.OUT theo định dạng yêu cầu. Ví dụ, nếu N = 5, kết quả sẽ được ghi là “10001” vào tệp P11.OUT. Lưu ý là chương trình sẽ ghi kết quả vào cuối tệp P11.OUT (sử dụng mode ‘a’ trong hàm open)…

Cài đặt bài toán Dãy Fibonacci với C++

Dưới đây là một ví dụ về cách thực hiện bằng ngôn ngữ C++:

#include <iostream>
#include <fstream>
using namespace std;

// Hàm tính số Fibonacci thứ n
int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    int a = 0;
    int b = 1;
    int c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

// Hàm chuyển đổi số nguyên sang chuỗi
string intToString(int num) {
    string str = "";
    while (num > 0) {
        str = to_string(num % 10) + str;
        num /= 10;
    }
    return str;
}

// Hàm tìm biểu diễn Fibonacci của số N
string findFibonacciRepresentation(int N) {
    string fibRepresentation = "";
    int k = 2; // Khởi tạo k = 2 vì F1 = F2 = 1
    while (N > 0) {
        int fk = fibonacci(k);
        if (fk <= N) {
            N -= fk;
            fibRepresentation += "1";
        } else {
            fibRepresentation += "0";
        }
        k++;
    }
    return fibRepresentation;
}

int main() {
    ifstream inputFile("P11.INP");
    ofstream outputFile("P11.OUT");

    if (!inputFile.is_open()) {
        cout << "Khong the mo file input!" << endl;
        return 0;
    }
    if (!outputFile.is_open()) {
        cout << "Khong the mo file output!" << endl;
        return 0;
    }

    int N;
    while (inputFile >> N) {
        string fibRepresentation = findFibonacciRepresentation(N);
        outputFile << fibRepresentation << endl;
    }

    inputFile.close();
    outputFile.close();

    return 0;
}

Để sử dụng đoạn mã trên, bạn cần tạo một tệp văn bản có tên là “P11.INP” chứa các số tự nhiên cần tìm biểu diễn Fibonacci. Kết quả sau khi chạy chương trình sẽ được ghi vào tệp văn bản “P11.OUT”. Chương trình sẽ đọc số từ tệp “P11.INP”, tính biểu diễn Fibonacci tương ứng và ghi kết quả vào “P11.OUT”. Vui lòng đảm bảo rằng bạn đã biên dịch và chạy chương trình trên môi trường C++ để có kết quả chính xác. Chúc bạn thành công!

Lập trình C/C++, Lập trình Python

Dãy số Fibonacci (Đề thi Tin học trẻ)

Bài toán – Dãy số Fibonacci (Dành cho học sinh THCS)

Lời giải bài toán Dãy số Fibonacci

Cài đặt bài toán Dãy Fibonacci với Python

Cài đặt bài toán Dãy Fibonacci với C++

Trả lời Hủy