查找数组元素的最大值和最小值众数问题

查找数组元素的最大值和最小值众数问题 《算法设计与分析》 上 机 实 验 报 告 专 业 班 级 学 号 学生姓名 完成日期 1. 上机题目及实验环境 1.1上机题目: 1.1.1 用分治法查找数组元素的最大值和最小值 1.1.2 众数问题 1.2实验环境: CPU:Intel Core i3 2.30GHz 内存:2.0G 操作系统:Windows 7 软件平台:Visual C++ 2. 算法设计与分析 2.1 查找数组最值 2.1.1 分治递归方法: , 将max和min设置为静态全局变量; , 将数据集array平均分为两个数据集; , 分别求解两个数据集中的最大和最小值; , 最终的最大和最小值通过与max和min的值比较; , 采用同样的处理方法递归处理以分好的数据集。 2.1.2 细节处理: n2, 数组的大小为，n=0,1,2,3...... , 数组中的数字随机产生，数字的范围为1~100; , 静态全局变量:max的初值为0，min的初值为101。 2.2 众数问题 2.2.1 快速排序算法: , 设置两个变量i、j，排序开始的时候:i=left，j=right+1; , 以第一个数组元素作为关键数据，赋值给temp，即temp=array[left]; , 从j开始向前搜索，即由后开始向前搜索(--j)，找到第一个小于temp的值array[j]; , 从i开始向后搜索，即由前开始向后搜索(++i)，找到第一个大于temp的array[i]; , 交换array[i]和array[j]的值; , 重复搜索步骤，直到i=j; , 将temp的值和array[j]的值交换，并以此为界，分别在对左右两边进行快速排序。 3. 核心代码 3.1 查找最值 3.1.1 图(如图1) (核心函数为void MaxAndMin(int array[N], int left, int right)): 开始 该数组只 有两个值 比较、更新max将该数组均分，并分别对 和min的值 其求最值MaxAndMin() 结束 图1.查找最值的流程图 3.1.2 核心代码如下: (注:max和min是静态全局变量) void MaxAndMin(int array[N], int left, int right) // 求最大值最小值函数，分治递归法 { int mid; // 数组的分界点 if ( (left + 1) == right) // 分治的数组只有两个值时，更新max和min的值 { if ( array[left] < array[right] && max < array[right] ) // 判断、更新最大值 max = array[right]; if ( array[left] > array[right] && max < array[left] ) max = array[left]; if ( array[left] < array[right] && min > array[left]) // 判断、更新最小值 min = array[left]; if ( array[left] > array[right] && min > array[right]) min = array[right]; } else { mid = (left + right) / 2; // 对数组进行分治 MaxAndMin(array, left, mid); // 对左边的数组进行分治递归 MaxAndMin(array, mid + 1, right); // 对右边的数组进行分治递归 } } 3.2 众数问题 3.2.1 流程图(如图2) 开始 left temp); // 从后面找小于基准的数 if(i >= j) // 当left>right时停止 break; swap(array[i], array[j]); // 交换两值 } array[left] = array[j]; array[j] = temp; int part = j; // 以靠左的较小值为界，对左右两部分数继续快排 quickSort(array, left, part-1); quickSort(array, part+1, right); } } 4. 运行与调试 4.1 查找数组最值 产生随机数组并排序:(如图3、图4、图5) 图3.随机数组之一及结果 图4.随机数组之二及结果 图5.随机数组之三及结果 4.2 众数问题 4.2.1 只有一个众数(如图6、图7) 图6.只有一个众数的数组 图7.只有一个众数的结果 4.2.2 没有众数(如图8、图9) 图8.没有众数的数组 图9.没有众数的结果 4.2.3 有两个众数(如图10、图11) 图10.有两个众数的数组 图11.有两个众数的结果 5. 结果分析和小结 5.1 结果分析: 通过设置不同的测试数据及运行的结果，可以看出程序的算法思想是正确的，程序的运行也是有效的，全面的。 5.2 实验的收获、心得

体会

针灸治疗溃疡性结肠炎昆山之路icu常用仪器的管理名人广告失败案例两会精神体会

: 通过对于这两个题目的分析和设计，我正确的掌握了分治算法的思想，以及使用分治算法来解决不同的问题，对程序的设计思想有了更好、更深的练习。 附录(C/C++源代码) 一、查找数组最大、最小值 //程序默认数组的大小值为2的幂，随机数的范围是1~100 #include #include #include #define N8 // 数组的大小 static int max=0; // 存储最大值 static int min=101; // 存储最小值 void CreateArray(int *); void ShowArray(int *); void MaxAndMin(int *, int, int); void main() { int array[N]; CreateArray(array); printf("产生的随机数组为:\n"); ShowArray(array); MaxAndMin(array, 0, 7); printf("该数组的最大值为:%d，最小值为:%d\n",max,min); } void MaxAndMin(int array[N], int left, int right) // 求最大值最小值函数，分治递归法 { int mid; if ( (left + 1) == right) // 分治的数组只有两个值时，更新max和min的值 { if ( array[left] < array[right] && max < array[right] ) // 判断、更新最大值 max = array[right]; if ( array[left] > array[right] && max < array[left] ) max = array[left]; if ( array[left] < array[right] && min > array[left]) // 判断、更新最小值 min = array[left]; if ( array[left] > array[right] && min > array[right]) min = array[right]; } else { mid = (left + right) / 2; // 对数组进行分治 MaxAndMin(array, left, mid); // 对左边的数组进行分治递归 MaxAndMin(array, mid + 1, right); // 对右边的数组进行分治递归 } } void ShowArray(int *array) // 输出数组 { int i; for (i = 0; i < N; i++) printf("%d ",array[i]); printf("\n"); } void CreateArray(int *array) // 创建随机数数组 { int i; srand( (unsigned) time( NULL ) ); // 给随机函数设置种子 for (i = 0; i < N; i++) array[i] = rand() % 100 + 1; //产生1~100内的随机数 } 二、众数问题 #include #include using namespace std; class Numbers //存储数组中数字出现的次数 { public: Numbers() { count = 0; // 初始化每个数字出现的次数 } int value; int count; }; int ReadLen(char *); void ReadArray(char *, int *, int); void Show(int *, int); void quickSort(int *, int, int); void Mode(int *, int, Numbers *); void WriteFile(char *, int, Numbers *); void main() { int size = 0; //

记录

混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载

数组的长度 char *inFile = "e:\\input.txt"; // input文件的绝对路径 char *outFile = "e:\\output.txt"; // output文件的绝对路径 size=ReadLen(inFile); int *array = new int[size]; // 创建数组 ReadArray(inFile, array, size); quickSort(array, 0, size-1); //对数组用快速排序法按从小到大排序 cout << "排序好的数组为:" << endl; Show(array, size); Numbers *numbers = new Numbers[size]; Mode(array, size, numbers); WriteFile(outFile, size, numbers); } void WriteFile(char* filename, int size, Numbers *numbers) //将结果写入文件 { int maxCount = 0; for(int i = 1; i < size; i++) // 找出数组中出现次数最多的数值最小的数 if(numbers[i].count > numbers[maxCount].count) maxCount = i - 1; if (maxCount == 0) cout << "该数组中不存在众数～" < temp); // 从后面找小于基准的数 if(i >= j) // 当left>right时停止 break; swap(array[i], array[j]); // 交换两值 } array[left] = array[j]; array[j] = temp; int part = j; // 以靠左的较小值为界，对左右两部分数继续快排 quickSort(array, left, part-1); quickSort(array, part+1, right); } } void Show(int *array,int size) // 显示数组的结果 { for(int i = 0; i < size; i++) cout << array[i]<<'\t'; cout<> temp; // 将第一个表示长度的读取，放弃 for(int i = 0; i < size; i++) input >> array[i]; input.close(); } int ReadLen(char *fileName) // 读取数组长度 { int size; ifstream input(fileName, ios::in); input >> size; return size; }