做百度移动端网站,html5 服装网站,网站宣传内容,广东seo推广多少钱目录
一、斐波那契数列
二、青蛙跳台阶问题
三、变态跳台阶 一、斐波那契数列
题目#xff1a;写一个函数#xff0c;输入n#xff0c;求斐波那契数列的第n项。
思路#xff1a;用递归的方法#xff0c;f(n) f(n-1) f(n-2)。代码比较简单。
#includeiostream写一个函数输入n求斐波那契数列的第n项。
思路用递归的方法f(n) f(n-1) f(n-2)。代码比较简单。
#includeiostream
using namespace std;int Fibonacci(int n)
{if(n 0){return 0;}if(n 1){return 1;}return Fibonacci(n-1)Fibonacci(n-2);
}int main()
{cout Fibonacci(-1) ;cout Fibonacci(0) ;cout Fibonacci(1) ;cout Fibonacci(2) ;cout Fibonacci(3) ;cout Fibonacci(4) ;cout Fibonacci(5) ;return 0;
}
上面的代码如果n的值较大递归的次数较多就会造成栈溢出。
代码优化
思路可以用循环将数字从开始加到n。
#includeiostream
using namespace std;int Fibonacci(int n)
{int f1 1;int f2 1;int f3 0;if(n 0){return 0;}if(n 1 || n 2){return 1;}while(n 2){f3 f1f2;f1 f2;f2 f3;n--;}return f3;
}int main()
{cout Fibonacci(-1) ;cout Fibonacci(0) ;cout Fibonacci(1) ;cout Fibonacci(2) ;cout Fibonacci(3) ;cout Fibonacci(4) ;cout Fibonacci(5) ;return 0;
} 二、青蛙跳台阶问题
题目一只青蛙一次可以跳上1级台阶也可以跳2级台阶。求该青蛙跳上一个n级台阶总共有多少种跳法。
思路一级台阶只有一种跳法。两级台阶可以一次跳一级也可以一次跳两级一共两种方法。如果是三级的话就是从二阶或者从一阶跳上来以此类推所以可以用递归的方式。
#includeiostream
using namespace std;int JumpFloor(int n)
{if( n 0){return 0;}if( n 1 || n 2 ){return n;}return JumpFloor(n-1) JumpFloor(n-2);
}int main()
{cout JumpFloor(0) endl;cout JumpFloor(1) endl;cout JumpFloor(2) endl;cout JumpFloor(3) endl;cout JumpFloor(4) endl;cout JumpFloor(5) endl;return 0;
}
代码优化思路和上面的例子相同。
#includeiostream
using namespace std;int JumpFloor(int n)
{if( n 0){return 0;}if( n 1 || n 2){return n;}int f1 1;int f2 2;int f3 0;while(n 2){f3 f1f2;f1 f2;f2 f3;n--;}return f3;
}int main()
{cout JumpFloor(0) endl;cout JumpFloor(1) endl;cout JumpFloor(2) endl;cout JumpFloor(3) endl;cout JumpFloor(4) endl;cout JumpFloor(5) endl;return 0;
}三、变态跳台阶
题目一只青蛙一次可以跳上1级台阶也可以跳2级台阶 ... 也可以跳上n级。求该青蛙跳上一个n级台阶总共有多少种跳法。
思路当有一级台阶时跳法:0-1。 当有二级台阶时跳法 0-1-2 ,0-2。 当有三级台阶时跳法 0-1-2-3,0-1-3, 0-2-3, 0-3。 当有四级台阶时跳法 0-1-2-3-4,0-1-2-4,0-1-3-4, 0-1-4,0-2-3-4,0-2-4,0-3-4,0-4。
规律f(n) 2^(n-1)。
#includeiostream
using namespace std;int JumpFloor(int n)
{if(n 0){return 0;}if(n 1 || n 2){return n;}return 2 *JumpFloor(n-1) ;
}int main()
{cout JumpFloor(-1) endl;cout JumpFloor(0) endl;cout JumpFloor(1) endl;cout JumpFloor(2) endl;cout JumpFloor(3) endl;cout JumpFloor(4) endl;cout JumpFloor(5) endl;
}
优化
int JumpFloor(int n)
{if(n 0){return 0;}if(n 1){return 1;}int count 1;while(n-1 ! 0){count * 2;n--;}return count;
}int main()
{cout JumpFloor(-1) endl;cout JumpFloor(0) endl;cout JumpFloor(1) endl;cout JumpFloor(2) endl;cout JumpFloor(3) endl;cout JumpFloor(4) endl;cout JumpFloor(5) endl;
}
