第2节作业参考程序.docx

众数问题Problem description给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如，S={1，2，2，2，3，5}。多重集S的众数是2，其重数为3。对于给定的由n 个自然数组成的多重集S，编程计算S 的众数及其重数。Input输入的第1行多重集S中元素个数n；接下来的n 行中，每行有一个自然数，值在整数范围内Output程序运行结束时，将计算结果输出。输出文件有2 行，第1 行给出众数，第2 行是重数。如果很多数的出现次数相同则输出最小的那个。Sample Input6122235Sample Output23提示：穷举法：先进行排序，再线性统计（毫无技术含量）分治法，先根据某数X，将小于X的放于其左，大于X的放于其右，统计X出现的次数T，如果X左边数的个数=T，向左递归；如果X右边数的个数T，向右递归//功能：众数问题//作者：邹竞//思路：分治法，先根据某数mid，将小于mid的放于其左，大于mid的放于其右，统计mid出现的次数T，如果X左边数的个数=T，向左递归；如果X右边数的个数T，向右递归//版本：v2.0//日期：2010-08-31#includeiostream#includefstream#includealgorithmusingnamespace std;template typename Typeclass Repeat{protected:int n; //数组元素个数 Type * a; //数组首地址 Type ans; //众数int count; //众数的个数（重数）int Partition (int p, int r, Type x, int t); //以x为基准对a进行划分，t表示x出现了多少次 Type Select(int p, int r, int k); //线性时间选择void Process(int p, int r); //递归分治public: Repeat(int nn); //构造 ~Repeat(); //析构void Process(); //处理void ReadData(fstream fileIn); //读入数据void Output(fstream fileOut); //输出结果};template typename TypeRepeatType::Repeat(int nn){ n = nn; a = new Type [n];}template typename TypeRepeatType::~Repeat(){delete [] a;}template typename Typevoid RepeatType::ReadData(fstream fileIn){int i;for(i = 0; i n; i++) fileIn a[i]; count = 0; ans = 32767;}template typename Typeint RepeatType::Partition (int p, int r, Type x, int t){int i, left = p, right = r; Type * b = new Type [r - p + 1];for(i = 0; i r - p + 1; i++) { b[i] = a[p + i]; }for(i = 0; i r - p + 1; i++) {if(b[i] x) { a[left++] = b[i]; }elseif(b[i] x) { a[right--] = b[i]; } }for(i = left; i = right; i++) { a[i] = x; } t = right - left + 1;delete [] b;return left;}template typename TypeType RepeatType::Select(int p, int r, int k){int i,j; Type x;int t;if (r - p 75) { sort(a + p, a + r + 1);return a[p + k - 1]; }for(i = 0; i = (r - p - 4)/ 5; i++) { sort(a + p + 5 * i, a + p + 5 * i + 5);//将a[p+