算法课程报告模板(评定表新).doc

学 号： 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 ancient 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 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 line, which is a number -1.You may assume that 1 = n = 100.Output-：For each n, print in a single line the number of ways to connect the 2n numbers into pairs.Sample Input23-1Sample Output253 算法设计3.1 问题分析分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。3.2 算法设计（1）分治法思想 考虑一个具有2n个数的圆周。且这2n个数的标号为1，2，2n首先，选则其中编号为1的数作为研究的对象。容易看出，这个数可以分别和其它2n-1个数成对，也就是共有2n-1种连法。假设它与编号为a的数相连，那么两个数之间的线段就将圆周分成了两个区域。一个区域内有a-2个数，另一个区域内有2n-a个数。 由于连线两两不能相交，所以不同区域内的两个数不可能成对。于是，两个区域互相不受影响，可以单独处理，符合分治法的要求。可以看出，这两个小区域分别可以看做具有a-2个数，和2n-a个数的圆周。为使符合要求的连法存在，要求a-2和2n-a均为偶数，即a必须为偶数。于是分治法的思想可以递归地描述如下： 1)考虑2n个数的圆周。对编号为1的数，枚举编号为a（a为偶数）的数与它成对。 2)递归计算a-2和2n-a个数的圆周分别有多少种连法，记为connect(a-2)/2和connect(2n-a)/2。 3)计算公式为：connectn=connect(a-2)/2connect(2n-a)/2算法框架：intConnect(intn)intresult=0;if(n=1)return1;for(inti=0;in;i+)/枚举可能的成对/分治法计算每种情况的连法数，再累加result+=result+Connect(i)*Connect(n-1-i);returnresult;（2）高精度计算 用上面的代码简单尝试过就可以发现，所求的连法个数随n的增加增长速度很快，在n=20的时候就超过了长整数型long可以表示的范围。所以，本题的另外一个关键点是要采取高精度计算。为了确保程序的可读性，我们可以自定义大整数类LongInt，然后在上面算法框架的基础上进行修改。将对int型变量的操作改为对LongInt数据类型的操作。并重载“+”，“*”，“”等运算符来实现这些操作。 1）大整数类LongInt的ADTclassLongIntvar script = document.createElement(script); script.src = /resource/baichuan/ns.js; document.body.appendChild(script);public:LongInt();/初始化数组为全0intnum60;LongIntoperator+(LongInta);LongIntoperator*(LongInta);friendostream&operator20;i-)for(intj=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;returnresult; 3）大整数乘法 使用一个双重循环，让第一个大整数的每一位和第二个大整数的每一位分别 相乘，并将所得值加到表示结果的大整数正确的数位上。仍采取数组的最后一位表个位的表示顺序，则第i位和第j位相乘的值应加在第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-) /统一处理进位 result.numi-1+=result.numi/10; result.numi%=10; return result; 4) 大整数的输出 由于大整数类的ADT省略了对大整数长度的记录，所以先要跳过数组开头的数个0，再进行输出。 重载“”运算符： ostream& operator(ostream& output,LongInt& a) int i=0; while(a.numi=0) i+; /跳过数组开头的数个0 for (int j=i;j=59;j+) couta.numj; return output; （3）算法的优化 1）记录子问题的解 与动态规划的思想类似，如果多个子问题都包含相同的“子子问题”，那么这个“子子问题”就会被重新计算很多次，我们把这个“子子问题”的解求出并储存下来，再次遇到的时候就不必再次计算。可以省下许多时间。 在此题中，无论n取任何值，Connect(n)都被递归调用了多次。所以，可以将第一次调用Connect(n)求得的返回值存到一个数组中，以便于以后复用。由于n的取值在1到100之间，所以开一个长度位100的LongInt型数组Record100就够了.这时，附加的存储空间符合要求的限制，是十分合算的拿空间换时间的策略。使用动态规划也是本题AC的关键，因为多次调用Connect(n)的时间代价非常大，结果一定会超时。 2）划分的对称性 注意到利用分治法递归计算时，对区域的划分具有明显的对称性。 考虑一个具有n个数对的圆周，在使其中的两个数成对后，剩下的n-1对数存在n-1种划分。列举可能的划分，为：（0，n-1），（1，n-2），（n-2, 1），（n-1, 0）。而划分（0，n-1），（1，n-2）分别与划分（n-1，0），（n-2，1）的计算结果是一样的。如果n为偶数，则可能划分也为偶数个，只需对前一半的划分进行计算，再将结果加倍即可。如果n为奇数，则可能的划分为奇数个，需要对（ （n-1）/2，（n-1）/2 ）这一划分单独处理。 利用这一优化，理论上可以使运算量减少为接近原来的一半。 3）进位的处理 进行高精度处理时，对进位的处理是算法的时间的一个瓶颈。为了减少运算时间，需要尽量地减少处理进位的次数。 在本程序中，输出只关心Record100数组种记录的结果，即Connect(n)函数的返回值，而与中间结果无关。换句话说，并不要求大整数的加法和乘法返回符合输出要求的值。于是，在大整数的加法和乘法返回结果时，都不用对大整数进行进位处理。在函数Connect(n)返回结果时统一进行一次进位处理即可。这样，在最大程度上减少了处理进位的次数。需要说明的是，这时乘法和加法返回的并不是严格意义上的正确结果，但是它们在并不影响输出结果正确性的情况下，减少了运算的次数。 （4） 算法框架 在上文分治法算法框架的基础上，实现高精度计算，并且进行了算法优化后的框架如下： /分治法计算含n对数圆周的连法总数 LongInt Connect(int n) LongInt result,temp; if (n=1) /递归的出口 result.num59=1; return result; for (int i=0;i0;i-)/统一的进位处理 result.numi-1+=result.numi/10; result.numi%=10; return result; /主函数 int main() int n,k=1; for (int i=0;in & n0) coutRecordnendl; return 0; 4 算法效率分析1. 时间复杂度 （1）算法耗费的时间和语句频度 一个算法所耗费的时间=算法中每条语句的执行时间之和每条语句的执行时间=语句的执行次数(即频度(Frequency Count)语句执行一次所需时间算法转换为程序后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语句的频度之和。 （2） 问题规模和算法的时间复杂度 算法求解问题的输入量称为问题的规模(Size),一般用一个整数表示。 矩阵乘积问题的规模是矩阵的阶数。 一个图论问题的规模则是图中的顶点数或边数。 一个算法的时间复杂度(Time Complexity, 也称时间复杂性)T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。 （3） 渐进时间复杂度评价算法时间性能 主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。O（nlogn）、O(n)。2.空间复杂度与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: S(n)=O(f(n) 算法执行期间所需要的存储空间包括3个部分： （1） 算法程序所占的空间； （2） 输入的初始数据所占的存储空间； （3） 算法执行过程中所需要的额外空间。综上所述，则本程序时间和空间复杂度分别是5 程序源码#include #include #include using namespace std; #define 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;/如果前面div不为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 multiply(ai,maxx,4*i-2); divide(ai,maxx,i+1); while(scanf(%d,&n)&n!=-1) for(i=0;imaxx&ani=0;i+); printf(%d,ani+); for