回溯法实验报告(2020年10月整理).pdf

回溯法实验(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<<"物品重量和价值分别为："<

基础光学实验实验报告

基 础 光 学 实 验 姓名：许达学号：2120903018 应物21班

一．实验仪器 基础光学轨道系统，基础光学组合狭缝及偏振片，红光激光器及光圈支架，光传感器与转动传感器，科学工作室500或750接口，DataStudio软件系统 二．实验目的 1.通过该实验让学生了解并会运用实验器材，同时学会用计算机分析和处理实验数据。 2.通过该实验让学生了解基本的光学现象，并掌握其物理机制。三．实验原理 单缝衍射：当光通过单缝发生衍射，光强极小（暗点）的衍射图案由下式给出asinθ=mλ(m=1,2,3……），其中a是狭缝宽度，θ为衍射角度，λ是光波波长。 双缝干涉：当光通过两个狭缝发生干涉，从中央最大值（亮点）到单侧某极大值的角度由下式给出dsinθ=mλ(m=1,2,3……),其中d是狭缝间距，θ为从中心到第m级最大的夹角，λ是光波波长，m为级数。 光的偏振：通过第一偏振器后偏振电场为E0，以一定的角度β穿过第二偏振器，则场强变化为E0cosβ,由于光强正比于场强的平方，则，第二偏振器透过的光强为I=I0cos2β. 四．实验内容及过程

单缝衍射 单缝衍射光强分布图 如果设单缝与接收屏的距离为s,中央极强到光强极小点的距离为c,且sinθ≈tanθ=c/s,那么可以推得a=smλ/c.又在此次实验中，s=750mm,λ=6.5E(-4)mm,那么推得a=0.4875m/c,又由图可知：当m=1时，c=(88-82)/2=3mm,推得a=0.1625mm; 当m=2时，c=(91-79)/2=6mm,推得a=0.1625mm; 当m=3时，c=(94-76)/2=9mm,推得a=0.1625mm; 当m=4时，c=(96-74)/2=11mm,推得a=0.1773mm; 得到a的平均值0.1662mm,误差E=3.9%。 双缝干涉

回溯法论文-回溯法的分析与应用

沈阳理工大学算法实践与创新论文

摘要 对于计算机科学来说，算法的概念是至关重要的，算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。为了更加的了解算法，本篇论文中，我们先研究一个算法---回溯法。 回溯法是一种常用的重要的基本设计方法。它的基本做法是在可能的范围之内搜索，适于解一些组合数相当大的问题。圆排列描述的是在给定n个大小不等的圆 C1,C2,…,Cn,现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。图着色问题用数学定义就是给定一个无向图G=（V, E），其中V为顶点集合，E为边集合，图着色问题即为将V分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的 K值。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。 在本篇论文中，我们将运用回溯法来解决着图的着色问题，符号三角形问题，图排列问题，将此三个问题进行深入的探讨。 关键词: 回溯法图的着色问题符号三角形问题图排列问 题

目录 第1章引言 (1) 第2章回溯法的背景 (2) 第3章图的着色问题 (4) 3.1 问题描述 (4) 3.2 四色猜想 (4) 3.3 算法设计 (5) 3.4 源代码 (6) 3.5 运行结果图 (10) 第4章符号三角形问题 (11) 4.1 问题描述 (11) 4.2 算法设计 (11) 4.3 源代码 (12) 4.4 运行结果图 (16) 第5章圆的排列问题 (17) 5.1 问题描述 (17) 5.2 问题分析 (17) 5.3 源代码 (18) 5.4 运行结果图 (22) 结论 (23) 参考文献 (24)

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

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

} } 测试结果 当输入图如下时： 当输入图如下时： 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.docsj.com/doc/ba1207052.html,=0; Y.bestn=0; Y.bestx=v; Y.Backtrack(1); delete [] Y.x; cout<<"最大团的顶点数："<

回溯法实验报告

实验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)搜索

回溯法实验报告

数学与计算机学院实验报告 一、实验项目信息 项目名称：回溯法 实验时间： 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

光学仪器实验报告

常用光电仪器原理及使用 实验报告 班级：11级光信息1班 姓名：姜萌萌 学号：110104060016 指导老师：李炳新

数字存储示波器 一、实验目的 1、熟悉数字存储示波器的使用方法； 2、测量数字存储示波器产生方波的上升时间； 二、实验仪器 数字存储示波器 三、实验步骤 1、产生方波波形 ⑴、打开示波器电源阅读探头警告，然后按下OK。按下“DEFAULT SETUP”按钮，默认的电压探头衰减选项是10X。 ⑵、在P2200探头上将开关设定到10X并将探头连接到示波器的通道1上，然后向右转动将探头锁定到位，将探头端部和基线导线连接到“PROBE COMP”终端上。 ⑶、按下“AUTOSET”按钮，在数秒钟内，看到频率为1KHz 电压为5V峰峰值得方波。按两次CH1BNC按钮删除通道1，

按下CH2BNC按钮显示通道2，重复第二步和第三步。 2、自动测量 ⑴、按下“MUASURE”按钮，查看测量菜单。 ⑵、按下顶部的选项按钮，显示“测量1菜单”。 ⑶、按下“类型”“频率”“值”读书将显示测量结果级更新信息。 ⑷、按下“后退”选项按钮。 ⑸、按下顶部第二个选项按钮；显示“测量2菜单”。 ⑹、按下“类型”“周期”“值”读数将显示测量结果与更新信息。 ⑺、按下“后退”选项按钮。 ⑻、按下中间选项按钮；显示“测量3菜单”。 ⑼、按下“类型”“峰-峰值”“值”读数将显示测量结果与更新信息。 ⑽、按下“后退”选项按钮。 ⑾、按下底部倒数第二个按钮；显示“测量4菜单”。⑿、按下“类型”“上升时间”“值”读数将显示测量结果与更新信息。

LCR测试仪 一、实验目的 1、熟悉LCR测试仪的使用方法； 2、了解LCR测试仪的工作原理； 3、精确测量一些电阻，电感，电容的值； 二、实验仪器 LCR测试仪，电阻，电容，电感等元件 三、LCR测试原理 根据待测元器件实际使用的条件和组合上的差别，LCR 测量仪有两种检测模式，串联模式和并联模式。串联模式以检测元器件Z为基础，并联模式以检测元器件的导纳Y为基础，当用户将测出流过待测元件的电流I，数字电压表将测出待测元件两端的电压V，数字鉴相器将测出电压V和电流I 之间的相位角 。检测结果被储存在仪器内部微型计算机的

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

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

实验报告 一、实验目的与要求 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]的个数。 五、总结 这次实验的内容都很有代表性，通过上机操作实践与对问题的思考，让我更深层地领悟到了回溯算法的思想。 回溯算法的基本思路并不难理解，简单来说就是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯法的基本做法是深度优先搜索，是一种组织得井井

光学基础学习报告

光学基础学习报告 一、教学内容： 光电镜头是用来作为光电接收器（CCD,CMOS ）的光学传感器元件。 光学特性参数： 1、 焦距EFL （学名f ’） 是指主面到相应焦点的距离（如图1.1） 图1.1 每个镜片都有前后两个主面－前主面和后主面（放大率为1的共轭面）。相应的也有两个焦点－前焦和后焦。 凸透镜：双凸；平凸；正弯月（如图1.1） 图1.2 凹透镜：双凹；平凹；负弯月 图 1.3

折射率实际反映的是光在物质中传播速度与真空中速度的比值关系。 薄透镜：)]1()1[()1('12 1R R n f -?-== Φ Φ—透镜光焦距； f ’—焦距； n —折射率； R 1,R 2－两球面曲率半径 厚透镜：2 1221)1()]1()1[()1('1R nR d n R R n f -+ -?-==Φ d －中心厚度 干涉仪与光距座可以量测f ’,R1,R2,d →利用上述的公式可以计算出n 值，从而来确定所用材料。 A 、 EFL 增加，TOTR （光学总长）增加；要降低TOTR 就必须降低EFL ，但EFL 降低， 像高就要降低 B 、 EFL 与某些象差相关 C 、 EFL 上升将使F/NO 增大 D 、 EFL ，FOV （视场角）和IMA （像高）三者间有关系 tanFOV ?=EFL IMA －铁三角关系 EFL 的增大（减小）会使像高变大（小），为了保持像高，就必须要增大（减小）FOV ，然而FOV 的增大会使得REL （相对照度）的数值增大。 2、 BFL 后焦距（学名后截距） 图2.1 3、 F 数（F/NO ） D f NO F '/= f ’－FEL D 入－入瞳直径 入瞳为光阑经其前方光学镜片所成的像，反映进入光学系统的光线 A 、 与MTF 相关，F/NO ↑，则MTF ↑；反之下降 B 、 与景深相关，F/NO ↑，则景深↑，反之下降 C 、 与象差相关，F/NO ↑，则象差↓，反之增加 D 、 与光通量相关，F/NO ↑，则光通量↓，反之增加 对于光电镜头，F/NO 最大在2.8～3.5之间（经验值）允许有±5%的误差，在物方有照

光学实验报告

建筑物理 ——光学实验报告 实验一：材料的光反射比、透射比测量实验二：采光系数测量 实验三：室内照明实测 实验小组成员： 指导老师： 日星期二3月12年2013日期： 实验一、材料的光反射比和光透射比测量

一、实验目的与要求 室内表面的反射性能和采光口中窗玻璃的透光性能都会直接或间接的影响室内光环境的好坏，因此，在试验现场采光实测时，有必要对室内各表面材料的光反射比，采光口中透光材料的过透射比进行实测。 通过实验，了解材料的光学性质，对光反射比、透射比有一巨象的数值概念，掌握测量方法和注意事项。 二、实验原理和试验方法 （一）、光反射比的实验原理、测量内容和测量方法 光反射比测量方法分为直接测量方法和间接测量法，直接测量法是指用样板比较和光反射比仪直接得出光反射比；间接法是通过被测表面的照度和亮度得出漫反射面的光反射比。下面是间接测量法。 1.实验原理 （1）用照度计测量： P是投射到某一材料表面反射出来的光通量与被该光源的光通量的比值，根据光反射比的定义：光反射比即： φφP=P/因为测量时将使用同一照度计，其受光面积相等， 且，所以对于定向反射的表面，我们可以用上述代入式，整理后得： P=EE P/对于均匀扩散材料也可以近似的用上述式。 可知只要测出材料表面入射光照度E和材料反射光照度Ep，即可计算出其反射比。 （2）用照度计和亮度计测量 用照度计和亮度计分别测量被测表面的照度E和亮度L后按下式计算 πL/EP= 2；被测表面的亮度，cd/m式中：L---E—被测表面的照度，lx 。 2.测量内容 要求测量室内桌面、墙面、墙裙、黑板、地面的光反射比。每种材料面随机取3个点测量3次，然后取其平均值。 3.测量方法 ①将照度计电源（POWER）开关拨至“ON”，检查电池，如果仪器显示窗出现“BATT”字样，则需要换电池； ②将光接收器盖取下，将其光敏表面放在待测处，再将量程（RANGE）开关拨至适当位置，例如，拨在×1挡，测量的仪器显示值乘以量程因子即为测量结果。另有一种自动量程照度计，数字显示中的小数点随照度的大小不同而自动移位，只需将所显示的数字乘以量程因子即为测量结果（单位：lx）。有的照度计为自动量程，直接读取照度计数字即为测量结果。 ③在稳定光源下，将光接收器背面紧贴被测表面，测其入射照度E；然后将光接收器感光面对准被测表面的同一位置，逐渐平移光接收器平行离开测点，照度值逐渐增大并趋于稳定（约300mm左右），读；ρ，即可计算出光反射比Ep取反射照度值 ④测量时尽量缩短入射照度和反光照度间的时间间隔，并尽可能的保持周围光环境的一致性。

回溯法实验(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<<"皇后问题的解为："<

光学实验报告 (一步彩虹全息)

光学设计性实验报告（一步彩虹全息） 姓名： 学号： 学院：物理学院

一步彩虹全息 摘要彩虹全息是用激光记录全息图, 是用白光再现单色或彩色像的一种全息技术。彩虹全息术的关键之处是在成像光路( 即记录光路) 中加入一狭缝, 这样在干板上也会留下狭缝的像。本文研究了一步彩虹全息图的记录和再现景象的基本原理、一步彩虹全息图与普通全息图的区别和联系、一步彩虹全息的实验光路图，探讨了拍摄一步彩虹全息图的技术要求和注意事项，指出了一步彩虹全息图的制作要点, 得出了影响拍摄效果的佳狭缝宽度、最佳狭缝位置及曝光时间对彩虹全息图再现像的影响。 关键词：一步彩虹全息；狭缝；再现 1 光学实验必须要严密，尽可能地减少实验所产生的误差； 2 实验仪器 防震全息台激光器分束镜成像透镜狭缝干板架光学元件架若干干板备件盒洗像设备一套线绳辅助棒扩束镜2个反射镜2个 3 实验原理 3.1 像面全息图 像面全息图的拍摄是用成像系统使物体成像在全息底板上，在引入一束与之相干的参考光束，即成像面全息图，它可用白光再现。再现象点的位置随波长而变化，其变化量取决于物体到全息平面的距离。 像面全息图的像（或物）位于全息图平面上，再现像也位于全息图上，只是看起来颜色有变化。因此在白光照射下，会因观察角度不同呈现的颜色亦不同。 3.2 彩虹全息的本质 彩虹全息的本质是要在观察者与物体的再现象之间形成一狭缝像，使观察者通过狭缝像来看物体的像，以实现白光再现单色像。若观察者的眼睛在狭缝像附近沿垂直于狭缝的方向移动,将看到颜色按波长顺序变化的再现像。若观察者的眼睛位于狭缝像后方适当位置, 由于狭缝对视场的限制, 通过某一波长所对应的狭缝只能看到再现像的某一条带, 其色彩与该波长对应, 并且狭缝像在空间是连

回溯法及其应用

八皇后问题的基本策略及其应用 郭洋洋王刚李晴孙佳 （陕西师范大学计算机科学学院09级计算机科学与技术，西安，710062） 摘要：针对八皇后问题，本文采用回溯法，给出递归与非递归两种算法的设计与分析，并通过实验验证两种算法的性能，得出最佳的算法。 关键词：八皇后；回溯法；递归算法；非递归算法 The Basic Algorithm Strategy For Eight Queens And Its Application Guo Yangyang,Wang Gang,Li Qing, Sun Jia (School of Computer Science ,Shanxi Normal University ,Xi’an ,710062 ) Abstract: Aiming at the problem of Eight Queens,this paper gives Backtracking , and Recursive algorithm and Non-recursive algorithm , and show the design and analysis of the two kinds of algorithms,and through the experiment ,verified the performance of them,getting the most suitable algorithm. Keywords: Eight Queens; Backtracking; Recursive; Non-Recursive 1 引言 八皇后问题由19 世纪著名的数学家高斯在1850 年提出:在8 ×8 格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法. 回溯算法是尝试搜索算法中最为基本的一种算法，其采用了一种“走不通就调头”的思想，作为其控制结构[1]。回溯法在用来求问题的所有解时，要回溯到根，且根节点的所有可行的子树都已被搜索遍才结束。而回溯法在用来求解问题任一解时，只要搜索到问题的一个解就可以结束。这就是以深度优先的方式系统的搜索问题解的回溯法，它适用于解决一些类似n皇后问题等就切方案问题，也可以解决一些最优化问题。 2 问题描述与模型 八皇后问题：在8 ×8 格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法. 例如图一所示：

实验报告：回溯法求解N皇后问题(Java实现)

实验报告 一、实验名称：回溯法求解N皇后问题（Java实现） 二、学习知识： 回溯法：也称为试探法，它并不考虑问题规模的大小，而是从问题的最明显的最小规模开始逐步求解出可能的答案，并以此慢慢地扩大问题规模，迭代地逼近最终问题的解。这种迭代类似于穷举并且是试探性的，因为当目前的可能答案被测试出不可能可以获得最终解时，则撤销当前的这一步求解过程，回溯到上一步寻找其他求解路径。 为了能够撤销当前的求解过程，必须保存上一步以来的求解路径，这一点相当重要。 三、问题描述 N皇后问题：在一个 N * N 的国际象棋棋盘中，怎样放置 N 个皇后才能使 N 个皇后之间不会互相有威胁而共同存在于棋局中，即在 N * N 个格子的棋盘中没有任何两个皇后是在同一行、同一列、同一斜线上。 深度优先遍历的典型案例。 四、求解思路 1、求解思路：最容易想到的方法就是有序地从第 1 列的第 1 行开始，尝试放上一个皇后，然后再尝试第 2 列的第几行能够放上一个皇后，如果第 2 列也放置成功，那么就继续放置第 3 列，如果此时第 3 列没有一行可以放置一个皇后，说明目前为止的尝试是无效的（即不可能得到最终解），那么此时就应该回溯到上一步（即第 2 步），将上一步（第 2 步）所放置的皇后的位置再重新取走放在另一个符合要求的地方…如此尝试性地遍历加上回溯，就可以慢慢地逼近最终解了。 2、需要解决的问题：如何表示一个 N * N 方格棋盘能够更有效？怎样测试当前所走的试探路径是否符合要求？这两个问题都需要考虑到使用怎样的数据结构，使用恰当的数据结构有利于简化编程求解问题的难度。 3、我们使用以下的数据结构： int column[col] = row 表示第 col 列的第 row 行放置一个皇后 boolean rowExists[i] = true 表示第 i 行有皇后 boolean a[i] = true 表示右高左低的第 i 条斜线有皇后（按→↓顺序从1~ 2*N -1 依次编号） boolean b[i] = true 表示左高右低的第 i 条斜线有皇后（按→↑顺序从1~ 2*N -1 依次编号） 五、算法实现 对应这个数据结构的算法实现如下：

光学全息照相实验报告

光学全息照相实验报告

实验II 光学全息照相 光学全息照相是利用光波的干涉现象，以干涉条纹的形式，把被摄物表面光波的振幅和位相信息记录下来，它是记录光波全部信息的一种有效手段。这种物理思想早在1948年伽柏（D.Gabor）即就已提出来了，但直到1960年，随着激光器的出现，获得了单色性和相干性极好的光源时,才使光学全息照相技术的研究和应用得到迅速地发展。光学全息照相在精密计量、无损检测、遥感测控、信息存储和处理、生物医学等方面的应用日益广泛，另外还相应出现了微波全息，X光全息和超声全息等新技术，全息技术已发展成为科学技术上的一个新领域。 本实验通过对三维物体进行全息照相并再现其立体图像，了解全息照相的基本原理及特点，学习拍摄方法和操作技术，为进一步学习和开拓应用这一技术奠定基础。 实验目的

了解光学全息照相的基本原理和主要特点； 学习静态光学全息照相的实验技术； 观察和分析全息全图的成像特性。 仪器用具 全息台、He —Ne 激光器及电源、分束镜、全反射镜、扩束透镜、曝光定时器、全息感光底版等。 基本原理 全息照片的拍摄 全息照相是利用光的干涉原理将光波的振幅和相位信息同时记录在感光板上的过程.相干光波可以是平面波也可以是球面波，现以平面波为例说明全息照片拍摄的原理。如图1所示，一列波函数为t i ae y πυ21=、振幅为a 、频率为υ、波长为λ 的平面单色光波作为参考光垂直入射到感光板上。另一列同频率、波函数为t i r T t i Be be y πυλπ222==??? ??-的相 干平面单色光波从物体出发，称为物光，以入射角θ同时入射到感光板上，物光与参考光产生干涉，在感光板上形成的光强分布为 ax ab b a I cos 222++= (1)

回溯法

第8章回溯法 (1) 8.1概述 (1) 8.1.1 问题的解空间树 (1) 8.1.2 回溯法的设计思想 (2) 8.1.3 回溯法的时间性能 (3) 8.1.4 一个简单的例子——素数环问题 (4) 8.2图问题中的回溯法 (5) 8.2.1 图着色问题 (5) 8.2.2 哈密顿回路问题 (8) 8.3组合问题中的回溯法 (10) 8.3.1 八皇后问题 (10) 8.3.2 批处理作业调度问题 (13) 习题8 (16)

第8章回溯法 教学重点回溯法的设计思想；各种经典问题的回溯思想教学难点批处理作业调度问题的回溯算法 教学内容 和 教学目标 知识点 教学要求 了解理解掌握熟练掌握问题的解空间树√ 回溯法的设计思想√ 回溯法的时间性能√ 图着色问题√ 哈密顿回路问题√ 八皇后问题√ 批处理作业调度问题√ 8.1 概述 回溯法（back track method）在包含问题的所有可能解的解空间树中，从根结点出发，按照深度优先的策略进行搜索，对于解空间树的某个结点，如果该结点满足问题的约束条件，则进入该子树继续进行搜索，否则将以该结点为根结点的子树进行剪枝。回溯法常常可以避免搜索所有的可能解，所以，适用于求解组合数较大的问题。 8.1.1 问题的解空间树 复杂问题常常有很多的可能解，这些可能解构成了问题的解空间（solution space），并且可能解的表示方式隐含了解空间及其大小。用回溯法求解一个具有n个输入的问题，一般情况下，将问题的可能解表示为满足某个约束条件的等长向量X=(x1, x2, …, x n)，其中分量x i（1≤i≤n）的取值范围是某个有限集合S i={a i,1, a i,2, …, a i,r i }，所有可能的解向量构成了问题的解空间。例如，对于有n个物品的0/1背包问题，其可能解由一个等长向量{x1, x2, …, x n}组成，其中x i=1（1≤i≤n）表示物品i装入背包，x i=0表示物品i没有装入背包，则解空间由长度为n的0/1向量组成。当n=3时，其解空间是：

回溯法解0 1背包问题实验报告

实验4 回溯法解0-1背包问题 一、实验要求 1．要求用回溯法求解0-1背包问题； 要求交互输入背包容量，物品重量数组，物品价值数组；2．要求显示结果。3． 二、实验仪器和软件平台 仪器：带usb接口微机 软件平台：WIN-XP + VC++ 三、实验源码 #include \ #include #include #include<> #include using namespace std; template class Knap { public: friend void Init(); friend void Knapsack(); friend void Backtrack(int i); friend float Bound(int i); bool operator<(Knap a)const { if(fl< return true; else return false; } private: ty w; ; cout<>bag[i].v; for(i=0;i

{ bag[i].flag=0; bag[i].kk=i; bag[i].fl=*bag[i].v/bag[i].w; } }void Backtrack(int i){cw+=bag[i].w;if(i>=n) <=c) lag=1; cp+=bag[i].v; Backtrack(i+1); cw-=bag[i].w; cp-=bag[i].v; } if(Bound(i+1)>bestp)lag=0; Backtrack(i+1); }}<=cleft){; b+=bag[i].v; i++; } /bag[i].w * cleft; return b; } void Knapsack() k]=bag[k].flag; lag*bag[k].v; //价值累加 } cout<

光学仪器实验报告

燕山大学 常见光学仪器原理及使用实验报告 L.C.R测试仪 紫外可见分光度计 傅立叶光谱仪 阿贝折射仪 干涉显微镜 数字存储示波器 学院（系）： 年级专业： 学号： 学生姓名： 指导教师：

实验一LCR测试仪 一．实验目的 LCR测试仪能准确并稳定地测定各种各样的元件参数，主要是用来测试电感、电容、电阻的测试仪。它具有功能直接、操作简便等特点，能以较低的预算来满足生产线质量保证、进货检验、电子维修业对器件的测试要求。 二．实验仪器 LCR测试仪 三．实验原理 Vx与Vr均是矢量电压表，Rr是理想电阻。自平衡电桥的意思是：当DUT(Device Under Test)接入电路时，放大器的负反馈配置自动使得OP输入端虚地。Vx准确测定DUT两端电压（DUT的Low电位是0），Vr与Rr测得DUT电流Ix，由此可计算Zx。 LCR测试原理图 HP4275的测试端Hp,Hc,Lp,Lc（下标c代表current, 下标p代表Potentail)，Guard（接地)的配置可导致测试的误差的差异。 提高精度的方法是: 1,Hp,Lp,Hc,Lc尽量接近DUT; 2,减小测试电流Ix 的回路面积&磁通量（关键是分析Ix，要配合使用Guard与Cable最小化回路面积);3,使用Gurard与Cable构建地平面中断信号线间的电场连接，虽然会增加信号线的对地电容（对地电容不影响测试结果），但是会减少信号线的互容。

LCR测试原理图 Guard与Cable的对地寄生阻抗（Zhg,Zlg) 不影响测试结果，电桥平衡时Zlg的两端电压是0，流向Rr的电流不会被Zlg分流，Zhg的分流作用不影响Hp的电压测量。 LCR测试原理图 四．实验步骤 LCR测试仪一般用于测试电感和电容。测量步骤如下： 1.设置测试频率。 2.测试电压或者电流水平。 3.选择测试参数，比如Z、Q、LS（串联电感）、LP（并联电感）、CS(串联电感）、CP（并联电容）、D等。 4.仪器校准，校准主要进行开路、短路校准，高档的仪器要进行负载校准 5.选择测试夹具。 6.夹具补偿。 7.将DUT放在夹具上开始测试。

立式光学仪实验报告doc

立式光学仪实验报告 篇一：光学实验报告 建筑物理 ——光学实验报告实验一：材料的光反射比、透射比测量实验二：采光系数测量 实验三：室内照明实测实验小组成员：指导老师：日期：XX年12月3日星期二实验一、材料的光反射比和光透射比测量 一、实验目的与要求室内表面的反射性能和采光口中窗玻璃的透光性能都会直接或间接的影响室内光环境的好坏，因此，在试验现场采光实测时，有必要对室内各表面材料的光反射比，采光口中透光 材料的过透射比进行实测。通过实验，了解材料的光学性质，对光反射比、透射比有一巨象的数值概念，掌握测量方法和注意事项。 二、实验原理和试验方法 （一）、光反射比的实验原理、测量内容和测量方法光反射比测量方法分为直接测量方法和间接测量法，直接测量法是指用样板比较和光反 射比仪直接得出光反射比；间接法是通过被测表面的照度和亮度得出漫反射面的光反射比。 下面是间接测量法。

1. 实验原理 （1）用照度计测量：根据光反射比的定义：光反射比p是投射到某一材料表面反射出来的光通量与被该光源的光通量的比值，即： p=φp/φ 因为测量时将使用同一照度计，其受光面积相等，且，所以对于定向反射的表面，我们 可以用上述代入式，整理后得：p=ep/e 对于均匀扩散材料也可以近似的用上述式。可知只要测出材料表面入射光照度e和材料反射光照度ep，即可计算出其反射比。（2） 用照度计和亮度计测量 用照度计和亮度计分别测量被测表面的照度e和亮度l 后按下式计算 p=πl/e 式中：l---被测表面的亮度，cd/m2； e—被测表面的照度，lx 。 2.测量内容要求测量室内桌面、墙面、墙裙、黑板、地面的光反射比。每种材料面随机取3个点测量3次，然后取其平均值。 3.测量方法 ①将照度计电源（power）开关拨至“on”，检查电池，如果仪器显示窗出现“batt”字 样，则需要换电池；

回溯法

回溯法 回溯法也是搜索算法中的一种控制策略，但与枚举法不同的是，它是从初始状态出发，运用题目给出的条件、规则，按照深度优秀搜索的顺序扩展所有可能情况，从中找出满足题意要求的解答。回溯法是求解特殊型计数题或较复杂的枚举题中使用频率最高的一种算法。 一、回溯法的基本思路 何谓回溯法，我们不妨通过一个具体实例来引出回溯法的基本思想及其在计算机上实现的基本方法。【例题12.2.1】n皇后问题 一个ｎ×ｎ（1≤n≤100）的国际象棋棋盘上放置ｎ个皇后，使其不能相互攻击，即任何两个皇后都不能处在棋盘的同一行、同一列、同一条斜线上，试问共有多少种摆法？ 输入： n 输出： 所有分案。每个分案为n+1行，格式： 方案序号 以下n行。其中第i行（1≤i≤n）行为棋盘i行中皇后的列位置。 在分析算法思路之前，先让我们介绍几个常用的概念： 1、状态（state） 状态是指问题求解过程中每一步的状况。在ｎ皇后问题中，皇后所在的行位置i(1≤i≤n)即为其时皇后问题的状态。显然，对问题状态的描述，应与待解决问题的自然特性相似，而且应尽量做到占用空间少，又易于用算符对状态进行运算。 2、算符（operater） 算符是把问题从一种状态变换到另一种状态的方法代号。算符通常采用合适的数据来表示，设为局部变量。n皇后的一种摆法对应1．．ｎ排列方案（a1，…，a n）。排列中的每个元素a i对应ｉ行上皇后的列位置（1≤i≤n）。由此想到，在ｎ皇后问题中，采用当前行的列位置i(1≤i≤n)作为算符是再合适不过了。由于每行仅放一个皇后，因此行攻击的问题自然不存在了，但在试放当前行的一个皇后时，不是所有列位置都适用。例如(l，ｉ)位置放一个皇后，若与前1．．l-1行中的j行皇后产生对角线攻击(｜ｊ－l｜=｜a j －i｜)或者列攻击(ｉ≠a j)，那么算符ｉ显然是不适用的，应当舍去。因此，不产生对角线攻击和列攻击是ｎ皇后问题的约束条件，即排列（排列a1，…，a i，…，a j，…，a n）必须满足条件(｜ｊ－ｉ｜≠｜a j－a i｜) and (a i≠a j) (1≤i，j≤n)。 3、解答树（analytic tree） 现在让我们先来观察一个简单的ｎ皇后问题。设ｎ＝4，初始状态显然是一个空棋盘。 此时第一个皇后开始从第一行第一列位置试放，试放的顺序是从左至右、自上而下。每个棋盘由４个数据表征相应的状态信息（见下图）： （××××）