第二章习题.docx
- 文档编号:18610563
- 上传时间:2023-08-20
- 格式:DOCX
- 页数:23
- 大小:20.87KB
第二章习题.docx
《第二章习题.docx》由会员分享,可在线阅读,更多相关《第二章习题.docx(23页珍藏版)》请在冰点文库上搜索。
第二章习题
[讨论]算法实现题众数问题
«问题描述:
给定含有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
这是算法...
但我还看不懂...
我认为文件操作还好弄.就算法,它是用递归来做的.
voidmode(intLL,intRR)
{
intL1,R1;
intmed=median(a,LL,RR);
split(a,med,LL,RR,L1,R1);
if(largest if(L1-LL>largest)mode(LL,L1-1); if(RR-R1>largest)mode(R1+1,RR); } //median用于找中位数,split用中位数将数组分2为段. [此问题还有待解决,谢谢各位的参与! ] //首先在此文件夹下建立名为qingsongin2.txt的文件 //其内容为6122235之格式.其中第一的数为数组表长度 #include #include #defineMAXSIZE20 usingnamespacestd; typedefintKeyLype; typedefintStatus; typedefstruct{ KeyLypekey; }RedType; typedefstruct{ RedTyper[MAXSIZE+1]; intlength; }SqList; intSelectSort(SqList&L) { inti,j,t; for(j=0;j for(i=1;i<=L.length-j;i++) if(L.r[i].key { t=L.r[i].key; L.r[i].key=L.r[i-1].key; L.r[i-1].key=t; } return0; }//简单选择排序 intmedian(SqListL,inta,intb) { intmed; if((a+b)%2==0) med=(a+b)/2; else med=(a+b-1)/2; returnmed; } intL1(SqListL,intmed) { while(med>=1&&med<=L.length) {if(L.r[med].key==L.r[med-1].key) med--; else returnmed-1; } } intR1(SqListL,intmed) { while(med>=1&&med<=L.length) {if(L.r[med].key==L.r[med+1].key) med++; else returnmed+1; } } voidmode(SqListL,inta,intb,int&max_num,int&max_count) { if(a==b) return; else { intl1,r1; intmed,j,k; k=j=med=median(L,a,b); l1=L1(L,med); r1=R1(L,j); if(max_count { 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); } } intmain() { ifstreamfin("qingsongin2.txt"); ofstreamfout("qingsongout2.txt"); SqListL; intmax_num;//众数 intmax_count;//众数的个数 if(fin.fail()) { cout<<"输入qingsongin2.txt文件出错! "< return-1; } if(fout.fail()) { cout<<"fout(\"qingsongout2.txt\");"< return-2; } intn;//n是数组表的长度 fin>>n; inti; for(i=1;i<=n;i++) //cin>>L.r[i].key; fin>>L.r[i].key; L.length=n; //cout< SelectSort(L); mode(L,1,L.length,max_num,max_count); //cout<<"众数是: "< //cout<<"重复次数是: "< fout<<"众数是: "< fout<<"它的个数是: "< cout<<"请查看此文件夹下的qingsongout2.txt文件"< return0; } 但它的前提是已排好序的. 算法第2章第11题集合划分问题 2009-11-0217: 37 Description 问题描述: 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和非空子集数m Output 计算出的不同的由m个非空子集组成的集合数输出 SampleInput SampleOutput 6 #include inta[1000][1000]; intt(intn,inti) { intm,pp=0; m=i-1;n--; if(m==n) pp++; else { if(n==1) pp++; else { if(m==1) pp++; else pp+=t(n,m); pp+=i*t(n,i); } } returnpp; } intmain() { intn,m,sum; cin>>n>>m; sum=t(n,m); cout< return0; } 43 算法第2章第10题集合划分问题 2009-11-0217: 36 Description 问题描述: 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行是元素个数n Output 将计算出的不同的非空子集数输出 SampleInput SampleOutput 52 #include inta[1000][1000]; intt(intn,inti) { intm,pp=0; m=i-1;n--; if(m==n) pp++; else { if(n==1) pp++; else { if(m==1) pp++; else pp+=t(n,m); pp+=i*t(n,i); } } //cout< returnpp; } intmain() { inti,j,n,sum=0; cin>>n; for(i=1;i<=n;i++) { if(i==1||i==n) a[n][i]=1; else a[n][i]=t(n,i); sum+=a[n][i]; } cout< return0; } 5 算法第2章第9题排列的字典序问题 2009-11-0217: 35 Description 问题描述: n个元素{1,2,...,n}有n! 个不同的排列。 将这n! 个排列按字典序排列,并编号为0,1,…, n! -1。 每个排列的编号为其字典序值。 例如,当n=3时,6个不同排列的字典序值如下: 字典序值012345 排列123132213231312321 编程任务: 给定n以及n个元素{1,2,...,n}的一个排列,计算出这个排列的字典序值,以及按字 典序排列的下一个排列。 Input 第1行是元素个数n。 接下来的1行是n个元素{1,2,...,n}的一个排列。 Output 将计算出的排列的字典序值和按字典序排列的下一个排列输出.第一行是字典序值,第2行是按字典序排列的下一个排列。 SampleInput SampleOutput 8227 26458317 #include #include voidxiageshuzi(intn,int*Src,int*Des) { inti,j,temp,min,mark; i=n-1; while((Src[i] i--; memcpy(Des,Src,n*sizeof(int)); if(i==0) return; else { temp=Des[i-1]; min=Des[i]; for(j=i;j { if((Des[j]>temp)&&(Des[j]<=min)) mark=j; } Des[i-1]=Des[mark]; Des[mark]=temp; for(;i for(j=n-1;j>i;j--) { if(Des[j] { temp=Des[j]; Des[j]=Des[j-1]; Des[j-1]=temp; } } } } intPermToNum(intn,int*p) { inti,j,count,k,ret,m; k=1; ret=0; for(i=n-1,j=0;i>=0;i--,j++) { count=p[i]-1; for(m=0;m if(p[m] count--; if(j==0) k=1; else k*=j; ret+=count*k; } returnret; } intmain() { intn,i,sum; inta[100]={0}; intDes[100]={0}; scanf("%d",&n); for(i=0;i scanf("%d",&a[i]); sum=PermToNum(n,a); printf("%d\n",sum); xiageshuzi(n,a,Des); for(i=0;i printf("%d",Des[i]); return0; } 8 26458173 算法第2章第6题半数单集问题 Description 给定一个自然数n,由n开始可以依次产生半数集set(n)中的数如下。 (1)n∈set(n); (2)在n的左边加上一个自然数,但该自然数不能超过最近添加的数的一半; (3)按此规则进行处理,直到不能再添加自然数为止。 例如,set(6)={6,16,26,126,36,136}。 半数集set(6)中有6个元素。 注意半数集不是多重集。 集合中已经有的元素不再添加到集合中。 编程任务: 对于给定的自然数n,编程计算半数集set(n)中的元素个数。 Input 只有1行,给出整数n。 (0 Output 只有1行,给出半数集set(n)中的元素个数。 SampleInput SampleOutput 6 #include intmain() { intn,N,p[10000],count,i,k,j; count=0; cin>>N; n=N/2; for(i=0;i<=n;i++) p[i]=0; for(i=1;i<=n;i++) { k=i/2; for(j=1;j<=k;j++) p[i]+=p[j]; p[i]+=1; count+=p[i]; if((i>10)&&(2*(i/10)<=i%10)) count-=p[i/10]; } count+=1; cout< return0; } 6 #include inta[1000]; intprog(intk) { inti,s; if(k==1) return1; else { if(a[k]==0) { s=1; for(i=1;i<=k/2;i++) { s+=prog(i); if(i>10&&(i/10<=(i%10)/2)) s-=prog(i/10); } a[k]=s; } returna[k]; } } intmain() { intj,n; while(scanf("%d",&n),n) { for(j=0;j<=n;j++) a[j]=0; printf("%d\n",prog(n)); } return0; } 算法第2章第5题半数集问题 2009-11-0217: 31 Description 给定一个自然数n,由n开始可以依次产生半数集set(n)中的数如下。 (1)n∈set(n); (2)在n的左边加上一个自然数,但该自然数不能超过最近添加的数的一半; (3)按此规则进行处理,直到不能再添加自然数为止。 例如,set(6)={6,16,26,126,36,136}。 半数集set(6)中有6个元素。 注意半数集是多重集。 编程任务: 对于给定的自然数n,编程计算半数集set(n)中的元素个数。 Input 有多行 每行为一个整数n (n大于0,且小于1000) Output 按行给出每行的结果(半数集set(n)中的元素个数)。 SampleInput SampleOutput 6 #include intmain() { intn,N,p[10000],count,i,k,j; while(cin>>N) { count=0; n=N/2; for(i=0;i<=n;i++) p[i]=0; for(i=1;i<=n;i++) { k=i/2; for(j=1;j<=k;j++) p[i]+=p[j]; p[i]+=1; count+=p[i]; } count+=1; cout< } return0; } 6 算法第2章第3题邮局选址问题 2009-11-0217: 30 Description 在一个按照东西和南北方向划分成规整街区的城市里,n个居民点散乱地分布在不同的 街区中。 用x坐标表示东西向,用y坐标表示南北向。 各居民点的位置可以由坐标(x,y)表示。 街区中任意2点(x1,y1)和(x2,y2)之间的距离可以用数值|x1-x2|+|y1-y2|度量。 居民们希望在城市中选择建立邮局的最佳位置,使n个居民点到邮局的距离总和最小。 给定n个居民点的位置,编程计算n个居民点到邮局的距离总和的最小值。 Input 输入数据的第1行是居民点数n,1<=n<=10000。 接下来n行 是居民点的位置,每行2个整数x和y,-10000<=x,y<=10000。 Output 输出的第1行中的数是n个居民点到邮局的距离总和的最小值 SampleInput SampleOutput 10 #include #include intcmp(constvoid*a,constvoid*b) { return*(int*)a-*(int*)b; } voidmain() { intn,i=0,j,s,pp,qq,*x,*y; scanf("%d",&n); x=malloc(sizeof(int)*n); y=malloc(sizeof(int)*n); for(i=0;i scanf("%d%d",x+i,y+i); qsort(x,n,sizeof(int),cmp); qsort(y,n,sizeof(int),cmp); for(i=0;i { s=0; for(j=0;j s+=(*(y+i)-*(y+j)); j++; for(;j s+=(*(y+j)-*(y+i)); if(i==0) pp=s; if(s pp=s; } for(i=0;i { s=0; for(j=0;j s+=(*(x+i)-*(x+j)); j++; for(;j s+=(*(x+j)-*(x+i)); if(i==0) qq=s; if(s qq=s; } printf("%d\n",pp+qq); } 5 12 22 13 3-2 33 算法第2章第2题众数问题 2009-11-0217: 29 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行是重数。 SampleInput SampleOutput Hint 2 3 #include #include intcmp(constvoid*,constvoid*); intmain() { intn,i,*a,num,max=0,t=1; scanf("%d",&n); a=malloc(sizeof(int)*n); for(i=0;i scanf
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 习题