实验四Bezier曲线生成算法实现

《计算机图形学》实验报告

(实验四,.Bezier曲线生成算法实现)

一、实验目的及要求

三次Bezier曲线及de Casteljau算法以及b样条曲线

二、理论基础

详见教材！

三、算法设计与分析

Bezier曲线生成算法

int degree=3,i,x,y;

float t;

float coeff_x[4]={50.0,200.0,200.0,500.0};

float coeff_y[4]={50.0,300.0,50.0,200.0};

pDC->MoveTo(coeff_x[0],coeff_y[0]);

for(i=1;i<=3;i++)

{

pDC->LineTo(coeff_x[i],coeff_y[i]);

}

for(t=0;t<=1;t+=0.001)

{

x=hornbez(degree,coeff_x,t);

y=hornbez(degree,coeff_y,t);

pDC->SetPixel(x,y,RGB(0,0,0));

}

float CMy2View::hornbez(int degree,float coeff[],float t) {

int i,n_choose_i;

float fact,t1,aux;

t1=1.0-t;fact=1.0;

n_choose_i=1;

aux=coeff[0]*t1;

for(i=1;i

{

fact =fact*t;

n_choose_i=n_choose_i*(degree-i+1)/i;

aux=(aux+fact*n_choose_i*coeff[i])*t1;

}

aux=aux+fact*t*coeff[degree];

return aux;

}

de Casteljau算法

void CTuView::bezpoint(int degree,int npoints,float *coeff,float points[]) {

float t,delt;

int i;

delt=1.0/(float)npoints;

t=0.0;

for (i=0;i

{

points[i]=decas(degree,coeff,t);

t=t+delt;

}

}

float CTuView::decas(int degree,float *coeff,float t)

{

int r,i;

float t1;

float coeffa[10];

t1=1.0-t;

for (i=0;i<=degree;i++)

coeffa[i]=coeff[i];

for(r=1;r<=degree;r++)

for (i=0;i<=degree-r;i++)

{

coeffa[i]=t1*coeffa[i]+t*coeffa[i+1];

}

return coeffa[0];

}

主函数：

void CTuView::OnDraw(CDC* pDC)

{

CTuDoc* pDoc = GetDocument();

ASSERT_VALID(pDoc);

// TODO: add draw code for native data here

int degree=5,npoints=1000,i;

float coeffx[]={10,40,265,300,400,500};

float coeffy[]={20,130,160,90,300,100};

float points1[1000],points2[1000];

for (i=0;i

{

pDC->MoveTo((int)coeffx[i],(int)coeffy[i]);

pDC->LineTo ((int)coeffx[i+1],(int)coeffy[i+1]);

}

bezpoint(degree,npoints,coeffx,points1);

bezpoint(degree,npoints,coeffy,points2);

for(i=0;i

pDC->SetPixel((int)points1[i],(int)points2[i],RGB(123,123,123));

}

B样条曲线

void CBView::bsp(int degree,int l,float *coeff,float *knot,int dense,float *points,int *point_num)

{

int i,ii;

float u;

*point_num=0;

for(i=degree-1;i

{

if(knot[i+1]>knot[i])

for(ii=0;ii

{

u=knot[i]+ii*(knot[i+1]-knot[i])/dense;

points[*point_num]=deboor(degree,coeff,knot,u,i);

*point_num=(*point_num)+1;

}

}

}

float CBView::deboor(int degree,float *coeff,float *knot,float u,int i) {

int k,j;

float t1,t2;

float coeffa[30];

for (j=i-degree+1;j<=i+1;j++)

coeffa[j]=coeff[j];

for (k=1;k<=degree;k++)

for(j=i+1;j>=i-degree+k+1;j--)

{

t1=(knot[j+degree-k]-u)/(knot[j+degree-k]-knot[j-1]);

t2=1.0-t1;

coeffa[j]=t1*coeffa[j-1]+t2*coeffa[j];

}

return coeffa[i+1];

}

主函数：

void CBView::OnDraw(CDC* pDC)

{

CBDoc* pDoc = GetDocument();

ASSERT_VALID(pDoc);

// TODO: add draw code for native data here

int k,n;

int degree,i,a;

int dense=290,l=5;

float coeffx[]={10,40,265,300,400,500,600};

float coeffy[]={20,130,160,90,300,100,300};

float points1[2000],points2[2000];

float knot[]={0,0,0,0,0,1,2,2,2,2,2};

int *point_num;

k=5,n=5;/*n+1个点*/

degree=5;

a=0;

point_num=&a;

for (i=0;i<6;i++)

{

pDC->MoveTo((int)coeffx[i],(int)coeffy[i]);

pDC->LineTo ((int)coeffx[i+1],(int)coeffy[i+1]);

}

bsp(degree,l,coeffx,knot,dense,points1,point_num);

bsp(degree,l,coeffy,knot,dense,points2,point_num);

for(i=0;i<2000;i++)

pDC->SetPixel((int)points1[i],(int)points2[i],RGB(123,123,123)); }

四、程序调试及结果的分析

1、de Casteljau图形曲线

2、b样条曲线

四、实验心得及建议

由于最近考试，这次的实验报告提交的比较晚。上次交了三次Bezier曲线，这次补上de Casteljau 算法以及b样条曲线的！

评语

常见OTDR测试曲线解析

常见OTDR测试曲线解析 一、正常曲线 一般为正常曲线图, A 为盲区, B 为测试末端反射峰。测试曲线为倾斜的,随着距离的曾长，总损耗会越来越大。用总损耗( dB )除以总距离( Ｋｍ)就是该段纤芯的平均损耗( dB/Km ）。 二、光纤存在跳接点 中间多了一个反射峰,因为很有可能中间是一个跳接点,现城域网光缆中,比较常见。如:现主干光缆由汇接局至光缆交接箱,当有需求时，需由光交接箱布放光缆至用户端，光交接箱就需跳纤联接,所以在测试这样的纤芯时,就会出现像图中这样的曲线图。当然也会有例外的情况,总之，能够出现反

射峰,很多情况是因为末端的光纤端面是平整光滑的。端面越平整，反射峰越高。例如在一次中断割接当中,当光缆砍断以后,测试的曲线应该如光路存在断点图所示，但当你再测试时,在原来的断点位置出现反射峰的话,那说明现场的抢修人员很有可能已经把该纤芯的端面做好了。 三、异常情况 出现图中这种情况,有可能是仪表的尾纤没有插好,或者光脉冲根本打不出去，再有就是断点位置比较进,所使用的距离、脉冲设置又比较大，看起来就像光没有打出去一样。出现这种情况，1、要检查尾纤连接情况; ２、就是把OTD Ｒ的设置改一下,把距离、脉冲调到最小，如果还是这种情况的话,可以判断: １、尾纤有问题；２、OTＤR 上的识配器问题; 3、断点十分近，OTDＲ不足以测试出距离来。如果是尾纤问题，只要换一根尾纤就知道,不行的话就要试着擦洗识配器，或就近查看纤芯了。 四、非反射事件

1、这种情况比较多见，曲线中间出现一个明显的台阶，多数为该纤芯打折，弯曲过小，受到外界损伤等因素，多为故障点。 2、若光纤模式、折射率不一样，接续时也会出现此情况，常见光纤G65１光纤(标准单模光纤，B１光缆)，G６53光纤(色散位移光纤,B2光缆）。造成这种现象的原因是由于接头两侧光纤的背向散射系数不一样，接头后光纤背向散射系数大于前段光纤背向散射系数，而从另一端测则情况正好相反,折射率不同也有可能产生增益现象。所以要想避免这种情况，只要用双向测试法就可以了。 五、光纤存在断点 这种情况一定要引起注意！曲线在末端没有任何反射峰就掉下去了，分析:１如果知道纤芯原来的距离,1、在没有到达纤

算法设计与分析实验指导2014版

算法分析 设计与实验 王 源 二0一四年十月

实验一：分治算法及其应用 实验要求： 掌握分治算法的原理. 掌握递归算法及递归程序的设计. 能用程序设计语言设计求解典型问题的算法 实验题： 1、棋盘覆盖问题：在一个2k ×2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。用图示的4种不同形态的L 型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L 型骨牌不得重叠覆盖。 2、最近对问题：设p 1=(x 1,y 1), p 2=(x 2,y 2), …, p n =(x 1,y 1)，是平面上n 个点构成的集合S ，最近对问题就是找出集合S 中距离最近的点对。 3、（选作）最大子段和问题：给定由n 个整数（可能有负整数）组成的序列(a 1, a 2, …, a n )， 最大子段和问题要求该序列形如 的最大值（1≤i ≤j ≤n ），当序列中所有整数均为负 整数时，其最大子段和为0。例如，序列(-20, 11, -4, 13, -5, -2)的最大子段和为 。 ∑=j i k k a ∑==4 220 k k a

实验要求： 基本动态规划法的原理方法； 能用程序设计语言实现求解背包问题的算法 实验题： 1、最长公共子序列问题：对给定序列X=(x1, x2,…, xm)和序列Z=(z1, z2,…, zk)，Z是X的子序列当且仅当存在一个递增下标序列(i1, i2,…, ik)，使得对于所有j=1, 2, …, k，有（1≤ij ≤m）。给定两个序列X和Y，当序列Z既是X的子序列又是Y的子序列时，称Z是序列X 和Y的公共子序列最长公共子序列问题就是在序列X和Y中查找最长的公共子序列。 2、（选作）多段图的最短路径问题：设图G=(V, E)是一个带权有向图，如果把顶点集合V 划分成k个互不相交的子集Vi (2≤k≤n, 1≤i≤k)，使得E中的任何一条边(u, v)，必有u∈Vi，v∈Vi+m (1≤i≤k, 1＜i+m≤k)，则称图G为多段图，称s∈V1为源点，t∈Vk为终点。多段图的最短路径问题求从源点到终点的最小代价路径。 3、

算法设计实验3

实验三：动态规划法 【实验目的】 应用动态规划算法思想求解矩阵连乘的顺序问题。 【实验要求】 应用动态规划算法的最优子结构性质和子问题重叠性质求解此问题。分析动态规划算法的基本思想，应用动态规划策略写出算法及相应的程序，求解此题。要读懂读透A[i,j]， A[1,n]=A[1,k] ×A[k+1,n]，m[i][j]，s[i][j]各式所表达的含义并正确加以应用。m[i][j]的递归定义： 0 （i=j ） m[i][j]= min{m[i][k]＋m[k+1][j]+n i-1n k n j （i #include class MatrixChain { public: MatrixChain(int mSize); //创建二维数组m和s，一维数组p，并初始化

炉温测试板制作及曲线测试规范(20200517094721)

炉温测试板制作及曲线测试规范 1、目的: 规范SMT炉温测试方法，为炉温设定、测试、分析提供标准，确保产品质量。为炉温曲线的 制作、确认和跟踪过程的一致性提供准确的作业指导； 2、范围: 本规范适用于公司PCBA部SMT车间所有炉温设定、测试、分析及监控。 3.定义: 3.1升温阶段：也叫预热区，从室温到120度，用以将PCBA从环境温度提升到所要求的活性 温度；升温斜率不能超过3°C度/s；升温太快会造成元件损伤、会出现锡球现象，升 温太慢锡膏会感温过度从而没有足够的时间达到活性温度；通常时间控制在60S左右； 3．2恒温阶段：也叫活性区或浸润区，用以将PCBA从活性温度提升到所要求的回流温度； 一是允许不同质量的元件在温度上同质；二是允许助焊剂活化，锡膏中挥发性物质得到 有利挥发，一般普遍的锡膏活性温度是120-150度，时间在60-120S之间，升温斜率一 般控制在1度/S左右；PCBA上所有元件要达到熔锡的过程，不同金属成份的锡膏熔点 不同，无铅锡膏（SN96/AG3.5/CU0.5）熔点一般在217-220度，有铅（SN63/PB37）一 般在183度含银（SN62/PB36/AG2）为179度； 3.3回流阶段：也叫峰值区或最后升温区，这个区将锡膏在活性温度提升到所推荐的峰值温 度，加热从熔化到液体状态的过程；活性温度总是比熔点低，而峰值温度总在熔点之上， 典型的峰值温度范围是（SN63/PB37）从205-230度；无铅（SN96/AG3.5/CU0.5）从235-250 度；此段温度设定太高会使升温斜率超过2-5度/S，或达到比所推荐的峰值高，这种情 况会使PCB脱层、卷曲、元件损坏等；峰值温度：PCBA在焊接过程中所达到的最高温度； 3.4冷却阶段：理想的冷却曲线一般和回流曲线成镜像，越是达到镜像关系，焊点达到的固 态结构越紧密，焊点的质量就越高，结合完整性就越好，一般降温斜率控制在4度/S； 4、职责: 4．1 工程部 4.1.1工程师制定炉温测试分析标准，炉温测试员按此标准测试、分析监控炉温。 4.1.2 指导工艺技术员如何制作温度曲线图； 4.1.3 定义热电偶在PCB上的测试点，特别是对一些关键的元件定位； 4.1.4基于客户要求和公司内部标准来定义温度曲线的运行频率；

《算法设计与分析》实验指导

《算法分析与设计》实验指导.

实验一锦标赛问题 [实验目的] 1.基本掌握分治算法的原理. 2.能用程序设计语言求解锦标赛等问题的算法; [预习要求] 1.认真阅读数据结构教材和算法设计教材,了解分治算法原理; 2.设计用分治算法求解背包问题的数据结构与程序代码. [实验题] 【问题描述】设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表： （1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能参赛一次； （3）循环赛在n-1天内结束。 请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1≤i≤n，1≤j≤n-1。 [实验提示] 我们可以按分治策略将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。 1 2 3 4 5 6 7 1 （1）（2）（3） 图1 2个、4个和8个选手的比赛日程表 图1所列出的正方形表（3）是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这

样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。 [实验步骤] 1.设计并实现算法并准备测试用例,修改并调试程序,直至正确为止; 2.应用设计的算法和程序求锦标赛问题; 3.去掉测试程序,将你的程序整理成功能模块存盘备用. [实验报告要求] 1.阐述实验目的和实验内容; 2.阐述分治算法原理; 3.提交实验程序的功能模块; 4.记录最终测试数据和测试结果。 [思考与练习] 【金块问题】老板有一袋金块(共n块，n是2的幂（n>=2）），将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，请用最少的比较次数找出最重和最轻的金块。

实验一 简单算法设计

实验一简单算法设计 一.实验目的和要求 1. 理解算法设计与分析的基本概念，理解解决问题的算法设计与实现过程； 2. 掌握简单问题的算法设计与分析，能设计比较高效的算法； 3. 熟悉C/C++语言等的集成开发环境，掌握简单程序设计与实现的能力； 二．实验内容 (一)相等元素问题 1.问题描述先排序函数，再查找函数。 #define size 100 Typedef strat { Int Array[size] Int listlength }List List a; Main() { 1、输入 2、排序 3、查找 4、输出 } 元素唯一性问题：给出一个整数集合，假定这些整数存储在数组A[1…n]中，确定它们中是否存在两个相等的元素。请设计出一个有效算法来解决这个问题，你的算法的时间复杂性是多少？ 2. 测试数据 输入： 9 71 25 64 38 52 5 31 19 45 26 35 17 92 53 24 6 57 21 12 34 2 17 86 75 33 15 87 32 7 84 35 26 45 78 96 52 22 37 65 9 43 21 3 33 91 输出：No Yes No 3. 设计与实现的提示 算法最坏情况和平均情况的时间复杂性是衡量算法优劣的重要指标，算法设计要求尽可能设计比较高效的算法。 (二) 整数集合分解（选做） 1.问题描述

设计算法把一个n个元素的整数集合（n为偶数）分成两个子集S1和S2，使得：每个新的集合中含有n/2个元素，且S1中的所有元素的和与S2中的所有元素的和的差最大。 2. 测试数据 输入： 68 25 34 16 2 37 3 95 76 57 21 13 4 78 29 6 17 39 51 20 43 12 28 3 48 59 14 32 47 51 42 61 9 24 52 78 65 2 37 78 51 73 29 7 26 95 37 2 输出： 2 3 4 6 12 13 16 17 20 21 25 29 34 37 39 43 51 57 68 76 78 95 2 2 3 7 9 1 4 24 26 28 29 32 37 37 42 47 48 51 51 52 59 61 62 65 73 78 95 3. 设计与实现的提示 本题可以有多种方法。算法时间复杂性是选取算法的重要依据。输出的两个新整数集合要求按照从小到大排序后输出。该排序步骤对算法时间复杂性的影响在此不计。

动态模量主曲线生成方法

主曲线使用方法 主曲线是一种将有限试验结果扩展至无限范畴的方法，它的前提是实验材料的力学特性具有时温特效，尤其是有机材料。 在时间历程上，测试4-5个温度（或者荷载）条件下的试验数据，然后，将其绘制在时间（x）-试验数据（y）的双对数log-log坐标轴上，使用时-温转换，得到主曲线。时-温转化的方法一般是，首先选择关注温度，并将该温度作为主温度；然后，顺次将不同温度下的数据沿时间（x）轴进行平移，平移多少由转换因子大小决定；最终，得到主曲线。 转换因子大小与温度值有关，可以选择WLF公式，也可以选择Arrhenius(阿尼乌斯)公式来计算，二者均可以从很多文献里获取。当不同的温度的曲线向主温度曲线处平移时，转换因子的正负便与平移方向有关，向左移是“+”，向右移是“-”(突然想起高中数学老师教的“+左-右”)。 有了上边的基本概念，就可以进行实际操作了，很简单，所有的操作都是在EXCEL表格里进行（在雅虎搜索里输入NCHRP09-29_mastersolver2-2.xls，点搜索后获取），只是要保证EXCEL 里装了solver规划求解宏（以OFFICE2007为例，点击左上角windows-Excel选项-加载项-规划求解加载项-转到-规划求解加载项-确定，如下图所示）。

在EXCEL表格DATA的sheet里，输入动态模量值和混合料其他体积参数，然后进入FIT的sheet里，将C4:C7里的数据拷贝到B4:B7，点击“规划求解”启动宏，目标单元格选择为Ⅰ23，“等于”这一项选择“最小值”，可变单元格选择为B4:B7，点击“求解”便可得到最小二乘法所列的最佳值。一般情况下，只需要一次计算就够了，个别的情况，可在使用一次规划求解，看看计算的结果不会变为止（第二次规划求解时不需要再拷贝C4:C7的数据）。

算法设计与实验报告讲解

算法设计与分析实验报告 学院：信息学院 专业：物联网1101 姓名：黄振亮 学号：20113379 2013年11月

目录 作业1 0-1背包问题的动态规划算法 (7) 1.1算法应用背景 (3) 1.2算法原理 (3) 1.3算法描述 (4) 1.4程序实现及程序截图 (4) 1.4.1程序源码 (4) 1.4.2程序截图 (5) 1.5学习或程序调试心得 (6) 作业2 0-1背包问题的回溯算法 (7) 2.1算法应用背景 (3) 2.2算法原理 (3) 2.3算法描述 (4) 2.4程序实现及程序截图 (4) 2.4.1程序源码 (4) 2.4.2程序截图 (5) 2.5学习或程序调试心得 (6) 作业3循环赛日程表的分治算法 (7) 3.1算法应用背景 (3) 3.2算法原理 (3) 3.3算法描述 (4) 3.4程序实现及程序截图 (4)

3.4.1程序源码 (4) 3.4.2程序截图 (5) 3.5学习或程序调试心得 (6) 作业4活动安排的贪心算法 (7) 4.1算法应用背景 (3) 4.2算法原理 (3) 4.3算法描述 (4) 4.4程序实现及程序截图 (4) 4.4.1程序源码 (4) 4.4.2程序截图 (5) 4.5学习或程序调试心得 (6)

作业1 0-1背包问题的动态规划算法 1.1算法应用背景 从计算复杂性来看,背包问题是一个NP难解问题。半个世纪以来,该问题一直是算法与复杂性研究的热点之一。另外,背包问题在信息加密、预算控制、项目选择、材料切割、货物装载、网络信息安全等应用中具有重要的价值。如果能够解决这个问题那么则具有很高的经济价值和决策价值，在上述领域可以获得最大的价值。本文从动态规划角度给出一种解决背包问题的算法。 1.2算法原理 1.2.1、问题描述： 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi ∈{0,1}, ?∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。 1.2.2、最优性原理： 设(y1,y2,…,yn)是 (3.4.1)的一个最优解.则(y2,…,yn)是下面相应子问题的一个最优解: 证明:使用反证法。若不然,设(z2,z3,…,zn)是上述子问题的一个最优解,而(y2,y3,…,yn)不是它的最优解。显然有 ∑vizi > ∑viyi (i=2,…,n) 且 w1y1+ ∑wizi<= c 因此 v1y1+ ∑vizi (i=2,…,n) > ∑ viyi, (i=1,…,n) 说明(y1,z2, z3,…,zn)是(3.4.1)0-1背包问题的一个更优解,导出(y1,y2,…,yn)不是背包问题的最优解,矛盾。 1.2.3、递推关系：

算法设计与分析实验指导书样本

算法设计与分析实验指导书

实验一 C/C++环境及递归算法( 4学时) 一、实验目的与要求 1、熟悉C/C++语言的集成开发环境; 2、经过本实验加深对递归过程的理解 二、实验内容: 掌握递归算法的概念和基本思想, 分析并掌握排列问题的递归算法和Hanoi塔问题的递归算法。 三、实验题 1、设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。任意输入一 串整数或字符, 输出结果能够用递归方法实现整数或字符的全排列。 2、设a,b,c是3个塔座。开始时, 在塔座a上有一叠共n个圆盘, 这些圆 盘自下而上, 由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上, 并仍按同样顺序叠置。 四、实验步骤 1．理解算法思想和问题要求; 2．编程实现题目要求; 3．上机输入和调试自己所编的程序; 4．验证分析实验结果; 5．整理出实验报告。 实验提示 1、 #include inline void swap(int &a,int &b) { int temp=a; a=b;

b=temp; } void perm(int list[],int k,int m) { if(k==m) { for(int i=0;i<=m;i++) cout<

算法设计实验报告一(简单算法设计)

实验报告一 课程C++ 实验名称简单算法设计第 1 页专业_数学与应用数学_ __ 班级__ 双师一班学号105012011056 姓名陈萌 实验日期：2013 年 3 月9 日报告退发(订正、重做) 一、实验目的 1. 理解算法设计与分析的基本概念，理解解决问题的算法设计与实现过程； 2. 掌握简单问题的算法设计与分析，能设计比较高效的算法； 3. 熟悉C/C++语言等的集成开发环境，掌握简单程序设计与实现的能力。 二、实验内容 (一)相等元素问题 1.问题描述 元素唯一性问题：给出一个整数集合，假定这些整数存储在数组A[1…n]中，确定它们中是否存在两个相等的元素。请设计出一个有效算法来解决这个问题，你的算法的时间复杂性是多少？ 2. 具体要求（若在ACM平台上提交程序，必须按此要求）――平台上1767题 输入：输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个测试例的数据由两行组成，其中第一行为一个正整数n (n<=500)，表示整数序列的长度，第二行给出整数序列，整数之间用一个空格隔开。 输出：对于每个测试例输出一行，若该组测试例中存在两个相等的元素则输出”Yes”，否则，输出”No”。每个测试例的输出数据用一行表示。 3. 测试数据 输入：3 10 9 71 25 64 38 52 5 31 19 45 16 26 35 17 92 53 24 6 57 21 12 34 2 17 86 75 33 20 15 87 32 7 84 35 26 45 78 96 52 22 37 65 9 43 21 3 33 91 输出：No Yes No (二) 整数集合分解 1.问题描述 设计算法把一个n个元素的整数集合（n为偶数）分成两个子集S1和S2，使得：每个新的集合中含有n/2个元素，且S1中的所有元素的和与S2中的所有元素的和的差最大。 2. 具体要求（若在ACM平台上提交程序，必须按此要求）――平台上1768题 输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个测试例的数据由两行组成，其中第一行为一个正整数n (n为偶数，且n<=500)，表示原整数集合的长度，第二行给出这n个整数序列，整数之间用一个空格隔开。 输出：对于每个测试例输出两行，分别表示新生成的整数集合。其中，第一行是元素和比较小的整数集合，第二行是元素和比较大的整数集合，整数之间用一个空格隔开。两个测

算法设计与分析课程设计-实验指导书

算法设计与分析课程设计 实验指导书 上海第二工业大学 计算机与信息学院软件工程系

一、运动员比赛日程表 设有n=2k个运动员要进行网球比赛。设计一个满足以下要求的比赛日程表： ●每个选手必须与其它n-1个选手各赛一次 ●每个选手一天只能赛一次 ●循环赛一共进行n-1天 1、运用分治策略，该问题的递归算法描述如下，根据算法编制程序并上机 通过。 输入：运动员人数n（假定n恰好为2的i次方） 输出：比赛日程表A[1..n,1..n] 1. for i←1 to n //设置运动员编号 2. A[i,1]←i 3. end for 4. Calendar(0,n) //位移为0，运动员人数为n。 过程Calendar(v, k) //v表示位移（v=起始行-1），k表示运动员人数。 1. if k=2 then //运动员人数为2个 2. A[v+2,2]←A[v+1,1] //处理右下角 3. A[v+1,2]←A[v+2,1]//处理右上角 4. else 5. Calendar(v,k/2) //假设已制定了v+1至v+k/2运动员循环赛日程表 6. Calendar(v+k/2,k/2) //假设已制定了v+k/2+1至v+k运动员循环赛日程表 7. comment：将2个k/2人组的解，组合成1个k人组的解。 8. for i←1 to k/2 9. for j←1 to k/2 10. A[v+i+k/2,j+k/2]←A[v+i,j] //沿对角线处理右下角 11. end for 12. end for 13. for i←k/2+1 to k 14. for j←1 to k/2 15. A[v+i-k/2,j+k/2]←A[v+i,j] //沿对角线处理右上角 16. end for 17. end for 18. end if 2、编制该问题的非递归算法，上机通过。 将如上文件保存在命名为“学号+姓名+实验一”的文件夹中并上传到指定的服务器。

南京邮电大学算法设计实验报告——动态规划法

实验报告 （2009/2010学年第一学期） 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程

实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。 任务：用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。 要求：掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件：计算机 软件：Visual C++

三、实验原理及内容（包括操作过程、结果分析等） 1、最长公共子序列（LCS）问题是：给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n}，要求找出X和Y的一个最长公共子序列。 例如：X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列，检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。 2、分析LCS问题特征可知，如果Z={z1,z2,……，z k}为它们的最长公共子序列，则它们一定具有以下性质： （1）若x m=y n，则z k=x m=y n，且Z k-1是X m-1和Y n-1的最长公共子序列； （2）若x m≠y n且x m≠z k，则Z是X m-1和Y的最长公共子序列； （3）若x m≠y n且z k≠y n，则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题： 若x m=y m，则进一步分解为求解两个（前缀）子字符序列X m-1和Y n-1的最长公共子序列问题； 如果x m≠y n，则原问题转化为求解两个子问题，即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。 由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度，由上述分析可得如下递推式： 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。

常见OTDR测试曲线解析80569

常见OTDＲ测试曲线解析 一、正常曲线 一般为正常曲线图， A 为盲区，B 为测试末端反射峰。测试曲线为倾斜的，随着距离的曾长，总损耗会越来越大。用总损耗( dB )除以总距离（Ｋｍ）就是该段纤芯的平均损耗（ｄB/Km ）。 二、光纤存在跳接点 中间多了一个反射峰，因为很有可能中间是一个跳接点，现城域网光缆中,比较常见。如：现主干光缆由汇接局至光缆交接箱，当有需求时,需由光交接箱布放光缆至用户端,光交接箱就需跳纤联接,所以在测试这样的纤芯时，就会出现像图

中这样的曲线图。当然也会有例外的情况,总之，能够出现反射峰,很多情况是因为末端的光纤端面是平整光滑的。端面越平整,反射峰越高。例如在一次中断割接当中,当光缆砍断以后，测试的曲线应该如光路存在断点图所示,但当你再测试时,在原来的断点位置出现反射峰的话,那说明现场的抢修人员很有可能已经把该纤芯的端面做好了。 三、异常情况 出现图中这种情况，有可能是仪表的尾纤没有插好,或者光脉冲根本打不出去,再有就是断点位置比较进，所使用的距离、脉冲设置又比较大，看起来就像光没有打出去一样。出现这种情况，1、要检查尾纤连接情况；2 、就是把OTD Ｒ的设置改一下,把距离、脉冲调到最小,如果还是这种情况的话，可以判断：１、尾纤有问题；２、OTDR 上的识配器问题；3、断点十分近，OTDＲ不足以测试出距离来。如果是尾纤问题，只要换一根尾纤就知道,不行的话就要试着擦洗识配器,或就近查看纤芯了。 四、非反射事件

1、这种情况比较多见，曲线中间出现一个明显的台阶，多数为该纤芯打折,弯曲过小,受到外界损伤等因素，多为故障点。 2、若光纤模式、折射率不一样，接续时也会出现此情况,常见光纤Ｇ６５1光纤（标准单模光纤，B１光缆），Ｇ6５3光纤(色散位移光纤，B２光缆）。造成这种现象的原因是由于接头两侧光纤的背向散射系数不一样,接头后光纤背向散射系数大于前段光纤背向散射系数,而从另一端测则情况正好相反，折射率不同也有可能产生增益现象。所以要想避免这种情况，只要用双向测试法就可以了。 五、光纤存在断点 这种情况一定要引起注意！曲线在末端没有任何反射峰就掉下去了，分析：1如果知道纤芯原来的距离,1、在没有到达

算法与设计实验报告

算法与分析实验报告软件工程专业 安徽工业大学 指导老师：许精明

实验内容 1：杨辉三角 2：背包问题 3：汉诺塔问题 一：实验目的 1：掌握动态规划算法的基本思想，学会用其解决实际问题。 2：通过几个基本的实验，提高算法分析与设计能力，提高动手操作能力和培养良好的编程习惯。 二：实验内容 1：杨辉三角 2：背包问题 3：汉诺塔问题 实验一：杨辉三角

问题分析： ①每行数字左右对称，由1开始逐渐变大，然后变小，回到1。 ②第n行数之和为2^n。 ③下一行每个数字等于上一行的左右两个数字之和。 算法设计及相关源代码： public void yanghui(int n) { int[] a = new int[n]; if(n==1){ System.out.println(1); }else if(n==2) { System.out.print(1 + " " +1); }else{ a[1]=1; System.out.println(a[1]); a[2]=1;

System.out.println(a[1]+" "+a[2]); for(int i=3;i<=n;i++){ a[1]=a[i]=1; for(int j=i-1;j>1;j--){ a[j]=a[j]+a[j-1]; } for(int j=1;j<=i;j++){ System.out.print(a[j]+" "); } System.out.println(); } } } 实验结果：n=10 实验二：0-1背包问题 问题分析：：令V(i,j)表示在前i(1<=i<=n)个物品中能够装入容量为就 j(1<=j<=C)的背包中的物品的最大价值，则可以得到如下的动态规划函数: (1) V(i,0)=V(0,j)=0 (2) V(i,j)=V(i-1,j) j

炉温曲线测试规范

炉温曲线测试规范 1．目的 本规范规定了炉温曲线的测试周期、测试方法等，以通过定期的、正确的炉温曲线测试确定最佳的曲线参数，最终保证PCB装配的最佳、稳定的质量，提高生产效率和产品直通率。 2．定义 2.1回流曲线 在使用焊膏工艺方式中，通过固定在PCB表面的热电偶及数据采集器测试出PCB在回流焊炉中时间与温度的可视数据集合，根据焊膏供应商推荐的曲线，对不同产品通过适当调整温度设置及传输链的速度所得到的最佳的一组炉温设置参数。 2.2固化曲线 在使用点胶或印胶工艺方式中，通过固定在PCB表面的热电偶及数据采集器测试出PCB在固化炉中时间与温度的可视数据集合，根据焊膏供应商推荐的曲线，对不同产品通过适当调整温度设置及传输链的速度所得到的最佳的一组炉温设置参数。 2.3基本产品 指在一个产品系列中作为基本型的产品，该系列的其它产品都在此基础上进行贴装状态更改或对印制板进行少量的改版，一般情况下一个产品系列同一功能的印制板其图号仅在版本号上进行区分，如“***-1”与“***-2”或“***V1.1”与“***V1.2”等。 2.4派生产品 指由于设计贴装状态更改、或印制板在原有基础上进行少量的改版所生成的其所改动的CHIP 类器件数量未超过50只、同时没有对外形尺寸大于□20mm×20mm的IC器件（不包括BGA、CSP等特殊封装的器件）的数量进行调整的产品。 2.5全新产品 指产品公司全新开发、设计贴装状态更改或印制板在原有基础上改版时所生成的其所改动的CHIP类器件数量超过50只、或对外形尺寸大于□20mm×20mm的IC器件的数量进行调整的产品。凡状态更改中增加或减少了BGA、CSP等特殊封装的器件的产品均视为全新产品。 2.6测试样板 指用来测试炉温的实装板，该板必须贴装有与用来测试的生产状态基本一致的元器件。 3．职责 4．炉温测试管理 4.1炉温测试周期：原则上工程师根据当月所生产的产品应每月测试一次，将测试结果记录在“炉温参数设置登记表”上，并将炉温曲线打印存档。 4.2原则上全新产品必须经过炉温测试，确定准确的炉温设置参数，但对批量小于100套的全新工程师可以根据原有的相似产品根据观察实物的焊接效果进行自行调整。 4.3全新产品在炉温测试时应领取新的测试样板，派生产品可采用原基本产品的测试样板进行炉温测试，以针对不同的产品及状态设置相应准确的炉温参数。 5．测试准备 5.1炉温测试使用DataPaq炉温测试仪，热电偶使用K型。 5.2选择测温点。 热电偶应该安装在能代表PCB板上最热与最冷的连接点上(引脚到焊盘的连接点上)，以及热敏感器件和其它高质量器件上，以保证其被足够地加热，一般测温点至少在三点及以上。测温点按以

算法设计与分析实验报告 统计数字问题

算法设计与分析实验报告 实验名称统计数字问题评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 1、掌握算法的计算复杂性概念。 2、掌握算法渐近复杂性的数学表述。 3、掌握用C++语言描述算法的方法。 4．实现具体的编程与上机实验，验证算法的时间复杂性函数。 二.实验内容 统计数字问题 1、问题描述 一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2， (9) 2、编程任务 给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0，1，2， (9) 三.程序算法 将页码数除以10，得到一个整数商和余数，商就代表页码数减余数外有多少个1—9作为个位数，余数代表有1—余数本身这么多个数作为剩余的个位数，此外，商还代表1—商本身这些数出现了10次，余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。 四.程序代码 #include int s[10]; //记录0~9出现的次数 int a[10]; //a[i]记录n位数的规律 void sum(int n,int l,int m) { if(m==1) {

int zero=1; for(int i=0;i<=l;i++) //去除前缀0 { s[0]-=zero; zero*=10; } } if(n<10) { for(int i=0;i<=n;i++) { s[i]+=1; } return; }//位数为1位时,出现次数加1 //位数大于1时的出现次数 for(int t=1;t<=l;t++)//计算规律f(n)=n*10^(n-1) { m=1;int i; for(i=1;i

算法设计与分析实验报告

算法设计与分析实验报告 教师： 学号： 姓名：

实验一：串匹配问题 实验目的：(1) 深刻理解并掌握蛮力法的设计思想; (2) 提高应用蛮力法设计算法的技能; (3) 理解这样一个观点: 用蛮力法设计的算法, 一般来说, 经过适度的努力后, 都可以对算法的第一个版本进行一定程度的改良, 改进其时间性能。 三、实验要求：( 1) 实现BF 算法; (2 ) 实现BF 算法的改进算法: KMP 算法和BM 算法; (3 ) 对上述 3 个算法进行时间复杂性分析, 并设计实验程序验证 分析结果。 #include "stdio.h" #include "conio.h" #include //BF算法 int BF(char s[],char t[]) { int i; int a; int b; int m,n; m=strlen(s); //主串长度 n=strlen(t); //子串长度 printf("\n*****BF*****算法\n"); for(i=0;i

西北工业大学算法设计实验2

实验二：回溯法VS分支定界法 一、问题分析 回溯法可以处理货郎担问题，分支定界法也可以处理货郎担问题，回溯法和分支定界法哪个算法处理货郎担问题效率更高呢？ 实现回溯法、分支定界法，以及不同的界值函数（课上讲过的或者自己新设计的），通过随机产生10个不同规模的算例（城市数量分别为10，20，40，80，100，120，160，180，200，500，或者其它规模），比较回溯法和分支定界法在相同界值函数下的执行效率。另外，分别比较回溯法和分支定界法在不同界值函数下的执行效率。 二、算法基本思想 1、回溯法 从初始状态出发，搜索其所能到达的所有“状态”， 当一条路走到尽头，再后退一步或若干步，从另外一种状态出发，继续搜索，直到所有的路径都搜索过。这种不断前进、不断回溯寻找解的方法叫回溯法。回溯法通常将问题解空间组织成“树”结构，采用系统的方法搜索解空间树，从而得到问题解。 搜索策略： 深度优先为主，也可以采用广度优先、函数优先、广度深度结合等。 避免无效搜索策略： 约束函数：在扩展结点处剪去不满足约束条件的子树 界限函数：在扩展结点处剪去得不到最优解的子树 2、分支限界法 分支界限法类似与回溯法，也是在问题解空间中搜索问题解的一种算法。 分支界限法与回溯法思想对比： 求解目标：回溯法的可以用于求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标通常是找出满足约束条件的一个解或最优解。 搜索方式的不同：回溯法主要以深度优先的方式搜索解空间树，而分支限界法则

主要以广度优先或以最小耗费优先的方式搜索解空间树。 在分支限界法中，每个活结点只有一次机会成为扩展结点。一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 三、算法设计 1、回溯法 TSP问题的目的是得到一条路径，即一个解向量（X1,X2...Xn），为排列树问题。 对所有城市进行编号后，按大小顺序存储于数组path中，构造一个交换函数swap（）；对数组path进行遍历，判断当前城市与目标城市是否连通，若连通，通过swap函数对当前节点和目标城市进行交换，即树的节点拓展。若不连通则恢复，并进入下一次的循环，循环到叶子节点时，判断叶是否与初始节点相连，并计算代价cost是否小于当前最小代价bestc，若小于，则更新bestc，再返回上一节点，知道遍历完树中的所有节点。 2、分支限界法 因为问题是经典的TSP问题，所以确定问题的解空间树为排列树。 问题解的表示：可以将问题的解表示成一个n元式 [x1,x2,…,xn]。 使用优先级队列实现最小耗费优先求解。 界函数的确定：首先利用贪心的方法获得一个较优的上界。对于当前路径下的扩展的过程中，每一步需要存储的当前的结点的下界。其中的第二部分需要计算的是当前路径的起始结点以及终止结点各自与仍未访问过的结点中的结点只存存在的最小代价。 结点的扩展过程如下：根据优先级从队列中选取优先级最高的元素，当结点不是叶子结点的父节点时，扩展该结点的所有子节点，在扩展的过程中需要根据计算所得的下界与当前求解得到的最优解进行对比，如果下界大于当前的最优解则对相应的子节点时进行剪枝处理，否则扩展该子节点，将其加入到队列中。当当前所访问的结点为叶子结点的父节点时，判断当前费用+当前结点到叶子结点的费