(递归)
1.fibonacci数列
fibonacci数列的第n步的值为
fibonacci(n);
fibonacci{
if(n <= 2)
return 1;
else
return fibonacci(n-1)+fibonacci(n-2);
}
斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 2,n ∈ N*)
数列上每个值都是之前两个值的和,而数列的前两项为1
快速版:
int fibonacci(int n){
int res = 1;
int last = 1;
int t;
for(int i = 2; i < n; i ++){
t = res;
res += last;
last = t;
}
return res;
}
2.青蛙跳
青蛙离台阶有n步,要么一次跳1步,要么一次跳3步,那么求青蛙跳到台阶有多少种跳法
jump(n);
int jump(int n){
if(n < 3)
{
return 1;
}
if(n ==3)
{
return 2;
}
return jump(n-1)+jump(n-3);
}
进阶版:青蛙离台阶有n步,青蛙要么一次跳a步,要么一次跳b步,那么求青蛙跳到台阶有多少种跳法(a,b>=1,n>=1)
jump(n,a,b);
int jump(int n,int a,int b){
if(a == b)
if(n == a)
return 2;
if(n == a)
return 1 + jump(n-b,a,b);
if(n == b)
return 1 + jump(n-a,a,b);
if(n<0)
return 0;
return jump(n-a,a,b)+jump(n-b,a,b);
}
2.2猴子吃桃
一只小猴子一天摘了许多桃子,第一天吃了一半,然后忍不住又吃了一个;第二天又吃了一半,再加上一个;后面每天都是这样吃。到第10天的时候,小猴子发现只有一个桃子了。问小猴子第一天共摘了多少个桃子。
int eatpeach(int x,int day){
if(day == 10){
return 1;
}else
return 2*(eatpeach(day+1)+1)
}
3.GCD最大公约数
int gcd(int n,int m){
if(n%m == 0)
return m;
else
return gcd(m,n%m);
}
-Pow
int MyPow(int x,int y){
int res = 1;
while(y > 0)
{
res = res * x;
}
}
4.牛顿迭代求开方
double msqrt(double n){
if(n < 0)
{
n = -n;
}
double res = n / 2;
res = ((n / res) + res) / 2;
res = ((n / res) + res) / 2;
res = ((n / res) + res) / 2;
res = ((n / res) + res) / 2;
res = ((n / res) + res) / 2;
res = ((n / res) + res) / 2;
res = ((n / res) + res) / 2;
res = ((n / res) + res) / 2;
res = ((n / res) + res) / 2;
res = ((n / res) + res) / 2;
res = ((n / res) + res) / 2;
res = ((n / res) + res) / 2;
res = ((n / res) + res) / 2;
return res;
}
5.输出最大的数(两个之中&三个之中)
//返回两数中最大的数
inline
int max(int a,int b)
{
return a>b?a:b;
}
//返回三数中最大的数
int max3(int a,int b,int c){
return a>b?(a>c?a:c):(b>c?b:c);
}
inline
int max3(int a,int b,int c){
return max(a,max(b,c));
}
6.进制输出
输出以 radix进制的数字 n.
void radixPrint(char *pstr,int n , int radix);
在pstr里面输出以 radix进制的数字 n.
全局变量 char __print_radix[]={"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"} 为每位进制字母.自动识别进制基数
如果radixPrint输入的radix > sizeof (print_radix)则使之限制,与sizeof(print_radix) 的值相等.(即超过n进制则采用n进制)
char __print_radix[]={"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"}; //进制每一位 sizeof即为基数
int _print_int(char *pstr,int n,int radix){
int x;
if(n < radix){
*pstr= __print_radix[n];
return 1;
}else
{
x = _print_int(pstr, n/radix,radix);
pstr[x] = __print_radix[n%radix];
return x + 1;
}
return 0;
}
void radixPrint(char *pstr,int n,int radix){
if(radix > (sizeof __print_radix)){
radix = sizeof __print_radix; //即超过sizeof __print_radix进制则采用n进制
}else if(radix < 2)
{
radix = 2;//小于二进制则使用二进制
}
if(n < 0){
*pstr = '-';
pstr++;
n = -n;
}
_print_int(pstr,n,radix);
return ;
}
文章评论