题解：P5718 【深基4.例2】找最小值

· · 题解

P5718 【深基4.例2】找最小值

题意

输入n个非负整数，求最小值。

分析

通过题意易得要比较这n个数，求最小值，而左右比较又是一个重复的事情，这里就可以使用递归。

递归思想

递归（Recursion）指函数直接或间接调用自身来解决问题的方法。递归通常用于解决可以分解为相同结构的子问题的情况。

递归的基本要素

1.递归基（Base Case）

我们知道函数中可以调用自身，但如果每次执行都会调用就会死循环，而递归基就是循环的终止条件，防止死循环。

2.递归关系（Recursive Case）

递归思想是将问题分解为更小的子问题，并通过调用自身解决的思想。所以使用递归时要将问题拆分。将大问题拆分成子问题，再将他们联系起来。

递归实现

本题递归关系就是比较前n−1个数的最小值和第n个数。

设findmin(i)为从1到i的最小值，所以本文的递归关系就是findmin(x)=min(a[x],findmin(x-1))(min函数头文件为<algorithm>，返回值是两个参数之间的最小值)。

而本文递归基也显而易见能看出是x!=1。

代码

#include<iostream>
#include<algorithm>//min函数头文件
using namespace std;
int n,a[1005];//数组开大五个，防止越界。定义全局变量方便函数调用。
int findmin(int x)
{
    if(x==1)return a[1];
    return min(a[x],findmin(x-1));
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    cout<<findmin(n);//调用函数直接输出
    return 0;
}

递归实现，时间复杂度O(n)（n次比较），空间复杂度O(n)（递归的栈空间）。