大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39
//递归的思想
public class Solution {
public int Fibonacci(int n) {
if(n<=0){
return 0;
} else if(n==1 || n==2){
return 1;
} else{
return Fibonacci(n-1)+Fibonacci(n-2);
}
}
}
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法
//迭代的思想
public class Solution {
public int JumpFloor(int target) {
int temp_1=1,temp_2=2;
int result=3;
if(target<=0){
return 0;
} else if(target==1){
return 1;
} else if(target==2){
return 2;
} else{
for(int i=1;i<target-1;i++){
result=temp_1+temp_2;//考虑target=3 的情况，先算result
temp_1=temp_2;
temp_2=result;
}
return result; //n>=3的return值
}
}
}
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
//f(n)=f(n-1)+f(n-2)+...f(0),f(n-1)不管前面的走法，只差一步到n级，以此类推。
//f(n-1)=f(n-2)+f(n-3)+...f(0),得到f(n)=2f(n-1）
public class Solution {
public int JumpFloorII(int target) {
if(target==0 || target==1){
return 1;
}else {
int result=1,temp=1;
for(int i=2;i<target+1;i++){
//迭代的思想
result=2*temp;
temp=result;
}
return result;
}
}
}
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
/*
*考虑最后的情况，一个1*2 的矩形覆盖 f(n-1)，或者两个2*1的矩形覆盖 f(n-2);和为f(n-1)+f(n-2)
*/
public class Solution {
public int RectCover(int target) {
if(target==1){
return 1;
} else if(target==2){
return 2;
} else if(target<=0){
return 0;
}else{
int temp1=1,temp2=2;
int result=0;
for(int i=3;i<=target;i++){
result=temp1+temp2;
//更新temp1 的值
temp1=temp2;
//更新temp2 的值
temp2=result;
}
return result;
}
}
}
这样一道智力题：“某商店规定：三个空汽水瓶可以换一瓶汽水。小张手上有十个空汽水瓶，她最多可以换多少瓶汽水喝？”答案是5瓶，方法如下：先用9个空瓶子换3瓶汽水，喝掉3瓶满的，喝完以后4个空瓶子，用3个再换一瓶，喝掉这瓶满的，这时候剩2个空瓶子。然后你让老板先借给你一瓶汽水，喝掉这瓶满的，喝完以后用3个空瓶子换一瓶满的还给老板。如果小张手上有n个空汽水瓶，最多可以换多少瓶汽水喝？
输入3,10,81
输出1,5,40
/*
*递归的思想，递归到底的条件是n=1,2,3 的情况。n=4 时可以考虑
drink的饮料数=先兑换的4/3+喝完空瓶兑换以及剩余空瓶兑换的（喝完的4/3+剩下的4%3）
*/
int softWater(int n){
if (n<=1){
return 0;
}
else if(n==2 || n==3){
return 1;
} else{
return n/3+softWater(n/3+n%3);
}
}
