算法设计与分析

2024-06-30 19:29| 来源: 网络整理| 查看: 265

文章目录问题描述：数据输入结果输出输入样例和输出样例思路分析：实现代码分析与总结：学习借鉴分析与总结

问题描述：条件：给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如，S={1，2，2，2，3，5}。多重集S的众数是2，其重数为3。注意，这个多重集是有序的，不考查排序算法任务：对于给定的由n个自然数组成的多重集S，编程计算S 的众数及其重数。不能一次完整的遍历。数据输入

输入数据由文件名为input.txt的文本文件提供。文件的第1行多重集S中元素个数n；接下来的n 行中，每行有一个自然数。

结果输出

程序运行结束时，将计算结果输出到文件output.txt中。输出文件有2 行，第1 行给出众数，第2行是重数。

输入样例和输出样例

input.txt

6 1 2 2 2 3 5

output.txt

2 3 思路分析：首先遍历一定是不行，时间复杂度是O（n），结合刚学的分治思想，将大问题分解成小问题。常见的分治算法的样例去思考，归并排序，将整体长的划分成短的，然后在合并成长的，分的是问题规模。大数乘法分的也是问题规模，那么类似的，这道题是否可以从问题规模的角度去考虑？参考了一下，通过实现代码 #include #include #include using namespace std; const int MAX_SIZE = 1000; /* 功能：times是返回当前index对应的数字在数组num中出现的次数参数：num：进行递归的数组 size：参与比较元素的实际大小 start，end：是参与比较的左右左右索引的起始段落 index：是获取出现次数元素的索引 up：元素出现次数的上界 down：是元素出现的下界 */ void getTimes(int* num, int size, int& times, int index, int& up, int& down) { up = index - 1, down = index + 1; while (up >= 0) { //遍历目标数字的左边 if (num[up] == num[index]) { times++; up--; } //制定推出条件 if (num[up] != num[index]) { break; } } while (down times++; down++; } //制定推出条件 if (num[down] != num[index]) { break; } } return; } /* 描述：进行递归的过程参数： num：进行递归的数组 size：参与比较元素的实际大小 start，end：是参与比较的左右左右索引的起始段落 */ int getDivide(int* num, int size, int start, int end, int& value) { while (start //左半部分进行递归 left = getDivide(num, size, start, up, compare); if (left > times) { times = left; value = compare; } } //判定是否需要进行右边的递归 if (times times = right; value = compare; } } return times; } } /* 描述：递归调用的外函数，num为原始数组，size数组的实际长度参数：num是原始数组，size数组的大小注意：数组的最后一个的元素用来保存出现次数最多的值 */ int RecursionOuter(int* num, int size) { int value = 0, times = 0; if (size == 0) { return 0; } else if (size == 1) { return 1; } else { times = getDivide(num, size - 1, 0, size - 2, value); num[size - 1] = value; return times; } } int main() { //读入文件 ifstream infile; infile.open("data.txt"); //文件的异常 if (!infile.is_open()) { cerr 0 },size = nums[0]; //cout if(l>r)return; int ll=l; //记录原来的l位置 int rr=r; //记录原来的r位置 int mid=(l+r)>>1; for(; lmid&&a[r]!=a[mid]; r--); //寻找众数的最右边 //经过两个for循环后，众数个数就是r-l+1 if(ans idx=min(mid,idx); } else idx=mid; ans=r-l+1; } if(l-1-ll+1>=ans) //剪枝 split(ll,l-1); // 对左边部分分治 if(rr-r-1+1>=ans) //剪枝 split(r+1,rr); // 对右边部分分治 } void solve() { scanf("%d",&n); for(int i=0; i

【本文地址】

公司简介

联系我们