2022年ACM程序设计与竞赛作业要点.docx
《2022年ACM程序设计与竞赛作业要点.docx》由会员分享,可在线阅读,更多相关《2022年ACM程序设计与竞赛作业要点.docx(34页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、ACM程序设计与竞赛作业1 .采药.金字塔问题3毛毛虫问题. Hamming Problem4 .字符串正反连接.去掉空格5 .成绩转换.金块问题9工资问题.“水仙花数”问题10 .大小写转换.取数游戏11 .整除问题.警察抓小偷12 .n!13 .汉诺塔问题.猴子吃桃问题(递归)14 . A4-B for Input-Output Practice . A+B for Input-Output Practice (EQ15 . A+B for Input-Output Practice (HI). A+B for Input-Output Practice (TV)For each thre
2、e prime numbers pl, p2 and p3, let*s define Hamming sequence Hi(pl, p2, p3), i=l,. as containing in increasing order all the natural numbers whose only prime divisors are pl, p2 or p3.For example, H(2, 3, 5) = 2, 3, 4, 5, 6, 8, 9, 10,12,15,16,18, 20, 24, 25, 27,.So H5(2, 3, 5)=6.输入In the single line
3、 of input file there are space-separated integers pl p2 p3 i.输出The output file must contain the single integer - Hi(pl, p2, p3). All numbers in input and output are less than 1CT18.样例输入样例输出6#include stdio.hint minx(int pl,int p2,int p3)/ 定义有参函数 minx;|int min二pl;if(p2min)min=p2;min=p3;return min;求pl,
4、p2,p3的最小值;int mainQ(int pl,p2,p3,t,i;int a,b,c;char num 10000;scanf(%d%d%d%dn,&pl,&p2,&p3,&t);a=b=c=0;num0 = 1;for(i=l;i=t;i+4-)numi=minx(pl*numa,p2*numb,p3*num|c);/调用 minx 函数;if(numi=pl*numa)a+;if(numi=p2*numb)b+;if(numi=p3*numc)c+;求所有的能被pl,p2,p3整除口勺数;printf(H%dnn,numt);return 0;心得:运用动态规划的思想,定义一种一维
5、数组,把所有符合条件的数按次序存进 一维数组中,这个编程运用了函数调用日勺措施求三个数日勺最小值,然后把这个最小 值存进一维数组中,每次存进一种数,下次都会用存进去H勺这个数求解下一种数, 进行循环。5问题B:字符串正反连接时间限制:1 See内存限制:128 MB提交:68处理:42网口题目描述所给字符串正序和反序连接,形成新串并输出输入任意字符串(长度V二50)输出字符串正序和反序连接所成的新字符串样例输入123abe样例输出123abccba321#include#includevoid mainQchar a50;定义一种字符串;int i,f;while(scanf(”%s”,&a)
6、!=EOF) 实现多行实例输入;(f=strlcn(a);把字符串口勺长度值赋给f;for(i=0;i=0;i)(print/%心叫);/把字符串反序输出;printf(,nH);)心得:定义一种字符串,运用strlenO函数获取字符串的长度值f,首先用for循环, 把这个字符串正序输出,然后再用for循环对这个字符串进行反序输出,这里重要考 察了输入输出。6问题C:去掉空格时间限制:1 Sec内存限制:128 MB提交:27处理:4DDD题目描述读入某些字符串,将其中的空格去掉。输入输入为多行,每行为一种字符串,字符串只由字母、数字和空格构成,长度不超过80o输入以End of file结束
7、。输出对于每行输入,输出转换后的字符串。样例输入Hello World 1 23Nice to meet youJabc样例输出HelloWorld 123Nicetomeetyou abc提醒 用scanf是不能读入一行有空格的字符串日勺,用gets吧。用“gets(str) !二NULL”可 以判断输入与否结束,假如此条件为假(即gets(str) = NULL),那么表达输入结束(对 于此题)。#include#includcvoid rnainQint i,f;char a90;定义一种字符串;while(gets(a)!=NULL)f=strlcn(a);把字符串的长度值赋给f;fo
8、r(i=0;if;i+)(printf(”c”闵i+1);/去掉空格; i=i+l;)elseprintf(c”,ai);没有空格,直接输出;printf(nnM);心得:这里也是重要考察输入输出问题,首先也是定义了一种字符串,用strlenO函 数获得字符串的长度K进行f次循环,判断这个字符串与否有空格?假如有把数组 中的每个数往后进一位,即去点空格,假如没有直接输出。7问题D:成绩转换时间限制:1 See内存限制:128 MB提交:78处理:30网口题目描述输入一种百分制的成绩3将其转换成对应日勺等级,详细转换规那么如下:90100 为 A;8089为B;7079为C;6069为D;059
9、为E;输入输入数据有多组,每组占一行,由一种整数构成。输出对于每组输入数据,输出一行。假如输入数据不在。10。范围内,请输出一行:“Score is error!w。样例输入56 67100123样例输出EDAScore is error!提醒#includeint main。int x;while(scanf(%d”,&x)!=EOB 实现多行实例输入;if(x60)printf(En”);else if(x70)printf(Dn”);else if(x80)printf(nCnn);else if(x90) printfCBnn);else if(x=2),最优秀日勺雇员得到其中最重的一
10、块, 最差的雇员得到其中最轻的一块。假设有一台比较重量H勺仪器,但愿用至少的比较 次数找出最重和最轻日勺金块。输入输入共两行, 第一行输入金块的数量N100000;第二行N金块的重量,用空格间隔。输出两个数用空格分开,最重金块 最轻金块样例输入537964样例输出93#includeint mainQint n,al00000;int max,min,i;“出血做2(”十,&0!=。丹/实现多行实例输入;(for(i=0;imax)max=ai;/求最最重的金块;fbr(i=l;in;i+)22 ,埃及分数23 .完数. Fibbonacci Number _Hdu 207024 . Pake
11、ts.不要 62 _Hdu 20891问题B:采药时间限制:1 Sec内存限制:128 MB提交:87处理:72题目描述辰辰是个很有潜能、天资聪颖口勺孩子,他的梦想是成为世界上最伟大的医师。为此, 他想拜附近最有威望口勺医师为师。医师为了判断他的资质,给他出了一种难题。医 师把他带到个到处都是草药的山洞里对他说:“孩子,这个山洞里有某些不一样的 草药,采每一株都需要某些时间,每一株也有它自身的价值。我会给你一段时间, 在这段时间里,你可以采到某些草药。假如你是一种聪颖H勺孩子,你应当可以让采 到的草药H勺总价值最大。”假如你是辰辰,你能完毕这个任务吗?输入输入的第一行有两个整数T (1 T10
12、00)和M (1M 100) , T代表总共可以 用来采药口勺时间,M代表山洞里口勺草药的数目。接下来|勺M行每行包括两个在1到 100之间(包括和100)的整数,分别表达采摘某株草药口勺时间和这株草药的价值。min=ai;”/求最轻的金块;printf(n%d %dnn,max,min);)return 0;心得:这题重要运用分治算法啊思想,把一种大问题提成一种个小日勺子问题去求解, 这个题目是经典的二分法问题,把这个题提成两个小问题,即求最重日勺和求最轻日勺 金块,首先定义了一种一维数组,把所有金块的质量存入其中,把数组的初始值赋 给最重H勺和最轻H勺金块,然后运用循环对数组中每个金块H勺
13、质量与金块H勺初始值进 行比较,求H勺最重和最轻的金块,然后输出。9问题B:工资问题时间限制:1 Sec内存限制:128 MB提交:121处理:74non题目描述某单位给每个职工发工资(精确到元),为了保证不要临时兑换零钱,且取款的张 数至少,取工资前要记录出所有职工的工资所需多种币值(100, 50, 20, 10, 5, 2, 1元共7种)的张数,请编程完毕。输入输入一种工资数10000元输出输出各个币种的张数,没有的用0替代,中间用空格分开样例输入173样例输出1110011#includeint mainQint j,z,a;int b7=100,50,20,10,5,2,1;把所有币
14、值按从从大到小的次序存到一位数组中;int s7 = ();/定义一种一位数组,元素值全为0;scanf(%d,&z);for(j=0;j7;j+)(a=z/bj;sQ=a;z=z-a*bj; 求需要各个币值的个数;printf(H%dH,sO);for(j=l;j7;j+)printf(M %d,sj);输出需要各个币值的个数;return 0;心得:这个题重耍运用贪婪算法H勺措施,运用可行的方略,求出可行解的一种解元 素由所有解元素合成问题的一种可行解。要想获得的张数至少,可以先考虑币值最大 的进行分发,然后再取更小现金口勺币值。依次取之。首先定义一种一维数组,把币 值从大到小存进去,运用
15、一循环,把每次算的钱数口勺成果,依次对数组的币值进行 取整。然后依次存入数组输出。10问题C: “水仙花数”问题1时间限制:1 Sec内存限制:128 MB提交:138处理:75DDD题目描述判断一种数与否为“水仙花数”,所谓“水仙花数”是指这样日勺一人数:其各位数字口勺立 方和等于该数自身。例如:371是一种“水仙花数”,371 =3人3+7八3+13.输入一种三位数输出I或者0(1代表此数为水仙花数,0代表此数不是水仙花数)样例输入371样例输出1#includevoid mainQ(int n,x,y,z;scanf(H%dM,&n);x=n/100;求三位数口勺百位数字;z=n%10;
16、求三位数日勺个位数字;y=(n-(x*100+z)/10;/求三位数的十位数字;if(n=x*x*x+y*y*y+z*z*z)printf(%dM,l);elseprintf(“d”,0);/判断这个三位数与否为水仙花数,是输出1,否输出2;)心得:首先,输入一种三位数,运用对这个数取整,取余,运用数学公式,分别算 出它日勺百位,十位,和个位的数字,然后判断这三个数字日勺平方和与否等于这个三 位数,假如是,输出1,假如不是输出0.11问题E:大小写转换时间限制:1000 Sec内存限制:65536 MB提交:182处理:116UUU题目描述读入某些字符串,将其中的小写字母转成大写字母(其他字符
17、不变)。输入输入为多行,每行为一种字符串,字符串只由字母和数字构成,长度不超过8()。输 入以End of file结束。输出对于每行输入,输出转换后的字符串。样例输入HelloICPC12345abcde样例输出HELLOICPC12345ABCDE#include#includevoid mainQint j;char string80;/定义一种字符串;while(scanf(s”,&string)!= EOF) 实现多行实例输入;for(j=0;j=,a,)&(stringj=,z!)string。尸string。-32;/实现字母大小写转换;printf(n%snn,string);
18、心得:这个题目重耍考察输入输出,尚有大小写转换问题,首先还是定义一种字符 串,用while(scanf(”s”,&strin初=EOF)语句实现多行实例输入,对这个字符串进行循 环,假如这个字符串有大写的话,转化成小写的,假如有小写口勺话,那么转化成大 写电12问题B:取数游戏时间限制:1 Sec内存限制:128 MB提交:46处理:39non题目描述有2个人轮番取2n个数中日勺n个数,所取数之和大者为胜,请编写算法,让先取数 者胜,模拟取数过程。输入输入两行,第一行一种整数NUOOOOO;第二行N个数,用空格分开。输出输出取胜人取数和。失败人取数的和,空格分开。样例输入6123456样例输出
19、129#includeint main()(int n,i,sum l,sum2,al OOOOO;whilc(scanf(”%d”,&n)!二EOF) 实现多行实例输入;(suml=sum2=0;for(i=0;in;i+4-)scanff%d,&ai);for(i=0;in;i=i+2)suml=sumH-ai;for(i=l;in;i=i+2)sum2=sum2+ai;/隔数取数求和:suml ,sum2 ;printf(M%d %dnn,suml,sum2);elseprintf(%d %dn,sum2,sum 1);次序输出取胜人取数和。失败人取数和; return 0;)心得;这题
20、重要运用贪心算法的思想,要想先取数人获胜,就得让这个人每一步都尽 量获得最大日勺数,这样他取数口勺和才会总体不小于后取数日勺那个人的取数和。首先 定义一种一维数组,把要获得数从小到大的次序放在里面,然后一种人从第一种按 照隔一种数取,求和suml;另一种人从第二个按照隔一种人取,求和sum2,比较sum1 和sum2 H勺最大值,输出。13问题C:整除问题时间限制:1 Sec内存限制:128 MB提交:70处理:44(网题目描述编写算法对输入的一种整数,判断它能否被3, 5, 7整除,并输出如下信息之一:能同步被3, 5, 7整除;能被其中两个数(要指出哪两个)整除;能被其中一种数(要指出那一
21、种)整除;不能被3, 5, 7任一种整除;输入输入一种整数Viooooo;输出假如都能整除输出“油”假如都不能整除输出“ none假如能被3和5整除那么输出“3 5”。中间有一种空格,注意按由小到大输出。样例输入35样例输出57#includevoid mainQ(long n; int k;scanf(n%d,&n);k=(n%3=0)+(n%5=0)*2+(n%7=0)*4);/判断整数与否能被 2,3,5 整除;switch (k)(case 7:printf(naH);break;case 6:printf(n5 7H);break;case 5:printf(*3 7);break;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022 ACM 程序设计 竞赛 作业 要点
限制150内