算法实验报告(第二大班)(第2组).doc

院 系： 计算机科学学院 专 业： 计算机科学与技术 年 级： 09级 课程名称： 算法设计与分析基础 班 号： 二大班 组 号： 2组 指导教师： 邢光林 2011年 5月 5日组员学号姓名实验名称算法实验整体框架的构建 实验室9#205实验目的或要求实验目的: 熟悉实验环境VC6.0 ； 复习C、C+语言以及数据结构课程的相关知识，实现课程间的平滑过度；实验要求:1）设计的主菜单可以是图形模式的，也可以是控制台模式的。以控制台为例，主菜单大致如下： 算法设计与分析实验1. 算法分析基础Fibonacci序列问题2. 分治法在数值问题中的应用矩阵相乘问题3. 减治法在组合问题中的应用8枚硬币问题4. 变治法在排序问题中的应用堆排序问题 99. 退出本实验 请输入您所要执行的操作（1，2，3，4，99）：2）点击操作后进入相应的实验项目或是相应项目的下一级菜单；3）可以反复执行，直到退出实验。实验原理（算法基本思想）用switch,case语句来控制选择，用while循环来控制程序何时退出，从而实现反复执行，直到退出实验为止程序代码#includeusing namespace std;void menu();int main()int choose;do menu(); cinchoose; switch(choose) case 1: experiment1 ();break; case 2: expriment2();break; case 3: experiment3();break; case 4: experiment4(); break;case 99:break; default:coutnot a valid choice,choose again!endl;while(choose!=99); return 0;void menu()cout-n;coutexperiment n;cout-n;cout 1. Analysis algorithm based-Fibonacci problem n n;cout 2. Partition method in the application of numerical problems-Matrix multiplication problem nn;cout 3. Among the reduction in combination of the problems of the application-8 coin problem nn;cout 4. Among the change in the application of scheduling problems-Pile of scheduling problems nn;cout 99. Quit this experiment n ;cout-n;cout please choose（1，2，3，4,99）:;实验结果及分析结果分析：通过输入数字，来选择你要执行的子程序，这是用case语句来判断的，一旦case语句后面的语句遇到break语句，就会跳出switch语句，从而执行while语句，用来判断你是否要继续，当按了99就退出程序，实验名称斐波那契数列实验室9#205实验目的或要求 实验题目 给定一个非负整数n，计算第n个Fibonacci数 实验目的 1）理解递归算法和迭代算法的设计思想以及递归程序的 调式技术 2）掌握并应用递归算法和迭代算法效率的理论分析(前验分 析)和经验分析(后验分析)方法； 3）理解这样一个观点：不同的算法可以解决相同的问题， 这些算法的解题思路不同，复杂程度不同，效率也不同实验原理（算法基本思想）迭代算法：根据斐波那契数列的生成规律，用3个变量f1,f2,f3分别存储前二个和第三个的数值,然后第将f3赋给f2,f2赋给f1,依次迭代下去，求的你所需的斐波那契值递归算法：由斐波那契的值是由前2个数值决定的，第一个数值是0，第二个数值是1，所以用前二个数值递归求的你所需的数值程序代码#include#include long fib(int n)if(n=0)return 0;if(n=1)return 1;if(n1)return fib(n-1)+fib(n-2);void Iteration(int n)long f1=0,f2=1,f3=0,i=1;while(in)f3=f2+f1;coutf3 ;f1=f2;f2=f3;i+;void main()int n;long y,RunTime;clock_t start,finish;coutn; Iteration(n);start=clock();y=fib(n);finish=clock();RunTime=(long)(finish-start)/CLOCKS_PER_SEC);coutRunTimen;实验结果及分析实验名称分治法在数值问题中的应用矩阵相乘问题 实验室9#203实验目的或要求实验目的:1）提高应用蛮力法设计算法的技能；2）深刻理解并掌握分治法的设计思想；3）理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对其进行改进，以提高算法的效率。 实验要求1）设计并实现用BF方法求解矩阵相乘问题的算法；2）设计并实现用DAC方法求解矩阵相乘问题的算法；3）以上两种算法的输入既可以手动输入，也可以自动生成；4）对上述两个算法进行时间复杂性分析，并设计实验程序验证分析结果；5）设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。实验要求：1）设计并实现用BF方法求解矩阵相乘问题的算法；2）设计并实现用DAC方法求解矩阵相乘问题的算法；3）以上两种算法的输入既可以手动输入，也可以自动生成；4）对上述两个算法进行时间复杂性分析，并设计实验程序验证分析结果；5）设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。实验原理（算法基本思想） 首先定义两个数据类型Strassen和BruteForce。BruteForce用于蛮力法操作；Strassen类用于strassen操作。先利用BruteForce类中Input()方法输入N*N维数组，再利用MatrixBruteForce()方法进行蛮力法矩阵相乘，最后通过Output()输出排序结果。Strassen用于分治法法操作，先利用Input()方法把N扩展为2的指数，不足补零。再利用MatrixStrassen()方法进行分治矩阵相乘，再利用Output()方法输出。程序代码#include Strassen.h#include BruteForce.h#include using namespace std;void main() BruteForce BF;Strassen SF; cout现在录入矩阵ANN和矩阵BNN:endlendl; /定义三个矩阵A,B,C BF.Input();cout输出矩阵ANN:endl; BF.Output(BF.A,BF.N); /输出矩阵ANN和矩阵BNNcout输出矩阵BNN:endl; BF.Output(BF.A,BF.N); BF.MatrixBruteForce();cout用蛮力法计算ANN*BNN:endl; BF.Output(BF.C,BF.N);SF.Input(BF); N);cout用Strassen法计算ANN*BNN:endl;SF.MatrixStrassen(SF.A,SF.B,SF.C,SF.N);BF.Output(SF.C,SF.N);#pragma once#ifndef BRUTEFORCE_H#define BRUTEFORCE_Htypedef float* ArryPtr;class BruteForce public: BruteForce(void); BruteForce(void); void Input(); void Output(float *P,int n); void MatrixBruteForce(); ArryPtr *A,*B,*C; int N;#endif#pragma once#ifndef STRASSEN_H#define STRASSEN_H#include BruteForce.hclass Strassen public: Strassen(void); Strassen(void); void Input(BruteForce BRF); void MatrixMultiply(float *P,float *Q,float *C); void MatrixAdd(float *P,float *Q,float *CC,int n); void MatrixSub(float *P,float *Q,float *CC,int n); void MatrixStrassen(float *P,float *Q,float *C,int n);ArryPtr *A,*B,*C; int N;#endif#include BruteForce.h#include #include #include using namespace std;BruteForce:BruteForce(void)BruteForce:BruteForce(void)void BruteForce:Input() coutN;N=8; float next; A=new ArryPtrN; B=new ArryPtrN; C=new ArryPtrN; ifstream input;input.open(input.txt); if(input.fail() coutnext; for(int i=0;iN;i+)Ai=new floatN; for(int j=0;jnext; for(int i=0;iN;i+) Bi=new floatN; Ci=new floatN; for(int j=0;jnext; void BruteForce:Output(float *P,int n)coutsetw(6);for(int i=0;in;i+)for(int j=0;jn;j+)cout*(*(P+i)+j)setw(6); coutendl; coutendl;void BruteForce:MatrixBruteForce() for(int i=0;iN;i+)for(int j=0;jN;j+)Cij=0;for(int k=0;kN;k+)Cij+=Aik*Bkj;#include Strassen.h#include BruteForce.h#include #include #include using namespace std;Strassen:Strassen()Strassen:Strassen(void)void Strassen:Input(BruteForce BRF) int FA=1;/如果N不是的指数则其余位补if(BRF.N=0)FA=0; while(FABRF.N)FA=FA*2;N=FA;A=new ArryPtrN; B=new ArryPtrN; C=new ArryPtrN; for(int i=0;iN;i+)Ai=new floatN;Bi=new floatN;Ci=new floatN; for(int j=0;jN;j+)if(iBRF.N&jBRF.N)Aij=BRF.Aij; Bij=BRF.Bij;elseAij=0; Bij=0; void Strassen:MatrixMultiply(float *P,float *Q,float *C)for(int i=0;i2;i+)for(int j=0;j2;j+)*(*(C+i)+j)=0;for(int t=0;t2;t+)*(*(C+i)+j)=*(*(C+i)+j)+(*(*(P+i)+t)*(*(*(Q+t)+j);void Strassen:MatrixAdd(float *P,float *Q,float *CC,int n)for(int i=0;in;i+) for(int j=0;jn;j+)*(*(CC+i)+j)=*(*(P+i)+j)+*(*(Q+i)+j);void Strassen:MatrixSub(float *P,float *Q,float *CC,int n)for(int i=0;in;i+) for(int j=0;jn;j+)*(*(CC+i)+j)=*(*(P+i)+j)-*(*(Q+i)+j);void Strassen:MatrixStrassen(float *P,float *Q,float *C,int n) ArryPtr *A11=new ArryPtrn,*A12=new ArryPtrn,*A21=new ArryPtrn,*A22=new ArryPtrn; ArryPtr *B11=new ArryPtrn,*B12=new ArryPtrn,*B21=new ArryPtrn,*B22=new ArryPtrn; ArryPtr *C11=new ArryPtrn,*C12=new ArryPtrn,*C21=new ArryPtrn,*C22=new ArryPtrn; ArryPtr *M1=new ArryPtrn,*M2=new ArryPtrn,*M3=new ArryPtrn,*M4=new ArryPtrn,*M5=new ArryPtrn,*M6=new ArryPtrn,*M7=new ArryPtrn; ArryPtr *BB=new ArryPtrn,*AA=new ArryPtrn; ArryPtr *CC1=new ArryPtrn,*CC2=new ArryPtrn; for(int i=0;in;i+) A11i=new floatn; A12i=new floatn; A21i=new floatn; A22i=new floatn; B11i=new floatn; B12i=new floatn; B21i=new floatn; B22i=new floatn; C11i=new floatn; C12i=new floatn; C21i=new floatn; C22i=new floatn; M1i=new floatn; M2i=new floatn; M3i=new floatn; M4i=new floatn; M5i=new floatn; M6i=new floatn; M7i=new floatn; BBi=new floatn; AAi=new floatn; CC1i=new floatn; CC2i=new floatn; if(n=2) MatrixMultiply(P,Q,C); else for(int i=0;in/2;i+) for(int j=0;jn/2;j+) A11ij=*(*(P+i)+j); A12ij=*(*(P+i)+j+n/2); A21ij=*(*(P+(i+n/2)+j); A22ij=*(*(P+(i+n/2)+j+n/2); B11ij=*(*(Q+i)+j); B12ij=*(*(Q+i)+j+n/2); B21ij=*(*(Q+(i+n/2)+j); B22ij=*(*(Q+(i+n/2)+j+n/2); MatrixAdd(A11,A22,AA,n/2); MatrixAdd(B11,B22,BB,n/2); MatrixStrassen(AA,BB,M1,n/2);/M1=(A11+A22)*(B11+B22) MatrixAdd(A21,A22,AA,n/2); MatrixStrassen(AA,B11,M2,n/2);/M2=(A21+A22)*B11 MatrixSub(B12,B22,BB,n/2); MatrixStrassen(A11,BB,M3,n/2);/M3=A11*(B12-B22) MatrixSub(B21,B11,BB,n/2); MatrixStrassen(A22,BB,M4,n/2);/M4=A22*(B21-B11) MatrixAdd(A11,A12,AA,n/2); MatrixStrassen(AA,B22,M5,n/2);/M5=(A11+A12)*B22 MatrixSub(A21,A11,AA,n/2); MatrixAdd(B11,B12,BB,n/2); MatrixStrassen(AA,BB,M6,n/2);/M6=(A21-A11)*(B11+B12) MatrixSub(A12,A22,AA,n/2); MatrixAdd(B21,B22,BB,n/2); MatrixStrassen(AA,BB,M7,n/2);/M7=（A12-A22）*(B21+B22) MatrixAdd(M1,M4,CC1,n/2); MatrixSub(M5,M7,CC2,n/2); MatrixSub(CC1,CC2,C11,n/2);/C11=M1+M4-M5+M7 MatrixAdd(M3,M5,C12,n/2);/C12=M3+M5 MatrixAdd(M2,M4,C21,n/2);/C21=M2+M4 MatrixAdd(M1,M3,CC1,n/2); MatrixSub(M2,M6,CC2,n/2); MatrixSub(CC1,CC2,C22,n/2);/C11=M1+M3-M2+M6 for(int i=0;in/2;i+) for(int j=0;jn/2;j+) *(*(C+i)+j)=C11ij; *(*(C+i)+j+n/2)=C12ij; *(*(C+(i+n/2)+j)=C