《ACM算法与数据结构设计》大作业模板.doc
ACM算法与数据结构设计课程大作业报告题 目： 全排列 学 生 姓 名 陈迪 班 级 学 号 B 学 生 学 院 通信与信息工程学院 学 生 专 业 通信工程 联 系 电 话 电 子 邮 件 B 指 导 教 师 陈 志 指 导 单 位 计算机学院软件工程系 日 期 2011.5.24 成 绩批阅人陈 志日 期2011.6.1注意事项（1）课程大作业从ACM算法与数据结构设计课程实验二（2011年4月19日）或实验三（2011年5月10日）中任选一个课题完成。（2）课程大作业内容包括课题名称、课题内容和要求、课题分析、概要设计、详细设计、测试数据及其结果分析、调试过程中的问题、参考资料列表、课程小结等。（3）课程报告可以打印，也可以手写，但前面两页内容、大作业撰写纲要、课程小结不可遗漏和更换。（4）课程小结给出ACM程序设计过程的收获、遇到的问题，遇到问题解决问题过程的思考、程序调试能力的思考等，需要手写签字。（5）课程大作业提交时间为2011年5月24日（第14周星期二）晚 19:0020:00，地点：计算中心A机房。一、课题名称二、课题内容和要求三、课题分析对课题问题及解决方法进行分析，给出预想的程序模块划分方案、输入输出测试方案等。四、概要设计 在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义，例如数组、字符串、结构体、链表等）。五、详细设计各个功能模块算法实现的源程序（可以是一组源程序，每个功能模块采用不同的函数实现），源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。六、测试数据及其结果分析测试数据，应准备多组测试数据，对测试输出的结果进行分析。七、调试过程中的问题每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），以及问题解决方案的改进设想。八、参考资料详细列出你在进行ACM程序设计、撰写课程大作业时用到的资料，包括书藉信息、网上资料（给出链接）等 南京邮电大学ACM算法与数据结构设计课程小结学 生 姓 名 班 级 学 号 学 生 学 院 学 生 专 业 电 子 邮 件 指 导 教 师 陈 志 学 期 2010-2011-2 ACM算法与数据结构设计课程小结学生签字： 年 月 日 ACM算法与数据结构设计课程大作业报告题 目： 全排列 学 生 姓 名 陈迪 班 级 学 号 B 学 生 学 院 通信与信息工程学院 学 生 专 业 通信工程 联 系 电 话 电 子 邮 件 B 指 导 教 师 陈 志 指 导 单 位 计算机学院软件工程系 日 期 2011.5.24 成 绩批阅人陈 志日 期2011.6.1一、课题名称全排列二、课题内容和要求时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte给定n个整数，现请编程求它们所有的全排列。 输入输入包括两个行，第一行给出正整数n( 0 < n <=8), 第二个是 n个整数（大小范围：-104, 104）。输出按字典序输出这n个整数的全排列，每一行给出一个全排列。样例输入31 23 88样例输出1 23 881 88 2323 1 8823 88 188 1 2388 23 1三、课题分析全排列的生成就是对于给定的字符集或数集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。对给定的字符集中的字符规定一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后，或根据给定的数集中的大小关系，规定两个全排列的先后是从左到右逐个比较对应的数的大小，即依照字典序给出全排列。例如字符集1,2,3,较小的数字较先,这样按字典序生成的全排列是：1 2 31 3 22 1 32 3 13 1 23 2 1四、概要设计1、定义一个main函数。2、自定义一个qsort函数用来解决顺序的比较问题。3、另外再自定义一个print_permutation函数，这是整个函数的最关键的部分，达到打印所有全排列的效果。五、详细设计1，主函数：int main() int n,i; scanf("%d", &n); for(i = 0; i<n; i+) scanf("%d", &arri); qsort(arr, n, sizeof(arr0), cmp); print_permutation(n,0); return 0; 2、qsort函数：/qsort的比较函数int cmp ( const void *a , const void *b ) return *(int *)a - *(int *)b;3、关键的自定义函数部分void print_permutation(int n, int cur) int i, j; if (cur = n) /递归边界 for (i = 0; i < n; i+) if (i) printf(" %d", arrAi-1); else printf("%d", arrAi-1); printf("n"); else for (i=1; i<=n; i+) /尝试在Acur中填各种整数i int ok = 1; for (j=0;j<cur;j+) if (Aj = i) /如果i已经在A0Acur-1出现过，则不能再选 ok =0; if (ok) Acur = i; print_permutation(n, cur+1); /递归调用 六、调试过程中的问题自定义函数被放在主函数之后，而开始未进行定义，显示函数qsort未被定义；开始时print_permutation函数中的递归调用没有定义出口，导致整个函数无法运行，调试到最后才发现这个问题。七、参考资料1. C语言程序设计 作者 : 谭浩强出版社 : 清华大学出版社2. 实用算法的分析与程序设计作 者：吴文虎/王建德著出 版 社：电子工业出版社出版日期：1998-013、南邮ACM4、武汉大学ACM南京邮电大学ACM算法与数据结构设计课程小结学 生 姓 名 陈迪 班 级 学 号 B 学 生 学 院 通信与信息工程学院 学 生 专 业 通信工程 电 子 邮 件 B 指 导 教 师 陈 志 学 期 2010-2011-2 ACM算法与数据结构设计课程小结Acm学习确实是一件很辛苦的事，要想想通，听懂就要专心、一刻不敢走神等到做题时，更是全力以赴。这学期给我印象最深的是那些编程高手的速度与激情，还有那个胖乎乎的大四学长，幽默而充满智慧的话语给原本沉闷的课堂带来一丝轻松，相比于上学期选的那些“打酱油”的课程，虽然ACM比较难学，而且我确实很多也没听懂，但我的收获还是很多的，体验了全力以赴去干一件事情而后的满足，听到看到了一些大牛的事迹，对我来说有很大的鼓舞和激励，总的来说收获还是很大的。学生签字： 年 月 日
