算法 实验1

实验1程序的灵魂――算法1．实验目的（1）掌握算法的概念，会设计简单的算法。

（2）掌握掌握用流程图来表达算法的方法。

（3）熟悉用伪代码来表示算法的方法。

（4）掌握用Word来画流程图的方法。

（5）进一步熟悉C程序的编辑、编译、连接和运行的过程。

2．实验内容和步骤（1）用传统流程图求解以下问题的算法：有两个瓶子A和B，分别盛放醋和酱油，要求将它们互换（即A瓶原来盛醋，现在盛酱油，B瓶则相反）。

（第二章习题2.4（1））解：显然，如果只有两个瓶子，肯定不能完成此任务，必须有一个空瓶C作为过渡。

即先将A瓶中的醋倒给C瓶，再将B瓶中的酱油倒给A瓶，再将C瓶中的醋倒给B瓶，即可实现题目要求。

本实验学习如何用Word来画流程图①打开Word，选择菜单工具－＞自定义，打开对话框，如图所示，选中绘图，则在窗口下方出现绘图工具栏。

自选图形－＞流程图－＞终止，如图所示②选择绘图工具栏上的③在Word中的白纸上拖曳鼠标画出一个起止框矩形。

选中此图形点击鼠标右键，可向其中添加文字，④选择绘图工具栏上的自选图形－＞流程图－＞过程，并在Word中的白纸上拖曳鼠标画出一个过程⑤选择绘图工具栏上的箭头，然后在以上两个框之间自向而下拖动，则画出一个箭头，选择此箭头，调整其位置，并用鼠标右键点击之，设置其属性。

(在画图和调整图形位置时分别按住键盘上的shif 和ctrl 看会发生什么情况)⑦试考虑，将以上流程图中的第三个框和第四个框互换位置可以吗？为什么。

（2）用流程图求解问题以下问题：有3个数a 、b 、c ，要求按大小顺序把它们输出。

（3）用流程图求解以下问题求1＋2＋3＋4＋…….＋100的和。

并编程实现。

（4）用流程图求解以下问题：判定某一年是否为闰年。

并编程实现。

（2）（3）#include<stdio.h>void main(){int sum=0,i;for(i=1;i<=100;i++)sum+=i;printf(“1+2+3+……+100=%d\n”,sum); }（4）。

实验一：循环与递归算法的应用【实验目的】1．掌握循环、递归算法的基本思想、技巧和效率分析方法。

2．熟练掌握循环和递归的设计要点，清楚循环和递归的异同。

3．学会利用循环、递归算法解决实际问题。

【实验内容】1. 问题描述：（1）题目一：打印图形编程打印如下图所示的N阶方阵。

1 3 6 10 152 5 9 144 8 137 1211（2）题目二：计算前n项和根据参数n，计算1+2+……+n。

要求：用循环和递归分别实现（3）题目三：回文判断判断s字符串是否为“回文”的递归程序。

2. 数据输入：个人设定，由键盘输入。

3. 要求：（1）上述题目一、二必做，题目三选做；（2）独立完成实验及实验报告。

【具体实现过程】题目一：【算法分析】通过两个for循环控制数字的输出。

【实现代码】#include<stdio.h>int main(){int i,j,k,n,l,middle,temp;printf("请输入n的大小\n");scanf("%d",&n);k = 1;temp = 0;middle = 0;for(i=1;i<=n;i++){middle = i+1;k += temp;printf("%d ",k);l = k;for(j=n;j>0;j--){if(j==1)printf("\n");else{l += middle;printf("%d ",l);middle++;}}temp++;n--;}return 0;}题目二：【算法分析】定义一个sum函数求和,把求出的新值赋给sum,最后求得的值即为前n项和。

【实现代码】递归#include "stdio.h"int fun(int num){int sum;if( num==1)sum=1;elsesum=num+fun(num-1);return sum;}void main(){int n,s;printf("n=");scanf("%d",&n);s=fun(n);printf("s=%d\n",s);}循环#include<stdio.h>void main(){int sum=0;int n,i=1;printf("n=");scanf("%d",&n);while(i<=n){sum+=i*i;i++;}printf("%d",sum);}【实验心得】通过本实验掌握循环、递归算法的基本思想、技巧和效率分析方法。

精品文档可修改昆明理工大学信息工程与自动化学院学生实验报告（ 2011 — 2012 学年第 1 学期）课程名称：算法分析与设计开课实验室：信自楼机房444 2011年10月12日一、上机目的及内容上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。

上机内容求两个自然数m和n的最大公约数。

二、实验原理及基本技术路线图（方框原理图或程序流程图）实验原理（1）至少设计出三个版本的求最大公约数算法；（2）对所设计的算法采用大O符号进行时间复杂性分析；（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间；（4）通过分析对比，得出自己的结论。

流程图三、所用仪器、材料（设备名称、型号、规格等或使用软件）设备：1台PC及VISUAL C++6.0软件。

四、实验方法、步骤（或：程序代码或操作过程）源程序：#include<stdio.h>#include<time.h>#include<stdlib.h>int max(int m,int n){int r;if(m>n)r=n;elser=m;return r;}void Menu(){int a;void algorithmone();void algorithmtwo();void algorithmthree();printf("请选择算法:\n");printf("1.算法一\n");printf("2.算法二\n");printf("3.算法三\n");scanf("%d",&a);getchar();switch(a){case 1:algorithmone();break;case 2:algorithmtwo();break;case 3:algorithmthree();break;default:printf("请输入1,2,3中的一个!\n");}}void algorithmone() //算法一{clock_t start,finish;int m,n,r;char key;printf("求两个数的最大公约数，请输入这两个数：");scanf("%d %d",&m,&n);getchar();start=clock();r=max(m,n);while(r>0){if(m%r==0){if(n%r==0){printf("算法一求出的最大公约数为%d\n",r);finish=clock();break;}elser=r-1;}elser=r-1;}printf("算法一所需的时间是:%ld秒\n",(finish-start));printf("是否返回主菜单?(y/n):");key=getchar();switch(key){case 'y':Menu();break;case 'Y':Menu();break;case 'n':break;case 'N':break;default:printf("error!\n");}}void algorithmtwo() //算法二{clock_t start,finish;int m,n,r;char key;printf("求两个数的最大公约数，请输入这两个数：");scanf("%d %d",&m,&n);start=clock();while((r=m%n)!=0){m=n;n=r;r=m%n;if(r==0){printf("算法二求出的最大公约数为%d\n",n);finish=clock();break;}}printf("算法二所需的时间是:%ld秒\n",(finish-start));getchar();printf("是否返回主菜单?(y/n):");key=getchar();switch(key){case 'y':Menu();break;case 'Y':Menu();break;case 'n':break;case 'N':break;default:printf("error!\n");}}void commonzhishu(int arraym[],int arrayn[]) //提取公共质数{int i,j,k=0,common[3],d=0;for(i=0;i<3;i++)for(j=0;j<3;j++)if(arraym[i]==arrayn[j]){common[k]=arraym[i];k=k+1;}for(k=0;k<3;k++)for(d=k+1;d<3;d++)if(common[k]==common[d])common[d]=1;printf("算法三结果%d\n",common[0]*common[1]*common[2]);}void algorithmthree() //算法三{clock_t start,finish;int m,n,mr,nr,i;float count;char key;mr=2;nr=2;printf("求两个数的最大公约数，请输入这两个数：");scanf("%d %d",&m,&n);int arraym[3],arrayn[3];i=0;start=clock();while(m!=1) //将两数分解{if((count=(float)(m%mr))==0.0){arraym[i]=mr;i++;m=m/mr;}elsemr++;}for(i=0;i<3;i++)printf("%d ",arraym[i]);printf("\n");i=0;while(n!=1){if((count=(float)(n%nr))==0.0){arrayn[i]=nr;i++;n=n/nr;}elsenr++;}for(i=0;i<3;i++)printf("%d ",arrayn[i]);printf("\n");commonzhishu(arraym,arrayn);finish=clock();printf("算法三所需的时间是:%ld秒\n",(finish-start));getchar();printf("是否返回主菜单?(y/n):");key=getchar();switch(key){case 'y':Menu();break;case 'Y':Menu();break;case 'n':break;case 'N':break;default:printf("error!\n");}}void main(){int a;printf("请选择算法:\n");printf("1.算法一\n");printf("2.算法二\n");printf("3.算法三\n");scanf("%d",&a);getchar();switch(a){case 1:algorithmone();break;case 2:algorithmtwo();break;case 3:algorithmthree();break;default:printf("请输入1,2,3中的一个!\n");}}五、实验过程原始记录( 测试数据、图表、计算等)六、实验结果、分析和结论（误差分析与数据处理、成果总结等。

实验1 金刚石图案算法一、实验目的在圆的基础上绘制金刚石图案。

金刚石图案是一个二维图案，仅使用二维坐标（x,y）就可以绘制：利用数学函数sin（）及cos（）函数计算点坐标，利用MoveTo（）及LineTo （）函数将顶点连接起来，验证算法的正确性，并修改程序，加深对VC++绘图的理解。

二、实验任务将半径为r的圆周n等份，然后用直线将各等分点两两相连，形成的图案称为“金刚石”图案，并编程实现。

三、实验内容1.建立工程----“TestDiamond”。

2. 编写Diamond（）函数：（1）指定n、及r的值；（2）根据等分点数，计算金刚石图案的等分角“theta”，theta=2*PI/n；（3）将等分点坐标存储在数组中；（4）设计二重循环，将各等分点两两相连。

3.OnDraw（）中调用Diamond（）函数。

4.注意：（1）用到sin（）等数学函数，所以在CtestDiamondView.cpp中添加“#include "math.h"”语句；（2）为了简单起见（没有使用面向对象的方法定义“点”类，没有使用动态内存分配），初始化存储点坐标的数组x[]和y[]为固定大小，即x[i]和y[i]共同表示第i个点的x和y坐标。

5.代码（1）Diamond（）函数void CTestDiamondView::Diamond(CDC *pDC, int n, double r){//n为等分点的个数，r为圆的半径double Theta;//thta为圆的等分角double PI=3.1415926;double x[40];double y[40];int MaxX=700;int MaxY=700;//圆心设定为（350 ，350）Theta=2*PI/n;for(int i=0;i<n;i++) //等分圆{x[i]=r*cos(i*Theta)+MaxX/2;y[i]=r*sin(i*Theta)+MaxY/2;}for(i=0;i<=n-2;i++) //二次循环，点点连接{for(int j=i+1;j<=n-1;j++){pDC->MoveTo(int(x[i]),int(y[i]));pDC->LineTo(int(x[j]),int(y[j]));}}}（2）OnDraw（）函数void CTestDiamondView::OnDraw(CDC* pDC){CTestDiamondDoc* pDoc = GetDocument();ASSERT_V ALID(pDoc);// TODO: add draw code for native data hereCPen PenBlue(PS_SOLID,1,RGB(0,0,255));//定义蓝色笔pDC->SelectObject(&PenBlue);Diamond(pDC,31, 300 );}。

实验一：搜索算法问题求解智能1402 201408070221 李帅玲目录实验一：搜索算法问题求解 (1)一、实验目的 (2)二、实验的硬件、软件平台 (2)三、实验内容及步骤 (2)四、思考题 (2)五．实验报告 (3)（一）算法的基本原理 (3)（二）算法的实验结果 (5)（三）实验分析和思考题 (6)（四）实验源代码 (7)一、实验目的1.了解一致代价搜索算法的基本原理；2.能够运用计算机语言实现一致代价搜索算法；3.应用搜索算法解决罗马尼亚问题；4.能够通过实验分析了解算法性能的优劣；二、实验的硬件、软件平台硬件：计算机软件：操作系统；WINDOWS 2000应用软件：C,Java或者MATLAB三、实验内容及步骤图一：罗马尼亚地图1、根据图一创建搜索树，以Arad为初始状态，Bucharest为目标状态；2、实现一致代价搜索的图搜索算法并记录搜索路径。

四、思考题1、根据实验结果分析一致代价搜索的完备性，最优性，时间和空间复杂度。

2、指出无信息搜索策略和有信息搜索策略的不同。

3、分析一致代价搜索如何保证算法的最优性五．实验报告（一）算法的基本原理1.基本原理一致代价搜索总是扩展路径消耗最小的结点n。

n点的路径消耗等于前一结点n-1的路径消耗加上n-1到n的路径消耗。

2.算法实现流程a.相关函数：地图初始化函数：其中map.txt为图搜索树信息：路径数目23条，路径起始点s，结束点t，路径消耗cost:下标获取函数：ｂ．主函数实现流程：首先初始化地图，创建优先队列ｑ，输入起始城市和目标城市并获取城市的下标，将起始结点入队列。

一致搜索过程：将优先队列中当前路径消耗最小的头结点弹出，（因为结点在优先队列中，其头结点必然为队列中路径消耗最小的才会弹出。

）对其进行扩展标记，判断当前结点是否为目标结点，如果不是，将该结点的后继结点入队列，并记录其前继结点，后继结点的路径消耗值等于当前结点的路径消耗加上当前结点到它的路径消耗；如果当前结点为目标结点，则将路线及路径总耗散输出，即把记录的前继结点结点输出。

- 1 -实验一：实现单链表各种基本运算的算法一、 实验目的1、 掌握单链表存储结构的类型定义；2、 实现单链表各种基本运算的算法。

二、 实验环境1、 Windows 操作系统；2、 Visual C++ 6.0三、 实验内容实现单链表各种基本运算的算法。

四、 概要设计1.存储结构的类型定义：Typedef struct LNode{ElemType data;Struct LNode *next;}LinkList;2.单链表示意图：3.项目组成图:4.algo2_2.cpp 的程序文件包含的函数原型及功能:InitList(LinkList *&L) 初始化单链表LDestroyList(LinkList *&L) 释放单链表LListEmpty(LinkList *L)判断单链表L 是否为空表ListLength(LinkList *L)返回单链表L 的元素个数DispList(LinkList *L)输出单链表LGetElem(LinkList *L,int i,ElemType &e)获取单链表L 的第i 个元素LocateElem(LinkList *L,ElemType e)在单链表L 中查找元素eListInsert(LinkList *&L,int i,ElemType e)在单链表L 中的第i 个位置上插入元素e…… head a 1 a 2 a 3 a n ∧ListDelete(LinkList *&L,int i,ElemType &e)在单链表L中删除第i个元素5.exp2_2.cpp程序文件简介:InitList(LinkList *&L) 初始化单链表LDestroyList(LinkList *&L) 释放单链表LListEmpty(LinkList *L) 判断单链表L是否为空表ListLength(LinkList *L) 返回单链表L的元素个数DispList(LinkList *L) 输出单链表LGetElem(LinkList *L,int i,ElemType &e) 获取单链表L的第i个元素LocateElem(LinkList *L,ElemType e) 在单链表L中查找元素eListInsert(LinkList *&L,int i,ElemType e) 在单链表L中的第i个位置上插入元素e ListDelete(LinkList *&L,int i,ElemType &e) 在单链表L中删除第i个元素6.proj2-2的项目的模块结构:在文件algo2-2中，(1)定义单链表结构类型；(2)初始化单链表(3)定义释放单链表的函数(4)定义判断单链表是否为空的函数(5)定义返回单链表元素个数的函数(6)定义输出单链表的函数(7)定义获取第i个元素的函数(8)定义查找元素的函数(9)定义插入元素的函数(10)定义删除元素的函数在文件exp2-2中分别调用algo2-2中所定义的函数7.函数调用关系图:五、详细设计源代码清单见附录。

实验1 秦九韶算法（贺俊杰 2020022060）一、实验目的人类的计算能力等于计算工具的效率与计算方法的效率的乘积，高效率计算方法大大减少了计算次数，从而也能较少舍入误差的传播和积累，构造高效率计算方法一直是科学计算的一个主要目的。

本次实验以完成秦九韶算法为契机，深入了解高效计算多项式结果的数值计算方法，同时加深对Matlab 环境的熟悉。

二、算法分析对于n 次多项式：1110()n n n n n P x a x a x a x a −−=+++ (1)可改写为嵌套形式：1210()((()))n n n n p x a x a x a x a x a −−=++++ (2)在(1)式中，n i n i a x −−需要计算n i −次乘法运算(其中0,1,1i n =−)和n 次加法运算，共需要进行(1)2n n+次乘法运算和n 次加法运算。

而在(2)式中，仅需要经过n 次乘法运算和n 次加法运算，能够极大地减少运算次数，提高运算效率。

根据程序设计地习惯，把公式(2)写成下来等价的地推形式：(1,2,)n n k y a y y x a k n −⇐⎧⎨⇐⋅+=⎩ (3)三、算法代码实现秦九韶算法Matlab 实现如下：Qinjiu.m 文件其中a 为多项式系数从高次向低次排列数组(缺项系数为0)，n 为多项式多高次数，x 为变量。

四、实验结果1、 设543()851f x x x x =++−，计算()f x 在1,1.5,2.1,3x =上的值。

编写run_qinjiu.m 代码文件如下所示：run_qinjiu.m 文件取多项式系数a = [8, 5, 1, 0, 0, -1]，运行结果如下图所示：图1 run_qinjiu.m 运行结果由图可知算法能正确运行。

2、 利用Matlab 库中的horner 命令，可直接把多项式变为如(2)式的嵌套形式。

编写run_horner.m 代码文件如下所示：程序运行结果如下图所示：从图中可看出，horner库函数可正确地将多项式转为嵌套形式。

银行家算法实验报告【实验目的】（1）根据设计题目的要求，充分地分析和理解题目，叙述系统的要求，明确程序要求实现的功能以及限制条件。

（2）明白自己需要用代码实现的功能，清楚编写每部分代码的目的，做到有的放矢，有条理不遗漏的用代码实现银行家算法。

【实验要求】（1）了解和理解死锁；（2）理解利用银行家算法避免死锁的原理；（3）会使用某种编程语言。

【实验原理】一、安全状态指系统能按照某种顺序如<P1,P2,…,Pn>(称为<P1,P2,…,Pn>序列为安全序列)，为每个进程分配所需的资源，直至最大需求，使得每个进程都能顺利完成。

二、银行家算法假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requesti[j]=k。

系统按下述步骤进行安全检查：（1）如果Request i≤Need i则继续以下检查，否则显示需求申请超出最大需求值的错误。

（2）如果Request i≤Available则继续以下检查，否则显示系统无足够资源，Pi阻塞等待。

（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Available［j］∶=Available［j］-Request i[j］;Allocation［i,j］∶=Allocation［i,j］+Request i［j］;Need［i,j］∶=Need［i,j］-Requesti［j］;（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。

若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

三、安全性算法（1）设置两个向量：①工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work∶=Available;② Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。

开始时先做Finish［i］∶=false; 当有足够资源分配给进程时，再令Finish ［i］∶=true。