MATLAB算法技巧和实现斐波那契数列的解决思路

MATLAB算法技巧和实现斐波那契数列

这篇博客主要说一下自己在算法设计课上用matlab做的两道算法题，题目解起来都比较简单，但是需要些技巧。

• 公倍数的应用
• 斐波那契数列的应用

题目要求

题目一:公倍数的应用

  心里想好一个1~100之间的整数x，将它分别除以3，5，7并得到3个余数。把这三个余数输入计算机，计算机能马上猜出这个数

题目二:斐波那契数列的应用

  斐波那契数列有如下特点：a1,a2已知 a(n)=a(n-1)+a(n-2) n>=3
  例题：楼梯上有n阶台阶，上楼时可以一步上1阶，也可以一步上2阶，编写算法计算共有多少种不同的上楼梯方法

解题思路

问题一，问题一可以将该数转换为d=70*a+21*b+15*c的乘积，主要是利用了他们的公倍数性质。

详细数学模型解释：
1）不难理解当s=u+3*v+3*w时，s除以3的余数与u除以3的余数是一样的。
2）对s=cu+3*v+3*w，当c除以3余数为1的数时, s除以3的余数与u除以3的余数也是一样的。证明如下：c 除以 3余数为1，记c=3*k+1，则s=u+3*k*u+3*v+3*w，由1)的结论，上述结论正确。记a，b，c分别为所猜数据d除以3，5，7后的余数，则d=70*a+21*b+15*c。为问题的数学模型，其中70称作a的系数，21称作b的系数,15称作c的系数。

问题二，就单纯是递归问题，编者对于递归也不太熟悉，正在逐步探索中。

数学模型：
此问题如果按照习惯，从前向后思考，也就是从第一阶开始，考虑怎么样走到第二阶、第三阶、第四阶……，则很难找出问题的规律；而反过来先思考“到第n阶有哪几种情况？”，答案就简单了，只有两种情况：
1） 从第n-1阶到第n阶；
2） 从第n-2阶到第n阶。
记n阶台阶的走法数为f(n)，则
f(n)= 1 n=1
f(n)=2 n=2
f(n-1)+f(n-2) n>2

代码实现

主文件：main.m

%made by Canlong
%%
%编写算法完成下面给余猜谜的游戏
%心里想好一个1~100之间的整数x，将它分别除以3，5，7并得到3个余数。把这三个余数输入计算机，计算机能马上猜出这个数。
%方法一：穷举法
disp('方法一：穷举法')
num1 = input('请输入第一个数：');
num2 = input('请输入第二个数：');
num3 = input('请输入第三个数：'); 
for i=1:100
    if rem(i,3)==num1 && rem(i,5)==num2 && rem(i,7)==num3  
       fprintf('该数为：%d \n',i); 
    end
end

%%
%方法二，建模.
disp('方法二，建模.');
num1 = input('请输入第一个数：');
num2 = input('请输入第二个数：');
num3 = input('请输入第三个数：'); 
d=70*num1+21*num2+15*num3;
while d>105
   d = d-105 ;
end
fprintf('该数为：%d \n',d);

%%
%斐波那契数列的应用
%斐波那契数列有如下特点：a1,a2已知  a(n)=a(n-1)+a(n-2)  n>=3
%例题：楼梯上有n阶台阶，上楼时可以一步上1阶，也可以一步上2阶，编写算法计算共有多少种不同的上楼梯方法
%楼梯阶数
n=10;
disp('如果楼梯阶数为10，上楼梯的方法数，解得：');
fprintf('f(%d)为：%d \n',n,f(n));

函数文件：f.m

%输入n为阶梯数，a为返回的阶梯数
%made by Canlong
function a=f(n)
    if n==1
         a=1;
         return;
    end
    if n==2
         a=2;
         return
    else
         a=f(n-1)+f(n-2);
         return
    end
end

运行结果

在MATLAB R2015b软件下运行得到：

总结

  太久没用matlab写代码了，对于matlab很多语法很多都不熟悉了，写到函数那里还以为return 数值会直接返回数值，原来matlab的函数，是通过某个变量来返回值的，不能直接return 数值，如function a=f(n)中的a就是用来接受返回数值的，要返回数值的函数一定要对a进行赋值。这一点上与java等语言不太类似。