寻找众数问题实验报告

《算法设计与分析》上机实验报告专业软件工程班级1101班学号04113033学生姓名岳彦利完成日期2013-10-241.上机题目及实验环境1.1上机题目：众数问题1.2实验环境：CPU：英特尔第二代酷睿i3-2330M@2.2GHz双核内存：4G操作系统：windows7软件平台：ubuntu2.算法设计与分析1.用快速排序把随机生成的一组数排序放到数组中。2.把排好的数组用下标按次序逐个比较，如果相等就用count=count+1,设个标记的flag,将count赋给flag,不相等就count=1，下标相加，循环，直到最后一个数。3.在把最后比较的数放到x中，最终输出次数最多的数x和它的次数flag.3.核心代码//快速排序递归，a[]代表数组，low代表数组的第一个数的下标，high代标数组最后一个数的下标intPartition(inta[],intlow,inthigh){intx=a[low];//将数组的第一个数赋给xwhile(lowhigh){while(a[high]=x&&lowhigh)//从后往前找比x小的数high--;if(lowhigh){a[low]=a[high];//从后往前找到比x小的数赋给a[low]low++;}while(a[low]x&&lowhigh)//从前往后找比x大的数low++;if(lowhigh){a[high]=a[low];//从前往后找比x大的数赋给a[high]high--;}}a[low]=x;returnlow;}//开速排序voidQuickSort(inta[],intlow,inthigh){if(lowhigh){intpos=Partition(a,low,high);//递归调用QuickSort(a,low,pos-1);QuickSort(a,pos+1,high);}}//查找众数voidfindmode(inta[],intn){intcount=1,flag=1,flag1=0;inti=0,x,x1;while(in){if(a[i+1]==a[i])//判断是否相等{count++;if(count==flag){flag1=count;x1=a[i];}if(countflag){flag=count;x=a[i];}}elsecount=1;i++;}printf(outputput:\n);if(flag==1)printf(没有众数！\n);elseif(flag==flag1)printf(众数是：%d,%d\n出现的次数都是：%d\n,x,x1,flag);elseprintf(%d\n%d\n,x,flag);}4.运行与调试图一.当没有众数的错误情况图二.没有众数的正确情况图三.输出含有两个众数错误情况图四.输出含有两个众数正确的情况图五.输出含有1个众数的情况5.结果分析和小结（1）如图一，是因为没有考虑到count=1时要输出的输出的数，所以输出的是一个垃圾数据，后来，加了一个标志flag，如果flag没有变就代表数组中没有众数，修改后如图二。如图二，没有考虑到1，1，2，2，3的那种情况，每次就能输出1，后来在比较countflag前比较一下相等，再把2的值赋给另一个数，最后把两种情况都输出就可以了，修改后如图四。如图五：从键盘输入的8代表要随机生成随机数的个数，outputnumber:代表从文件中读出的数，第一个数是总随机个数，剩下的是产生的随机数，最下面两行5众数，4代表5出现的次数。（2）让我更熟悉分治法，对快速排序有了更深的理解，在写的过程中出现了段错误，调试了好久才发现是因为定义出了错，感觉自己需要学习的太多了，只有上机编写才能发现自己真正的问题，除此之外感觉编程也很有趣。附录（C/C++源代码）#includestdio.h#includestdlib.h#includefcntl.h#includemath.h#includetime.h//快速排序递归，a[]代表数组，low代表数组的第一个数的下标，high代标数组最后一个数的下标intPartition(inta[],intlow,inthigh){intx=a[low];//将数组的第一个数赋给xwhile(lowhigh){while(a[high]=x&&lowhigh)//从后往前找比x小的数high--;if(lowhigh){a[low]=a[high];//从后往前找到比x小的数赋给a[low]low++;}while(a[low]x&&lowhigh)//从前往后找比x大的数low++;if(lowhigh){a[high]=a[low];//从前往后找比x大的数赋给a[high]high--;}}a[low]=x;returnlow;}//开速排序voidQuickSort(inta[],intlow,inthigh){if(lowhigh){intpos=Partition(a,low,high);//递归调用QuickSort(a,low,pos-1);QuickSort(a,pos+1,high);}}//查找众数voidfindmode(inta[],intn){intcount=1,flag=1,flag1=0;inti=0,x,x1;while(in){if(a[i+1]==a[i])//判断是否相等{count++;if(count==flag){flag1=count;x1=a[i];}if(countflag){flag=count;x=a[i];}}elsecount=1;i++;}printf(outputput:\n);if(flag==1)printf(没有众数！\n);elseif(flag==flag1)printf(众数是：%d,%d\n出现的次数都是：%d\n,x,x1,flag);elseprintf(%d\n%d\n,x,flag);}main(){FILE*fp;inti,d;intn;if((fp=fopen(input.txt,wt))==NULL){printf(failtoopenfile!\n);exit(1);}printf(Inputnumbern:\n);scanf(%d,&n);inta[n];fprintf(fp,%d\n,n);//将n写入文件srand((int)time(0));//将产生的随机数在下次时打乱顺序for(i=0;in;i++){a[i]=1+(int)(10.0*rand()/(RAND_MAX+1.0));//将产生的随机数写入数组fprintf(fp,%d\n,a[i]);//将产生的随机数写入文件}fclose(fp);fp=fopen(input.txt,rt);//将结果写入文件printf(outputnumber:\n);i=0;while(fscanf(fp,%d,&a[i])!=EOF){printf(%d\n,a[i]);i++;}for(i=0;i=n;i++)a[i]=a[i+1];fclose(fp);QuickSort(a,0,n-1);//调用快速排序findmode(a,n);//调用查找函数}