ACM程序设计与竞赛作业.doc

《ACM程序设计与竞赛作业.doc》由会员分享，可在线阅读，更多相关《ACM程序设计与竞赛作业.doc（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、ACM程序设计与竞赛作业1. 采药2. 金字塔问题3. 毛毛虫问题4. Hamming Problem5. 字符串正反连接6. 去掉空格7. 成绩转换8. 金块问题9. 工资问题10.“水仙花数”问题11.大小写转换12.取数游戏13.整除问题14.警察抓小偷15.n！16.汉诺塔问题17.猴子吃桃问题（递归）18. A+B for Input-Output Practice (I)19. A+B for Input-Output Practice (II)20. A+B for Input-Output Practice (III)21. A+B for Input-Output Pract

2、ice (IV)22.埃及分数23.完数24. Fibbonacci Number _Hdu 207025. Pakets26. 不要62 _Hdu 20891问题 B: 采药时间限制:1 Sec内存限制:128 MB提交:87解决:72提交状态讨论版题目描述辰辰是个很有潜能、天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的

3、孩子，你应该可以让采到的草药的总价值最大。”如果你是辰辰，你能完成这个任务吗？输入输入的第一行有两个整数T（1 T 1000）和M（1M 100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。输出输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。样例输入70 371 10069 11 2 样例输出3#include stdio.hvoid main() int a1021002=0; int t,t1,m1,m,i,i1,k=1; sca

4、nf(%d%d,&t,&m); scanf(%d%d,&t1,&m1); for(i1=1;i1=t1) aki1=m1; k+; for(i=2;i=m;i+) scanf(%d%d,&t1,&m1); for(i1=1;i1=t;i1+) if(i1m1+ak-1i1-t1) aki1=ak-1i1; /采完总价值下降 else aki1=m1+ak-1i1-t1;/值得采的情况； k+; printf(%d,amt);心得：这是一个动态规划的题目，首先定义一个二维数组，根据草药的性价比，优先采取较高的草药，如果时间不够，则降低性价比继续采取草药，直至时间结束，根据采集的草药计算它的最大值

5、，这题通过比较算出可能采的情况，和不能采的情况，如果能采，那再判断值不值得采，得出最优解。2问题 A: 金字塔问题时间限制:1 Sec内存限制:128 MB提交:54解决:32提交状态讨论版题目描述給一个金字塔，如上图所示，请你求出一个从塔顶到塔底的路径，要求路径经过的点的数字和最小。例如上图所示的金字塔的最小路径为：40输入输入第一行是一个整数n1000；接下来是n行，第一行一个数；第二行两个数；。第n行n个数；数之间用空格分开。数的链接方式如图所示。输出一个数，就是从塔顶到塔底的路径的最小距离。样例输入5912 1510 6 83 18 9 519 7 10 4 16样例输出40#incl

6、udevoid main() int i,j,n; int a100100;定义一个二维数组； scanf(%d,&n); for(i=1;i=n;i+) for(j=1;j=1;i-) for(j=1;jai+1j+1) aij=aij+ai+1j+1; else aij=aij+ai+1j; /求得每次路径最小值； printf(%d,a11); 心得：这个题目主要运用了动态规划的思想，定义一个二维数组，把所输入的数据存入进去，然后从它的第一行处理，比较相邻位置数的大小，取最小的路径和上一行对应的数相加，取得最小路径，进行循环，直到求出数组中a11,即所求的结果。3问题 B: 毛毛虫问题时

7、间限制:1 Sec内存限制:128 MB提交:32解决:16提交状态讨论版题目描述Mary在她家门口水平种了一排苹果树，共有N棵。突然Mary发现在左起第P棵树上(从1开始计数)有一条毛毛虫。为了看到毛毛虫变蝴蝶的过程，Lele在苹果树旁观察了很久。虽然没有看到蝴蝶，但Lele发现了一个规律：每过1分钟，毛毛虫会随机从一棵树爬到相邻的一棵树上。比如刚开始毛毛虫在第2棵树上，过1分钟后，毛毛虫可能会在第1棵树上或者第3棵树上。如果刚开始时毛毛虫在第1棵树上，过1分钟以后，毛毛虫一定会在第2棵树上。现在告诉你苹果树的数目N，以及毛毛刚开始所在的位置P，请问，在M分钟后，毛毛虫到达第T棵树，一共有多

8、少种行走方案数。输入输入四个整数N P M T。输出输出一个整数，就是行走的方案数。样例输入7 4 4 4样例输出6#includevoid main() int i,j; int p,m,n,t; int a100100=0;/定义一个二维数组； scanf(%d%d%d%d,&n,&p,&m,&t); a0p=1;毛毛虫刚开始在数组中的位置； for(i=1;i=m;i+) for(j=1;j=n;j+) aij=ai-1j-1+ai-1j+1;/每一步的方案数； printf(%dn,amt);M分钟后到T棵树行走的方案数；心得：这一题运用了动态规划的思想，毛毛虫的每一步都会影响下一步的

9、结果，所以首先按照普通情况找出规律及其其公式，进而算出方案数。首先定义一个二维数组，初始化毛毛虫的起始位置，然后通过两个循环，求出毛毛虫走每一步的方案数，存在二维数组中，然后求出第M分钟到T棵树行走的方案数。4问题 A: Hamming Problem时间限制:1 Sec内存限制:128 MB提交:61解决:23提交状态讨论版题目描述For each three prime numbers p1, p2 and p3, lets define Hamming sequence Hi(p1, p2, p3), i=1, . as containing in increasing order al

10、l the natural numbers whose only prime divisors are p1, 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 of input file there are space-separated integers p1 p2 p3 i.输出The output file must contain the single integer - H

11、i(p1, p2, p3). All numbers in input and output are less than 1018.样例输入2 3 5 5样例输出6#include stdio.hint minx(int p1,int p2,int p3)/ 定义有参函数minx； int min=p1; if(p2min) min=p2; if(p3min) min=p3; return min;/求p1,p2,p3的最小值；int main() int p1,p2,p3,t,i; int a,b,c; char num10000; scanf(%d%d%d%d,&p1,&p2,&p3,&t

12、); a=b=c=0; num0=1; for(i=1;i=t;i+) numi=minx(p1*numa,p2*numb,p3*numc);/调用minx函数； if(numi=p1*numa) a+; if(numi=p2*numb) b+; if(numi=p3*numc) c+; 求所有的能被p1,p2,p3整除的数； printf(%dn,numt); return 0; 心得：运用动态规划的思想，定义一个一维数组，把所有符合条件的数按顺序存进一维数组中，这个编程运用了函数调用的方法求三个数的最小值，然后把这个最小值存进一维数组中，每次存进一个数，下次都会用存进去的这个数求解下一个数

13、，进行循环。5问题 B:字符串正反连接时间限制:1 Sec内存限制:128 MB提交:68解决:42提交状态讨论版题目描述所给字符串正序和反序连接，形成新串并输出输入任意字符串（长度=50）输出字符串正序和反序连接所成的新字符串样例输入123abc样例输出123abccba321#include#includevoid main()char a50;/定义一个字符串；int i,f;while(scanf(%s,&a)!=EOF)/实现多行实例输入； f=strlen(a);/把字符串的长度值赋给f; for(i=0;i=0;i-) printf(%c,ai);/把字符串反序输出； print

14、f(n);心得：定义一个字符串，运用strlen()函数获取字符串的长度值f，首先用for循环，把这个字符串正序输出，然后再用for循环对这个字符串进行反序输出，这里主要考察了输入输出。6问题 C: 去掉空格时间限制:1 Sec内存限制:128 MB提交:27解决:4提交状态讨论版题目描述读入一些字符串，将其中的空格去掉。输入输入为多行，每行为一个字符串，字符串只由字母、数字和空格组成，长度不超过80。输入以“End of file”结束。输出对于每行输入，输出转换后的字符串。样例输入Hello World1 2 3Nice to meet youabc样例输出HelloWorld123Nic

15、etomeetyouabc提示用scanf是不能读入一行有空格的字符串的，用gets吧。 用“gets(str) != NULL”可以判断输入是否结束，如果此条件为假（即gets(str) = NULL），则表示输入结束（对于本题）。#include#includevoid main()int i,f;char a90;/定义一个字符串；while(gets(a)!=NULL)f=strlen(a);/把字符串的长度值赋给f; for(i=0;if;i+) if(ai= )printf(%c,ai+1);/去掉空格；i=i+1;elseprintf(%c,ai);/没有空格，直接输出； pri

16、ntf(n);心得：这里也是主要考察输入输出问题，首先也是定义了一个字符串，用strlen()函数获得字符串的长度f，进行f次循环，判断这个字符串是否有空格？如果有把数组中的每个数往后进一位，即去点空格，如果没有直接输出。7问题 D: 成绩转换时间限制:1 Sec内存限制:128 MB提交:78解决:30提交状态讨论版题目描述输入一个百分制的成绩t，将其转换成对应的等级，具体转换规则如下：90100为A;8089为B;7079为C;6069为D;059为E;输入输入数据有多组，每组占一行，由一个整数组成。输出对于每组输入数据，输出一行。如果输入数据不在0100范围内，请输出一行：“Score

17、is error!”。样例输入5667100123样例输出EDAScore is error!提示#includeint main()int x;while(scanf(%d,&x)!=EOF)/实现多行实例输入；if(x60)printf(En);else if(x70)printf(Dn);else if(x80)printf(Cn);else if(x90)printf(Bn);else if(x=2),最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。输入输入共两行，第一行输入金块的数量N;第二行N金块的重

18、量，用空格间隔。输出两个数用空格分开，最重金块 最轻金块样例输入53 7 9 6 4样例输出9 3#includeint main()int n,a;int max,min,i;while(scanf(%d,&n)!=EOF)/实现多行实例输入；for(i=0;in;i+)scanf(%d,&ai);max=min=a0;/把数组a0的值赋给max和min；for(i=1;imax)max=ai;/求最最重的金块；for(i=1;in;i+)if(aimin)min=ai;/求最轻的金块；printf(%d %dn,max,min);return 0;心得：这题主要运用分治算法的思想，把一个大

19、问题分成一个个小的子问题去求解，这个题目是典型的二分法问题，把这个题分成两个小问题，即求最重的和求最轻的金块，首先定义了一个一维数组，把所有金块的质量存入其中，把数组的初始值赋给最重的和最轻的金块，然后运用循环对数组中每个金块的质量与金块的初始值进行比较，求的最重和最轻的金块，然后输出。9问题 B: 工资问题时间限制:1 Sec内存限制:128 MB提交:121解决:74提交状态讨论版题目描述某单位给每个职工发工资（精确到元），为了保证不要临时兑换零钱，且取款的张数最少，取工资前要统计出所有职工的工资所需各种 币值（100，50，20，10，5，2，1元共7种）的张数，请编程完成。输入输入一个

20、工资数10000元输出输出各个币种的张数，没有的用0代替，中间用空格分开样例输入173样例输出1 1 1 0 0 1 1#includeint main()int j,z,a;int b7=100,50,20,10,5,2,1;/把所有币值按从从大到小的顺序存到一位数组中；int s7=0;/定义一个一位数组，元素值全为0；scanf(%d,&z); for(j=0;j7;j+) a=z/bj; sj=a;z=z-a*bj; /求需要各个币值的个数； printf(%d,s0); for(j=1;j7;j+) printf( %d,sj);/输出需要各个币值的个数；return 0;心得：这个

21、题主要运用贪婪算法的方法，利用可行的策略，求出可行解的一个解元素由所有解元素合成问题的一个可行解。要想取得的张数最少，可以先考虑币值最大的进行分发，然后再取更小钞票的币值。依次取之。首先定义一个一维数组，把币值从大到小存进去，运用一循环，把每次算的钱数的结果，依次对数组的币值进行取整。然后依次存入数组输出。10问题 C: 水仙花数问题1时间限制:1 Sec内存限制:128 MB提交:138解决:75提交状态讨论版题目描述判断一个数是否为水仙花数，所谓水仙花数是指这样的一人数：其各位数字的立方和等于该数本身。例如：371是一个水仙花数，371=33+73+13.输入一个三位数输出1或者0(1代表

22、此数为水仙花数,0代表此数不是水仙花数)样例输入371样例输出1#includevoid main() int n,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；心得：首先，输入一个三位数，运用对这个数取整，取余，运用数学公式，分别算出它的百位，十位，和个位的数字，然后判断这三个数字的平方和是否等于这

23、个三位数，如果是，输出1，如果不是输出0.11问题 E: 大小写转换时间限制:1000 Sec内存限制:65536 MB提交:182解决:116提交状态讨论版题目描述读入一些字符串，将其中的小写字母转成大写字母（其他字符不变）。输入输入为多行，每行为一个字符串，字符串只由字母和数字组成，长度不超过80。输入以“End of file”结束。输出对于每行输入，输出转换后的字符串。样例输入HelloICPC200412345abcde样例输出HELLOICPC200412345ABCDE#include#includevoid main()int j;char string80;/定义一个字符串；

24、 while(scanf(%s,&string)!=EOF)/实现多行实例输入；for(j=0;j=a)&(stringj=z) stringj=stringj-32;/实现字母大小写转换； printf(%sn,string);心得：这个题目主要考察输入输出，还有大小写转换问题，首先还是定义一个字符串，用while(scanf(%s,&string)!=EOF)语句实现多行实例输入，对这个字符串进行循环，如果这个字符串有大写的话，转化成小写的，如果有小写的话，那么转化成大写的。12问题 B: 取数游戏时间限制:1 Sec内存限制:128 MB提交:46解决:39提交状态讨论版题目描述有2个人

25、轮流取2n个数中的n个数，所取数之和大者为胜，请编写算法，让先取数者胜，模拟取数过程。输入输入两行，第一行一个整数N；第二行N个数，用空格分开。输出输出取胜人取数和。失败人取数的和，空格分开。样例输入61 2 3 4 5 6样例输出12 9#includeint main()int n,i,sum1,sum2,a;while(scanf(%d,&n)!=EOF)/实现多行实例输入；sum1=sum2=0;for(i=0;in;i+)scanf(%d,&ai);for(i=0;in;i=i+2)sum1=sum1+ai;for(i=1;isum2)printf(%d %dn,sum1,sum2)

26、;elseprintf(%d %dn,sum2,sum1);/顺序输出取胜人取数和。失败人取数和；return 0;心得;这题主要运用贪心算法的思想，要想先取数人获胜，就得让这个人每一步都尽可能取得最大的数，这样他取数的和才会总体大于后取数的那个人的取数和。首先定义一个一维数组，把要取得数从小到大的顺序放在里面，然后一个人从第一个按照隔一个数取，求和sum1;另一个人从第二个按照隔一个人取,求和sum2，比较sum1和sum2的最大值，输出。13问题 C: 整除问题时间限制:1 Sec内存限制:128 MB提交:70解决:44提交状态讨论版题目描述编写算法对输入的一个整数，判断它能否被3，5，

27、7整除，并输出以下信息之一：能同时被3，5，7整除；能被其中两个数（要指出哪两个）整除；能被其中一个数（要指出那一个）整除；不能被3，5，7任一个整除；输入输入一个整数;输出如果都能整除输出“all如果都不能整除输出nonel如果能被3和5整除则输出“3 5”。中间有一个空格，注意按由小到大输出。样例输入35样例输出5 7#includevoid main()long n; int k;scanf(%d,&n);k=(n%3=0)+(n%5=0)*2+(n%7=0)*4);/判断整数是否能被2,3,5整除；switch(k)case 7:printf(all);break;case 6:pri

28、ntf(5 7);break;case 5:printf(3 7);break;case 4:printf(4);break;case 3:printf(3 5);break;case 2:printf(5);break;case 1:printf(3);break;case 0:printf(none);break;/用switch语句输出结果；心得：这题主要考察输入输出问题，首先输入一个整数，运用语句k=(n%3=0)+(n%5=0)*2+(n%7=0)*4)，判断这个数能否被2,3,5整除，用switch语句输出所有可能发生的结果，然后输出题目中所要求输出的结果，其中用switch语句起

29、到了优化算法的作用。14问题A警察抓小偷时间限制:1 Sec内存限制:128 MB提交:115解决:88提交状态讨论版题目描述警察局抓了a,b,c,d,4名小偷嫌疑犯，其中只有一个人是小偷，审问中，a说：我不是小偷，b说：c是小偷，c说：小偷肯定是d，d说：c在冤枉人。 现在已经知道4个人中3人说的是真话，一人说的是假话，问到底谁是小偷。输入输出小偷是c样例输入样例输出小偷是c#includevoid main()int x;for(x=1;x=4;x+)/执行4次循环；if(x!=1)+(x=3)+(x=4)+(x!=4)=3)/判断是否有三个人说真话的情况；printf(%c,64+x);

30、心得：这个题目主要考察把文字信息转化为数字信息，即信息数字化，把A，B，C，D看成1，2，3，4；x定义为小偷，然后把A，B，C，D四人所说的话变成数字语言，判断当他们四个人有三个人说真话的情况，然后以把数字变成字母输出。15问题 B: n!时间限制:1 Sec内存限制:128 MB提交:262解决:162提交状态讨论版题目描述输入一个整数N，输出它的阶乘。输入输入一个整数20;输出输出它的阶乘样例输入5样例输出120提示#includeint main()int add(int m);/对add函数进行声明；int n,sum;scanf(%d,&n);sum=add(n);printf(%

31、dn,sum);return 0;int add(int n)/定义add函数int f; if (n=0|n=1)f=1;/判断当n等于0和1这两种情况；else f=n*add(n-1);/调用add函数求值；return f;心得：这里主要运用函数的递归调用，首先用if对输入的数进行判断，看是否为1和0，如果是，那么输出其阶乘等于1，如果不是那么调用函数f=n*add(n-1)进行求值，add函数总共被调用了n次，求得最后的结果，输出。16汉诺塔问题时间限制:1 Sec内存限制:128 MB提交:224解决:138提交状态讨论版题目描述把N个盘子从A柱子借助B柱子移到C柱子，要求每次只能

32、移动一个盘子，并且小盘子不能放到大盘子上。问如何移动。输入输入盘子的个数N（=10)输出输出移动的次数。样例输入3样例输出7提示#includeint main() int i,j,n,sum; scanf(%d,&n); j=1; if(n!=1)/去除盘子的个数为1的情况；for(i=1;i=n;i+) j=j*2; sum=j-1;/求盘子移动的次数； else sum=1; printf(%d,sum); return 0; 心得：这题主要考察循环与递归问题，先假设盘子的个数，取几个特殊值，找出移动盘子次数的规律。这个编程首先判断盘子个数，如果是1，则输出1次，如果不是1，执行n次循环

33、，求得j,然后求出移动盘子的次数j-1，输出。17问题 D: 猴子吃桃子问题（递归）时间限制:1 Sec内存限制:128 MB提交:98解决:87提交状态讨论版题目描述一只猴子摘了若干桃子，每天吃现有桃子的一半多一个，到第10天时就只有一个桃子了，求原来有多少个桃。输入输出输出原来的桃子数样例输入样例输出提示#includeint main()int i,x=1;for(i=9;i0;i-)/执行9次循环；x=(x+1)*2;/求每天桃子的个数；printf(%dn,x);return 1;心得：这个题目运用数学中倒推的方法求得，先求出第10天桃子的个数，然后再求出前一天桃子的个数，直到求出第

34、1天桃子的个数，找出其规律。设桃子的个数为x，则每天剩余桃子的个数满足公式x=(x+1)*2，再用一个for循环求出原来的桃子数。18问题 A: A+B for Input-Output Practice (I)时间限制:1 Sec内存限制:128 MB提交:402解决:183提交状态讨论版题目描述Your task is to Calculate a + b.Too easy?! Of course! I specially designed the problem for acm beginners.You must have found that some problems have t

35、he same titles with this one, yes, all these problems were designed for the same aim.输入The input will consist of a series of pairs of integers a and b, separated by a space, one pair of integers per line.输出For each pair of input integers a and b you should output the sum of a and b in one line, and

36、with one line of output for each line in input.样例输入1 510 20样例输出630提示#includevoid main()int a,b,s;while(scanf(%d%d,&a,&b)!=EOF)/实现多行实例输入；s=a+b;/求a和b的和；printf(%dn,s); 心得：这个题主要考察了输入和输出问题，目的是计算整数a和b的和，首先用while(scanf(%d%d,&a,&b)!=EOF)语句实现多行实例输入，然后求出a和b的和，输出。19A+B for Input-Output Practice (II)时间限制:1 Sec内存限制:128 MB提交:310解决:179提交状态讨论版题目描述Your task is to Calculate a + b.输入Input contains an integer N in the first line, and then N lines follow. Each line consists of a pair of integers a and