从斐波那契序列体会编程算法

1、纯递归，巨慢

function F = fibo01(n)

%   The recursion solution of the fibonacci sequence

%   call the fibo(n) , n is a positive integer number

arguments

   n (1,1) {mustBeInteger,mustBePositive}

end

if n <= 2

   F = 1;

else

   F = fibo01(n-1)+fibo01(n-2);

end

end

2、加入备忘录，自底向上，预分配内存，空间换时间，快多了

function  F = fibo02(n)

%The memo and End-Top Method of the fibonacci sequences

%   call fibo02(n) to get the ans, n is a positive integer

arguments

   n (1,1) {mustBeInteger,mustBePositive}

end

memo = sym(ones(1,n));  % preallocate the memory and tradeoff space with time

if n <= 2

   F = memo(n);

else

   for i = 3:n

       memo(i) = memo(i-1)+ memo(i-2);

   end

   F = memo(n);

end

3、加入备忘录，自顶向上，还是递归

function F = fibo03(n)

%the memo version of fibonacci sequences

%   call fibo03(n) ,here n is a positive  integer number

arguments

   n (1,1) {mustBeInteger,mustBePositive}

end

global memo

memo = sym(ones(1,n));

F = fibo_03(n);

end

function F = fibo_03(n)

%the memo version of fibonacci sequences

%   call fibo03(n) ,here n is a positive  integer number

arguments

   n (1,1) {mustBeInteger,mustBePositive}

end

global memo

if n<=2

   F = memo(n);

elseif memo(n) == 1

   memo(n) = fibo_03(n-1)+fibo_03(n-2);

   F = memo(n);

else

   F = memo(n);

end

end

4、双指针，省时省空间

function F = fibo04(n)

%double pointer solution of fibonacci sequences

%   call fibo04(n),n is a positive integer number here

arguments

   n (1,1) {mustBeInteger,mustBePositive}

end

a = sym(1); % initialize the two pointer

b = sym(1);

if n<=2

   F = 1;

else

   for i = 3:n

       c = a+b;  % solve the i-th fabonacci

       a = b;    % swap the a,b,c ,prepare for next interation

       b = c;

   end

   F = c;

end

很明显，双指针的速度要快很多，其次是向上模拟，然后是带备忘录的递归，最次是递归，根本算不出结果，由于使用了一些符号化以及输入参数的限定，提高了鲁棒性，同时也附加了额外的开销