ACM程序设计综合实践

1、程序设计综合实践课程设计报告系 （部）计算机科学系专 业计算机科学与技术学 号*学生姓名 *指导教师 *提交日期2014 年 12 月 23 日目 录1设计的目的与意义32设计的内容与要求32.1 中文ACM题目132.2 中文ACM题目232.3 英文ACM题目143课程设计总结44参考文献41设计的目的与意义 程序设计综合实践课程设计是计算机科学与技术、网络工程专业学生的 重要实践性环节，它可加深学生对该课程所学内容的进一步的理解与巩固，是将计算机课程与实际问题相联接的关键步骤。通过本课程设计，学生可以了解数据结构、算法设计的基本方法与基本原理，能够提高学生分析问题、解决问题，从而运用所学

2、知识解决实际问题的能力，掌握软件设计中数据的组织，算法的设计，为今后参加ACM竞赛、从事实际工作打下基础。同时，作为整个实践教学体系一部分，能够系统培养学生采用面向对象的方法分析问题与解决问题的能力及团体组织与协作能力。2 设计的内容与要求2.1 房间安排 【题目描述】2010年上海世界博览会（Expo 2010），是第41届世界博览会。于2010年5月1日至10月31日期间，在中国上海市举行。本次世博会也是由中国举办的首届世界博览会。上海世博会以“城市，让生活更美好”（Better City, Better Life）为主题，将充分探索21世纪城市生活。 这次世博会总投资达450亿人民币，创

3、造了世界博览会史上最大规模记录。吸引200个国家和国际组织参展。预计有7000万人次的参观者。 为了更好地接待在这期间来自世界各地的参观者，如何合理安排各宾馆的住房问题提到了日程。组委会已接到了大量的客房住宿定单，每张定单的内容包括要住宿的房间数，开始住宿时间和要住的天数。为了便于整个城市各宾馆的管理，组委会希望对这些定单进行安排，目的是用尽可能少的房间来满足这些定单，以便空出更多的房间用于安排流动游客。 组委会请求DR. Kong来完成这个任务，对这些定单进行合理安排，使得满足这些定单要求的房间数最少。 假设：某个定单上的游客一旦被安排到某房间，在他预定住宿的期间内是不换房间的。为了简化描述

4、，定单上的开始住宿时间为距离现在的第几天。例如，定单为（10，30，5）表示游客要求使用10个房间，第30天开始连住5天。 【标准输入】 第一行： N 表示定单数 接下来有N行，每行有三个整数 A B C 表示房间数，开始住宿时间和天数 【标准输出】 输出一个整数，为满足所有定单要求的最少房间数。 【约束条件】 1N10000 1A10，1B180， 1C10 【 样 例 】 标准输入 标准输出 3 73 10 4 4 9 3 3 12 6 【分析】建立简单的数学模型，求出游客需要房间数和所住天数，房间数和所住天数最大值Max，【代码】#include<iostream> usin

5、g namespace std; #define MAX 230 int sumMAX; int main() int N;int room;int start;int day; int i=0; for(i=0;i<MAX;i+) sumi=0; scanf("%d",&N); while(N-) scanf("%d%d%d",&room,&start,&day); for(i=0;i<day;i+) sumstart+i+=room; int max=-1; for(i=0;i<MAX;i+) if(

6、max<sumi) max=sumi; cout<<max<<endl; return 0; 【运行截图】2.2 聪明的“KK”【题目描述】非洲某国展馆的设计灵感源于富有传奇色彩的沙漠中陡然起伏的沙丘，体现出本国不断变换和绚丽多彩的自然风光与城市风貌。展馆由五部分组成，馆内影院播放名为一眨眼的瞬间的宽银幕短片，反映了建国以来人民生活水平和城市居住环境的惊人巨变。可移动“沙丘”变戏法 的灵感源于其独特而雄伟的自然景观富于传奇色彩的险峻沙丘。宏伟的结构、可循环的建材，与大自然相得益彰。环绕一周，发现它正是从沙丘那不断变换的形态中汲取灵感的。外形逼真到无论从哪个角度去观

7、察，都能清楚地辨识出沙丘的特征。它“坡面”高达20米，微风吹来，你是否感觉到沙的流动？用手去触碰，却发现原来是“魔术戏法”。它表面的不锈钢面板呈现出一种富于变幻的色彩，从不同角度观察，呈现不同色泽，由此来模仿流动沙丘的光感。走进第三展厅有一个超大的屏幕，通过奇妙的特效，让观众犹如亲身来到浩瀚的沙漠。更为奇妙的是，只见一个小动物“KK”正从沙漠区域（矩形）的左上角沿着向右或向下的方向往右下角跑去。KK太聪明了，它居然能在跑的过程中会选择吃掉尽可能多的虫子线路。你知道它吃掉多少虫子吗？【标准输入】第一行：N M 表示沙漠是一个N*M的矩形区域接下来有N行：每行有M个正整数，Xi1 Xi2 Xim

8、表示各位置中的虫子数（单个空格隔开）【标准输出】输出有一个整数， 表示“KK”吃掉最多的虫子数。【约束条件】1 N M 20 0Xij 500 (i=1,2.N, j=1,2,M)假设“KK”只能向右走或向下走【分析】类似“TheTriangle”这个题利用数塔，数塔的思想就是从下往上来进行运算，不断的更新数组，最终求出最大和。有些细节要注意，当KK走倒最后一列是只能向下走，当KK走到最后一行时，只能向右走。运用数组构建矩形，使用动态规划使初始位置和最终位置初始为零，由于在所考虑的子问题空间中，总共只有O(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。计算最

9、长公共子序列长度的动态规划算法LCS_Length(X,Y)，以序列X=<x1, x2, , xm>和Y=<y1, y2, , yn>作为输入。输出两个数组c0.m ,0.n和b1.m ,1.n。其中ci,j存储Xi与Yj的最长公共子序列的长度，bi,j记录指示ci,j的值是由哪一个子问题的解达到的，这在构造最长公共子序列时要用到。最后，X和Y的最长公共子序列的长度记录于cm,n中。【代码】#include<cstdio> #include<cstdlib> #include<iostream> #include<algorit

10、hm> #include<vector> #include<cstring> using namespace std; int N, M; int map2525, d2525; int dp(int N, int M) memset(d, 0, sizeof(d); for(int i=0; i<=N; i+) for(int j=0; j<=M; j+) if(di+1j>dij+1) di+1j+1 = di+1j + mapi+1j+1; else di+1j+1 = dij+1 + mapi+1j+1; return dNM; int

11、main() scanf("%d %d",&N, &M); for(int i=1; i<=N; i+) for(int j=1; j<=M; j+) cin>>mapij; int t = dp(N,M); printf("%dn",t); system("pause"); return 0; 【运行截图】 2.3SUBSTRING【题目描述】 You are given a string input. You are to find the longest substring of inpu

12、t such that the reversal of the substring is also a substring of input. In case of a tie, return the string that occurs earliest in input. Note well: The substring and its reversal may overlap partially or completely. The entire original string is itself a valid substring . The best we can do is fin

13、d a one character substring, so we implement the tie-breaker rule of taking the earliest one first. 【Standard input】 The first line of input gives a single integer, 1 N 10, the number of test cases. Then follow, for each test case, a line containing between 1 and 50 characters, inclusive. Each chara

14、cter of input will be an uppercase letter ('A'-'Z'). 【Standard output】 Output for each test case the longest substring of input such that the reversal of the substring is also a substring of input 【Sample Input】 3 ABCABA XYZ XCVCX 【Sample Output】 ABA X XCVCX 【分析】运用了数组的思想，来求这个回文字符串，fo

15、r循环控制截取的子串，然后再检测该子串反转之后是否为原串的子串 ，如果符合要求并超过最大长度 ，则保存当前最大长度，并用x，y记录最长串在原串中的开始和结束位置 ，最后输出最大子串。其中运用到strstr() 函数搜索一个字符串在另一个字符串中的第一次出现。找到所搜索的字符串，则该函数返回第一次匹配的字符串的地址；如果未找到所搜索的字符串，则返回NULL。#include <stdio.h>#include <string.h>int main(void)int n, len, ok, i, j, k, p, max, x, y;char buf51, arr51;sc

16、anf("%d", &n);while (n-) scanf("%s", buf);len = strlen(buf);/外两层循环控制截取的子串 for (i = 0, max = x = y = 0; i < len; i+) for (j = i; j < len; j+) ok = 1;/ 检测该子串反转之后是否为原串的子串 / 反序读入，该OJ评测系统不能使用strrev()，否则出现CompileError for (k = j, p = 0; k >= i; k-, p+)arrp = bufk;arrp = &#

17、39;0'if (strstr(buf, arr) = NULL) ok = 0;/如果符合要求并超过最大长度 /则保存当前最大长度，并用x，y记录最长串在原串中的开始和结束位置 if (ok && j - i + 1 > max) max = j - i + 1;x = i;y = j;/输出最大子串 for (i = x; i <= y; i+)printf("%c", bufi);printf("n");return 0;【运行截图】3 课程设计总结这次的程序设计，我收获很多，也体会很多，要学好一门计算机语言，没

18、有刻苦钻研的精神是不行的，只有在不断的尝试中，不断经历失败，然后又不断的尝试才能获得成功。要完成一个优秀的程序，必须熟练掌握各种语句的特点及用法，要学会举一反三，充分实现C程序的灵活性。在平时的学习实践中，要不断开动脑筋，活学活用。善于发问，善于思考。刚开始学习C语言的时候觉得它很无聊，但是随着不断的学习还是越来越感兴趣了。通过这次的程序设计，我学到了很多，首先就是能够更加熟练的使用和深入的了解C语言这门通用的计算机语言，还有就是可以自己编写程序了，还是很有成就感的。C语言是一门深奥的语言，我从一开始的懵懂到现在的有点理解可以说和老师的教导分不开的。虽然俗语说师傅领进门，修行靠自身。但是师傅的作用还是不可取代的。老师不仅是我们的老师，还是我们的朋友。和他在一起的时候没有那种隔阂感，这也是我们能好好学习的基础吧。不过有时开小差是不可避免的，但也只是偶尔啦。光书本的知识的确不行，还是要理论联系实践才行。因此不断的练习是必要的，上机