分治算法.doc

分治算法.doc深圳大学实验报告课程名称: 算法设计与分析实验项目名称:分治算法-循环赛日程表的分治算法实现学院:计算机与软件学院专业、班级:计算机07级1班指导教师:王华民报告人:柳青学号:2007130071联系方式:610418实验时间:2009年10月15日--11月5日实验报告提交时间:2009年教务处制(注:此模版仅为参考)要求:提交实验报告(电子版和书面两种形式),内容包含:,理解递归算法以及分治算法的基本思想,能对递归算法以及分治算法进行设计、分析。理解Strassen矩阵乘法的理论分析或循环赛日程表的分治算法以及编程实现。本课程实验目的是验证、巩固和补充课堂讲授的理论知识。培养学生初步具备独立设计算法和对给定算法进行复杂性分析的能力,为后继课程和实际工作打下基础。(两题任选一)题目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天。:题目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的情形,完成n=2k+1和n=2k的不同处理并输出形如下表的比赛日程表。其中:k为【3,7】间的随机整数(3)讨论分治算法的时间复杂性。表分治法n=10的比赛日程表123456789102153748910638124591067459132106785421013678967891015432761082915438367910215491046873215**********(方案)说明(如:你如何实现矩阵划分、矩阵结果的合并)将所有的选手分为两半,n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地对选手进行分割,直到只剩下2个选手时,让这2个选手进行比赛即可,同理处理剩下的n/2个,最后输出n个选手的比赛。(主要函数功能、变量、语句进行注释)#include<iostream>#include<string>#include<iomanip>#include<cmath>usingnamespacestd;constintN=10000;inta[N][N],b[N];intk;voi