C语言程序与设计——函数(二)递归练习

在上一篇文章中接触到了递归这种编程方法，下面我们将用几个程序加深以下对递归的理解。

递归实际上就是程序调用自身的编程技巧
递归程序的组成：

1. 边界条件处理
2. 针对于问题的处理过程和递归过程
3. 结果返回

二分查找

首先分析二分查找的查找逻辑：

1. 需要三个指针分别指向数组：head，tail和mid。
2. 当arr[mid] > aim : 说明目标数据在mid 和head之间，让head指向mid ，mid 重新计算
3. 当arr[mid] < aim : 说明目标数据在mid 和head之间，让tail指向mid ，mid 重新计算
4. 如果出现head > tail 的情况说明，说明该数组没有该值，则返回false
   

所以由此，我们设计二分查找函数的时候，可以确认需要传入四个参数，分别为数组arr、头指针head、尾指针tail以及目标值aim。
tip：使用二分查找时需要保证数组内的数据是单调的，我写的这一版是单调递增的。

#include<stdio.h>
#define SIZE 10

int binary_search(int *arr, int aim,int start, int len){
    if(len < start ){
        return 0;
    }
    int mid = (start + len) >> 1;
    if(*(arr + mid) == aim) return mid;
	else if(*(arr + mid) > aim) return binary_search(arr, aim, start, mid - 1);
    else if(*(arr + mid) < aim) return binary_search(arr, aim, mid + 1, len);
}

int main(){
    int arr[SIZE] = {4,5,8,9,10,15,23,34,56,96};
    int n;
    while(~scanf("%d", &n)){
        if(!binary_search(arr, n, 0, SIZE)) {
            printf("it is not existed!\n");
            continue;
        }
        printf("arr[%d] = %d\n", binary_search(arr, n, 0, SIZE), n);
    }
}

运行结果：

二分查找的两种特殊情况

在二分查找中有两种特殊情况

000000000011111111111：查找该数列的第一个1
111111111110000000000：查找该数列的最后一个1
这两种情况在对于抽象现实的问题，可以提供解决思路，例如当我们去筛选一组单调数据中满足条件的数据时，找到第一个（不）满足要求的数据位置，即找到分界位置。

二分查找数列需满足的条件就是需要数列是单调的，但是当数列出现两个或多个相同的元素时，该数列依然是单调的，但是我们所查找到的元素位置就是不确定的，那么对于找到分界位置，是极具意义的，具体寻找过程如下图演示过程。

- 000000000011111111111：查找该数列的第一个1

按照图示过程，可以看出，当mid值为1时，将tail指针指向mid，当mid值为0时，head指向mid+1的位置。当三个指针重合的时候即为所求位置，另外可以看出mid是向下取整的。在这其中呢还需要考虑两个特殊情况，即全为0和全为1的情况，需要考虑返回的结果与位置的正确性。这里着重需要考虑全为0的情况，全为0时依旧会返回一个索引位置，但是整个数列是都不满足的，所以我在返回处加了一组特判解决。

#include<stdio.h>
#define SIZE 10
//000000000000111111111111找第一个1
int bin_search1(int *arr, int aim, int len){
    int head = 0, tail = len, mid = (head + tail) >> 1;
    while(head < tail){
       printf("head = %d, mid = %d, tail = %d\n", head, mid, tail);
        if(*(arr + mid) == aim) tail = mid;
        else if(*(arr + mid) < aim) head = mid + 1;
        mid = (head + tail ) >> 1;
    } 
    return arr[head] == aim? head:-1;
}
//递归写法
int b_search1(int *arr, int aim,int head, int tail){
    if(head >= tail){
        return arr[head] == aim ? head : -1;
    }
    int mid = (head + tail) >> 1;
    if(*(arr + mid) == aim) return b_search1(arr, aim, head, mid);
    else if(*(arr + mid) < aim) return b_search1(arr, aim, mid + 1, tail);
}
int main(){
    int arr[SIZE + 5] = {0};
    int n, num;
    scanf("%d", &n);
    for(int i = 0;i < n; i++){
        scanf("%d", &arr[i]);
    }
    printf("the first 1 is located %d\n", b_search1(arr ,1 ,0 ,n));      
}

运行结果：

- 111111111110000000000：查找该数列的最后一个1

可以看到与上一中情况不同的时tail的更新变成了mid - 1，head更新为mid。而且mid也变成了向上取整(若不使用向上取整，当head与tail相邻的时候需要会陷入死循环)

#include<stdio.h>
#define SIZE 5
//111111111111000000000000找最后一个1
int bin_search2(int *arr, int aim, int len){
    int head = 0, tail = len, mid = (head + tail + 1) >> 1;
    while(head < tail){
       printf("head = %d, mid = %d, tail = %d\n", head, mid, tail);
        if(*(arr + mid) ==  aim) head = mid;
        else tail = mid - 1;

        mid = (head + tail + 1) >> 1;
    }
    return *(arr + head) == aim ? head:-1;
}
//递归写法
int b_search2(int *arr, int aim, int head, int tail){
    if(head >= tail){
        return *(arr + head) == aim ? head : -1;
    }
    int mid = (head + tail + 1) >> 1;
    if(*(arr + mid) == aim) return b_search2(arr, aim, mid, tail);
    else return b_search2(arr, aim, head, mid - 1);
}

int main(){
    int arr[SIZE + 5] = {0};
    int n, num;
    scanf("%d", &n);
    for(int i = 0;i < n; i++){
        scanf("%d", &arr[i]);
    }
    printf("the last 1 is located %d\n", b_search2(arr ,1, 0 ,n));
}

运行结果：

总结
当我们在一个单调的且只有两种元素的序列找分界线的时，mid取整方向与“1”所在方向相反，mid取整方向很重要，否则会使得程序陷入死循环。同时应该考虑全为0或全为1的两种特殊情况。

欧几里得算法(辗转相除法)

1. 欧几里得算法又名辗转相除法
2. 迄今为止已知最古老的算法，距今2324年
3. 用于快速计算两个数字的最大公约数
4. 还可以用于快速求解$a\ast x+b\ast y=1$方程的一组整数解

欧几里得算法是，两个整数a和b通过不断的相除取余从而最后得出a与b的最大公约数，下面是欧几里得算法的公式推导
$$\begin{gathered} \{\begin{array}{l}a={\epsilon }_{1}r\\ b={\epsilon }_{2}r\end{array}，（其中{\epsilon }_1{\epsilon }_2互素） \\ a\%b=\lfloor a-kb\rfloor =\lfloor {\epsilon }_1-k{\epsilon }_2\rfloor r\Rightarrow 可证明r为a和b的引述，只需证明r最大 \\ 若使r最大，则只需证明{\epsilon }_1与k{\epsilon }_2互素即可\Rightarrow gcd({\epsilon }_1,k{\epsilon }_2)=1 \end{gathered}$$
由此可以求出a，b的最小公因数，由上述公式也可退出求解a,b的最大公倍数
$$\begin{gathered} 已知\{\begin{array}{l}a={\epsilon }_{1}r\\ b={\epsilon }_{2}r\end{array}，（其中{\epsilon }_1{\epsilon }_2互素） \\ a\ast b={\epsilon }_{1}r\ast {\epsilon }_{2}r={\epsilon }_1{\epsilon }_1{r}^2 \\ 因为r为a,b的公约数，且{\epsilon }_1{\epsilon }_2互素，则最小公倍数为{\epsilon }_1{\epsilon }_{2}r=\frac{a\ast b}{r} \end{gathered}$$
代码很简洁，如下：

#include<stdio.h>

int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}

int lcm(int a, int b){
    return a * b / gcd(a , b);
}

int main(){
    int a, b;
    while(~scanf("%d %d", &a, &b)){
        printf("the greatest common divisor is %d and the lcm is %d about %d and %d \n", gcd(a, b),lcm(a, b), a , b);
    }
}

运行结果：

拓展计算平方根

我们已经了解二分查找的查找方式，那么现在我们拓展一下，使用二分查找来计算平方根

思路：

1. 传入被开方数n，查找范围就是从0~n
2. 考虑到精度问题，定义一个误差范围，当tail与head的差小于误差时就可输出
3. 注意数据类型，这里推荐全都使用double

#include<stdio.h>
#include<math.h>
#define EPSL 1e-6

double my_sqrt(double n){

    double mid = n / 2.0, tail = n, head = 0;
    while(tail - head > EPSL){
        if(mid * mid < n) head = mid;
        else tail = mid;
        mid = (head + tail) / 2.0;
    }
    return mid;
}

int main(){
    double n;
    while(~scanf("%lf", &n)){
        printf("my_sqrt(%lf) = %lf\n", n, my_sqrt(n));
        printf("sqrt(%lf) = %lf\n", n, sqrt(n));
    }
}

在上述代码中存在一个bug，该程序只能计算大于1的程序，这里我们可以通过加一个特判的形式，通过if用两部分代码来进行实现全部情况，但是这里有一个更为简洁的方式就是令tail = n + 1。
因为主要问题在于小于0的被开方数是小于开放结果的，所以导致我们head和tail往相反的两边跑，使得不能逼近开方结果，所以只要先令tail大于1也就可以使得head和tail从两侧逼近开方结果,下面结果与c语言的sqrt()函数有些许的小出入，是我们定义的精度问题。可以让精度更小就更贴近真实值。

牛顿法

在计算机中实现sqrt()函数，开方运算的实际上就是使用的牛顿法，在这里我们也实现一下。
如下图所示，以求$\sqrt{4}$为例子，我们定义一个函数
$$f(x)=x^2-4$$
求出f(x)的零点，大于0的$x_1$即为平方结果，首先就是我们可以在函数上取$(4,f(4))$的点然后通过求导得出该点切线的斜率,通过点斜式的方法求出切线方程$l_1$，然后求出$l_1$的零点，求得$x_1$然后将$x_1$带入到原函数$f(x)$中求得第二点$(x_1,f(x_1))$在通过之前的方法求出$x_3$，如此往复使得，$x_n$不断逼近所求平方根，当$x_n-0<ESPL$时，$x_n$即为所求

#include<stdio.h>
#include<math.h>
#define EPSL 1e-6

double y(double x, double n){
    return x * x - n;
}
double partial_y(double x){
    return 2 * x;
}

double newton(double (*F)(double, double), double (*f)(double),double n){
    double x = 1.0;
    while(fabs(F(x, n)) > EPSL){
        x -= F(x, n) / f(x);
    }
    return x;
}

int main(){
    double n;
    while(~scanf("%lf", &n)){
        printf("mysqrt(%lf) = %lf\n", n, newton(y, partial_y,n));
        printf("sqrt(%lf) = %lf\n", n, sqrt(n));
    }
}