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

HUNAN CITY UNIVERSITY

算法设计与分析课程设计

题 目： 求最大值与最小值问题 专 业： 学 号： 姓 名： 指导教师：

成 绩：

二0年月日

一 、问题描述

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

二、 课程设计目的

通过课程设计，提高用计算机解决实际问题的能力，提高独立实践的能力，将课本上的理论知识和实际有机的结合起来，锻炼分析解决实际问题的能力。提高适应实际，实践编程的能力。在实际的编程和调试综合试题的基础上，把高级语言程序设计的思想、编程巧和解题思路进行总结与概括，通过比较系统地练习达到真正比较熟练地掌握计算机编程的基本功，为后续的学习打下基础。了解一般程序设计的基本思路与方法。

三、 问题分析

看到这个题目我们最容易想到的算法是直接比较算法：将数组的第 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 情况。

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

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

4.1 当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。

把n个元素分成两组：

A1={A[1],...,A[int(n/2)]}和A2={A[int(N/2)+1],...,A[N]}

分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。

例如有下面一组元素：-13，13，9，-5，7，23，0，15。用分治策略比较的过程如下：

图中每个方框中，左边是最小值，右边是最大值。从图中看出，用这种方法一共比较了10次，比直接比较法的14次减少4次，即约减少了1/3。 4.2 分治法在每一层递归上都有三个步骤：

分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题； 合并：将各个子问题的解合并为原问题的解。

4.3 在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取 k = 2。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。

五、 算法代码及运行结果 5.1 分治法

import java.util.Arrays; import java.util.Scanner;

public class lianxi {

public static void main(String[] args) {

}

System.out.println(\"请输入要比较数字的总个数（数组长度）：\"); Scanner cin = new Scanner(System.in); int a;

a = cin.nextInt(); int[] arr=new int[a];

for (int i = 0; i < a; i++) { arr[i] = cin.nextInt(); if(i == a){ return; } }

int result[] = new int[2];

result = minMax(arr, 0, arr.length - 1);

System.out.println(Arrays.toString(result));

public static int[] minMax(int[] arr, int l, int r) { int min = 0; int max = 0;

} }

if (l == r) { min = arr[l]; max = arr[l];

} else if (l + 1 == r) { if (arr[l] < arr[r]) { min = arr[l]; max = arr[r]; } else {

min = arr[r]; max = arr[l]; }

} else {

int mid = (l + r) / 2;

int[] preHalf = minMax(arr, l, mid);

int[] postHalf = minMax(arr, mid + 1, r);

min = preHalf[0] < postHalf[0] ? preHalf[0] : postHalf[0]; max = preHalf[1] > postHalf[1] ? preHalf[1] : postHalf[1]; }

return new int[] { min, max };

分治法运行结果：

5.2直接法代码

import java.util.Scanner;

public class lianxi2 {

public static void main(String[] args) {

System.out.println(\"请输入要比较数字的总个数（数组长度）：\"); Scanner cin = new Scanner(System.in); int a;

a = cin.nextInt();

int[] list=new int[a];

for (int i = 0; i < a; i++) { list[i] = cin.nextInt(); if(i == a){ return;

} }

int max = list[0]; int min = list[0];

for (int i=0;i//依次比较得最大值（大值下沉） if(max<=list[i]){ max=list[i]; }

//依次比较取最小值 if(min>=list[i]){ min=list[i]; }

System.out.println(\"这些数字中最大的数字是：\" + max); System.out.println(\"这些数字中最小的数字是：\" + min); } }

直接法运行结果：

5.3：排序法代码

import java.util.Arrays; import java.util.Scanner;

public class lianxi2 {

public static void main(String[] args) {

System.out.println(\"请输入要比较数字的总个数（数组长度）：\"); Scanner cin = new Scanner(System.in); int a;

a = cin.nextInt();

int[] list=new int[a];

for (int i = 0; i < a; i++) { list[i] = cin.nextInt(); if(i == a){

}

}

return; } }

//先从小到大进行排序在取最大值与最小值 Arrays.sort(list);

System.out.println(\"数组按从小到大排序为：\"); for (int i = 0; i < list.length; i++) { System.out.print(list[i]+\); }

System.out.println(\"这些数字中最大的数字是：\" + list[a-1]); System.out.println(\"这些数字中最小的数字是：\" + list[0]);

排序法运行结果：

六、 各种算法比较与分析

虽然所有算法运行结果相同，但是他们的运行时间却是有很大差距的，任

何一种以比较为基础的搜索算法，其最坏情况下的所用时间不可能低于Θ（log n） 。不可能存在其最坏情况下时间比折半搜索数量级（阶）还低的算法。事实上，折半搜索所产生的比较树的所有叶结点都在相邻的两个层次上，而且这样的二叉树使得比较树的高度最低。因此，折半搜索是解决搜索问题在最坏情况下的最优算法。

七、心得体会

课程设计终于做完了，虽然有些疲劳和困倦，但带给我很多的收获。算法

设计与分析已经学了一个学期，有许多知识都存在似懂非懂的现象，这种现象通过实际的上机操作，实际应用，已经减少了许多。对这些知识也有了更深的理解

和很好的掌握。许多困惑，有许多已经通过实际操作解决了，并能够深刻认识，但也有很多没有明白。通过课程设计，明白做一件事需要考虑到很多方面的问题的，这些都是要在实践中摸索的，这与平时做练习是不同的，但也因为平时有许多的练习基础，会使你做起程序来，更加得心应手。另外就是要把错误总结，有许多错误或者陷阱是平时自己陷进去的，因此很深刻，但也有些错误或者陷阱是自己还没有接触或者犯过的，这就应该看多些别人的总结，使自己不犯这些错误。不让自己掉进这些陷阱。这样长期总结，会对自己有很大的帮助。

通过实验对各种算法有了更深一步的理解，知道了它们适合解决哪类的问题，锻炼和提高了自我的分析问题解决问题的能力，也使我对分治法的核心思想也有了更加深刻的理解和应用。

参考文献：

［1］《算法设计与分析》（第二版）霍红卫 编著，西安电子科技大学出版社，2010