3.斐波那契(Fibonacci)数列的定义为:它的第 1项和第 2项分别为0和1,以后各项为其前两项之和。若斐波那契数列中的第 n 项用 Fb(n)表示，试编写出计算 Fib(n)的递归算法和非递归算法,以及求出各自的时间和空间复杂度 long Fib(int n);//求斐波那契数列中第 n项的递归算法 long FibN(int n); //求斐波那契数列中第 n项的非递归算法

递归算法：

long Fib(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    return Fib(n - 1) + Fib(n - 2);
}

递归算法的时间复杂度为 O(2^n)，空间复杂度为 O(n)。

非递归算法：

long FibN(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    long f1 = 1, f2 = 1, f3 = 0;
    for (int i = 3; i <= n; i++) {
        f3 = f1 + f2;
        f1 = f2;
        f2 = f3;
    }
    return f3;
}

非递归算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

相关问题

Fibonacci数列定义如下：（可使用函数递归） f1=1 f2=1 fn=fn-1+fn-2 (n>2) 求Fibonacci数列的第10项和第20项。

Fibonacci数列是一个经典的数学序列，其特点是每个数字（从第三个开始）等于前两个数字之和。使用递归函数来计算Fibonacci数列的第n项，我们可以定义如下的Python函数：

def fibonacci(n):
    if n <= 0:
        return "输入错误，n需要大于0"
    elif n == 1 or n == 2:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# 计算第10项和第20项
fibo_10th = fibonacci(10)
fibo_20th = fibonacci(20)

print(f"Fibonacci数列的第10项是：{fibo_10th}")
print(f"Fibonacci数列的第20项是：{fibo_20th}")

需要注意的是，由于递归的特性，这种方法在计算较大的Fibonacci数时会非常慢，因为会产生大量的重复计算。实际应用中，通常会使用动态规划或矩阵快速幂等优化算法来提高效率。

Matlab Fibonacci数列定义如下：（可使用函数递归） f1=1 f2=1 fn=fn-1+fn-2 (n>2) 求Fibonacci数列的第10项和第20项。

在Matlab中，你可以创建一个函数来计算Fibonacci数列的特定项。这里是一个使用递归定义的简单示例：

function [f10, f20] = fibonacci(n)
% 初始化前两项
if n == 1 || n == 2
    f10 = n;
else
    f1 = 1;
    f2 = 1;
    for i = 3:n
        fn = f1 + f2;
        f1 = f2;
        f2 = fn; % 更新值
    end
    f10 = fn; % 计算第10项
end

% 计算第20项
if n >= 11
    f20 = fibonacci(n - 9); % 因为已经计算了第1到第10项，所以从第11项开始只需加减即可
else
    error('Index out of range for Fibonacci sequence');
end
end

% 调用函数并打印结果
[f10, f20] = fibonacci(10);
fprintf('The 10th Fibonacci number is: %d\n', f10);
[f10, f20] = fibonacci(20);
fprintf('The 20th Fibonacci number is: %d\n', f20);

运行这个函数会输出Fibonacci数列的第10项和第20项。