ACM算法设计实验题目汇总.docx
- 文档编号:17367993
- 上传时间:2023-07-24
- 格式:DOCX
- 页数:67
- 大小:39.90KB
ACM算法设计实验题目汇总.docx
《ACM算法设计实验题目汇总.docx》由会员分享,可在线阅读,更多相关《ACM算法设计实验题目汇总.docx(67页珍藏版)》请在冰点文库上搜索。
ACM算法设计实验题目汇总
ACM算法设计实验题目汇总
1020PermutationwithRepetition1
1021双色Hanoi塔问题3
1022SearchNumber4
1023整数划分问题5
1024Counting6
1025输油管道问题8
1026IntegerFactorization9
1027邮局选址问题11
1031矩阵连乘问题13
1032最长公共子序列14
1033MAXSUM16
1034NumberTriangles17
1035编辑距离问题18
1036PebbleMerging19
1037租用游艇问题21
1038MinimalmSums22
1040KnapsackProblem24
1041最优装载25
1042LectureHalls26
1043程序存储问题29
1048OptimalServices30
1049汽车加油问题30
1059子集树问题32
10600-1Knapsack33
1061排列树问题36
1062ProblemDGeneralSearch38
1020PermutationwithRepetition
Description
R={r1,r2,…,rn}是要进行排列的n个元素。
其中元素r1,r2,…,rn可能相同。
试设计一个算法,列出R的所有不同排列。
编程任务:
给定n以及待排列的n个元素。
计算出这n个元素的所有不同排列。
Input
输入由多组测试数据组成。
每组测试数据的第1行是元素个数n,1<=n<=500。
接下来的1行是待排列的n个元素。
Output
对应每组输入,将计算出的n个元素的所有不同排列输出,每种排列单独一行。
最后1行中的数是排列总数。
SampleInput
4
aacc
SampleOutput
aaccacacaccacaaccacaccaa6
#include
#include
usingnamespacestd;
intans;
intok(charstr[],inta,intb)
{
if(b>a)
for(inti=a;i
if(str[i]==str[b])
return0;
return1;
}
voidperm(charstr[],intk,intm)
{
inti;
if(k==m)
{
ans++;
for(i=0;i<=m;i++)
{
printf("%c",str[i]);
}
printf("\n");
}
else
{
for(i=k;i<=m;i++)
if(ok(str,k,i))
{
swap(str[k],str[i]);
perm(str,k+1,m);
swap(str[k],str[i]);
}
}
}
intmain(intargc,char*argv[])
{
charstr[1000];
intn;
while(scanf("%d",&n)!
=EOF)
{
ans=0;
scanf("%s",str);
perm(str,0,n-1);
printf("%d\n",ans);
}
return0;
}
1021双色Hanoi塔问题
Description
A、B、C是3个塔座。
开始时,在塔座A上有一叠共n个圆盘,这些圆盘自下而上,由大到小地叠在一起。
各圆盘从小到大编号为1,2,……,n,奇数号圆盘着蓝色,偶数号圆盘着红色,如图所示。
现要求将塔座A上的这一叠圆盘移到塔座B上,并仍按同样顺序叠置。
在移动圆盘时应遵守以下移动规则:
规则
(1):
每次只能移动1个圆盘;
规则
(2):
任何时刻都不允许将较大的圆盘压在较小的圆盘之上;
规则(3):
任何时刻都不允许将同色圆盘叠在一起;
规则(4):
在满足移动规则
(1)-(3)的前提下,可将圆盘移至A,B,C中任一塔座上。
试设计一个算法,用最少的移动次数将塔座A上的n个圆盘移到塔座B上,并仍按同样顺序叠置。
编程任务:
对于给定的正整数n,编程计算最优移动方案。
Input
输入由多组测试数据组成。
每组测试数据的第1行是给定的正整数n。
Output
对应每组输入,输出的每一行由一个正整数k和2个字符c1和c2组成,表示将第k个圆盘从塔座c1移到塔座c2上。
SampleInput
3
SampleOutput
1AB
2AC
1BC
3AB
1CA
2CB
1AB
#include
usingnamespacestd;
intmain()
{voidhanoi(int,char,char,char);
intm;cin>>m;
hanoi(m,'A','B','C');
return0;
}
voidhanoi(intn,chara,charb,charc)
{voidmove(int,char,char);
if(n==1)move(n,a,b);else
{hanoi(n-1,a,c,b);
move(n,a,b);
hanoi(n-1,c,b,a);
}
}
voidmove(intn,charx,chary)
{cout< 1022SearchNumber Description 科研调查时得到了n个自然数,每个数均不超过1500000000。 已知不相同的数不超过10000个,现在需要在其中查找某个自然数,如找到则输出并统计这个自然数出现的次数,如没找到则输出NO。 Input 输入由多组测试数据组成。 每组测试数据输入包含n+1行; 第一行是两个整数n和x,n表示自然数的个数,x表示要查找的自然数,两者之间用空格隔开; 第2至n+1每行一个自然数。 Output 对应每组输入,如果查找到x,则每行输出两个整数,分别是自然数和该数出现的次数,其间用一个空格隔开;如果没有查找到x,则每行输出NO. SampleInput 8100 2 4 2 4 5 100 2 100 83 2 4 2 4 5 100 2 100 SampleOutput 1002 NO #include #include #defineLEN200000 inta[LEN],temp,mid; intsort(int*a,intlow,inthigh)//一趟快排 { mid=a[low]; while(low { while(low temp=a[low];a[low]=a[high];a[high]=temp; while(low temp=a[low];a[low]=a[high];a[high]=temp; } returnlow; } voidquicksort(int*a,intlow,inthigh)//快排递归 { //intmid; if(low { mid=sort(a,low,high); quicksort(a,low,mid-1); quicksort(a,mid+1,high); } } intmain() { inti,n,s; intSum=0; scanf("%d",&n); scanf("%d",&s); for(i=0;i {scanf("%d",&a[i]);} quicksort(a,0,n-1);//调用快排 for(i=0;i { if(a[i]==s) { Sum++; } } if(Sum==0) { printf("NO"); } else { printf("%d%d",s,Sum); } } 1023整数划分问题 Description 将正整数n表示成一系列正整数之和: n=n1+n2+…+nk,其中n1≥n2≥…≥nk≥1,k≥1。 正整数n的这种表示称为正整数n的划分。 求正整数n的不同划分个数。 例如正整数6有如下11种不同的划分: 6; 5+1; 4+2,4+1+1; 3+3,3+2+1,3+1+1+1; 2+2+2,2+2+1+1,2+1+1+1+1; 1+1+1+1+1+1。 Input 输入包含n+1行; 第一行是一个整数n,表示有n个测试用例; 第2至n+1每行一个正整数。 Output 对应每组输入,输出正整数n的不同划分个数。 SampleInput 2 5 6 SampleOutput 7 11 #include intsplit(intn,intm) { if(n<1||m<1)return0; if(n==1||m==1)return1; if(n if(n==m)return(split(n,m-1)+1); if(n>m)return(split(n,m-1)+split((n-m),m)); } intmain() { intk,i; inta[100]; scanf("%d",&k); for(i=0;i { scanf("%d",&a[i]); } for(i=0;i { printf("%d\n",split(a[i],a[i])); } } 1024ProblemA: Counting Description 问题描述: 一本书的页码从自然数1开始顺序编码直到自然数n。 书的页码按照通常的习惯编排,每个页码都不含多余的前导数字0。 例如,第6页用数字6表示,而不是06或006等。 数字计数问题要求对给定书的总页码n,计算出书的全部页码中分别用到多少次数字0,1,2,…,9。 编程任务: 给定表示书的总页码的10进制整数n(1≤n≤109)。 编程计算书的全部页码中分别用到多少次数字0,1,2,…,9。 Input 输入由多组测试数据组成。 每组测试数据输入只有1行,给出表示书的总页码的整数n。 Output 对应每组输入,输出共有10行,在第k行输出页码中用到数字k-1的次数,k=1,2,…,10。 SampleInput 11 SampleOutput 1 4 1 1 1 1 1 1 1 1 程序代码: #include voidstatNum(longintsn[10],intn) { inti,c,k,s,pown; for(i=0;i<10;i++) sn[i]=0; for(k=s=0,pown=1;n>0;k++,n/=10,pown*=10) { c=n%10; for(i=0;i<10;i++) sn[i]+=c*k*(pown/10); for(i=0;i sn[i]+=pown; sn[c]+=1+s; sn[0]-=pown; s+=c*pown; } } intmain() { inti,n; longintsn[10]; cin>>n; statNum(sn,n); for(i=0;i<10;i++) cout< return0; } 1025ProblemB: 输油管道问题 Description 问题描述: 某石油公司计划建造一条由东向西的主输油管道。 该管道要穿过一个有n口油井的油田。 从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。 如果给定n口油井的位置,即它们的x坐标(东西向)和y坐标(南北向),应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置? 编程任务: 给定n口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。 Input 输入由多组测试数据组成。 每组测试数据输入的第1行是油井数n,1≤n≤10000。 接下来n行是油井的位置,每行2个整数x和y,-10000≤x,y≤10000。 Output 对应每组输入,输出的第1行中的数是油井到主管道之间的输油管道最小长度总和。 SampleInput 5 12 22 13 3-2 33 SampleOutput 6 #include usingstd: : cout; usingstd: : endl; usingstd: : cin; intsPath(int*,int,int); intaSize=0; intmain(){ //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); cin>>aSize; int*x=newint[aSize]; int*y=newint[aSize]; for(inti=0;i cin>>x[i]; cin>>y[i]; } intp=0; p=sPath(y,0,aSize-1); cout< return0; } intsPath(inta[],intx,inty){ intf,b,total=0; if(x==y){//计算该点到其他点的距离 for(inti=0;i total+=abs(a[x]-a[i]); returntotal; } //分两部分计算各自的最优值 f=sPath(a,x,(x+y)/2); b=sPath(a,(x+y)/2+1,y); returnf f: b;//归并操作,返回这两部分中更优解 } 1026ProblemC: IntegerFactorization Description 问题描述: 大于1的正整数n可以分解为: n=X1*X2*…*Xm。 例如,当n=12时,共有8种不同的分解式: 12=12; 12=6*2; 12=4*3; 12=3*4; 12=3*2*2; 12=2*6; 12=2*3*2; 12=2*2*3。 编程任务: 对于给定的正整数n,编程计算n共有多少种不同的分解式。 Input 输入由多组测试数据组成。 每组测试数据输入第一行有1个正整数n(1≤n≤2000000000)。 Output 对应每组输入,输出计算出的不同的分解式数。 SampleInput 12 SampleOutput 8 #include #include structDP { intnum; intsum; }d[50000]={0}; intmax=0; voidqsort(intlow,inthigh,structDPkey[]) { inti=low,j=high; structDPtag=key[i]; if(i { do { while(tag.num if(i { key[i]=key[j]; i++; while(tag.num>=key[i].num&&i if(i { key[j]=key[i]; j--; } } }while(i key[i]=tag; qsort(low,j-1,key); qsort(i+1,high,key); } } intdfs(intleft) { inti,p; intl,r,m; intcount=0; l=0;r=max; while(l<=r) { m=(l+r)>>1; if(d[m].num } p=l;if(d[p].sum)returnd[p].sum; for(i=1;i<=d[i].num;i++) { if(left%d[i].num==0)count+=dfs(left/d[i].num); } d[p].sum=count; returncount; } intmain(void) { inti,j,tmp; intn; scanf("%d",&n);tmp=sqrt(n); for(i=1;i<=tmp;i++) { if(n%i==0) { d[max].num=i;max++; d[max].num=n/i;max++; } }max--; qsort(0,max,d); d[0].sum=1; printf("%d\n",dfs(n)); return0; } 1027ProblemD: 邮局选址问题 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 5 12 22 13 3-2 33 SampleOutput 10 #include usingnamespacestd; voidQuickSort(intarry[],intl,inth); intmain() { inti,j,n,l,h,x,y,a,b; intsum1=0,sum2=0; cin>>n; l=0; h=n-1; intarry[10000][2]; int*x1=newint[n]; int*y1=newint[n]; for(i=0;i for(j=0;j<2;j++) { scanf("%d",&arry[i][j]); } for(i=0;i { x1[i]=arry[i][0]; y1[i]=arry[i][1]; } QuickSort(x1,l,h); QuickSort(y1,l,h); x=x1[(n-1)/2]; y=y1[(n-1)/2]; for(i=0;i { a=arry[i][0]-x; if((arry[i][0]-x)<0) { a=x-arry[i][0]; } b=arry[i][1]-y; if((arry[i][1]-y)<0) { b=y-arry[i][1]; } sum1+=a; sum2+=b; } cout< return0; } voidQuickSort(intarry[],intl,inth) { inti=l,j=h;//低LOW,高HIGH inttemp=arry[l];//取第一个做标准数据元书的 while(i { while(i if(i { arry[i]=arry[j]; i++; } while(i if(i { arry[j]=arry[i]; j--; } } arry[i]=temp; if(l if(i } 1031ProblemA: 矩阵连乘问题 Description 给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2,…,n-1。 如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。 Input 输入包含多组测试数据。 第一行为一个整数C,表示有C组测试数据,接下来有2*C行数据,每组测试数据占2行,每组测试数据第一行是1个整数n,表示有n个矩阵连乘,接下来一行有n+1个数,表示是n个矩阵的行及第n个矩阵的列,它们之间用空格隔开. Output 你的输出应该有C行,即每组测试数据的输出占一行,它是计算出的矩阵最少
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- ACM 算法 设计 实验 题目 汇总