[讨论]算法实现题众数问题«问题描述：给定含有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.txt6122235output.txt23这是算法...但我还看不懂...我认为文件操作还好弄.就算法,它是用递归来做的.void mode(int LL,int RR){int L1,R1;int med=median(a,LL,RR);split(a,med,LL,RR,L1,R1);if(largest<R1-L1+1) largest=R1-L1+1;element=med;if(L1-LL>largest) mode(LL,L1-1);if(RR-R1>largest) mode(R1+1,RR);}//median用于找中位数,split用中位数将数组分2为段.[此问题还有待解决,谢谢各位的参与!]//首先在此文件夹下建立名为qingsongin2.txt的文件//其内容为6 1 2 2 2 3 5 之格式.其中第一的数为数组表长度#include<iostream>#include<fstream>#define MAXSIZE 20using namespace std;typedef int KeyLype;typedef int Status;typedef struct {KeyLype key;} RedType;typedef struct {RedType r[MAXSIZE + 1];int length;} SqList;int SelectSort(SqList &L){int i,j,t;for(j=0;j<L.length;j++)for(i=1;i<=L.length-j;i++)if(L.r[i].key<L.r[i-1].key){t=L.r[i].key;L.r[i].key=L.r[i-1].key;L.r[i-1].key=t;}return 0;}//简单选择排序int median(SqList L,int a,int b){int med;if((a+b)%2==0)med=(a+b)/2;elsemed=(a+b-1)/2;return med;}int L1(SqList L,int med){while(med>=1&&med<=L.length){ if(L.r[med].key==L.r[med-1].key)med--;elsereturn med-1;}}int R1(SqList L,int med){while(med>=1&&med<=L.length){ if(L.r[med].key==L.r[med+1].key)med++;elsereturn med+1;}}void mode(SqList L,int a,int b,int &max_num,int &max_count) {if(a==b)return ;else{int l1,r1;int med,j,k;k=j=med=median(L,a,b);l1=L1(L,med);r1=R1(L,j);if(max_count<r1-l1-1){max_count=r1-l1-1;max_num=L.r[k].key;}if(l1-a+1>max_count)mode(L,a,l1,max_num,max_count);if(b-r1+1>max_count)mode(L,r1,b,max_num,max_count);}}int main(){ifstream fin("qingsongin2.txt");ofstream fout("qingsongout2.txt");SqList L;int max_num;//众数int max_count;//众数的个数if (fin.fail()){cout<<"输入qingsongin2.t xt文件出错!"<<endl;return -1;}if (fout.fail()){cout<<"fout(\"qingsongout2.txt\");"<<endl;return -2;}int n;//n是数组表的长度fin>>n;int i;for(i=1;i<=n;i++)//cin>>L.r[i].key;fin>>L.r[i].key;L.length=n;//cout<<endl;SelectSort(L);mode(L,1,L.length, max_num,max_count);//cout<<"众数是:"<<max_num<<endl;//cout<<"重复次数是:"<<max_num<<endl;fout<<"众数是:"<<max_num<<endl;fout<<"它的个数是:"<<max_count<<endl;cout<<"请查看此文件夹下的qingsongout2.txt文件"<<endl; return 0;}但它的前提是已排好序的.算法第2章第11题集合划分问题2009-11-02 17:37Description问题描述：n个元素的集合{1,2,?,n}可以划分为若干个非空子集。

例如，当n=4时，集合{1，2，3，4}可以划分为15个不同的非空子集如下：{{1}，{2}，{3}，{4}}，{{1，2}，{3}，{4}}，{{1，3}，{2}，{4}}，{{1，4}，{2}，{3}}，{{2，3}，{1}，{4}}，{{2，4}，{1}，{3}}，{{3，4}，{1}，{2}}，{{1，2}，{3，4}}，{{1，3}，{2，4}}，{{1，4}，{2，3}}，{{1，2，3}，{4}}，{{1，2，4}，{3}}，{{1，3，4}，{2}}，{{2，3，4}，{1}}，{{1，2，3，4}}其中，集合{{1，2，3，4}}由 1 个子集组成；集合{{1，2}，{3，4}}，{{1，3}，{2，4}}，{{1，4}，{2，3}}，{{1，2，3}，{4}}，{{1，2，4}，{3}}，{{1，3，4}，{2}}，{{2，3，4}，{1}}由2个子集组成；集合{{1，2}，{3}，{4}}，{{1，3}，{2}，{4}}，{{1，4}，{2}，{3}}，{{2，3}，{1}，{4}}，{{2，4}，{1}，{3}}，{{3，4}，{1}，{2}}由3 个子集组成；集合{{1}，{2}，{3}，{4}}由4个子集组成。

编程任务：给定正整数n和m，计算出n个元素的集合{1,2,?,n}可以划分为多少个不同的由m 个非空子集组成的集合。

Input第1 行是元素个数n和非空子集数mOutput计算出的不同的由m个非空子集组成的集合数输出Sample InputSample Output6#include<iostream.h>int a[1000][1000];int t(int n,int i){int m,pp=0;m=i-1;n--;if(m==n)pp++;else{if(n==1)pp++;else{if(m==1)pp++;elsepp+=t(n,m);pp+=i*t(n,i);}}return pp;}int main(){int n,m,sum;cin>>n>>m;sum=t(n,m);cout<<sum<<endl;return 0;}4 3算法第2章第10题集合划分问题2009-11-02 17:36Description问题描述：n个元素的集合{1,2,...,n}可以划分为若干个非空子集。

例如，当n=4时，集合{1，2，3，4}可以划分为15个不同的非空子集如下：{{1}，{2}，{3}，{4}}，{{1，2}，{3}，{4}}，{{1，3}，{2}，{4}}，{{1，4}，{2}，{3}}，{{2，3}，{1}，{4}}，{{2，4}，{1}，{3}}，{{3，4}，{1}，{2}}，{{1，2}，{3，4}}，{{1，3}，{2，4}}，{{1，4}，{2，3}}，{{1，2，3}，{4}}，{{1，2，4}，{3}}，{{1，3，4}，{2}}，{{2，3，4}，{1}}，{{1，2，3，4}}编程任务：给定正整数n，计算出n个元素的集合{1,2,...,n}可以划分为多少个不同的非空子集。

Input第1 行是元素个数nOutput将计算出的不同的非空子集数输出Sample InputSample Output52#include<iostream.h> int a[1000][1000]; int t(int n,int i) {int m,pp=0;m=i-1;n--;if(m==n)pp++;else{if(n==1)pp++;else{if(m==1)pp++;elsepp+=t(n,m);pp+=i*t(n,i);}}//cout<<pp<<endl; return pp;}int main(){int i,j,n,sum=0;cin>>n;for(i=1;i<=n;i++) {if(i==1||i==n)a[n][i]=1;elsea[n][i]=t(n,i); sum+=a[n][i];}cout<<sum<<endl;return 0;}5算法第2章第9题排列的字典序问题2009-11-02 17:35Description问题描述：n个元素{1,2,...,n}有n!个不同的排列。