循环赛日程表的分治算法实现实验报告_gxl.doc

深 圳 大 学 实 验 报 告 课程名称： 算法设计与分析 实验项目名称： 分治算法 -矩阵相乘的Strassen算法及时间复杂性分析 或-循环赛日程表的分治算法实现 或-多项式乘积问题的分治算法及时间复杂性分析 学院： 专业、班级： 指导教师： 报告人： 学号： 实验时间： 实验报告提交时间： 教务处制一、 实验目的与实验内容11实验目的通过本设计性实验，理解递归算法以及分治算法的基本思想。理解Strassen矩阵乘法的理论分析或循环赛日程表的分治算法以及编程实现。掌握多项式乘积的分治方法。能对递归算法以及分治算法进行设计、分析。本课程实验目的是验证、巩固和补充课堂讲授的理论知识。培养学生初步具备独立设计算法和对给定算法进行复杂性分析的能力，为后继课程和实际工作打下基础。12实验题目 （三题任选一）题目1：设计一个矩阵相乘的Strassen算法编程实现并做算法的时间复杂性分析。其中：乘积矩阵C = A*B， A=（aij）n*n，B=（bij）n*n（1）考虑n为2的幂次方的情形，取n=8实现分治递归； （2）考虑n不是2的幂次方，n为偶数的情形，设计一个传统方法与的Strassen算法相结合的矩阵相乘算法,取n=12实现分治递归（可以有多种方案实现）；矩阵A,B元素自动生成，限定矩阵元素在0-10之间。题目2：设计一个满足以下要求的循环比赛日程表：（）(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)当n是奇数时,循环赛一共进行n天, n是偶数时,循环赛进行n-1天。题目3：设计一个多项式乘积问题的分治算法并做算法的时间复杂性分析 13实验要求：题目1具体要求：（1）矩阵阶数n由用户输入（注意n非 2k 时的处理）；（2）n阶矩阵A、B调用随机函数自动生成，限定矩阵元素在0-10之间；（3）输出A、B及C=A*B其中：输出传统定义矩阵乘积结果和Strassen矩阵乘积的结果，验证分治算法的正确性；（4）对直接计算（传统定义）矩阵乘积、Strassen矩阵乘积进行执行时间统计，分别记为T1，T2，并给出对比和时间复杂性分析。题目2具体要求：（1）选手人数n由用户输入（注意n为奇数和偶数时的不同处理）；（2）验证n=2k的比赛日程表；（3）完成n=2k+1和n=2k的不同处理并输出形如下表的比赛日程表。其中： k 为【5，7】间的整数；12345678910215374891063812459106745913210678542101367896789101543276108291543836791021549104687321510975684321表 分治法n=10的比赛日程表题目3具体要求：对教材114页第21题的数据，完成两个多项式乘积的分治算法：（1） 多项式Pn(X)的n与Qm (X)的m由用户输入；（2） 输出直接计算多项式乘积和分治算法多项式乘积的结果，验证分治算法的正确性；（3） 对直接计算多项式乘积、分治算法多项式乘积进行执行时间统计，分别记为T1，T2，并给出对比和时间复杂性分析。（4） 对P4(X)= X4 X3 + X2 - X +1与Q5 (X)= X5 3 X+ -10，按要求（1）（3）完成两个多项式乘积的分治算法。 二、 开发环境VC 6.0编程软件三、 算法简述总体思路：按分治策略，将所有分为两半，n个选手可以通过n/2个选手设计的比赛日程表来决定。递归地用一分为二的略对选手进行分割，直到只剩下两个选手。对于N为奇数的情况可以虚拟多一个选手，使其编程N+1个选手的日程表，最然后忽略虚拟运动员参与的比赛。对于分割时候N/2的情况也做特殊处理, 前n/2轮比赛空选手与下一个未参赛的选手进行比赛。四、 模型求解4.1 程序设计（方案）说明（如：你如何实现矩阵划分、矩阵结果的合并）4.2 主要源代码（主要函数功能、变量、语句进行注释）（1）分治法 void tourna(int n)if(n=1)a11=1;return;tourna(n/2);copy(n);（2）n为偶数的情况Copy（）函数：A.将左上角递归计算出的小块的所有数字按其相对位置抄到右下角，B.将右上角的小块的所有数字加n/2后按其相对位置抄到左下角，将左下角的小块中的所有数字按其相对位置抄到右上角void copy(int n)int m=n/2;for(int i=1;i=m;i+)for(int j=1;j1&odd(n/2) copyodd(n); /对n/2为奇数的情况的处理 else copy(n); /偶数的情况 (6)copyodd(n)实现n/2为奇数的时候的复制n/2奇数的一种处理方法：前n/2轮比赛空选手与下一个未参赛的选手进行比赛void copyodd(int n) int m=n/2; for(int i=1;i=m;i+) bi=m+i;bm+i=bi; for(i=1;i=m;i+) for(int j=1;jm) aij=bi;am+ij=(bi+m)%n; else am+ij=aij+m; for(j=2;j=m;j+) aim+j=bi+j-1; abi+j-1m+j=i; 4.3 程序使用说明（如：矩阵阶数n由用户输入）4.4 模型的解（含运行结果截图）当n=偶数时当n=奇数时4.5 测试及结果分析（如：1. 对传统定义矩阵乘积、Strassen矩阵乘积给出计算结果对比；2. 进行执行时间统计的对比并讨论算法性能的比较）五、 实验总结及自我评价（可含个人心得体会）（对实验中遇到的问题、难点及解决方法进行总结：自己在实验中的有哪些体会；对个人能力的评价。）整个赛程，当N为偶数的时候，N-1天能够结束。而当N为奇数的时候，只能在至少N天结束。比如N=3的时候，每场必须有两个人，则每天只能有一场比赛，假设是1和2比赛，则3号运动员没有对象比赛，所以一天最多一场比赛，这个比赛需要的比赛场数C=3场，则整个比赛需要的天数为C/1=3天。题目存