众数问题

众数问题一、实验目的1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。3．学会利用分治算法解决实际问题。二、问题描述给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重数集S中的重数最大的元素称为众数。例如，S={1,2,2,2,3,5}。多重集S得众数是2，其重数为3。对于给定的由n个自然数组成多重数集S，计算S的众数及其重数。三．算法设计数据结构与核心算法的设计描述：voidsplit(ints[],intn,int&l,int&r)//以中间的数字为界限，确定左右起始和终止界限{intmid=n/2;for(l=0;ln;++l){if(s[l]==s[mid])break;}for(r=l+1;rn;++r){if(s[r]!=s[mid])break;}}//num众数，maxCnt重数voidgetMaxCnt(int&mid,int&maxCnt,ints[],intn){intl,r;split(s,n,l,r);//进行切割intnum=n/2;intcnt=r-l;//updateif(cntmaxCnt){maxCnt=cnt;mid=s[num];}//l表示左边的个数，左边的个数必须大于maxCnt才有必要搜寻if(l+1maxCnt){getMaxCnt(mid,maxCnt,s,l+1);}//右边搜寻,右边数组的起始地址要变更if(n-rmaxCnt){getMaxCnt(mid,maxCnt,s+r,n-r);}}算法设计：以中间为界限，先计算围绕中间这个数字的众数情况，然后左右分开递归计算结果，取最值即可。左右递归计算的时候要先做判断函数调用及主函数设计：intmain(void){ints[]={1,2,2,2,3,3,5,6,6,6,6};intn=sizeof(s)/sizeof(s[0]);intmaxCnt=0;intnum=0;getMaxCnt(num,maxCnt,s,n);printf(%d%d\n,num,maxCnt);return0;}四、程序调试及运行结果分析五、实验总结通过众数问题，感觉自己进一步了解了分治递归算法，想问题要全面彻底，不能想当然的认为自己知道了。六、程序清单#includestdafx.h#includeiostream#includecstdiousingnamespacestd;//以中间的数字为界限，确定左右起始和终止界限voidsplit(ints[],intn,int&l,int&r){intmid=n/2;for(l=0;ln;++l){if(s[l]==s[mid])break;}for(r=l+1;rn;++r){if(s[r]!=s[mid])break;}}//num众数，maxCnt重数voidgetMaxCnt(int&mid,int&maxCnt,ints[],intn){intl,r;split(s,n,l,r);//进行切割intnum=n/2;intcnt=r-l;//updateif(cntmaxCnt){maxCnt=cnt;mid=s[num];}//l表示左边的个数，左边的个数必须大于maxCnt才有必要搜寻if(l+1maxCnt){getMaxCnt(mid,maxCnt,s,l+1);}//右边搜寻,右边数组的起始地址要变更if(n-rmaxCnt){getMaxCnt(mid,maxCnt,s+r,n-r);}}intmain(void){ints[]={1,2,2,2,3,3,5,6,6,6,6};intn=sizeof(s)/sizeof(s[0]);intmaxCnt=0;intnum=0;getMaxCnt(num,maxCnt,s,n);printf(在输出的数中众数和重数分别是：%d%d\n,num,maxCnt);return0;}