算法设计期末考试.doc

算法设计一、填空题1、衡量算法的两个指标：时间复杂度、空间复杂度。2、回溯算法的基本思想：按照深度优先的策略，从根节点出发搜索解空间树。3、动态规划算法适合解决的问题：最优化问题。4、分治算法的典型应用：二分法。5、时间复杂度T（n）中O的定义；判断时间复杂度等价于什么？定义：用来表示解决问题算法所需的时间总量f（n）的上界。O是数量级的符号，用来表示时间复杂度。6、分支限界法的基本思想：以广度优先或以最小耗费优先的方式搜索解空间树。7、贪婪算法适合解决什么问题：局部最优化问题。8、递归算法的定义：定义：递归是一个过程或函数在其定义或说明中又直接或间接调用自身的方法。算法定义：就是把一个大型复杂的问题层层转化为一个与原问题想死的规模较小的问题，在逐步求解小问题后，再返回（回溯）得到大问题的解。二、选择题1、算法时间复杂度密集度高低判断？O（l）O（log2n）O（n）O（nt）O（tn）O（n!）2、最大效益优先是哪种算法的首选方式？分支限界法。3、P、NP类问题及关系？存在多项式时间的算法的一类问题为P类问题，没有找到多项式时间的算法的一类问题为NP类问题。NP类中的所有问题都是P类。4、设计循环赛日程表采用什么算法？二分策略递归算法、二分策略非递归算法、利用数据间的规律构造算法、二维递推算法。5、动态规划的步骤有：划分阶段、选择状态、确定决策并写出状态转移方程。6、贪婪算法的基本要素：最优子结构设计、贪婪选择性质。7、分治算法解决问题必须满足的条件：1）能将这几个数据分解成k个不同子集合，且得到k个子集合是可以独立求解的子问题，其中1k=32）上楼梯问题为什么适合用斐波那契数列求解？上楼梯问题通过反向思考，到第n阶有两种情况：从第n-1阶到第n阶；从第n-2阶到第n阶。记n阶台阶的走法数为f(n),则f(n)=1n=1;2n=2;f(n-1)+f(n-2)n2反向分析法和递归设计一样，就是找出大规模问题与小规模问题之间的关系，而这个关系正好符合斐波那契数列的规律。4、写出算法设计思路并分析。（1）递归（汉诺塔问题）设计思路：找出大规模问题与小规模问题的递归关系。1）将A基座上面的n-1个盘子借助B基座移到C基座上。2）将A基座剩余的一个n号盘子移到B基座上。3）将C基座的n-1个盘子借助A基座移到B基座上。分析：递归算法执行中有递归调用的过程和回溯的过程，递归法就是通过调用把问题从大规模归结到小规模，当小规模得到解决后又把小规模的结果回溯，从而退出大规模的解。（2）上楼梯问题设计思路：通过反向分析法考虑到第n阶有两种情况：从第n-1阶到第n阶；从第n-2阶到第n阶。记n阶台阶的走法数为f(n),则f(n)=1n=1;2n=2;f(n-1)+f(n-2)n2分析：反向分析法和递归设计一样，就是找出大规模问题与小规模问题之间的关系。5、分析某一个程序的执行结果包括执行过程（test()）执行结果：当n=3时：32100123执行过程：test (int n)print n; if( n0)test(n-1) ; elseprint “; print n 四、证明题1、证明时间复杂度的线性/非线性。假设n=2k，有迭代方程T(n)=2T(n/2)+2，计算O（n）。T(n)=2T(n/2)+2=2(T(n/22)+2)+2=4+n/22+4+2=4(2T(n/23)+2)+4+2所以：O(n)=2(k-1)+(2k-2)=3/2*2k-2=(3/2)n-2，所以此时间复杂度为线性级。2、递归调用的迭代方程（原式=1+11+111+1111）不变式：Sn=0n=0;=1n=1;(Sn-1-Sn-2)*10+1+Sn-1=11Sn-1-10Sn-2+1n=2#includestdio.hint main()int f(int n),n;printf(请输入n:);scanf(%d,&n);printf(%d,f(n);int f(int n)if(n=1)return 1;else if(n=0) return 0;elsereturn f(n-1)+(f(n-1)-f(n-2)*10+1);3、证明数列稽查适合用贪婪算法求解2个人轮流取2n个书中的n个数，所取数之和大者为胜，请编写算法，让先取数者为胜，模拟取数过程。数学模型建立：n个数排成一排，给这n个数从左到右编号的数计算机只能取到另一种编号的数。算法设计：分别计算一组数的基数为和偶数位的数据之和，然后就有了先取数者为胜的取数方案了。以下面排数为例：1,2,3,10,5,6,7,8,9,4，奇编号数之和为25，小于偶编号数之和30，第一次取出以后，计算机取哪边的数，取数者就取哪边的数，这样就可以保证取数者自始至终取代欧编号的数，而计算机自始至终取到奇编号的数。算法：（1）(a*b+1)*c+1=a*a*a+(2k1+k2)a*a+k1(k1+k2)+1*a+k1+k2+1 （2）(a*c+1)*b+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+1 （3）(b*c+1)*a+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+1所以此问题应用贪婪算法。五、算法设计1、假设有八个人，画出循环日程表，并写出算法。1234567821436587341278564321876556781234658721437856341287654321int a5050;table1()int k,n=1,i,j;input(k);for(i=1;i=k;i+)n=n*2;dimi(1,n,n);for(i=1;i=n;i+)print(/n);for(j=1;jn/2;k1-)for(k2=i;k2=i-1+n/2;k2+)ak2k1=ak2+n/2k1-n/2;for(k2=i+n/2;k2=i-1+n;k2+)ak2k1=ak2-n/2k1-n/2;2、编写算法解如下数字谜。ABCABxADDDDDD#includeint main()int a,d;long x,y;for(a=3;a10;a+)for(d=1;d10;d+)x=d*100000+d*10000+d*1000+d*100+d*10+d;if(x%a=0) y=x/a;if(y/10000=a&(y%100)/10=a)printf(ABCAB=%ldn,y);printf(A=%ldn,a);printf(DDDDDD=%ldn,x);