算法-名企面试(360)
2019-04-18 本文已影响0人
e7affd6a0ae8
一、.使用递归实现:a0=1,a1=1;a2=a0+a1;a3=a1+a2;a4=a2+a3...以此类推,求a30
Answer解法
方式一:采用逆向思维
非常明显这是一道简单动态规划的题目,
从后往前逆向推理,递推公式如下:
An=A(n−1)+A(n−2)
An=A(n−1)+A(n−2)
终止条件:当n=2时,A(n-1 )和 A(n-2)分别为 A0 和 A1
方式二:采用正向思维
从a0和a1,逐个往后计算,知道找到自己需要的值。
代码如下:
public static void main(String args[ ]){
int a0=0;
int a1=1;
System.out.println("方法一测试结果:"+getNum(a0, a1, 30));
System.out.println();
System.out.println("方法二测试结果:"+getNum(30));
}
/**正向思维:优点,起始值可以人为控制;不局限于本题的a0=a1=1; 缺点:计算过程复杂一些
* 使用递归实现:a0=1,a1=1;a2=a0+a1;a3=a1+a2;a4=a2+a3...以此类推,求an
* @param a 起始数1:a0
* @param b 起始数2:a1
* @param times 递归次数:an,则times=n-1
* @return
*/
public static int getNum(int a,int b,int times){
int temp=a+b;
times--;
if(times==0){
return temp;
}
return getNum(b, temp,times);
}
/**逆向思维:优点,清晰明了
* 使用递归实现:a0=1,a1=1;a2=a0+a1;a3=a1+a2;a4=a2+a3...以此类推,求an
* @param num 是an的下标,即num=n
* @return
*/
public static int getNum(int num){
if (num==0||num==1) {
num=1;
}else {
num=getNum(num-1)+getNum(num-2);
}
return num;
}
测试结果:
1555581542(1).jpg