最近对蛮力分治实验报告

《算法设计与分析》实验报告一

学号： 1004091130

姓名： 金玉琦 日期： 2011-10-13

得分：

一、实验内容：

最近对问题，即找出一个点集合中距离最近的点对，分别运用蛮力法和分治法性能解决该问题，对两种算法进行性能比较。 二、所用算法的基本思想及复杂度分析：

1.分治法

1）基本思想

我们用分治法解决最近对问题，就是将集合S 分成两个子集S 1和S2，每个子集中有n/2个点。然后在每个子集中递归的求其最接近的点对，在求出每个子集的最接近点对后，关键问题是如何实现分治法中的合并步骤，如果组成S 的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。但是，如果这2个点分别在S1和S2中，则对于S1中任一点p ，S2中最多只有n/2个点与它构成最接近点对的候选者，仍需计算才能得到准确结果。

2）复杂度分析

应用分治法求解含有n 个点得最近对问题，其时间复杂性可由下面的递推式表示：

T （n ）=2T （n /2）+f (n )

合并子问题的解的时间f （n ）=O （1），由通用分治递推式的主定理可得，T （n ）=O （nlog 2n )

2．蛮力法

1）基本思想

蛮力法求解最近对问题的过程是：分别计算每一对点之间的距离，然后找出距离最小的一对，为了避免对同一对点计算两次距离，只考虑i

2）复杂度分析

算法的基本操作是计算两个点的欧几里得距离。注意到在求欧几里得距离时，避免了球平方根操作，原因是：如果被开方的数越小，则它的平方根也越小。所以，算法的基本操作就是求平方，其执行次数为：

T(n)=∑-=11n i ∑+=n i j 12 =2∑-=-11

)(n i i n =n （n-1）=O （n 2） 三、源程序及注释：

#define LENGTH 10000

#define min(X,Y) ((X)<(Y)?(X):(Y))

#include

#include

#include

#include

#include

#include

using namespace std;

struct point{

double x;

double y;

};

point points[LENGTH*2];

// point tempLeft[LENGTH];

// point tempRight[LENGTH];

//排序

int cmpp(point a,point b)

{

if(a.x!=b.x) return a.x

return a.y

}

//求距离的平方，在这不用求出距离，直接求出平方少计算一次，效果相同double Distence(point a,point b)

{

return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);

}

//蛮力法函数

double ClosestPoints(int n,point p[],int &index1,int &index2) {

double minDist=DBL_MAX;

double temp;

for (int i=0;i

for (int j=i+1;j<=n;j++)

{

temp=Distence(p[i],p[j]);

if(temp

{

minDist=temp;

index1=i;

index2=j;

}

}

return sqrt(minDist);

}

//分治法函数

double DivPoints(point p[],int begin,int end)

{

int i,j;

int n=end-begin+1;

int m=(begin+end)/2;

if(n==2)return Distence(p[begin],p[end]);//两个点返回距离

if(n==3)//三个点直接求最近点并返回距离

{

double d1=Distence(p[begin],p[begin+1]);

double d2=Distence(p[begin+1],p[end]);

double d3=Distence(p[begin],p[end]);

if(d1<=d2&&d1<=d3)return d1;

else if(d2<=d3)return d2;

else return d3;

}

double left=DivPoints(p,begin,m);

double right=DivPoints(p,m+1,end);

double d=min(left,right);

int k,l,flag=0;

//找到以m为中心的与m横坐标距离小于sqrt(d)的点

for(i=begin;i<=end;i++)

{

if(flag==0&&(p[m].x-p[i].x)<=sqrt(d))

{flag=1;k=i;}

if((p[i].x-p[m].x)<=sqrt(d))

l=i;

}

for (i=k;i<=m;i++)

{

for (j=m+1;j<=l&&fabs((p[j].y-p[i].y))

{

if(Distence(p[i],p[j])<=d)

d=Distence(p[i],p[j]);

}

}

// for(i=begin;i<=m;i++)

// if((p[m].x-p[i].x)<=sqrt(d))

// tempLeft[k++]=p[i]; //将m左侧与m水平距离小于d的点放入tempLeft中

// for(i=m+1;i<=end;i++)

// if((p[i].x-p[m].x)<=sqrt(d))

// tempRight[l++]=p[i]; //将m右侧与m水平距离小于d的点放入tempRight中

// //将tempLeft和tempRight按y升序排列

// sort(tempLeft,tempLeft+k,cmpy);

// sort(tempRight,tempRight+l,cmpy);

// double md=DBL_MAX;

// for(i=0;i

// for(j=0;j

// if(Distence(tempLeft[i],tempRight[j])<=md)

// md=Distence(tempLeft[i],tempRight[j]);

// }

return d;

}

//主函数

void main()

{

LARGE_INTEGER begin,end,frequency;

int n;

int index1,index2;

double forcedist,divdist;

cout<<"输入随机点个数：";

cin>>n;

cout<

//生成随机数

srand(time(0));

for (int i=0;i

{

points[i].x=rand();

points[i].y=rand();

}

//蛮力法求最近对时间

QueryPerformanceFrequency(&frequency);

QueryPerformanceCounter(&begin);

forcedist=ClosestPoints(n,points,index1,index2);

QueryPerformanceCounter(&end);

cout<<"最短距离是："<

<

cout<<"蛮力法求解时间"<<(double)(end.QuadPart-begin.QuadPart)/frequency.QuadPart<<"s"<

//分治法求最近对时间

QueryPerformanceCounter(&begin);

sort(points,points+n,cmpp); //对点对排序

divdist=sqrt(DivPoints(points,0,n-1));

QueryPerformanceCounter(&end);

cout<<"最短距离是："<

cout<<"分治法求解时间"<<(double)(end.QuadPart-begin.QuadPart)/frequency.QuadPart<<"s"<

}

四、运行输出结果：

五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：

1在点的个数比较少的时候，蛮力法所用时间时间比分治法少，点数比较多的情况下，分治法的优势就很明显了，所用时间明显比蛮力法少。

2.在输入一个点的时候程序会崩溃，因为返回值是无穷大，分治法的合并过程中会出错。

3.分治法中，借鉴别人的做法，没有产生P1和P2两个子点集，这样节省了空间，而且将整个点集排序之后就没有必要划分成两个点集。上述代码中被注释部分是将整个点集划分成两个子集的做法。

测量电压实验报告

测量电压实验报告 篇一：基于Labview的电压测量仿真实验报告 仿真实验一基于Labview的电压测量仿真实验 一、实验目的 1、了解电压测量原理； 2、通过该仿真实验熟悉虚拟仪器技术——LABVIEW的简单编程方法； 3、通过本次实验了解交流电压测量的各种基本概念。 二、实验仪器 微机一台、LABVIEW8.5软件三、实验原理 实验仿真程序如下（正弦波、三角波、锯齿波、方波（占空比30%、50%、60%）： 四、实验内容及步骤 （1）自己编写LABVIEW仿真信号源实验程序，要求可以产生方波（占空比 可调）、正弦波、三角波、锯齿波等多种波形，而且要求各种波形的参数可调、可控。 （2）编写程序对各种波形的有效值、全波平均值、峰

值等进行测量，在全波平均值测量时要注意程序编写过程。同时记录各种关键的实验程序和实验波形并说明。 实验所得波形如下：（正弦波、三角波、锯齿波、方波（占空比30%、50%、60%）： 正弦波： 三角波： 锯齿波： 方波（占空比30%）： 方波（占空比50%）： 方波（占空比60%）： （3）对各种波形的电压进行测量，并列表记录。如下表： 五、实验小结 由各波形不同参数列表可知，电压量值可以用峰值、有效值和平均值表征。被测电压是非正弦波的，必须根据电压表读数和电压表所采用的检波方法进行必要地波形换算，才能得到有关参数。 篇二：万用表测交流电压实验报告1

万用表测交流电压实验报告 篇三：STM32 ADC电压测试实验报告 STM32 ADC电压测试实验报告 一、实验目的 1.了解STM32的基本工作原理 2. 通过实践来加深对ARM芯片级程序开发的理解 3.利用STM32的ADC1通道0来采样外部电压值值，并在TFTLCD模块上显示出来 二、实验原理 STM32拥有1~3个ADC，这些ADC可以独立使用，也可以使用双重模式（提高采样率）。STM32的ADC是12位逐次逼近型的模拟数字转换器。它有18个通道，可测量16个外部和2个内部信号源。各通道的A/D转换可以单次、连续、扫描或间断模式执行。ADC的结果可以左对齐或右对齐方式存储在16位数据寄存器中 接下来，我们介绍一下执行规则通道的单次转换，需要用到的ADC寄存器。第一个要介绍的是ADC控制寄存器（ADC_CR1和ADC_CR2）。ADC_CR1的各位描述如下： ADC_CR1的SCAN位，该位用于设置扫描模式，由软件

算法设计与分析实验报告

本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼110 专业班级：物联网1601 学号：2016002105 学生姓名：俞梦真 指导教师：郝晓丽

2018年05月04 日 实验一递归与分治算法 1.1 实验目的与要求 1．进一步熟悉C/C++语言的集成开发环境； 2．通过本实验加深对递归与分治策略的理解和运用。 1.2 实验课时 2学时 1.3 实验原理 分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。 需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。 1.4 实验题目 1．上机题目：格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。 对于给定的正整数n，格雷码为满足如下条件的一个编码序列。 （1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。 （2）序列中无相同的编码。 （3）序列中位置相邻的两个编码恰有一位不同。 2．设计思想：

根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。 3．代码设计：

实验报告 分治与递归

实验报告分治与递归 中国矿业大学计算机科学与技术学院孟靖宇 一、实验目的与要求 1、熟悉C/C++语言的集成开发环境； 2、通过本实验加深对递归过程的理解 二、实验内容： 掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。 三、实验题 任意输入一个整数，输出结果能够用递归方法实现整数的划分。 四、算法思想 对于数据n,递归计算最大加数等于x 的划分个数+最大加数不大于x-1的划分个数。最大加数x 从n 开始，逐步变小为n-1, (1) 考虑增加一个自变量：对于数据n,最大加数n1不大于m 的划分个数记作),(m n q 。则有： ???????>>=<==-+--+=1 1,1),()1,()1,(1),(1),(m n m n m n m n m m n q m n q n n q n n q m n q 五、代码实现 #include "stdafx.h" #include #include #include using namespace std; int q(intn,int m); int main(){ int n; cout<<"请输入要划分的整数："<>n; int p=q(n,n); cout<<"正整数"<

return 0; } int q(intn,int m){ if((n<1)||(m<1)) return 0; if((n==1)||(m==1)) return 1; if(n

回溯法实验(0-1背包问题)

算法分析与设计实验报告第五次附加实验

附录： 完整代码（回溯法） //0-1背包问题回溯法求解 #include using namespace std; template class Knap //Knap类记录解空间树的结点信息 { template friend Typep Knapsack(Typep [],Typew [],Typew,int); private: Typep Bound(int i); //计算上界的函数 void Backtrack(int i); //回溯求最优解函数

Typew c; //背包容量 int n; //物品数 Typew *w; //物品重量数组| Typep *p; //物品价值数组 Typew cw; //当前重量 Typep cp; //当前价值 Typep bestp; //当前最后价值 }; template Typep Knapsack(Typep p[],Typew w[],Typew c,int n); //声明背包问题求解函数template inline void Swap(Type &a,Type &b); //声明交换函数 template void BubbleSort(Type a[],int n); //声明冒泡排序函数 int main() { int n ;//物品数 int c ;//背包容量 cout<<"物品个数为："; cin>>n; cout<<"背包容量为："; cin>>c; int *p = new int[n];//物品价值下标从1开始 int *w = new int[n];//物品重量下标从1开始 cout<<"物品重量分别为："<>w[i]; } cout<<"物品价值分别为："<>p[i]; } cout<<"物品重量和价值分别为："<

算法实验报告

华北电力大学 实验报告| | 实验名称算法设计与分析综合实验 课程名称算法设计与分析 | | 专业班级软件12 学生姓名： 学号：成绩： 指导教师：胡朝举实验日期：

实验一分治策略—归并排序 一、实验要求 （1）编写一个模板函数：template ，MergeSort(T *a, int n); 以及相应的一系列函数，采用分治策略，对任意具有:bool operator<(const T&x,const T&y);比较运算符的类型进行排序。 （2）与STL库中的函数std::sort(..)进行运行时间上的比较，给出比较结果,如：动态生成100万个随机生成的附点数序列的排序列问题, 给出所用的时间比较。 二、实验代码 #include <> #include <> #include <> #include <> #define MAX 50 typedef struct { int arr[MAX+1]; int length; }SortArr; SortArr *CreateSortArr() { int i = 0; char buf[4*MAX] = ""; char *ptr = NULL; SortArr *sortArr = (SortArr *)malloc(sizeof(SortArr)); memset(sortArr, 0, sizeof(SortArr)); printf("请输入待排序数据，以逗号分隔，以分号结束\n" "input:"); scanf("%s", buf); ptr = buf; sortArr->arr[i] = 0; i = 1; while(*ptr != ';') { sortArr->arr[i] = atoi(ptr); i++; ptr = strstr(ptr, ","); if(!ptr) { break; } ptr++; } sortArr->length = (i - 1); return sortArr; } int merge(int arr[], int p, int q, int r) { int i = 0; int j = 0; int k = 0; int n1 = 0; int n2 = 0; int *leftArr = NULL; int *rightArr = NULL; n1 = q - p + 1; n2 = r - q;

回溯法实验(最大团问题)

算法分析与设计实验报告第七次附加实验

} } 测试结果 当输入图如下时： 当输入图如下时： 1 2 3 4 5 1 2 3 4 5

当输入图如下时： 1 2 3 4 5

附录： 完整代码（回溯法） //最大团问题回溯法求解 #include using namespace std; class Clique { friend void MaxClique(int **,int *,int ); private: void Backtrack(int i); int **a; //图的邻接矩阵 int n; //图的顶点数 int *x; //当前解 int *bestx; //当前最优解 int cn; //当前顶点数 int bestn; //当前最大顶点数 }; void Clique::Backtrack(int i) { //计算最大团 if(i>n) //到达叶子节点 { for(int j=1;j<=n;j++) bestx[j]=x[j]; bestn=cn;

cout<<"最大团：（"; for(int i=1;i=bestn) { //修改一下上界函数的条件，可以得到 x[i]=0; //相同点数时的解 Backtrack(i+1); } } void MaxClique(int **a,int *v,int n) { //初始化Y Clique Y; Y.x=new int[n+1]; Y.a=a; Y.n=n; https://www.doczj.com/doc/9b17207549.html,=0; Y.bestn=0; Y.bestx=v; Y.Backtrack(1); delete [] Y.x; cout<<"最大团的顶点数："<

经典编辑南京航空航天大学结构强度的电测法实验报告(含数据)

《结构强度的电测方法》实验报告 学院：航空宇航学院 专业： 学号： 姓名： 组员： 指导教师： 日期：

结构强度电测法实验 一实验目的 1.掌握电阻应变测试原理及方法 2.掌握电阻应变片的安装工艺 3.掌握电阻应变片电桥线路的连接及电阻应变仪的使用 4.测定矩形截面受纯剪切内力作用时的剪切应力分布规律及许用载荷 5.测定特定的弹性元件在对称载荷作用方式下的最大许用载荷 6.测定特定的框架结构在指定外力作用下的危险点应力及最大许用载荷 7.给出测试结果并给出不确定度分析 二实验仪器、设备名称及型号 本实验主要实验仪器和设备有：TS3861静态电阻应变仪、压力试验机、2个待测弹性元件及1个钢架、电阻应变片、导线、电烙铁、丙酮、砂纸、502胶、绝缘胶带、镊子等。 TS3861静态电阻应变仪面板如图1所示。 图1 TS3861静态电阻应变仪面板示意图 其中：（1）CH为通道指示，其下面的两个按扭为通道选择键。 （2） 为读数应变显示窗，其下面的三个按键“自动”、“初值”、“测量”的作用为：“自动”按键在手动测量时无用；“初值”按键为在有初始值的情况下的测量；若先按“初值”再按“测量”按键，为将现通道设置为在“0”初始值的情况下的测量，即“置零”。 （3）根据应变片的阻值选择“应变片电阻Ω”的数字。 （4）根据应变片的灵敏系数选择“灵敏系数K”的数字。

三实验原理及实验方法 1、应变片原理 电阻片分丝式和箔式两大类。丝绕式电阻片是用0.003mm-0.01mm的合金丝绕成栅状制成的；箔式应变片则是用0.003mm-0.01mm厚的箔材经化学腐蚀制成栅状的，其主体敏感栅实际上是一个电阻。金属丝的电阻随机械变形而发生变化的现象称为应变-电性能。电阻片在感受构件的应变时（称做工作片），其电阻同时发生变化。实验表明，构件被测量部位的应变Δl/l与电阻变化率ΔR/R成正比关系，即： 比例系数Ks称为电阻片的灵敏系数。由于电阻片的敏感栅不是一根直丝， 所以K s 不能直接计算，需要在标准应变梁上通过抽样标定来确定。K s 的数值一般 约在2.0 左右，这里取K=2.048。 2、电阻应变仪原理 电阻应变仪是将电阻片感受到应变转化为电阻变化，再把电阻变化通过适当桥路和放大器转为电压变化，并显示出来。电阻应变仪按其测量对象可分为静态电阻应变仪和动态电阻应变仪。动态应变仪有电压和电流输出，提供相关记录仪记录，例如X-Y记录仪、光线示波器和磁带记录仪等等。也有一些应变仪兼有静态应变数值显示和动态电压输出，使用起来比较方便。由于电阻应变仪是一种专用仪器，其显示部分直接显示应变值。通过应变可以计算出载荷、应力和变形，为核算构件的强度提供依据，因此应变仪应用十分广泛应变仪测量电路是一个电桥电路(见图2)它的四个桥臂R1，R2，R3，R4顺序连接在A、B、C、D 之间。电桥AC对角接电源E；BD对角为电桥输出电压U DB。当四个电阻皆由电阻应变片组成，且四枚电阻片阻值和灵敏系数相等时，桥路有如下关系:

回溯法实验报告

实验04 回溯法 班级：0920561 姓名：宋建俭学号：20 一、实验目的 1.掌握回溯法的基本思想。 2.掌握回溯法中问题的解空间、解向量、显式约束条件、隐式约束条件以及子 集树与排列树的递归算法结构等内容。 3.掌握回溯法求解具体问题的方法。 二、实验要求 1.认真阅读算法设计教材,了解回溯法思想及方法; 2.设计用回溯算法求解装载问题、n后问题、图的m着色问题的java程序 三、实验内容 1.有一批共n个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱 i的重量为wi，且∑wi≤C1+C2。装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 2.在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则， 皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。 3.给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每 个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。 这个问题是图的m可着色判定问题。 四、算法原理 1、装载问题 用回溯法解装载问题时，用子集树表示其解空间是最合适的。可行性约束可剪去不满足约束条件(w1x1+w2x2+…+wnxn)<=c1的子树。在子集树的第j+1层结点Z处，用cw记当前的装载重量，即cw=(w1x1+w2x2+…+wjxj)，当cw>c1时，以结点Z为根的子树中所有结点都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪去。 解装载问题的回溯法中，方法maxLoading返回不超过c的最大子集和，但未给出达到这个最大子集和的相应子集。 算法maxLoading调用递归方法backtrack(1)实现回溯搜索。Backtrack(i)搜索

电测实验报告解析

《电子测量技术》实验报告 电气工程学院 姓名：李晓峰 学号：12281035 班级：电气1307班

实验一示波器波形参数测量 一、实验目的 通过示波器的波形参数测量，进一步巩固加强示波器的波形显示原理的掌握，熟悉示波器的使用技巧。 1.熟练掌握用示波器测量电压信号峰峰值，有效值及其直流分量。 2.熟练掌握用示波器测量电压信号周期及频率。 3.熟练掌握用示波器在单踪方式和双踪方式下测量两信号的相位差。 二、实验设备 1.信号发生器,示波器。 示波器——SS7802A a、主要参数： SS-7802模拟示波器·具有能够选择场方式、线路的TV/视频同步功能·附有光标和读出功能·5位数计数器规格及性能·显像管：6英寸、方型8*10p(1p=10mm)约16kV·垂直灵敏度：2mV/p~5V/p（1-2-5档）（通道1、通道2）精度：±2%·频率范围：20MHz·时间轴扫描A·100ns/p~500ms/p·TV/视频同步：能够选择场方式、能够选择ODD、EVEN、BOTH、扫描线路 b、主要功能描述 示波器操作板如图所示：

包括如下五个操作控制区域： 水平控制区 【?POSITION?】：将【?POSITION?】向右旋转，波形右移。 FINE 指示灯亮时，旋转【?POSITION?】可作微调。 MAG×10 ：扫描速率提高10倍，波形将基于中心位置向左右放大。 ALTCHOP ：选择ALT（交替，两个或多个信号交替扫描）或CHOP （断续，两个或多个信号交替扫描）。 垂直控制区 INPUT：输入连接器（CH1、CH2）,连接输入信号。 EXTINPUT ：用外触发信号做触发源。外信号通过前面板的EXTINPUT接入。 【VOLTS/DIV】：调节【VOLTS/DIV】选择偏转因数。按下【VOLTS/DIV】；偏转因数显示“”符号。在该屏幕下，可执行微调程序。 【▲POSITION▼】：垂直位移，向右旋转，波形上移。

分别用蛮力法、分治法、减治法实现a的N次方

《算法设计与分析》实验报告一 学号：姓名： 日期： 2012.11.5 得分： 一、实验内容： 分别用蛮力法、分治法、减治法实现a^n。 二、实验要求： 完成试验报告、给出对此结果。 为防止大数溢出，可以用1^n来测试在n比较大是的三种算法运行情况。 四、源程序及注释： #include #include using namespace std; //蛮力法求a的n次方 int Power1(int a,int n) { int as=1; for(int i=0;i

} int main() { int a=1; int n=10000; LARGE_INTEGER start1,end1,start2,end2,start3,end3,f; QueryPerformanceFrequency(&f); QueryPerformanceCounter(&start1) ; int p1=Power1(a,n); QueryPerformanceCounter(&end1); QueryPerformanceCounter(&start2) ; int p2=Power2(a,n); QueryPerformanceCounter(&end2); QueryPerformanceCounter(&start3) ; int p3=Power3(a,n); QueryPerformanceCounter(&end3); cout<<"a="<

回溯法实验报告

数学与计算机学院实验报告 一、实验项目信息 项目名称：回溯法 实验时间： 2016/06/08 实验学时： 03 学时 实验地点：工科楼503 二、实验目的及要求 理解回溯法的深度优先搜索策略、 掌握用回溯法解题的算法框架、 掌握回溯法的设计策略 三、实验环境 计算机Ubuntu Kylin14.04 CodeBlock软件四、实验内容及实验步骤 排兵布阵问题 某游戏中，不同的兵种处在不同的地形上其攻击能力不一样，现有n个不同兵种的角色{1,2,...,n}，需安排在某战区n个点上，角色i在j点上的攻击力为A ij。试设计一个布阵方案，使总的攻击力最大。 数据： 防卫点 角 色 1 2 3 4 5 1 2 3 4 5 回溯法： 程序： #include int position[10]; int a[10][10]; int check(int k){//每个节点检查的函数 int i; for(i=0;i=0) { sum=0; position[k]=position[k]+1; while(position[k]<=n)

if(check(k))break; else position[k]=position[k]+1; if(position[k]<=n && k==n-1) { for(i=0;i

接地电阻测量实验报告范文.doc

接地电阻测量实验报告范文 为了了解接地装置的接地电阻值是否合格、保证安全运行，同时根据配电设备维护规程的有关规定，我部于20xx年3月1日上午8:00 对乐民原料部弓角田煤矿各变配电点的接地及其各变压器对地绝缘情况进 行测量试验。试验过程及试验结果分析报告如下： 一、试验前的准备： 1、制订试验方案： 前期，我们组织机电队人员一起到现场查看接地装置，查找接地极的适合试验的位置，制订、讨论、修改试验方案，提出试验中的注意事项。 2、试验方法： 接地电阻表本身备有三根测量用的软导线，可接在E、P、C三个接线端子上。接在E端子上的导线连接到被测的接地体上，P端子为电压极，C端子为电流极（P、C都称为辅助接地极），根据具体情况，我们准备采用两种方式测量：（1）、将辅助接地极用直线式或三角线式，分别插入远离接地体的土壤中；（2）、用大于25cm×25cm的铁板作为辅助电极平铺在水泥地面上，然后在铁板下面倒些水，铁板的布放位置与辅助接地极的要求相同。两种方法我们都采取接地体和连接设备不 断开的方式测量，接地电阻电阻表将倍率开关转换到需要的量程上，用手摇发电机手柄，以每分钟0转/分以上的速度转时，使电阻表上的仪表指针趋于平衡，读取刻盘上的数值乘以倍率即为实测的接地电阻值。

3、试验工具： 我们准备好ZC29B-2型接地电阻测试仪、ZC110D-10（0~2500MΩ）型摇表、万用表、铜塑软导线（BVR 1.5mm2）、测电笔、接地极棒和接地板等试验用具及棉纱等辅助材料。 二、试验过程： 1、3月1日上午，现场试验人员进行简单碰头，并进行分工：由帅锐进行测量、值班人员蔡富贵和彭余坤配合操作、陈应沫记录、班长方兴华负责监护； 2、8:45试验开始； 3、测量辅助接地极间及与测量接地体间的距离； 4、采取第一种方法，将接地极棒插入到土壤中并按照图纸接好线； 5、将测量接地体连接处与连接端子牢靠连接； 6、将导线与接地电阻表接好； 7、校正接地电阻表； 8、测量并记录数据；（试验数据见附表） 9、采取第二种方法，测量并记录数据； 10、整个试验过程结束。 恒鼎实业弓角田煤矿春季预防性试验设备外壳接地测试记录 恒鼎实业弓角田煤矿春季预防性试验变压器绝缘测试记录 使用仪器： ZC29B-2型接地电阻测试仪 测量数据表： 测量数据单位（MΩ）

算法设计与分析实验报告

算法设计与分析课程实验项目目录 学生姓名：学号： *实验项目类型：演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。 本科实验报告专用纸

课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号 201 实验项目类型设计实验地点机房 学生姓名学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间 2012年 3月 1 日～6月30日温度24℃ 1.实验目的和要求： 熟悉蛮力法的设计思想。 2.实验原理和主要内容： 实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验内容：以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序，实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人给出的： S END +MORE MONEY . 这 里有两个前提假设：第一，字母和十进制数字之间一一对应，也就是每个字母只代表一个数字，而且不同的字母代表不同的数字；第二，数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意，解可能并不是唯一的，不同人的解可能并不相同。 3.实验结果及分析： （将程序和实验结果粘贴，程序能够注释清楚更好。） 本科实验报告专用纸(附页) 该算法程序代码如下：

#include "" #include "" int main(int argc, char* argv[]) { int x[100],y[100]; int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100]; printf("请输入点的个数：\n"); scanf("%d",&num); getchar(); clock_t start,end; start=clock(); printf("请输入各点坐标:\n"); for(l=0;l

算法分析实验报告--分治策略

《算法设计与分析》实验报告 分治策略 姓名：XXX 专业班级：XXX 学号：XXX 指导教师：XXX 完成日期：XXX

一、试验名称：分治策略 （1）写出源程序，并编译运行 （2）详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序，实现归并排序。 (2)编写一段程序，实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序，实现归并排序。 将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行 排序，最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序，实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有 数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数 据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通

过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割， 直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序，实现归并排序。 #include #include #define MAX 10 using namespace std; void merge(int array[],int p,int q,int r) { int i,k; int begin1,end1,begin2,end2; int* temp = new int[r-p+1]; begin1 = p; end1 = q; begin2 = q+1; end2 = r; k = 0; while((begin1 <= end1)&&(begin2 <= end2)) { if(array[begin1] < array[begin2]) { temp[k] = array[begin1]; begin1++; } else { temp[k] = array[begin2]; begin2++; } k++; } while(begin1 <= end1) {

算法设计与分析：回溯法-实验报告

应用数学学院信息安全专业班学号姓名 实验题目回溯算法 实验评分表

实验报告 一、实验目的与要求 1、理解回溯算法的基本思想； 2、掌握回溯算法求解问题的基本步骤； 3、了解回溯算法效率的分析方法。 二、实验内容 【实验内容】 最小重量机器设计问题：设某一个机器有n个部件组成，每个部件都可以m个不同供应商处购买，假设已知表示从j个供应商购买第i个部件的重量，表示从j个供应商购买第i个部件的价格，试用回溯法求出一个或多个总价格不超过c且重量最小的机器部件购买方案。 【回溯法解题步骤】 1、确定该问题的解向量及解空间树； 2、对解空间树进行深度优先搜索； 3、再根据约束条件（总价格不能超过c）和目标函数（机器重量最小）在搜索过程中剪去多余的分支。 4、达到叶结点时记录下当前最优解。 5、实验数据n,m, ] ][ [j i w,] ][ [j i c的值由自己假设。 三、算法思想和实现【实现代码】

【实验数据】 假设机器有3个部件，每个部件可由3个供应商提供（n=3，m=3）。总价不超过7（c<=7）。 部件重量表： 部件价格表： 【运行结果】

实验结果：选择供应商1的部件1、供应商1的部件2、供应商3的部件3，有最小重量机器的重量为4，总价钱为6。 四、问题与讨论 影响回溯法效率的因素有哪些？ 答：影响回溯法效率的因素主要有以下这五点： 1、产生x[k]的时间； 2、满足显约束得x[k]值的个数； 3、计算约束函数constraint的时间； 4、计算上界函数bound的时间； 5、满足约束函数和上界函数约束的所有x[k]的个数。 五、总结 这次实验的内容都很有代表性，通过上机操作实践与对问题的思考，让我更深层地领悟到了回溯算法的思想。 回溯算法的基本思路并不难理解，简单来说就是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯法的基本做法是深度优先搜索，是一种组织得井井

电力系统继电保护实验实验报告

网络高等教育《电力系统继电保护》实验报告 学习中心：奥鹏学习中心 层次：专科起点本科 专业：电气工程及其自动化 年级： 学号： 学生：

实验一电磁型电流继电器和电压继电器实验 一、实验目的 1. 熟悉DL型电流继电器和DY型电压继电器的的实际结构，工 作原理、基本特性； 2. 学习动作电流、动作电压参数的整定方法。 二、实验电路 1．过流继电器实验接线图 过流继电器实验接线图 2.低压继电器实验接线图 低压继电器实验接线图

三、预习题 1.过流继电器线圈采用_串联_接法时，电流动作值可由转动刻度盘上的指针所对应的电流值读出；低压继电器线圈采用__并联 _接法时，电压动作值可由转动刻度盘上的指针所对应的电压值读出。(串联，并联) 2. 动作电流（压），返回电流（压）和返回系数的定义是什么？ 答：1.使继电器返回的最小电压称为返回电压；使继电器动作的最大电压称为动作电压；返回电压与动作电压之比称为返回系数。 2.使继电器动作的最小电流称为动作电流；使继电器返回的最大电流称为返回电流；返回电流与动作电流之比称为返回系数。 四、实验容 1．电流继电器的动作电流和返回电流测试 表一过流继电器实验结果记录表

2．低压继电器的动作电压和返回电压测试 表二低压继电器实验结果记录表 五、实验仪器设备

六、问题与思考 1．电流继电器的返回系数为什么恒小于1？ 答：由于摩擦力矩和剩余力矩的存在，使得返回量小于动作量。根据返回力矩的定义，返回系数恒小于1. 2．返回系数在设计继电保护装置中有何重要用途？ 答：返回系数是确保保护选择性的重要指标，让不该动作的继电器及时返回，使正常运行的部分系数不被切除。 3. 实验的体会和建议 电流保护的动作电流是按躲开最大负荷电流整定的，一般能保护相邻线路。在下一条相邻线路或其他线路短路时，电流继电器将启动，但当外部故障切除后，母线上的电动机自启动，有比较大的启动电流，此时要求电流继电器必须可靠返回，否则会出现误跳闸。所以过电流保护在整定计算时必须考虑返回系数和自起动系数，以保证在上述情况下，保护能在大的启动电流情况下可靠返回。电流速断的保护的动作电流是按躲开线路末端最大短路电流整定的，一般只能保护线路首端。在下一条相邻线路短路时，电流继电器不启动，当外部故障切除后，不存在大的启动电流情况下可靠返回问题

算法实验报告

实验一分治与递归算法的应用 一、实验目的 1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。 2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。 3．学会利用分治算法解决实际问题。 二 . 实验内容 金块问题 老板有一袋金块（共n块，n是2的幂（n≥2））,最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。并对自己的程序进行复杂性分析。 三.问题分析: 一般思路：假设袋中有n 个金块。可以用函数M a x（程序 1 - 3 1）通过n-1次比较找到最重的金块。找到最重的金块后， 可以从余下的n-1个金块中用类似法通过n-2次比较找出最轻的金块。这样，比较的总次数为2n-3。

分治法：当n很小时，比如说，n≤2，识别出最重和最轻的金块，一次比较就足够了。当n 较大时（n＞2），第一步，把这袋金块平分成两个小袋A和B。第二步，分别找出在A和B中最重和最轻的金块。设A中最重和最轻的金块分别为HA 与LA，以此类推，B中最重和最轻的金块分别为HB 和LB。第三步，通过比较HA 和HB，可以找到所有金块中最重的；通过比较LA 和LB，可以找到所有金块中最轻的。在第二步中，若n＞2，则递归地应用分而治之方法 程序设计 据上述步骤，可以得出程序1 4 - 1的非递归代码。该程序用于寻找到数组w [ 0 : n - 1 ]中的最小数和最大数，若n < 1，则程序返回f a l s e，否则返回t r u e。 当n≥1时，程序1 4 - 1给M i n和M a x置初值以使w [ M i n ]是最小的重量，w [ M a x ]为最大的重量。 首先处理n≤1的情况。若n>1且为奇数，第一个重量w [ 0 ]将成为最小值和最大值的候选值，因此将有偶,数个重量值w [ 1 : n - 1 ]参与f o r循环。当n 是偶数时，首先将两个重量值放在for 循环外进行比较，较小和较大的重量值分别置为Min和Max，因此也有偶数个重量值w[2:n-1]参与for循环。 在for 循环中，外层if 通过比较确定( w [ i ] , w [ i + 1 ] )中的较大和较小者。此工作与前面提到的分而治之算法步骤中的2) 相对应，而内层的i f负责找出较小重量值和较大重量值中的最小值和最大值，

回溯法实验(n皇后问题)(迭代法)

算法分析与设计实验报告第三次附加实验

附录： 完整代码（回溯法） //回溯算法递归回溯n皇后问题#include #include #include #include"math.h" using namespace std; class Queen

{ friend int nQueen(int); //定义友元函数，可以访问私有数据 private: bool Place(int k); //判断该位置是否可用的函数 void Backtrack(int t); //定义回溯函数 int n; //皇后个数 int *x; //当前解 long sum; //当前已找到的可行方案数 }; int main() { int m,n; for(int i=1;i<=1;i++) { cout<<"请输入皇后的个数："; //输入皇后个数 cin>>n; cout<<"皇后问题的解为："<