算法设计与分析课程设计(完整版).pdfVIP

算法设计与分析课程设计(完整版)--第1页

HUNANCITYUNIVERSITY

算法设计与分析课程设计

题目：求最大值与最小值问题

专业：

学号：

姓名：

指导教师：

成绩：

二0年月日

算法设计与分析课程设计(完整版)--第1页

算法设计与分析课程设计(完整版)--第2页

一、问题描述

输入一列整数，求出该列整数中的最大值与最小值。

二、课程设计目的

通过课程设计，提高用计算机解决实际问题的能力，提高独立实践的能力，

将课本上的理论知识和实际有机的结合起来，锻炼分析解决实际问题的能力。提

高适应实际，实践编程的能力。在实际的编程和调试综合试题的基础上，把高级

语言程序设计的思想、编程巧和解题思路进行总结与概括，通过比较系统地练习

达到真正比较熟练地掌握计算机编程的基本功，为后续的学习打下基础。了解一

般程序设计的基本思路与方法。

三、问题分析

看到这个题目我们最容易想到的算法是直接比较算法：将数组的第1个元

素分别赋给两个临时变量：fmax:=A[1];fmin:=A[1];然后从数组的第2个元

素A[2]开始直到第n个元素逐个与fmax和fmin比较，在每次比较中，如果

A[i]fmax，则用A[i]的值替换fmax的值；如果A[i]fmin，则用A[i]

的值替换fmin的值；否则保持fmax（fmin）的值不变。这样在程序结束时的

fmax、fmin的值就分别是数组的最大值和最小值。这个算法在最好、最坏情况

下，元素的比较次数都是2(n-1)，而平均比较次数也为2(n-1)。

如果将上面的比较过程修改为：从数组的第2个元素A[2]开始直到第n

个元素，每个A[i]都是首先与fmax比较，如果A[i]fmax,则用A[i]的值替

换fmax的值；否则才将A[i]与fmin比较，如果A[i]fmin，则用A[i]

的值替换fmin的值。

这样的算法在最好、最坏情况下使用的比较次数分别是n-1和2(n-1),而平

均比较次数是3(n-1)/2,因为在比较过程中，将有一半的几率出现A[i]fmax

情况。

算法设计与分析课程设计(完整版)--第2页

算法设计与分析课程设计(完整版)--第3页

如果采用分治的思想，可以构造算法，其时间复杂度在最坏情况下和平均用时均

为3n/2-2:

四、主要算法（分治法）描述

4.1当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过

程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这

类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，

再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，

难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出

解为止。这就是分治策略的基本思想。

把n个元素分成两组