ACM程序设计综合实践讲义.doc

《程序设计综合实践》 课程设计报告 系 （部） 计算机科学系 专 业 计算机科学与技术 学 号 *** 学生姓名 *** 指导教师 *** 提交日期 2014 年 12 月 23 日 目 录 1．设计的目的与意义 3 2．设计的内容与要求 3 2.1 中文ACM题目1 3 2.2 中文ACM题目2 3 2.3 英文ACM题目1 4 3．课程设计总结 4 4．参考文献 4 1．设计的目的与意义 《程序设计综合实践》课程设计是计算机科学与技术、网络工程专业学生的 重要实践性环节，它可加深学生对该课程所学内容的进一步的理解与巩固，是将计算机课程与实际问题相联接的关键步骤。通过本课程设计，学生可以了解数据结构、算法设计的基本方法与基本原理，能够提高学生分析问题、解决问题，从而运用所学知识解决实际问题的能力，掌握软件设计中数据的组织，算法的设计，为今后参加ACM竞赛、从事实际工作打下基础。同时，作为整个实践教学体系一部分，能够系统培养学生采用面向对象的方法分析问题与解决问题的能力及团体组织与协作能力。 设计的内容与要求 2.1 房间安排 【题目描述】 2010年上海世界博览会（Expo 2010），是第41届世界博览会。于2010年5月1日至10月31日期间，在中国上海市举行。本次世博会也是由中国举办的首届世界博览会。上海世博会以“城市，让生活更美好”（Better City, Better Life）为主题，将充分探索21世纪城市生活。 这次世博会总投资达450亿人民币，创造了世界博览会史上最大规模记录。吸引200个国家和国际组织参展。预计有7000万人次的参观者。 为了更好地接待在这期间来自世界各地的参观者，如何合理安排各宾馆的住房问题提到了日程。组委会已接到了大量的客房住宿定单，每张定单的内容包括要住宿的房间数，开始住宿时间和要住的天数。为了便于整个城市各宾馆的管理，组委会希望对这些定单进行安排，目的是用尽可能少的房间来满足这些定单，以便空出更多的房间用于安排流动游客。 组委会请求DR. Kong来完成这个任务，对这些定单进行合理安排，使得满足这些定单要求的房间数最少。 假设：某个定单上的游客一旦被安排到某房间，在他预定住宿的期间内是不换房间的。为了简化描述，定单上的开始住宿时间为距离现在的第几天。例如，定单为（10，30，5）表示游客要求使用10个房间，第30天开始连住5天。 【标准输入】 第一行： N 表示定单数 接下来有N行，每行有三个整数 A B C 表示房间数，开始住宿时间和天数 【标准输出】 输出一个整数，为满足所有定单要求的最少房间数。 【约束条件】 1≤N≤10000 1≤A≤10，1≤B≤180， 1≤C≤10 【 样 例 】 标准输入 标准输出 3 7 3 10 4 4 9 3 3 12 6 【分析】 建立简单的数学模型，求出游客需要房间数和所住天数，房间数和所住天数最大值Max， 【代码】 #includeiostream using namespace std; #define MAX 230 int sum[MAX]; int main() { { int N;int room;int start;int day; int i=0; for(i=0;iMAX;i++) { sum[i]=0; } scanf(%d,N); while(N--) { scanf(%d%d%d,room,start,day); for(i=0;iday;i++) { sum[start+i]+=room; } } int max=-1; for(i=0;iMAX;i++) { if(maxsum[i]) { max=sum[i]; } } coutmaxendl; return 0; } 【运行截图】 2.2 聪明的“K