算法第二章上机实践报告

本文主要是介绍算法第二章上机实践报告，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

算法第二章上机实践报告

1、     实践题目：7-1 maximum number in a unimodal array 

2、    问题描述：

给定一个具有 n 个不同元素的单峰数组，这意味着它其中的元素先按递增顺序排列直到它的最大元素，然后它的元素按降序排列。请设计一个时间复杂度为 O(log n) 的算法来寻找数组中的最大元素。

输入格式： 第一行输入一个整数n（1<= n <= 10000）。第二行输入用空格隔开的N个整数，是一个单峰数组。

输出格式:

一个整数，它是数组中的最大整数

输入样例:

7

1 2 3 9 8 6 5

结尾无空行

输出样例:

9

3、    算法描述：

·定义search（int a[],int l, int r）。

此题利用二分搜索方法，在左边l小于等于右边r的情况下，不断地判断中间下标m的元素大小。

1)  若中间元素值大于其左边元素且大于其右边元素，则返回m（也就是最大值的下标）

if(a[m]>a[m+1]&&a[m]>a[m-1])

            return m;

2)  若中间值大于其左边元素且小于其右边元素，说明最大值在其右边区域，使l=m+1，检索范围缩小为[m+1,r]

if(a[m]>a[m-1]&&a[m]<a[m+1])

            l=m+1;

3)  若中间值小于其左边值且大于其右边值，说明最大值在其左边，另r=m-1，使检索范围缩小为[l,m-1]；不断缩小范围直至l>r,表示无最大峰。

if(a[m]<a[m-1]&&a[m]>a[m+1])

            r=m-1;

·在main函数中利用for循环输入值，调用search函数。

int main()

{

   int n;

   cin>>n;

    int a[n];

   for(int i=0;i<n;i++)

    {

       cin>>a[i];

    }

   int k=search(a,0,n-1);

   cout<<a[k];

    return 0;

}

4、    算法时间及空间复杂度分析：

时间复杂度：O（logn）

本题对长度为n的数组进行二分搜索，最坏的情况则为不停的折半搜索直至l>r,即运行了O（logn），循环体内部执行O（1），故为O（logn）

空间复杂度：

该算法并没借助辅助空间，只是对大小为n的数组进行操作，所以为O（1）。

5、    心得体会：

·第一次提交至pta的时候显示部分正确，犯了低级错误，在执行迭代操作时，在l=m+1和r=m-1前加了return，导致答案错误，这就说明平时打代码要思路清晰，对循环、迭代的结构要更加熟悉，避免犯低级错误。

·如果利用递归的方法，一定要加上边界条件，比如l<=r。

·在想解决方法的时候可以多动动笔，在纸上画出来，思路会更加清晰。

6、    分治法的个人体会和思考：

分治法也就是“分而治之”，有一些问题并不是本身很难，而是它的问题规模很大，因此要利用分治法，将一个大问题分成许多子问题，再一步步解决子问题，再将子问题的解合并。在这个过程中还会有不同的解法，我们也优先选择时间复杂度最小的。

这篇关于算法第二章上机实践报告的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！