分治法求斐波那契数列代码

下面是使用分治法求解斐波那契数列的Python代码实现：

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

这段代码使用递归调用实现了分治法求解斐波那契数列。当n为0或1时，直接返回n；否则，将问题分解为计算F(n-1)和F(n-2)两个子问题，然后递归调用fib函数解决这两个子问题，并将它们的解合并为F(n)的解。

相关问题

用分治法求斐波那契数列

斐波那契数列可以使用递归的方式求解，但是随着n的增大，递归的时间复杂度将呈指数级别长，因此可以采分治法来降时间复杂度。

具体的做法是将斐波那契数列的求解划分为两个子问题：求解第n-1个斐波那契数和第n-2个斐波那契数。然后递归地求解这两个子问题，直到n=1或n=2时返回结果。最终将两个子问题的结果相加即可得到第n个斐波那契数。

下面是使用分治法求解斐波那契数列的示例代码：

def fibonacci(n):
    if n <= 0:
        return None
    if n == 1 or n == 2:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

这个代码可以正常工作，但是当n比较大时，递归的层数将非常深，导致栈溢出。因此，我们可以使用尾递归优化，将递归转化为循环，避免栈溢出的问题。

def fibonacci(n):
    return fibonacci_iter(n, 1, 1)

def fibonacci_iter(n, a, b):
    if n == 1:
        return b
    else:
        return fibonacci_iter(n-1, b, a+b)

这个代码使用了尾递归优化，可以有效避免栈溢出的问题。同时，由于不需要保存递归调用的栈帧，因此空间复杂度也得到了优化。

c++分治法求斐波那契数列

分治法求解斐波那契数列的时间复杂度为 O(logn)。下面是使用 C++ 实现的代码：

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        int a = fibonacci(n / 2);
        int b = fibonacci(n / 2 + 1);
        if (n % 2 == 0) {
            return a * (2 * b - a);
        } else {
            return b * b + a * a;
        }
    }
}

int main() {
    int n;
    cout << "Enter a positive integer: ";
    cin >> n;
    cout << "The " << n << "th Fibonacci number is " << fibonacci(n) << endl;
    return 0;
}

通过递归的方式，将大问题拆分为两个规模更小的子问题，然后递归求解，最终将子问题的解合并得到原问题的解。在这个过程中，可以利用斐波那契数列的性质，将问题规模缩小到原来的一半。