算法实验报告算法实验报告引言：算法是计算机科学的核心内容之一，它是解决问题的方法和步骤的描述。
算法的设计和分析是计算机科学与工程中的重要研究方向之一。
本实验旨在通过对算法的实际应用和实验验证，深入理解算法的性能和效果。
实验一：排序算法的比较在本实验中，我们将比较三种常见的排序算法：冒泡排序、插入排序和快速排序。
我们将通过对不同规模的随机数组进行排序，并记录每种算法所需的时间和比较次数，以评估它们的性能。
实验结果显示，快速排序是最快的排序算法，其时间复杂度为O(nlogn)，比较次数也相对较少。
插入排序的时间复杂度为O(n^2)，比较次数较多，但对于小规模的数组排序效果较好。
而冒泡排序的时间复杂度也为O(n^2)，但比较次数更多，效率相对较低。
实验二：图的最短路径算法在图的最短路径问题中，我们将比较Dijkstra算法和Floyd-Warshall算法的效率和准确性。
我们将使用一个带权有向图，并计算从一个顶点到其他所有顶点的最短路径。
实验结果表明，Dijkstra算法适用于单源最短路径问题，其时间复杂度为O(V^2)，其中V为顶点数。
而Floyd-Warshall算法适用于多源最短路径问题，其时间复杂度为O(V^3)。
两种算法在准确性上没有明显差异，但在处理大规模图时，Floyd-Warshall算法的效率较低。
实验三：动态规划算法动态规划是一种通过将问题分解成子问题并记录子问题的解来解决复杂问题的方法。
在本实验中，我们将比较两种动态规划算法：0-1背包问题和最长公共子序列问题。
实验结果显示，0-1背包问题的动态规划算法可以有效地找到最优解，其时间复杂度为O(nW)，其中n为物品个数，W为背包容量。
最长公共子序列问题的动态规划算法可以找到两个序列的最长公共子序列，其时间复杂度为O(mn)，其中m和n分别为两个序列的长度。
结论：通过本次实验，我们对不同算法的性能和效果有了更深入的了解。
排序算法中，快速排序是最快且效率最高的；在图的最短路径问题中，Dijkstra算法和Floyd-Warshall算法分别适用于不同的场景；动态规划算法可以解决复杂的问题，并找到最优解。
实验一：完成多项式的相加运算（验证性、4学时）一、实验目的完成多项式的相加、相乘运算。
（1）掌握线性表的插入、删除、查找等基本操作设计与实现（2）学习利用线性表提供的接口去求解实际问题（3）熟悉线性表的的存储方法二、实验内容设计一个一元多项式的简单计算程序，其基本功能有：（1）输入并建立多项式；（2）输出多项式；（3）多项式的相加运算。
利用单链表实现。
三、算法描述及实验步骤1描述1、创建两个单链表A、B，分别调用CreatePolyn（）；2、输出多项式，分别调用PrintPolyn（）；3、多项式相加运算AddPolyn（）。
2算法流程图4 65inputA-B inputA-B inputA-B end3代码(注释)#include<stdio.h>#include<malloc.h>#include<math.h>typedef struct Polynomial{float coef;//系数变量int exp;//指数变量struct Polynomial *next;//定义next指针}*Polyn,Polynomial; //Polyn为结点指针类型void Insert(Polyn p,Polyn h) //插入新的结点p{if(p->coef==0) free(p); //系数为0的话释放结点else{Polyn q1,q2;q1=h;q2=h->next;while(q2&&p->exp<q2->exp) //查找插入位置{q1=q2;q2=q2->next;}if(q2&&p->exp==q2->exp) //将指数相同相合并{q2->coef+=p->coef;free(p);if(!q2->coef) //系数为0的话释放结点{q1->next=q2->next;free(q2);}}else //指数为新时将结点插入{p->next=q2;q1->next=p;}}}//Insertint f(float x)//判断输入是否为整形{float a;a=x-(long int)x;if(a==0&&x==fabs(x))return 1;elsereturn 0;}Polyn CreatePolyn(Polyn head,int m) //建立一个头指针为head、项数为m的一元多项式{int i;Polyn p;p=head=(Polyn)malloc(sizeof(struct Polynomial));head->next=NULL;for(i=0;i<m;i++){p=(Polyn)malloc(sizeof(struct Polynomial));//建立新结点以接收数据printf("please input NO.%d coef and exp:",i+1);scanf("%f %d",&p->coef,&p->exp);while(!f(p->coef)&&!f(p->exp)){printf("输入有错，请重新输入: ");scanf("%f %d",&p->coef,&p->exp);}Insert(p,head); //调用Insert函数插入结点}return head;}//CreatePolynvoid DestroyPolyn(Polyn p) //销毁多项式p{Polyn q1,q2;q1=p->next;q2=q1->next;while(q1->next){free(q1);q1=q2;//指针后移q2=q2->next;}}void PrintPolyn(Polyn P)//输出多项式{Polyn q=P->next;int flag=1; //项数计数器if(!q) //若多项式为空，输出0{putchar('0');printf("\n");return;}while (q){if(q->coef>0&&flag!=1) putchar('+'); //系数大于0且不是第一项if(q->coef!=1&&q->coef!=-1) //系数非1或-1的普通情况{printf("%g",q->coef);if(q->exp==1) putchar('X');else if(q->exp) printf("X^%d",q->exp);}else{if(q->coef==1){if(!q->exp) putchar('1');else if(q->exp==1) putchar('X');else printf("X^%d",q->exp);}if(q->coef==-1){if(!q->exp) printf("-1");else if(q->exp==1) printf("-X");else printf("-X^%d",q->exp);}}q=q->next;flag++;}//whileprintf("\n");}//PrintPolynint compare(Polyn a,Polyn b){if(a&&b){if(!b||a->exp>b->exp) return 1;else if(!a||a->exp<b->exp) return -1;else return 0;}else if(!a&&b) return -1;//A多项式已空，但B多项式非空else return 1;//B多项式已空，但A多项式非空}//comparePolyn AddPolyn(Polyn pa,Polyn pb)//求解并建立多项式A+B，返回其头指针{Polyn qa=pa->next;Polyn qb=pb->next;Polyn headc,hc,qc;hc=(Polyn)malloc(sizeof(struct Polynomial)); //建立头结点hc->next=NULL;headc=hc;while(qa||qb){qc=(Polyn)malloc(sizeof(struct Polynomial));switch(compare(qa,qb)) //功能选择{ case 1:{qc->coef=qa->coef;qc->exp=qa->exp;qa=qa->next;break;}case 0:{qc->coef=qa->coef+qb->coef;qc->exp=qa->exp;qa=qa->next;qb=qb->next;break;}case -1:{qc->coef=qb->coef;qc->exp=qb->exp;qb=qb->next;break;}}//switchif(qc->coef!=0){qc->next=hc->next;hc->next=qc;hc=qc;}else free(qc);//当相加系数为0时，释放该结点}//whilereturn headc;}//AddPolynPolyn SubtractPolyn(Polyn pa,Polyn pb){//求解并建立多项式A-B，返回其头指针Polyn h=pb;Polyn p=pb->next;Polyn pd;while(p){ //将pb的系数取反p->coef*=-1;p=p->next;}pd=AddPolyn(pa,h);for(p=h->next;p;p=p->next) //恢复pb的系数p->coef*=-1;return pd;}//SubtractPolynPolyn MultiplyPolyn(Polyn pa,Polyn pb){//求解并建立多项式A*B，返回其头指针Polyn hf,pf;Polyn qa=pa->next;Polyn qb=pb->next;hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点hf->next=NULL;for(;qa;qa=qa->next){for(qb=pb->next;qb;qb=qb->next){pf=(Polyn)malloc(sizeof(struct Polynomial));pf->coef=qa->coef*qb->coef;pf->exp=qa->exp+qb->exp;Insert(pf,hf);//调用Insert函数以合并指数相同的项}}return hf;}//MultiplyPolynvoid DevicePolyn(Polyn pa,Polyn pb){//求解并建立多项式A/B，返回其头指针Polyn hf,pf,af,temp1,temp2,q;Polyn qa=pa->next;Polyn qb=pb->next;hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点,存储商hf->next=NULL;pf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点，存储余数pf->next=NULL;temp1=(Polyn)malloc(sizeof(struct Polynomial));temp1->next=NULL;temp2=(Polyn)malloc(sizeof(struct Polynomial));temp2->next=NULL;temp1=AddPolyn(temp1,pa);while(qa!=NULL&&qa->exp>=qb->exp){temp2->next=(Polyn)malloc(sizeof(struct Polynomial));temp2->next->coef=(qa->coef)/(qb->coef);temp2->next->exp=(qa->exp)-(qb->exp);Insert(temp2->next,hf);pa=SubtractPolyn(pa,MultiplyPolyn(pb,temp2));qa=pa->next;temp2->next=NULL;}pf=SubtractPolyn(temp1,MultiplyPolyn(hf,pb));pb=temp1;printf("the quotient is :");PrintPolyn(hf);printf("the remainder is :");PrintPolyn(pf);}//DevicePolynint main(){int m,n,flag=0;float x;Polyn pa=0,pb=0,pc,pd,pe,pf;//定义各式的头指针，pa与pb在使用前付初值NULL printf("please input A number:");scanf("%d",&m);pa=CreatePolyn(pa,m);//建立多项式Aprintf("please input B number:");scanf("%d",&n);pb=CreatePolyn(pb,n);//建立多项式B//输出菜单printf("**********************************************\n");printf("choise：\n\t1.Output A and B\n\t2.CreatePolyn A+B\n");printf("\t3.CreatePolyn A-B\n\t4.CreatePolyn A*B\n");printf("\t5.CreatePolynA/B\n\t6.Return\n**********************************************\n");for(;;flag=0){printf("choise");scanf("%d",&flag);if(flag==1){printf("多项式A：");PrintPolyn(pa);printf("多项式B：");PrintPolyn(pb);continue;}if(flag==2){pc=AddPolyn(pa,pb);printf("多项式A+B：");PrintPolyn(pc);DestroyPolyn(pc);continue;}if(flag==3){pd=SubtractPolyn(pa,pb);printf("多项式A-B：");PrintPolyn(pd);DestroyPolyn(pd);continue;}if(flag==4){pf=MultiplyPolyn(pa,pb);printf("多项式a*b：");PrintPolyn(pf);DestroyPolyn(pf);continue;}if(flag==5){DevicePolyn(pa,pb);continue;}if(flag==6) break;if(flag<1||flag>6) printf("Error\n");continue;}//forDestroyPolyn(pa);DestroyPolyn(pb);return 0;}一、调试过程一次调试二次调试二、实验结果测试数据（1）多项式A:3x^4+11x^3+21x^2多项式B:2x^5+11x^4+12x^3+7x实验结果（1）多项式A+B=2x^5+14x^4+23x^3+21x^2+7x多项式A-B=-2x^5-8^4-x^3+21x^2-7x多项式A*B=6x^9+55x^8+199x^7+363x^6+273x^5+77x^4+147x^3多项式A/B=0实验截图（1）测试数据（2）：多项式A:2x^3+5x^-3多项式B:9x^2+6x^-2+11x^-3实验结果（2）：多项式A+B=2x^3+9x^2+6x^-2+16x^-3多项式A-B=2x^3-9x^2-6x^(-2)=16x^(-3)多项式A*B=18x^5+12x+22+45x^(-1)+30x^(-5)+55x^(-6)多项式A/B=0.222222x实验截图（2）：测试数据（3）多项式A:-x^7+3x^5多项式B:x^7-4x6%+7x^3实验结果（3）多项式A+B=-x^5+7x^3多项式A-B=-2x^7+7x^5-7x^3多项式A*B=-x^14+7x^12-19x^10+21x^8多项式A/B=-1实验截图（3）：三、总结1.在熟悉VC6.0环境的同时，对单链表的存储格式有了深刻的理解；2.复习C++语法的同时，对刚学的线性表进行综合性理解和表达，与之前所学融合。
实验一：误差传播与算法稳定性一：实验内容考虑一个简单由积分定义的序列： 显然0,1,2,.n I n >=L 当n=1时，11101/x I xe dx e -==⎰。
而对于2n ≥时，利用分步积分易得：另一方面，我们有1111/(1)n x n n I x e dx x dx n -=≤=+⎰⎰。
由以上递推关系，我们可以得到计算序列{}n I 的两种方法。
(Ⅰ) 11/I e =，111/,n 1,2,3,..n n I I -=-=⋯ (Ⅱ) 0N E =, 11,,1,2,,3,2nn E E n N N N n--==--L 二：实验要求及实验结果（1） 分别用算法(Ⅰ)、(Ⅱ)计算，并且在计算机中分别采用5位、6位和7位有效数字，请判断哪种算法能给出更精确的结果。
实验过程：ⅰ）编写MA TLAB 程序如下：a= input ('请输入有效位数a:'); %设定有效数字位数 syms n InIn=vpa((exp(-1)),a) %vpa 设定结果有效数字 for n=2:10; In=vpa((1-n*In),a) %循环计算End运行文件，输入有效数字a 分别为5位、6位和7位，得到运算结果如下表格所示：ⅱ）编写MA TLAB 程序如下： function In=NO1Bb= input ('请输入有效位数b:'); syms n EnEn=vpa(0,b) for n=10:-1:2;En=vpa(((1-En)/n),b) End由以上两种算法所得到的数据可知，对算法11/I e =，111/,n 1,2,3,..n n I I -=-=⋯从8I 开始，结果变得无规律，各个有效位数计算结果都不一样，这是因为随着计算的n 增大，误差会越来越大。
而对0N E =, 11,,1,2,,3,2nn E E n N N N n--==--L ，5位、6位和7位结果相近，随着有效数字位数的增加，结果越来越精确。
