《算法课程报告模板(评定表新)》由会员分享，可在线阅读，更多相关《算法课程报告模板(评定表新)（14页珍藏版）》请在金锄头文库上搜索。
1、学 号： 0121310880122课 程 报 告（算法设计与分析 B）题 目基于分治方法的游戏的连接问题求解学 院 计算机科学与技术专 业 软件工程班 级 软件 1302 班姓 名 龚鸥波指导教师 李晓红2015 年 12 月 10 日目录1 注册资料 .22 选题描述 .23 算法设计 .23.1 问题分析 .23.2 算法设计 .44 算法效率分析 .55 程序源码 .56 试算截屏图 .87 分析与总结 .88 参考文献 .91 注册资料用户名：gongoubo密码：aicai1994218选题题号：20842 选题描述 英文题目描述This is a small but ancien
2、t game. You are supposed to write down the numbers 1, 2, 3, . . . , 2n - 1, 2n consecutively in clockwise order on the ground to form a circle, and then, to draw some straight line segments to connect them into number pairs. Every number must be connected to exactly one another. And, no two segments
3、 are allowed to intersect. Its still a simple game, isnt it? But after youve written down the 2n numbers, can you tell me in how many different ways can you connect the numbers into pairs? Life is harder, right?Input-：Each line of the input file will be a single positive number n, except the last li
4、ne, which is a number -1. You may assume that 1 20;i-) for (int j=59;j59-i;j-) result.numi+j-59+=numi*a.numj; /按位相加 for (i=59;i0;i-) /统一处理进位 result.numi-1+=result.numi/10; result.numi%=10; return result; 3）大整数乘法 使用一个双重循环，让第一个大整数的每一位和第二个大整数的每一位分别 相乘，并将所得值加到表示结果的大整数正确的数位上。仍采取数组的最后一位表个位的表示顺序，则第 i 位和第 j
5、 位相乘的值应加在第 i+j-59 位上（数组大小为 60）。 再考虑对进位的处理。如果每次运算都进行进位处理，需进行n2 次处理，时间代价较大。所以选择最后一并进行进位处理，从低位到高位扫描，只需进行 n 次运算。 重载“*”运算符： LongInt LongInt:operator*(LongInt a) LongInt result; /第 i 位和第 j 位相乘的值加在第 i+j-59 位上 for (int i=59;i20;i-) for (int j=59;j59-i;j-) result.numi+j-59+=numi*a.numj; for (i=59;i0;i-) /统一处
6、理进位 result.numi-1+=result.numi/10; result.numi%=10; return result; 4) 大整数的输出 由于大整数类的 ADT 省略了对大整数长度的记录，所以先要跳过数组开头的数个 0，再进行输出。 重载“0;i-)/统一的进位处理 result.numi-1+=result.numi/10; result.numi%=10; return result; /主函数 int main() int n,k=1; for (int i=0;in & n0)cout #include #include using namespace std; #de
7、fine base 10000/数组一个单位存的是 10000 进制 #define maxx 100/数组长度 void multiply(int a,int max,int b) int i,array=0; for(i=max-1;i=0;i-) array+=b*ai; ai=array%base; array/=base; /for(i=0;imax;i+) printf(%d,ai); / printf(n); void divide(int a,int max,int b) int i,div=0; for(i=0;imax;i+) div=div*base+ai;/如果前面 d
8、iv 不为 0 则加上 div*base 如果为 0 不借位就算了 假如 ai-1=0000,ai=0006 b=3，这时前面 div 为 0 不借位就算了得到 2 ai=div/b; div%=b; /for(i=0;imax;i+) printf(%d,ai); /printf(n); int main() int n,i; int a101maxx; memset(a1,0,maxx*sizeof(int);/初始化 a1为 0 for(i=2,a1maxx-1=1;i101;i+) memcpy(ai,ai-1,maxx*sizeof(int);/把 ai-1复制进 ai multip
9、ly(ai,maxx,4*i-2); divide(ai,maxx,i+1); while(scanf(%d,&n)&n!=-1) for(i=0;imaxx printf(%d,ani+); for(;imaxx;i+) printf(%04d,ani); printf(n); return 0; 6 试算截屏图图 3 程序运行截图网站提交成功截图图 4 提交结果截图7 分析与总结这道题目没有什么需要注意的边界条件。只要分治法的递归描述公式正确，再确保大整数加法和乘法的函数能够返回正确的结果，基本上就可以 Ac 了。在进行数据验证时，可以先不用高精度做，然后记下 10 以内的数据，作为高精度
10、算法调试时的检验依据。用 10 以内的数据检验高精度算法的正确性，如果都能通过，就可以提交 acm 了。通过对这门课的学习，我了解了一些有用的算法。，例如分治算法和动态规划算法等等，通过自己的实践，自己能够更加深入的去了解，并且能够灵活的运用。自己需要更加的努力提高自己的能力。8 参考文献1 王红梅. 算法设计与分析（第二版）. 北京：清华大学出版社，2013.2 谭浩强. C 程序设计M. 北京：清华大学出版社，2005.3 严蔚敏，吴伟民. 数据结构M. 北京:清华大学出版社，1996.4 张富. C 及 C+程序设计M. 北京：人民邮电出版社.5骆吉洲，算法设计与分析，机械工业出版社. 本科生课程报告成绩评定表班级：软件 1302 班姓名：龚鸥波学号：0121310880122序号 评分项目 满分 实得分1 学习态度认真、遵守纪律 102 设计分析合理性 203设计方案正确性、可行性、创造性204 设计结果正确性 255 设计报告的规范性 156 设计验收 10总得分指导教师签名：2015 年 12 月 10 日
