ACM作业.docx
- 文档编号:2202817
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:46
- 大小:36.06KB
ACM作业.docx
《ACM作业.docx》由会员分享,可在线阅读,更多相关《ACM作业.docx(46页珍藏版)》请在冰点文库上搜索。
ACM作业
ACM程序设计与竞赛作业
1.采药
2.金字塔问题
3.毛毛虫问题
4.HammingProblem
5.字符串正反连接
6.去掉空格
7.成绩转换
8.金块问题
9.工资问题
10.“水仙花数”问题
11.大小写转换
12.取数游戏
13.整除问题
14.警察抓小偷
15.n!
16.汉诺塔问题
17.猴子吃桃问题(递归)
18.A+BforInput-OutputPractice(I)
19.A+BforInput-OutputPractice(II)
20.A+BforInput-OutputPractice(III)
21.A+BforInput-OutputPractice(IV)
22.埃及分数
23.完数
24.FibbonacciNumber_Hdu2070
25.Pakets
26.不要62_Hdu2089
1问题B:
采药
时间限制:
1Sec 内存限制:
128MB
提交:
87 解决:
72
[提交][状态][讨论版]
题目描述
辰辰是个很有潜能、天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。
为此,他想拜附近最有威望的医师为师。
医师为了判断他的资质,给他出了一个难题。
医师把他带到个到处都是草药的山洞里对他说:
“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。
我会给你一段时间,在这段时间里,你可以采到一些草药。
如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。
”
如果你是辰辰,你能完成这个任务吗?
输入
输入的第一行有两个整数T(1≤T≤1000)和M(1≤M≤100),T代表总共能够用来采药的时间,M代表山洞里的草药的数目。
接下来的M行每行包括两个在1到100之间(包括1和100)的整数,分别表示采摘某株草药的时间和这株草药的价值。
输出
输出只包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。
样例输入
703
71100
691
12
样例输出
3
#include"stdio.h"
voidmain()
{
inta[102][1002]={0};
intt,t1,m1,m,i,i1,k=1;
scanf("%d%d",&t,&m);
scanf("%d%d",&t1,&m1);
for(i1=1;i1<=t;i1++)//处理第一行
{
if(i1>=t1)
a[k][i1]=m1;
}
k++;
for(i=2;i<=m;i++)
{scanf("%d%d",&t1,&m1);
for(i1=1;i1<=t;i1++)
{
if(i1 a[k][i1]=a[k-1][i1]; else//可以采的情况 { if(a[k-1][i1]>m1+a[k-1][i1-t1]) a[k][i1]=a[k-1][i1];//采完总价值下降 else a[k][i1]=m1+a[k-1][i1-t1];//值得采的情况; } } k++; } printf("%d",a[m][t]); } 心得: 这是一个动态规划的题目,首先定义一个二维数组,根据草药的性价比,优先采取较高的草药,如果时间不够,则降低性价比继续采取草药,直至时间结束,根据采集的草药计算它的最大值,这题通过比较算出可能采的情况,和不能采的情况,如果能采,那再判断值不值得采,得出最优解。 2问题A: 金字塔问题 时间限制: 1Sec 内存限制: 128MB 提交: 54 解决: 32 [提交][状态][讨论版] 题目描述 給一个金字塔,如上图所示,请你求出一个从塔顶到塔底的路径,要求路径经过的点的数字和最小。 例如上图所示的金字塔的最小路径为: 40 输入 输入第一行是一个整数n<1000; 接下来是n行, 第一行一个数; 第二行两个数; 。 。 。 第n行n个数; 数之间用空格分开。 数的链接方式如图所示。 输出 一个数,就是从塔顶到塔底的路径的最小距离。 样例输入 5 9 1215 1068 31895 19710416 样例输出 40 #include voidmain() { inti,j,n; inta[100][100];定义一个二维数组; scanf("%d",&n); for(i=1;i<=n;i++) for(j=1;j<=i;j++) { scanf("%d",&a[i][j]); } for(i=n-1;i>=1;i--) for(j=1;j<=i;j++)//从最后一行开始处理; { if(a[i+1][j]>a[i+1][j+1]) a[i][j]=a[i][j]+a[i+1][j+1]; else a[i][j]=a[i][j]+a[i+1][j];//求得每次路径最小值; } printf("%d",a[1][1]); } 心得: 这个题目主要运用了动态规划的思想,定义一个二维数组,把所输入的数据存入进去,然后从它的第一行处理,比较相邻位置数的大小,取最小的路径和上一行对应的数相加,取得最小路径,进行循环,直到求出数组中a[1][1],即所求的结果。 3问题B: 毛毛虫问题 时间限制: 1Sec 内存限制: 128MB 提交: 32 解决: 16 [提交][状态][讨论版] 题目描述 Mary在她家门口水平种了一排苹果树,共有N棵。 突然Mary发现在左起第P棵树上(从1开始计数)有一条毛毛虫。 为了看到毛毛虫变蝴蝶的过程,Lele在苹果树旁观察了很久。 虽然没有看到蝴蝶,但Lele发现了一个规律: 每过1分钟,毛毛虫会随机从一棵树爬到相邻的一棵树上。 比如刚开始毛毛虫在第2棵树上,过1分钟后,毛毛虫可能会在第1棵树上或者第3棵树上。 如果刚开始时毛毛虫在第1棵树上,过1分钟以后,毛毛虫一定会在第2棵树上。 现在告诉你苹果树的数目N,以及毛毛刚开始所在的位置P,请问,在M分钟后,毛毛虫到达第T棵树,一共有多少种行走方案数。 输入 输入四个整数NPMT。 输出 输出一个整数,就是行走的方案数。 样例输入 7444 样例输出 6 #include voidmain() { inti,j; intp,m,n,t; inta[100][100]={0};//定义一个二维数组; scanf("%d%d%d%d",&n,&p,&m,&t); a[0][p]=1;毛毛虫刚开始在数组中的位置; for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { a[i][j]=a[i-1][j-1]+a[i-1][j+1];//每一步的方案数; } } printf("%d\n",a[m][t]);M分钟后到T棵树行走的方案数; } 心得: 这一题运用了动态规划的思想,毛毛虫的每一步都会影响下一步的结果,所以首先按照普通情况找出规律及其其公式,进而算出方案数。 首先定义一个二维数组,初始化毛毛虫的起始位置,然后通过两个循环,求出毛毛虫走每一步的方案数,存在二维数组中,然后求出第M分钟到T棵树行走的方案数。 4问题A: HammingProblem 时间限制: 1Sec 内存限制: 128MB 提交: 61 解决: 23 [提交][状态][讨论版] 题目描述 Foreachthreeprimenumbersp1,p2andp3,let'sdefineHammingsequenceHi(p1,p2,p3),i=1,...ascontaininginincreasingorderallthenaturalnumberswhoseonlyprimedivisorsarep1,p2orp3. Forexample,H(2,3,5)=2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,... SoH5(2,3,5)=6. 输入 Inthesinglelineofinputfiletherearespace-separatedintegersp1p2p3i. 输出 Theoutputfilemustcontainthesingleinteger-Hi(p1,p2,p3).Allnumbersininputandoutputarelessthan10^18. 样例输入 2355 样例输出 6 #include"stdio.h" intminx(intp1,intp2,intp3)//定义有参函数minx; { intmin=p1; if(p2 min=p2; if(p3 min=p3; returnmin; }//求p1,p2,p3的最小值; intmain() { intp1,p2,p3,t,i; inta,b,c; charnum[10000]; scanf("%d%d%d%d",&p1,&p2,&p3,&t); a=b=c=0; num[0]=1; for(i=1;i<=t;i++) {num[i]=minx(p1*num[a],p2*num[b],p3*num[c]);//调用minx函数; if(num[i]==p1*num[a]) a++; if(num[i]==p2*num[b]) b++; if(num[i]==p3*num[c]) c++; }求所有的能被p1,p2,p3整除的数; printf("%d\n",num[t]); return0; } 心得: 运用动态规划的思想,定义一个一维数组,把所有符合条件的数按顺序存进一维数组中,这个编程运用了函数调用的方法求三个数的最小值,然后把这个最小值存进一维数组中,每次存进一个数,下次都会用存进去的这个数求解下一个数,进行循环。 5问题B: 字符串正反连接 时间限制: 1Sec 内存限制: 128MB 提交: 68 解决: 42 [提交][状态][讨论版] 题目描述 所给字符串正序和反序连接,形成新串并输出 输入 任意字符串(长度<=50) 输出 字符串正序和反序连接所成的新字符串 样例输入 123abc 样例输出 123abccba321 #include #include voidmain() { chara[50];//定义一个字符串; inti,f; while(scanf("%s",&a)! =EOF)//实现多行实例输入; { f=strlen(a);//把字符串的长度值赋给f; for(i=0;i { printf("%c",a[i]);//把字符串正序输出; } for(i=f-1;i>=0;i--) { printf("%c",a[i]);//把字符串反序输出; } printf("\n"); } } 心得: 定义一个字符串,运用strlen()函数获取字符串的长度值f,首先用for循环,把这个字符串正序输出,然后再用for循环对这个字符串进行反序输出,这里主要考察了输入输出。 6问题C: 去掉空格 时间限制: 1Sec 内存限制: 128MB 提交: 27 解决: 4 [提交][状态][讨论版] 题目描述 读入一些字符串,将其中的空格去掉。 输入 输入为多行,每行为一个字符串,字符串只由字母、数字和空格组成,长度不超过80。 输入以“Endoffile”结束。 输出 对于每行输入,输出转换后的字符串。 样例输入 HelloWorld 123 Nicetomeetyou abc 样例输出 HelloWorld 123 Nicetomeetyou abc 提示 用scanf是不能读入一行有空格的字符串的,用gets吧。 用“gets(str)! =NULL”可以判断输入是否结束,如果此条件为假(即gets(str)==NULL),则表示输入结束(对于本题)。 #include #include voidmain() { inti,f; chara[90];//定义一个字符串; while(gets(a)! =NULL) { f=strlen(a);//把字符串的长度值赋给f; for(i=0;i { if(a[i]=='') { printf("%c",a[i+1]);//去掉空格; i=i+1; } else printf("%c",a[i]);//没有空格,直接输出; } printf("\n"); } } 心得: 这里也是主要考察输入输出问题,首先也是定义了一个字符串,用strlen()函数获得字符串的长度f,进行f次循环,判断这个字符串是否有空格? 如果有把数组中的每个数往后进一位,即去点空格,如果没有直接输出。 7问题D: 成绩转换 时间限制: 1Sec 内存限制: 128MB 提交: 78 解决: 30 [提交][状态][讨论版] 题目描述 输入一个百分制的成绩t,将其转换成对应的等级,具体转换规则如下: 90~100为A; 80~89为B; 70~79为C; 60~69为D; 0~59为E; 输入 输入数据有多组,每组占一行,由一个整数组成。 输出 对于每组输入数据,输出一行。 如果输入数据不在0~100范围内,请输出一行: “Scoreiserror! ”。 样例输入 56 67 100 123 样例输出 E D A Scoreiserror! 提示 #include intmain() { intx; while(scanf("%d",&x)! =EOF)//实现多行实例输入; { if(x<60) printf("E\n"); elseif(x<70) printf("D\n"); elseif(x<80) printf("C\n"); elseif(x<90) printf("B\n"); elseif(x<=100) printf("A\n"); else printf("Scoreiserror! \n"); }//分数转换为等级; return0; } 心得: 这里主要运用了选择语句,用while(scanf("%d",&x)! =EOF)语句实现多行实例输入,然后把所输入的分数通过if语句进行判断,转换成相应的等级,输出。 8问题A: 金块问题 时间限制: 1Sec 内存限制: 128MB 提交: 92 解决: 71 [提交][状态][讨论版] 题目描述 老板有一袋金块(共n块,n是2的冪(n>=2)),最优秀的雇员得到其中最重的一块,最差的雇员得到其中最轻的一块。 假设有一台比较重量的仪器,希望用最少的比较次数找出最重和最轻的金块。 输入 输入共两行, 第一行输入金块的数量N<100000; 第二行N金块的重量,用空格间隔。 输出 两个数用空格分开,最重金块最轻金块 样例输入 5 37964 样例输出 93 #include intmain() { intn,a[100000]; intmax,min,i; while(scanf("%d",&n)! =EOF)//实现多行实例输入; { for(i=0;i scanf("%d",&a[i]); max=min=a[0];//把数组a[0]的值赋给max和min; for(i=1;i { if(a[i]>max) max=a[i]; }//求最最重的金块; for(i=1;i { if(a[i] min=a[i]; }//求最轻的金块; printf("%d%d\n",max,min); } return0; } 心得: 这题主要运用分治算法的思想,把一个大问题分成一个个小的子问题去求解,这个题目是典型的二分法问题,把这个题分成两个小问题,即求最重的和求最轻的金块,首先定义了一个一维数组,把所有金块的质量存入其中,把数组的初始值赋给最重的和最轻的金块,然后运用循环对数组中每个金块的质量与金块的初始值进行比较,求的最重和最轻的金块,然后输出。 9问题B: 工资问题 时间限制: 1Sec 内存限制: 128MB 提交: 121 解决: 74 [提交][状态][讨论版] 题目描述 某单位给每个职工发工资(精确到元),为了保证不要临时兑换零钱,且取款的张数最少,取工资前要统计出所有职工的工资所需各种币值(100,50,20,10,5,2,1元共7种)的张数,请编程完成。 输入 输入一个工资数<10000元 输出 输出各个币种的张数,没有的用0代替,中间用空格分开 样例输入 173 样例输出 1110011 #include intmain() { intj,z,a; intb[7]={100,50,20,10,5,2,1};//把所有币值按从从大到小的顺序存到一位数组中; ints[7]={0};//定义一个一位数组,元素值全为0; scanf("%d",&z); for(j=0;j<7;j++) { a=z/b[j]; s[j]=a; z=z-a*b[j]; }//求需要各个币值的个数; printf("%d",s[0]); for(j=1;j<7;j++) printf("%d",s[j]);//输出需要各个币值的个数; return0; } 心得: 这个题主要运用贪婪算法的方法,利用可行的策略,求出可行解的一个解元素 由所有解元素合成问题的一个可行解。 要想取得的张数最少,可以先考虑币值最大的进行分发,然后再取更小钞票的币值。 依次取之。 首先定义一个一维数组,把币值从大到小存进去,运用一循环,把每次算的钱数的结果,依次对数组的币值进行取整。 然后依次存入数组输出。 10问题C: "水仙花数"问题1 时间限制: 1Sec 内存限制: 128MB 提交: 138 解决: 75 [提交][状态][讨论版] 题目描述 判断一个数是否为"水仙花数",所谓"水仙花数"是指这样的一人数: 其各位数字的立方和等于该数本身。 例如: 371是一个"水仙花数",371=3^3+7^3+1^3. 输入 一个三位数 输出 1或者0(1代表此数为水仙花数,0代表此数不是水仙花数) 样例输入 371 样例输出 1 #include voidmain() { intn,x,y,z; scanf("%d",&n); x=n/100;//求三位数的百位数字; z=n%10;//求三位数的个位数字; y=(n-(x*100+z))/10;//求三位数的十位数字; if(n==x*x*x+y*y*y+z*z*z) printf("%d",1); else printf("%d",0);//判断这个三位数是否为水仙花数,是输出1,否输出2; } 心得: 首先,输入一个三位数,运用对这个数取整,取余,运用数学公式,分别算出它的百位,十位,和个位的数字,然后判断这三个数字的平方和是否等于这个三位数,如果是,输出1,如果不是输出0. 11问题E: 大小写转换 时间限制: 1000Sec 内存限制: 65536MB 提交: 182 解决: 116 [提交][状态][讨论版] 题目描述 读入一些字符串,将其中的小写字母转成大写字母(其他字符不变)。 输入 输入为多行,每行为一个字符串,字符串只由字母和数字组成,长度不超过80。 输入以“Endoffile”结束。 输出 对于每行输入,输出转换后的字符串。 样例输入 Hello ICPC2004 12345abcde 样例输出 HELLO ICPC2004 12345ABCDE #include #include voidmain() { intj; charstring[80];//定义一个字符串; while(scanf("%s",&string)! =EOF)//实现多行实例输入; { for(j=0;j<80;j++) { if((string[j]>='a')&&(string[j]<='z')) string[j]=string[j]-32; }//实现字母大小写转换; printf("%s\n",string); } } 心得: 这个题目主要考察输入输出,还有大小写转换问题,首先还是定义一个字符串,用while(scanf("%s",&string)! =EOF)语句实现多行实例输入,对这个字符串进行循环,如果这个字符串有大写的话,转化成小写的,如果有小写的话,那么转化成大写的。 12问题B: 取数游戏 时间限制: 1Sec 内存限制: 128MB 提交: 46 解决: 39 [提交][状态][讨论版] 题目描述 有2个人轮流取2n个数中的n个数,所取数之和大者为胜,请编写算法,让先取数者胜,模拟取数过程。 输入 输入两行,第一行一个整数N<100000; 第二行N个数,用空格分开。 输出 输出取胜人取数和。 失败人取数的和,空格分开。 样例输入 6 123456 样例输出 129 #include intmain() { intn,i,sum1,sum2,a[100000]; while(scanf("%d",&n)! =EOF)//实现多行实例输入; { sum1=sum2=0; for(i=0;i scanf("%d",&a[i]); for(i=0;i sum1=sum1+a[i]; for(i=1;i sum2=sum2+a[i];//隔数取数求和
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- ACM 作业
![提示](https://static.bingdoc.com/images/bang_tan.gif)