算法设计与分析 (2).doc

算法设计与分析 实验报告 实验一1-1问题描述：斐波那契矩阵算法1-2 问题分析： 斐波那契数列：1，1,3,5,8，13，.从第二项之后往后每一项都是前两项的和。通过对矩阵的观察可以发现，a22=1,1,10的n次方就是斐波那契数列的第n项。 1-3策略选择 矩阵相乘的方法1-4算法模型 f(n)=1,1,1,0n1-5时间和空间复杂度分析 时间复杂度：O(n) 空间复杂度：O(1)1-6算法描述（流程图）1.7算法实现#includeusing namespace std;int sou15001;int a22;void init() int ta11, ta12, ta21, ta22; int a11, a12, a21, a22; int b11, b12, b22, b21; a11 = a12 = a21 = 1; b11 = b12 = b21 = 1; a22 = b22 = 0; for(int i=1;i=15000;i+) ta11 = a11,ta12=a12,ta21=a21,ta22=a22; a11 = (ta11*b11 + ta12*b21); a12 = (ta11*b12 + ta12*b22); a21 = (ta21*b11 + ta22*b21); a22 = (ta21*b12 + ta22*b22); soui = a12; int main() int n; init();cout请输入斐波那契数的位置：n; while(n!=-1) if(n=0) cout 0 endl; if(n=1) cout该位置斐波那契数是:; cout 1 endl;coutendl; else n %= 15000; cout该位置斐波那契数是:; cout soun-1 endl; cout请输入斐波那契数的位置：n; return 0;1.8测试与说明1.9总结 斐波那契数列可以用很多种方法实现，矩阵实现只是其中一种，通告实验，我更了解了斐波那契数，也提高了自己的算法分析与编程能力。实验二 高斯-赛德尔算法1. 雅可比迭代法设线性方程组 (1)的系数矩阵A可逆且主对角元素均不为零,令 并将A分解成 (2)从而(1)可写成 令 其中. (3)以为迭代矩阵的迭代法(公式) (4)称为雅可比(Jacobi)迭代法(公式),用向量的分量来表示,(4)为 (5)其中为初始向量.由此看出,雅可比迭代法公式简单,每迭代一次只需计算一次矩阵和向量的乘法.在电算时需要两组存储单元,以存放及.2.高斯塞德尔迭代法由雅可比迭代公式可知,在迭代的每一步计算过程中是用的全部分量来计算的所有分量,显然在计算第i个分量时,已经计算出的最新分量没有被利用，从直观上看,最新计算出的分量可能比旧的分量要好些.因此，对这些最新计算出来的第次近似的分量加以利用,就得到所谓解方程组的高斯塞德（Gauss-Seidel）迭代法.把矩阵A分解成 (6) 其中,分别为的主对角元除外的下三角和上三角部分,于是,方程组(1)便可以写成 即其中 (7)以为迭代矩阵构成的迭代法(公式) (8)称为高斯塞德尔迭代法(公式),用向量表示的形式为 (9)由此看出,高斯塞德尔迭代法的一个明显的优点是,在计算时,只需一组存储单元(计算出后不再使用,所以用冲掉,以便存放近似解.问题描述：用高斯-赛德尔迭代法解线性方程组时间复杂度：空间复杂度：算法描述（流程图）：算法实现：#include#includeusing namespace std;int k=0;float r;float norm=1000000.0,e,b100=0;int main()int m,n,a100100,c100,i,j;coutm;coutn;cout请依次输入常数：;for(i=0;ici;coute;cout请输入待解方程组的系数矩阵:endl;for(i=0;im;i+)for(j=0;jaij;while(norme|norm-e)k+;norm=0;for(i=0;in;i+)r=bi;bi=0;for(j=0;jm;j+)if(j!=i) bi=bi+aij*bj; bi=(ci-bi)/aii; cout该方程组的解为：endl;for(i=0;in;i+)coutXi=biendl;return 0;总结： 高斯-赛德尔迭代法比雅可比法收敛速度快，但它是发散的，使用这种方法可以很快解出方程组的解，精确度也比较高。 实验三 3-1问题描述：求最小子段和3-2算法分析利用3个for的嵌套（实现从第1个数开始计算子段长度为1，2，3n的子段和，同理计算出第2个数开始的长度为1，2，3n-1的子段和，依次类推到第n个数开始计算的长为1的子段和）和一个if（用来比较大小）,将其所有子段的和计算出来并将最小子段和赋值给minSum。3-3策略选择：穷举3-4算法模型：蛮力法3-5时间复杂度为O(n3)3-6算法描述（流程图）：3-7算法实现：#include using namespace std;int getminSum1(int a, int n)int minSum =10000 ;int i,j,k;for (i = 0; i n; +i) for (j = i; j n; +j) int tmp = 0; for (k = i; k =j; +k) tmp=tmp+ak; if ( tmp minSum ) minSum = tmp; return minSum;int main()int a100=0,i,n,minSum;cout请输入数列个数：n;cout请输入数列：endl;for(i=0;iai;minSum=getminSum1(a,n);cout最小子段和为：endl;coutminSumendl; 测试与说明二算法分析：1）、划分：按照平衡子问题的原则，将序列划分成长度相同的两个字序列和2）、求解子问题：对于划分阶段的情况分别的两段可用递归求解，如果最大子段和在两端之间需要分别计算s1，s2，则s1+s2为最小子段和。若然只在左边或右边，可以直接求出3）、合并：比较在划分阶段的3种情况下的最小子段和，取三者之中的较小者为原问题的解策略选择：分而治之算法模型：二分法时间复杂度为O(nlogn)算法描述（流程图）：算法实现：#includeusing namespace std;int min_sum(int a,int n)return(min_sub_sum(a,1,n);int min_sub_sum(int a,int left,int right)int center,i,left_sum,right_sum,s1,s2,lefts,rights;if(left=right)return(aleft);elsecenter=(left+right)/2;left_sum=min_sub_sum(a,left,center);right_sum=min_sub_sum(a,center+1,right);s1=acenter;lefts=0;for(i=center;i=left;i=i-1)lefts=lefts+ai;if(leftss1) s1=lefts;s2=acenter+1;rights=0;for(i=center+1;i=right;i=i+1)rights=rights+ai;if(rightsleft_sum & right_sumleft_sum) return(left_sum);if(s1+s2right_sum) return(right_sum);return(s1+s2);void main()int n,i,sum;int a101;cout请输入数列个数：n;cout请输入数列：endl;for(i=1;iai;sum=min_sum(a,n);cout最小子段和是：sumendl; 测试与说明3. 动态规划算法分析：关键是确定动态规划函数,算法实现很简单算法模型：动态规划时间复杂度为O(n)算法描述（流程图）：算法实现：void MinSum(int n,int a) int minsum=10000; int b=0; for(int i=1;i=n;i+) if(b0)b+=ai; else b=ai; if(bminsum)mi