算法设计期末考试

1、 / 5算法设计、填空题1、衡量算法的两个指标：时间复杂度、空间复杂度 。2、回溯算法的基本思想：按照深度优先的策略,从根节点出发搜索解空间树。3、动态规划算法适合解决的问题： 最优化问题。4、分治算法的典型应用：二分法。5、时间复杂度T (n)中。的定义；判断时间复杂度等价于什么？定义：用来表示解决问题算法所需的时间总量f (n)的上界。是数量级的符号，用来表示时间复杂度。6、分支限界法的基本思想：以广度优先或以最小耗费优先的方式搜索解空间树。7、贪婪算法适合解决什么问题：局部最优化问题。8、递归算法的定义：定义：一归是一个过程或函数在其定义或说明中又直接或间接调用自身的方法。算法定义：就是

2、把一个大型复杂的问题层层转化为一个与原问题想死的规模较小的问 题，在逐步求解小问题后，再返回(回溯)得到大问题的解。、选择题1、算法时间复杂度密集度高低判断？O O (log2n) O (n) O (nAt) O (t?)O(n!)2、最大效益优先是哪种算法的首选方式？分支限界法。3、P、NP类问题及关系？存在多项式时间的算法的一类问题为P类问题，没有找到多项式时间的算法的一类问题为NP类问题。NP类中的所有问题都是 P类。4、设计循环赛日程表采用什么算法？二分策略递归算法、二分策略非递归算法、利用数据间的规律构造算法、二维递推算法。5、动态规划的步骤有：划分阶段、选择状态、确定决策并写出状态

3、转移方程。6、贪婪算法的基本要素：最优子结构设计、贪婪选择性质。7、分治算法解决问题必须满足的条件：1)能将这几个数据分解成 k个不同子集合，且得到 k个子集合是可以独立求解的子问 题，其中1k=32)上楼梯问题为什么适合用斐波那契数列求解？上楼梯问题通过反向思考，到第n 阶有两种情况：从第 n-1 阶到第 n 阶；从第 n-2 阶到第 n 阶。记 n 阶台阶的走法数为 f(n), 则 f(n)=1 n=1;2n=2;f(n-1)+f(n-2)n2反向分析法和递归设计一样， 就是找出大规模问题与小规模问题之间的关系， 而这个关系正好符合斐波那契数列的规律。4、写出算法设计思路并分析。( 1)递

4、归(汉诺塔问题)设计思路：找出大规模问题与小规模问题的递归关系。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)=1 n=1;2n=2;f(n-1)+f(n-

5、2)n2分析：反向分析法和递归设计一样，就是找出大规模问题与小规模问题之间的关系。5、分析某一个程序的执行结果包括执行过程(test() )执行结果：当 n=3 时： 32100123执行过程： test (int n)print n;if( n0)test(n-1) ;elseprint“ ;print n四、证明题1、证明时间复杂度的线性/ 非线性。假设n=2，有迭代方程 T(n)=2T(n/2)+2,计算O (n)。T(n)=2T(n/2)+2=2(T(n/2A2)+2)+2=4+n/2A2+4+2=4(2T(n/2A3)+2)+4+2所以：O(n)=2A(k-1)+(2Ak-2)=3/

6、2*2Ak-2=(3/2)n-2,所以此时间复杂度为线性级。11)n=22、递归调用的迭代方程(原式 =1+11+111+11-不变式： Sn=0n=0;=1n=1;(Sn-1-Sn-2)*10+1+Sn-1=11Sn-1-10Sn-2+1#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、证明数列稽查

7、适合用贪婪算法求解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

8、(k1+k2)+1*a+k1+k2+1(a*c+1)*b+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+1(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;#includeint main()int a,d;long x,y;for(a=3;a10;a+) for(d=1;d10;d+) x=d*100