算法设计与分析实验报告肖志强.doc

院 系： 计算机科学学院 专 业： 计算机科学与技术 年 级： 2012 课程名称： 算法设计与分析基础 班 号： 1201 组 号： 1 指导教师： 邢光林 2015年 5 月 25 日组员学号姓名2012213508蒲灿 2012213510肖志强 2012213514邹治东实验名称 算法分析基础给定一个非负整数n，计算第n个Fibonacci数实验室9#206实验目的或要求1 实验目的1）理解递归算法和迭代算法的设计思想以及递归程序的调式技术2)握并应用递归算法和迭代算法效率的理论分析(前验分析)和经验分析(后验分析)方法；3)理解这样一个观点：不同的算法可以解决相同的问题，这些算法的解题思路不同，复杂程度不同，效率也不同；二实验要求1）使用教材2.5节中介绍的迭代算法Fib(n),找出最大的n,使得第n个Fibonacci数不超过计算机所能表示的最大整数，并给出具体的执行时间；2）对于要求1),使用教材2.5节中介绍的递归算法F(n)进行计算,同样给出具体的执行时间，并同1)的执行时间进行比较；3）对于输入同样的非负整数n，比较上述两种算法基本操作的执行次数；4）对1)中的迭代算法进行改进，使得改进后的迭代算法其空间复杂度为(1)；5）设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。实验原理（算法基本思想）1 迭代算法求最大Fibonacci在数列中位置1.先利用迭代求得计算机能表示的最大数MaxUnsignedInt.unsigned long int MaxUnsignedInt = 1;while ( MaxUnsignedInt*2+1 != MaxUnsignedInt ) MaxUnsignedInt=MaxUnsignedInt*2+1;2. 从1起进行(n-1) +( n-2) = n迭代，直到条件(temp3temp)时发生溢出(及超过最大数)，退出循环。求得此时的迭代次数-1即为最大Fibonacci的位置。unsigned long int n=MaxUnsignedInt;for( i=1; temp=n; i+ )/temptemp)/当temp3temp时，则发现temp发生溢出，结束计算break;temp3=temp;temp2=temp1;temp1=temp;2 递归算法1. 根据 / 0 n=0f(n)= 1 n=1 f(n-1)+f(n-2) n=2进行递归调用求解。long FF(unsigned int tt)/use di gui if( tt = 1 )return tt;elsereturn FF(tt-1) + FF(tt-2);三改进空间复杂度为(1)。利用公式：F(n)=(1/5)*(1+5)/2n - (1-5)/2nint fib(int n) double gh5=sqrt(double)5); return (pow(1+gh5),n)-pow(1-gh5),n)/(pow(double)2,n)*gh5); 程序代码void fibo()unsigned long int MaxUnsignedInt,n,times,t=100;clock_t start = clock();MaxUnsignedInt=1;while ( MaxUnsignedInt*2+1 != MaxUnsignedInt ) MaxUnsignedInt=MaxUnsignedInt*2+1;cout时间消耗：clock() - startendl;n=MaxUnsignedInt;int choose;bool end_this=true;while(end_this)cout*n;couta. 迭代算法 n;coutb 递归算法 n;coutc. 退 出 n;again: coutchoose;if( choose!= a & choose!=b & choose!=c )/输入菜单检查cout输入错误n;goto again;switch (choose)case a:coutt;start = clock();times=F(t);coutt是第times个Fibonacci数endl;cout时间消耗：clock() - startendl;break;Case b:start = clock();F(t);cout时间消耗：clock() - startendl;break;case c:cout最大数是nendl;/times=F(n);start = clock();unsigned long int temp=1,temp1=0,temp2=1,temp3=temp;int i;for( i=1; temp=n; i+ )/temptemp)/当temp3temp时，则发现temp发生溢出，结束计算break;temp3=temp;temp2=temp1;temp1=temp;coutn是第i-1个Fibonacci数endl;cout时间消耗：clock() - startendl;break; int F(unsigned int uu)unsigned long int temp=0,temp1=0,temp2=1; int i;/if(uu=0|uu=1)/return uu;for( i=1; i=uu; i+ )temp = temp1 + temp2 ;coutnumberiistemp=uu)return i;temp2 = temp1 ;temp1 = temp ;return 0;long FF(unsigned int tt)/use di gui if( tt = 1 )return tt;elsereturn FF(tt-1) + FF(tt-2);int fib(int n) double gh5=sqrt(double)5); return (pow(1+gh5),n)-pow(1-gh5),n)/(pow(double)2,n)*gh5); 实验结果及分析1. 迭代算法2. 递归算法时间过长，没有等待程序运行完毕，故没截图。1. 利用公式法对第n项Fibonacci数求解时可能会得出错误结果。主要原因是由于double类型的精度还不够，所以程序算出来的结果会有误差，要把公式展开计算。2. 由于递归调用栈是一个费时的过程，通过递归法和迭代法的比较表明，虽然递归算法的代码更精简更有可读性，但是执行速度无法满足大数问题的求解。3. 在当前计算机的空间较大的情况下，在一些速度较慢的问题中，空间换时间是一个比较周全的策略。实验名称分治法在数值问题中的应用 矩阵相乘问题实验室9#206实验目的或要求1 实验题目设M1和M2是两个nn的矩阵，设计算法计算M1M2 的乘积。2 实验目的1）提高应用蛮力法设计算法的技能；2）深刻理解并掌握分治法的设计思想；3）理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对其进行改进，以提高算法的效率。 三实验要求1）设计并实现用BF方法求解矩阵相乘问题的算法；2）设计并实现用DAC方法求解矩阵相乘问题的算法；3）以上两种算法的输入既可以手动输入，也可以自动生成；4）对上述两个算法进行时间复杂性分析，并设计实验程序验证 分析结果；5）设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。实验原理（算法基本思想）定义：若 A=(aij), B=(bij) 是 nn的方阵，则对i,j=1,2,n，定义乘积 C=AB中的元素 cij 为： 1. 分块解法通常的做法是将矩阵进行分块相乘，如下图所示：2 Strassen解法分治法思想 将问题实例划分为同一问题的几个较小的实例。对这些较小实例求解，通常使用递归方法，但在问题规模足够小时，也会使用另一种算法。如果有必要，合并这些问题的解，以得到原始问题的解。求解矩阵相乘的DAC算法，使用了strassen算法。DAC（A，B，n） If n=2 使用7次乘法的方法求得解 Else Divide（A）/把A分成4块Divide（B）/把B分成4块调用7次strassen算法求得解的4块合并这4块得到解并返回 伪代码Serial_StrassenMultiply(A, B, C) T1 = A0 + A3; T2 = B0 + B3; StrassenMultiply(T1, T2, M1); T1 = A2 + A3; StrassenMultiply(T1, B0, M2); T1 = (B1 - B3); StrassenMultiply (A0, T1, M3); T1 = B2 - B0; StrassenMultiply(A3, T1, M4); T1 = A0 + A1; StrassenMultiply(T1, B3, M5); T1 = A2 A0; T2 = B0 + B1; StrassenMultiply(T1, T2, M6); T1 = A1 A3; T2 = B2 + B3; StrassenMultiply(T1, T2, M7); C0 = M1 + M4 - M5 + M7 C1 = M3 + M5 C2 = M2 + M4 C3 = M1 - M2 + M3 + M6程序代码#includestdafx.h#include Matrix.hvoid MatMenu()std:cout - std:endl -a:蛮力法- std:endl -c:退 出- std:endl - std:endl;void MATRIX_MULTIPLY(arrayPtr* &MatrixA,arrayPtr* &MatrixB,arrayPtr* &MatrixC,int matrixALine,int matrixARow,int matrixBRow)for (int indexX = 0; indexX matrixALine; indexX+)for (int indexY = 0; indexY matrixBRow; indexY+)MatrixCindexXindexY = MatrixAindexX0 * MatrixB0indexY;/初始化结果矩阵中的每一个元素/得到结果矩阵中的每一个元素的值for (int indexZ = 1; indexZ matrixARow; indexZ+)MatrixCindexXindexY += MatrixAindexXindexZ * MatrixBindexZindexY;/申请内存void MewMemory(arrayPtr* &matrix, int matrixLine, int matrixRow)matrix = new arrayPtrmatrixLine;for (int index = 0; index matrixLine; index+)matrixindex = new unsigned intmatrixRow;/初始化矩阵void InitMatrix(arrayPtr* &Matrix, int matrixLine, int matrixRow)for (int indexX = 0; indexX matrixLine; indexX+)for (int indexY = 0; indexY matrixRow; indexY+)MatrixindexXindexY = rand() % 5 + 1;/释放内存void FreeMemory(arrayPtr* &Matrix, int matrixLine, int matrixRow)if (Matrix)for (int index = 0; index matrixLine; index+)deletematrixRowMatrixindex;deleteMatrix;Matrix = NULL;/输出矩阵void OutputMatrix(const arrayPtr* Matrix, const int matrixLine, const int matrixRow)for (int indexX = 0; indexX matrixLine; indexX+)for (int indexY = 0; indexY matrixRow; indexY+)std:cout std:setw(6) MatrixindexXindexY;std:cout std:endl;void MATRIX_ADD(arrayPtr* &MatrixA, arrayPtr* &MatrixB, arrayPtr* &MatrixC, int matrixLine)for (int indexX = 0; indexX matrixLine; indexX+)for (int indexY = 0; indexY matrixLine; indexY+)MatrixCindexXindexY = MatrixAindexXindexY + MatrixBindexXindexY;void MATRIX_SUB(arrayPtr* &MatrixA, arrayPtr* &MatrixB, arrayPtr* &MatrixC, int matrixLine)for (int indexX = 0; indexX matrixLine; indexX+)for (int indexY = 0; indexY matrixLine; indexY+)MatrixCindexXindexY = MatrixAindexXindexY - MatrixBindexXindexY;void ProcessMatrix()int matrixALine = 0;/定义矩阵A的行数int matrixARow = 0;/定义矩阵A的列数int matrixBRow = 0;/定义矩阵B的列数arrayPtr* MatrixA;/定义矩阵AarrayPtr* MatrixB;/定义矩阵BarrayPtr* MatrixC;/定义矩阵Bclock_t startTime;clock_t endTime;char choice;bool flag = true;dostd:cout matrixALine; while (matrixALine = 0);dostd:cout matrixARow; while (matrixARow = 0);dostd:cout matrixBRow; while (matrixBRow = 0);MewMemory(MatrixA, matrixALine, matrixARow);MewMemory(MatrixB, matrixARow, matrixBRow);MewMemory(MatrixC, matrixALine, matrixBRow);InitMatrix(MatrixA, matrixALine, matrixARow);InitMatrix(MatrixB, matrixARow, matrixBRow);MatMenu();while (flag)std:cout choice;switch (choice)case A:case a:std:cout 矩阵MatrixA为： std:endl;OutputMatrix(MatrixA, matrixALine, matrixARow);std:cout 矩阵MatrixB为： std:endl;OutputMatrix(MatrixB, matrixARow, matrixBRow);startTime = clock();MATRIX_MULTIPLY(MatrixA, MatrixB, MatrixC, matrixALine, matrixARow, matrixBRow);endTime = clock();std:cout 蛮力法所用时间是: (double)(endTime - startTime) / CLOCKS_PER_SEC 秒 std:endl;std:cout 矩阵MatrixC = MatrixA*MatrixB为： std:endl;OutputMatrix(MatrixC, matrixALine, matrixBRow);break;case B:case b:break;case C:case c:flag = false;break;/释放申请的空间FreeMemory(MatrixA, matrixALine, matrixARow);FreeMemory(MatrixB, matrixARow, matrixBRow);FreeMemory(MatrixC, matrixALine, matrixBRow);实验结果及分析时间复杂度1.分块相乘总共用了8次乘法，因而需要 (nlog28) 即 (n3) 的时间复杂度。2.在求解M1，M2，M3，M4，M5，M6，M7时需要使用7次矩阵乘法，其他都是矩阵加法和减法。因此时间复杂度下降为 O(nlog27)=O(n2.807) 。有得必有失，Strassen演算法的数值稳定性较差。实验名称减治法在组合问题中的应用8枚硬币问题 实验室9#206实验目的或要求2 实验目的1）深刻理解并掌握减治法的设计思想并理解它与分治法的区别；2）提高应用减治法设计算法的技能。3）理解这样一个观点：建立正角的模型对于问题的求解是非常重要的。二实验要求1）设计减治算法实现8枚硬币问题；2）设计实验程序，考察用减治技术设计的算法是否高效；3）扩展算法，使之能处理n枚硬币中有一枚假币的问题。实验原理（算法基本思想）减治法原理 假币问题程序代码#include stdafx.h#include iostream#include using namespace std;int Sum(int coin_Number, int index, int number)int sum = 0;for (int i = index; i number; i+)sum = sum + coin_Numberi;if (number = index)sum = coin_Numberindex;return sum;int Count(int coin_Number, int sum1, int sum2, int i, int j)if (sum1 sum2)i = (i + j) / 2;if (j - i) % 2 = 1)j-;sum1 = Sum(coin_Number, i, (i + j) / 2);sum2 = Sum(coin_Number, (i + j) / 2, j);elsereturn j;if (i = j)return j;Count(coin_Number, sum1, sum2, i, j);void ProcessFake()string reply;doint number;cout number;if (number 2)cout 输入的硬币数应当大于1，请重新输入硬币数：; while (number 2);typedef int* Int;Int coin_Number;coin_Number = new intnumber;cout 请输入硬币的重量：;for (int count = 0; count coin_Numbercount;if (coin_Numbercount 1)cout 输入的硬币重量应大于0，请重新输入：;count-;int sum1, sum2, i = 0, j = number;if (j % 2 = 1)j-;sum1 = Sum(coin_Number, i, j / 2);sum2 = Sum(coin_Number, j / 2, j);j = Count(coin_Number, sum1, sum2, i, j);if (j number)cout 假硬币是第 j + 1 枚。其重量为 coin_Numberj 克。 endl;cout reply;cout endl endl; while (reply = Y | reply = y);实验结果及分析 实验结果正确，能够在N枚硬币问题条件下准确查找假币在什么位置。通过硬币问题，让我更加理解了减治法的使用，让我对减治法有了更深的理解，对于以后的编程思想有了更深的研究实验名称变治法在排序问题中的应用堆排序 实验室9#204实验目的或要求3 实验目的1）深刻理解并掌握变治法的设计思想；2）掌握堆的概念以及如何用变治法把任意给定的一组数据改变成堆；3）提高应用变治法设计算法的技能。 二实验要求1）设计与实现堆排序算法；2）待排序的数据可以手工输入(通常规模比较小，10个数据左右），用以检测程序的正确性；也可以计算机随机生成（通常规模比较大，15003000个数据左右），用以检验(用计数法)堆排序算法的时间效率。实验原理（算法基本思想）1)将初始待排序关键字序列(R1,R2.Rn)构建成大顶堆，此堆为初始的无须区； 2)将堆顶元素R1与最后一个元素Rn交换，此时得到新的无序区(R1,R2,.Rn-1)和新的有序区(Rn),且满足R1,2.n-1= 1; i-)Swap(num, 0, i);/ 交换 size-;/ 每交换一次让规模减少一次 PercolateDown(num, 0, size);/ 将新的首元素下滤操作PrintHeap( Sort Heap:, num, iLength);/ 建堆方法，只需线性时间建好 void BuildHeap(int num, int size) int i;for (i = size / 2 - 1; i = 0; i-)/从最后一个非叶子节点开始，将每个父节点都调整为最小堆 PercolateDown(num, i, size);/ 进行下滤操作PrintHeap(Build heap:, num, size);/ 对该数进行下滤操作，直到该数比左右节点都小就停止下滤 void PercolateDown(int num, int index, int size) int min;/ 设置最小指向下标 while (index * 2 + 1size)/ 如果该数有左节点，则假设左节点最小 min = index * 2 + 1;/ 获取左节点的下标 if (index * 2 + 2 numindex * 2 + 2)/ 就和左节点分出最小者 min = index * 2 + 2;/ 此时右节点更小，则更新min的指向下标 / 此时进行该数和最小者进行比较， if (numi