MENU

递归求最大值

• November 2, 2020 • 递归

设a是有n个int类型数据元素的数组,试编写求a中最大值的递归函数


递归!!!

1.确定参数。数组是容器,无疑是第一个参数。我们在数组中不停地寻找最大数,不能避免两数比较,遍历数组确保将数组中每一个数都做了比较,因此还需要传入数组的下标。但是仅仅传入一个下标,我们在递归调用的时候还是无从下手,因为没有一个下标不能将所有的数都遍历到。所以我们接下来考虑传入两个下标看看,一个下标表示数组最左边的下标,另一个表示数组最右边的下标,在递归调用时两个下标逐渐逼近,就可以遍历到数组中的所有数字了。综上,三个参数:数组、左下标、右下标

2.参数的规律。数组作为容器,递归函数操作的数字始终在数组里面,所以数组必须一代一代的传下去;我们要遍历数组中所有的数字,有两个下标,这两个下标都要同时往中间靠,规律如下:

再看看代码:

3.递归出口。递归函数将数组一直折半,当折半到两个数字的时候无法再折半,此时出结果


下面是完整代码和注释:

代码实现:

#include<stdio.h>
#include<stdlib.h>
/*求数组中最大值*/
int getMax(int arr[], int left,int height) //数组容器,左标,右标
{
    /*如果左标和右标相邻了,返回两个数中大的那个数*/
    if (height - left < 2) {
        if (arr[left] > arr[height])
            return arr[left];
        else
            return arr[height];
    }
    else    //如果两标之间还有几个数,继续拆分,直到左标和右标相邻
    {
        int mid = (left + height) / 2;
        int max1 = getMax(arr, left, mid);      //在左标到中间下标之间找最大值,左半部分
        int max2 = getMax(arr, mid + 1, height);//在中间下标到右标之间找最大值。右半部分
        if (max1 > max2)  //返回在左半部分找出的最大值和右半部分找出的最大值较大的那一个
            return max1;
        else
            return max2;
    }
}
int main()
{
    int n,arr[100];
    printf("数组有多少个数:");
    scanf_s("%d", &n);
    printf("请输入这些数:");
    for (int i = 0; i < n; i++)
        scanf_s("%d", &arr[i]);
    int max = getMax(arr, 0, n-1);
    printf("数组中最大的数为:%d\n", max);
    system("pause");
    return 0;
}

运行结果:


测试一



测试二



测试三



代码编译器:Visual Studio 2017
ok,再见

Archives QR Code Tip
QR Code for this page
Tipping QR Code