数据结构与算法基础-C语言实践 01:(函数与递归)

(递归)

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 ;
}