ACM程序设计与竞赛作业要点.docx

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

1、程序设计及竞赛作业1. 采药2. 金字塔问题3. 毛毛虫问题4. 字符串正反连接5. 去掉空格6. 成绩转换7. 金块问题8. 工资问题10.“水仙花数”问题11.大小写转换12.取数游戏13.整除问题14.警察抓小偷15！16.汉诺塔问题17.猴子吃桃问题（递归）18. (I)19. ()20. ()21. ()22.埃及分数23.完数24. 207025. 26. 不要62 20891问题 B: 采药时间限制:1 内存限制:128 提交:87解决:72提交状态讨论版题目描述辰辰是个很有潜能、天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他

2、的资质，给他出了一个难题。医师把他带到个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”如果你是辰辰，你能完成这个任务吗？输入输入的第一行有两个整数T（1 T 1000）和M（1M 100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。输出输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可

3、以采到的草药的最大总价值。样例输入70 371 10069 11 2 样例输出3 a1021002=0; 1111; (11); (i1=111) aki11; (2) (11); (i1=111) (i1m11i11) aki11i1; 采完总价值下降 aki111i11值得采的情况； (mt);心得：这是一个动态规划的题目，首先定义一个二维数组，根据草药的性价比，优先采取较高的草药，如果时间不够，则降低性价比继续采取草药，直至时间结束，根据采集的草药计算它的最大值，这题通过比较算出可能采的情况，和不能采的情况，如果能采，那再判断值不值得采，得出最优解。2问题 A: 金字塔问题时间限制:1

4、内存限制:128 提交:54解决:32提交状态讨论版题目描述給一个金字塔，如上图所示，请你求出一个从塔顶到塔底的路径，要求路径经过的点的数字和最小。例如上图所示的金字塔的最小路径为：40输入输入第一行是一个整数n1000；接下来是n行，第一行一个数；第二行两个数；第n行n个数；数之间用空格分开。数的链接方式如图所示。输出一个数，就是从塔顶到塔底的路径的最小距离。样例输入5912 1510 6 83 18 9 519 7 10 4 16样例输出40 a100100;定义一个二维数组； (1) (1=1) (1a11) aijij11; aijij1j; 求得每次路径最小值； (11); 心得：这

5、个题目主要运用了动态规划的思想，定义一个二维数组，把所输入的数据存入进去，然后从它的第一行处理，比较相邻位置数的大小，取最小的路径和上一行对应的数相加，取得最小路径，进行循环，直到求出数组中a11,即所求的结果。3问题 B: 毛毛虫问题时间限制:1 内存限制:128 提交:32解决:16提交状态讨论版题目描述在她家门口水平种了一排苹果树，共有N棵。突然发现在左起第P棵树上(从1开始计数)有一条毛毛虫。为了看到毛毛虫变蝴蝶的过程，在苹果树旁观察了很久。虽然没有看到蝴蝶，但发现了一个规律：每过1分钟，毛毛虫会随机从一棵树爬到相邻的一棵树上。比如刚开始毛毛虫在第2棵树上，过1分钟后，毛毛虫可能会在第

6、1棵树上或者第3棵树上。如果刚开始时毛毛虫在第1棵树上，过1分钟以后，毛毛虫一定会在第2棵树上。现在告诉你苹果树的数目N，以及毛毛刚开始所在的位置P，请问，在M分钟后，毛毛虫到达第T棵树，一共有多少种行走方案数。输入输入四个整数N P M T。输出输出一个整数，就是行走的方案数。样例输入7 4 4 4样例输出6 a100100=0定义一个二维数组； a0p=1;毛毛虫刚开始在数组中的位置； (1) (1) aij1111每一步的方案数； (nmt)分钟后到T棵树行走的方案数；心得：这一题运用了动态规划的思想，毛毛虫的每一步都会影响下一步的结果，所以首先按照普通情况找出规律及其其公式，进而算出方

7、案数。首先定义一个二维数组，初始化毛毛虫的起始位置，然后通过两个循环，求出毛毛虫走每一步的方案数，存在二维数组中，然后求出第M分钟到T棵树行走的方案数。4问题 A: 时间限制:1 内存限制:128 提交:61解决:23提交状态讨论版题目描述 p1, p2 p3, s (p1, p2, p3), 1, . p1, p2 p3. , H(2, 3, 5) = 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, . H5(2, 3, 5)=6.输入 p1 p2 p3 i.输出 - (p1, p2, p3). 1018.样例输入2 3 5

8、5样例输出6 ( p1 p2 p3) 定义有参函数； 1; (p2) 2; (p3) 3;求p123的最小值； p123; 10000; (123); 0; 0=1; (1) i(p1*a2*b3*c)调用函数； (i1*a) (i2*b) (i3*c) 求所有的能被p123整除的数； (nt); 0;心得：运用动态规划的思想，定义一个一维数组，把所有符合条件的数按顺序存进一维数组中，这个编程运用了函数调用的方法求三个数的最小值，然后把这个最小值存进一维数组中，每次存进一个数，下次都会用存进去的这个数求解下一个数，进行循环。5问题 B:字符串正反连接时间限制:1 内存限制:128 提交:68解

9、决:42提交状态讨论版题目描述所给字符串正序和反序连接，形成新串并输出输入任意字符串（长度=50）输出字符串正序和反序连接所成的新字符串样例输入123样例输出123321 a50定义一个字符串；()实现多行实例输入； (a)把字符串的长度值赋给f; (0=0) (i)把字符串反序输出； (n);心得：定义一个字符串，运用()函数获取字符串的长度值f，首先用循环，把这个字符串正序输出，然后再用循环对这个字符串进行反序输出，这里主要考察了输入输出。6问题 C: 去掉空格时间限制:1 内存限制:128 提交:27解决:4提交状态讨论版题目描述读入一些字符串，将其中的空格去掉。输入输入为多行，每行为一

10、个字符串，字符串只由字母、数字和空格组成，长度不超过80。输入以“ ”结束。输出对于每行输入，输出转换后的字符串。样例输入1 2 3样例输出123提示用是不能读入一行有空格的字符串的，用吧。 用“() ”可以判断输入是否结束，如果此条件为假（即() ），则表示输入结束（对于本题）。 a90定义一个字符串；(a)(a)把字符串的长度值赋给f; (0)(ai )(1)去掉空格；1;(i)没有空格，直接输出；(n);心得：这里也是主要考察输入输出问题，首先也是定义了一个字符串，用()函数获得字符串的长度f，进行f次循环，判断这个字符串是否有空格？如果有把数组中的每个数往后进一位，即去点空格，如果没有

11、直接输出。7问题 D: 成绩转换时间限制:1 内存限制:128 提交:78解决:30提交状态讨论版题目描述输入一个百分制的成绩t，将其转换成对应的等级，具体转换规则如下：90100为A;8089为B;7079为C;6069为D;059为E;输入输入数据有多组，每组占一行，由一个整数组成。输出对于每组输入数据，输出一行。如果输入数据不在0100范围内，请输出一行：“ !”。样例输入5667100123样例输出EDA提示 x;()实现多行实例输入；(x60)(En); (x70)(Dn); (x80)(Cn); (x90)(Bn); (x=2),最优秀的雇员得到其中最重的一块，最差的雇员得到其中最

12、轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。输入输入共两行，第一行输入金块的数量N100000;第二行N金块的重量，用空格间隔。输出两个数用空格分开，最重金块 最轻金块样例输入53 7 9 6 4样例输出9 3 100000;()实现多行实例输入；(0)(i);0把数组a0的值赋给和；(1)i;求最最重的金块；(1)(ai)i;求最轻的金块；( n); 0;心得：这题主要运用分治算法的思想，把一个大问题分成一个个小的子问题去求解，这个题目是典型的二分法问题，把这个题分成两个小问题，即求最重的和求最轻的金块，首先定义了一个一维数组，把所有金块的质量存入其中，把数

13、组的初始值赋给最重的和最轻的金块，然后运用循环对数组中每个金块的质量及金块的初始值进行比较，求的最重和最轻的金块，然后输出。9问题 B: 工资问题时间限制:1 内存限制:128 提交:121解决:74提交状态讨论版题目描述某单位给每个职工发工资（精确到元），为了保证不要临时兑换零钱，且取款的张数最少，取工资前要统计出所有职工的工资所需各种 币值（100，50，20，10，5，2，1元共7种）的张数，请编程完成。输入输入一个工资数10000元输出输出各个币种的张数，没有的用0代替，中间用空格分开样例输入173样例输出1 1 1 0 0 1 1 b7=100,50,20,10,5,2,1把所有币值

14、按从从大到小的顺序存到一位数组中； s7=0定义一个一位数组，元素值全为0； (07) j; sj;*bj; 求需要各个币值的个数； (0); (17) ( j)输出需要各个币值的个数； 0;心得：这个题主要运用贪婪算法的方法，利用可行的策略，求出可行解的一个解元素由所有解元素合成问题的一个可行解。要想取得的张数最少，可以先考虑币值最大的进行分发，然后再取更小钞票的币值。依次取之。首先定义一个一维数组，把币值从大到小存进去，运用一循环，把每次算的钱数的结果，依次对数组的币值进行取整。然后依次存入数组输出。10问题 C: 水仙花数问题1时间限制:1 内存限制:128 提交:138解决:75提交状

15、态讨论版题目描述判断一个数是否为水仙花数，所谓水仙花数是指这样的一人数：其各位数字的立方和等于该数本身。例如：371是一个水仙花数，371=33+73+13.输入一个三位数输出1或者0(1代表此数为水仙花数,0代表此数不是水仙花数)样例输入371样例输出1 100求三位数的百位数字； 10求三位数的个位数字； (x*100)/10求三位数的十位数字； (*x*y*z*z) (,1); (,0)判断这个三位数是否为水仙花数，是输出1，否输出2；心得：首先，输入一个三位数，运用对这个数取整，取余，运用数学公式，分别算出它的百位，十位，和个位的数字，然后判断这三个数字的平方和是否等于这个三位数，如果

16、是，输出1，如果不是输出0.11问题 E: 大小写转换时间限制:1000 内存限制:65536 提交:182解决:116提交状态讨论版题目描述读入一些字符串，将其中的小写字母转成大写字母（其他字符不变）。输入输入为多行，每行为一个字符串，字符串只由字母和数字组成，长度不超过80。输入以“ ”结束。输出对于每行输入，输出转换后的字符串。样例输入200412345样例输出200412345 j; 80定义一个字符串； ()实现多行实例输入；(0=a)(j=z) jj-32;实现字母大小写转换； (n);心得：这个题目主要考察输入输出，还有大小写转换问题，首先还是定义一个字符串，用()语句实现多行实

17、例输入，对这个字符串进行循环，如果这个字符串有大写的话，转化成小写的，如果有小写的话，那么转化成大写的。12问题 B: 取数游戏时间限制:1 内存限制:128 提交:46解决:39提交状态讨论版题目描述有2个人轮流取2n个数中的n个数，所取数之和大者为胜，请编写算法，让先取数者胜，模拟取数过程。输入输入两行，第一行一个整数N100000；第二行N个数，用空格分开。输出输出取胜人取数和。失败人取数的和，空格分开。样例输入61 2 3 4 5 6样例输出12 9 12100000;()实现多行实例输入；12=0;(0)(i);(02)11i;(12)( n12);( n21);顺序输出取胜人取数和

18、。失败人取数和； 0;心得;这题主要运用贪心算法的思想，要想先取数人获胜，就得让这个人每一步都尽可能取得最大的数，这样他取数的和才会总体大于后取数的那个人的取数和。首先定义一个一维数组，把要取得数从小到大的顺序放在里面，然后一个人从第一个按照隔一个数取，求和1;另一个人从第二个按照隔一个人取,求和2，比较1和2的最大值，输出。13问题 C: 整除问题时间限制:1 内存限制:128 提交:70解决:44提交状态讨论版题目描述编写算法对输入的一个整数，判断它能否被3，5，7整除，并输出以下信息之一：能同时被3，5，7整除；能被其中两个数（要指出哪两个）整除；能被其中一个数（要指出那一个）整除；不能

19、被3，5，7任一个整除；输入输入一个整数100000;输出如果都能整除输出“如果都不能整除输出如果能被3和5整除则输出“3 5”。中间有一个空格，注意按由小到大输出。样例输入35样例输出5 7 n; k;(30)+(50)*2+(70)*4)判断整数是否能被2,3,5整除；(k) 7(); 6(5 7); 5(3 7); 4(4); 3(3 5); 2(5); 1(3); 0();用语句输出结果；心得：这题主要考察输入输出问题，首先输入一个整数，运用语句(30)+(50)*2+(70)*4)，判断这个数能否被2,3,5整除，用语句输出所有可能发生的结果，然后输出题目中所要求输出的结果，其中用语

20、句起到了优化算法的作用。14问题A警察抓小偷时间限制:1 内存限制:128 提交:115解决:88提交状态讨论版题目描述警察局抓了,4名小偷嫌疑犯，其中只有一个人是小偷，审问中，a说：我不是小偷，b说：c是小偷，c说：小偷肯定是d，d说：c在冤枉人。 现在已经知道4个人中3人说的是真话，一人说的是假话，问到底谁是小偷。输入输出小偷是c样例输入样例输出小偷是c x;(1=4)执行4次循环；(1)+(3)+(4)+(4)3)判断是否有三个人说真话的情况；(,64);心得：这个题目主要考察把文字信息转化为数字信息，即信息数字化，把A，B，C，D看成1，2，3，4；x定义为小偷，然后把A，B，C，D四

21、人所说的话变成数字语言，判断当他们四个人有三个人说真话的情况，然后以把数字变成字母输出。15问题 B: n!时间限制:1 内存限制:128 提交:262解决:162提交状态讨论版题目描述输入一个整数N，输出它的阶乘。输入输入一个整数20;输出输出它的阶乘样例输入5样例输出120提示 ( m)对函数进行声明；(n);(n); 0; ( n)定义函数 f; (01)1;判断当n等于0和1这两种情况；*(1)调用函数求值； f;心得：这里主要运用函数的递归调用，首先用对输入的数进行判断，看是否为1和0，如果是，那么输出其阶乘等于1，如果不是那么调用函数*(1)进行求值，函数总共被调用了n次，求得最后

22、的结果，输出。16汉诺塔问题时间限制:1 内存限制:128 提交:224解决:138提交状态讨论版题目描述把N个盘子从A柱子借助B柱子移到C柱子，要求每次只能移动一个盘子，并且小盘子不能放到大盘子上。问如何移动。输入输入盘子的个数N（=10)输出输出移动的次数。样例输入3样例输出7提示 1; (1)去除盘子的个数为1的情况；(10)执行9次循环；(1)*2求每天桃子的个数；(n); 1;心得：这个题目运用数学中倒推的方法求得，先求出第10天桃子的个数，然后再求出前一天桃子的个数，直到求出第1天桃子的个数，找出其规律。设桃子的个数为x，则每天剩余桃子的个数满足公式(1)*2，再用一个循环求出原来

23、的桃子数。18问题 A: (I)时间限制:1 内存限制:128 提交:402解决:183提交状态讨论版题目描述 a + b. ?! ! I . , , .输入 a a b, a , .输出 a b a b , .样例输入1 510 20样例输出630提示()实现多行实例输入；求a和b的和；(n);心得：这个题主要考察了输入和输出问题，目的是计算整数a和b的和，首先用()语句实现多行实例输入，然后求出a和b的和，输出。19 ()时间限制:1 内存限制:128 提交:310解决:179提交状态讨论版题目描述 a + b.输入 N , N . a a b, a , .输出 a b a b , .样例

24、输入21 510 20样例输出630提示提交状态讨论版 ()限制求和的次数； ()输入; (n)求的和；心得：这个题目主要考察了输入输出问题，题目要求第一行输入要输入要计算和的数量，用()语句满足了题目的要求，即执行n次，然后就是输入a和b，接着求出和，输出。20问题 C: ()时间限制:1 内存限制:128 提交:314解决:169提交状态讨论版题目描述 a + b.输入 . a a b, . A 0 0 .输出 a b a b , .样例输入1 510 200 0样例输出630()!(00)/*实现多行实例输入，当都为0时结束*/(n)求的和；心得：这个题目也是输入输出问题，目的也是求出a

25、和b的和，然后按要求输入输出，对于输入：()!(00)运用这个语句实现多行实例输入，如果输入0 0，则结束，然后求得a和b的和，输出。21问题 D: ()时间限制:1 内存限制:128 提交:287解决:166提交状态讨论版题目描述输入 . a N, N . A 0 .输出样例输入4 10 2 3 405 11 2 8 5 50 样例输出5531提示 1;(0)(0); 判断n是否为断0,是结束，不是执行下面语句；0;( 0)执行n次循环；每次循环求和; (n);心得：同样，这个题目也是主要考察了输入输出问题，计算一些整数的和，并按指定的格式输出，首先输入一些整数判断是否都为0，如果是，则结束

26、，如果不是则执行循环，把所有输入的整数相加，然后输出。22问题 B: 埃及分数时间限制:1 内存限制:128 提交:21解决:11提交状态讨论版题目描述 设计一个算法，把一个真分数表示为最少埃及分数之和的形式，所谓埃及分数，是指分子为1的分数。 如7/8=1/2+1/3+1/24。输入输入两个整数，第一个表示分子，第二个数表示分母。输出输出埃及分数之和，按分母有小到大的顺序，中间用空格分开。样例输入7 8样例输出2 3 24提示( )实现多行实例输入；(10)(n)如果这个数为1或分子为1，输出分母的值；(1) 1; *c; ( )通过公式求出埃及分数。 (01) (n); 1; 0;心得：首

27、先通过语句实现多行实例输入，首先输入这是分数的的分子分母，判断这个数是否为1或这个数的分子为1，如果是，直接输出分母的值；接下来用一循环，通过求公式依次算出埃及数，然后输出，用每次计算的结果判断分子是否能整除分母或分子为一，如果是，直接输出整除后结果。23问题 A: 完数时间限制:1 内存限制:128 提交:192解决:70提交状态讨论版题目描述完数的定义：如果一个大于1的正整数的所有因子之和等于它的本身，则称这个数是完数，比如6，28都是完数：6=1+2+3；28=1+2+4+7+14。本题的任务是判断两个正整数之间完数的个数。输入输入数据包含多行，第一行是一个正整数n，表示测试实例的个数，

28、然后就是n个测试实例，每个实例占一行，由两个正整数1和2组成,(11210000)。输出对于每组测试数据，请输出1和2之间（包括1和2）存在的完数个数。样例输入22 55 7样例输出01提示 12;()实现多行实例输入； (0)执行n次循环；( 12)输入两个整数；0;(12)执行21+1次循环； 0; (1) (0)判断1和2之间的数是否能被k 整除； 如果是完数，统计其个数；(n); 0;心得：这个题主要考察了输入输出和循环问题，用语句实现多行输入，首先输入两个数，判断这两个数之间的数（包括这两个数）是不是完数，如果是完数，则记录这两个数之间完数的个数，然后输出。24问题 C: 2070时

29、间限制:1 内存限制:128 提交:291解决:164提交状态讨论版题目描述 a a . :f(0) = 0f(1) = 1f(n) = f(1) + f(2) n 0 50输入 n a 0n50. -1.输出 a .样例输入345-1样例输出235提示 a51定义一个浮点型一维数组； n;a0=01=1; () )1)实现多行实例输入，当n等于-1时结束；( 2=50)ai12根据公式求出结果；(%.0nn); 0;心得：这个题考察输入及输出，还有首先定义一个浮点型一位数组，数组中第一个第二个数分别赋值为0和1，用语句实现多行实例输入，然后执行循环，根据公式算出所要求的结果，然后输出结果。2

30、5问题 A: 时间限制:1 内存限制:128 提交:37解决:9提交状态讨论版题目描述A h 1*1, 2*2, 3*3, 4*4, 5*5, 6*6. h 6*6. . A a . a .输入输入每行6个整数，空格分开，第1到第6位为1*1，2*2，。6*6盒子的个数。当输入为6个0时结束。输出输出每行一个整数，表示需要的盒子数。样例输入0 0 4 0 0 1 7 5 1 0 0 0 0 0 0 0 0 0 样例输出2 1 提示 4=0,5,3,1; 7; (,r); (1) 0; ( 1a2) (22+8)/9; a1*366*365*254*163*92*4; (1a1) 求a1的空位子，只需要统计剩余的面积即可 (11+35)/36; (n); 0;心得：对于6*6以及4*4尺寸的物品每个物品需要占有一个箱子，对于3*3的物品一个箱子可以放4个，2*2的物品箱子可以放9个，1*1的可以放36个，采用面积统计1*1箱子的空位，采用向上去整的方法统计箱子。第 27 页