河北工业大学2016算法分析与设计实验报告

河北工业大学

算法分析与设计

2016

实验报告

学院: 计算机科学与软件学院班级:

姓名:

学号:

实验一

【实验学时】

4学时

【实验目的】

1．深刻理解并掌握“分治算法”的设计思想；

2．提高应用“分治算法”设计技能；

3．理解这样一个观点：用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。【问题描述】

设有n=2k个选手要进行网球循环赛，要求设计一个满足以下要求的比赛日程表：

（1）每个选手必须与其他n-1个选手各赛一次；

（2）每个选手一天只能赛一次;

（3）循环赛一共进行n-1天.

按照分治的策略，可将所有参赛的选手分为两部分，n＝2k个选手的比赛日程表就可以通过为n/2＝2k-1个选手设计的比赛日程表来决定。递归地执行这种分割，直到只剩下2个选手时。

【源程序】

#include

#include

voidGameTable(int k, int a[80][80])

{

int n=2;

inti, j, t, temp;

a[1][1]=1; a[1][2]=2;

a[2][1]=2; a[2][2]=1;

for (t=1; t

{

temp=n; n=n*2;

for(i=temp+1; i<=n; i++)

for(j=1; j<=temp; j++)

a[i][j]=a[i-temp][j]+temp;

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

for(j=temp+1; j<=n; j++)

a[i][j]=a[i+temp][j-temp];

for(i=temp+1;i<=n; i++)

for(j=temp+1; j<=n; j++)

a[i][j]=a[i-temp][j-temp];

}

}

int main()

{

inti,j,k;

int a[80][80];

printf("请输入k的数值 k=");

scanf("%d",&k);

GameTable(k,a);

for(i=1; i<=pow(2,k); i++)

{

for(j=1; j<=pow(2,k); j++)

printf("%5d",a[i][j]);

printf("\n");

}

return 0;

}

【运行结果】

【分析总结】

本次实验思路简单，并且编程实现也不复杂。通过这次试验，我对于分治法的设计思想理解地更加深入。其主要思想就是将一个大问题，分解为一个个的小问题，知道每个小问题很容易求出解为止。最后再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出元问题的解。

实验二

【实验学时】

4学时

【实验目的】

（1）熟练掌握动态规划思想及教材中相关经典算法。

（2）掌握动态规划算法求解问题的一般特征和步骤；使用动态规划法编

程，求解0/1背包问题。

【问题描述】

0/1背包问题是给定n个重量为{w1, w2, … ,wn}、价值为{v1, v2, … ,vn}的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。0/1背包问题可以看作是决策一个序列(x1, x2, …, xn)，对任一变量xi的决策是决定xi=1还是xi=0。在对xi-1决策后，已确定了(x1, …, xi-1)，在决策xi时，问题处于下列两种状态之一：（1）背包容量不足以装入物品i，则xi=0，背包不增加价值；（2）背包容量可以装入物品i，则xi=1，背包的价值增加了vi。这两种情况下背包价值的最大者应该是对xi决策后的背包价值。

【源程序】

//本程序的测试用例是课本上的例题

#include

int x[100], V[100][100];

int max(int a, int b)

{

return (a>b ? a : b);

}

intKnapSack(int w[], int v[], int n, int C)

{

inti,j;

//初始化第0列

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

V[i][0]=0;

//初始化第0行

for(j=0; j<=C; j++)

V[0][j]=0;

//双重for循环完成填表过程

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

for(j=1; j<=C ; j++)

if(j

else V[i][j]=max(V[i-1][j], V[i-1][j-w[i]]+v[i]);

//从右下角开始往回寻找

for(j=C, i=n; i>0; i--)

{

if(V[i][j]>V[i-1][j])

{

x[i]=1;

j-=w[i];

}

else x[i]=0;

}

//返回背包最大价值

return V[n][C];

}

int main()

{

//n是物品个数；C是背包总容量

int w[100], v[100], n, C;

printf("请输入物品种类：");

scanf("%d",&n);

printf("请输入背包重量：");

scanf("%d",&C);

printf("请输入重量矩阵：");

for(inti=1; i<=n; i++)

scanf("%d",&w[i]);//这里注意i从1开始取值

printf("请输入价值矩阵：");

for(inti=1; i<=n; i++)

scanf("%d",&v[i]);//这里注意i从1开始取值

printf("\n");

printf("背包取得的最大价值为：%d\n",KnapSack(w, v, n, C)); printf("问题的最优解序列为：");

for(inti=1; i<=n; i++)

printf("%2d",x[i]);

printf("\n\n");

printf("二维矩阵V为:\n");

for(inti=0; i<=n; i++)

{

for(int j=0; j<=C; j++)

printf("%3d",V[i][j]);

printf("\n");

}

return 0;

}

【运行结果】

【分析总结】

通过这次试验，我体会到了动态规划法设计思想的巧妙之处。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，都希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。

实验三

【实验学时】

6学时

【实验目的】

掌握贪心算法求解问题的一般特征和步骤；通过使用贪心算法求解0/1背包和TSP问题，进一步加深对贪心算法的理解和运用。

【问题描述】

0/1背包问题是给定n个重量为{w1, w2, … ,wn}、价值为{v1, v2, … ,vn}的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中每次从物品集合中选择单位重量价值最大的物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量。因此背包问题具有最优子结构性质。

TSP问题是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。1）最近邻点策略：从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。2）最短链接策略：每次在整个图的范围内选择最短边加入到解集合中，但是，要保证加入解集合中的边最终形成一个哈密顿回路。

【0/1背包源程序】

//本程序的测试用例来源于课本例题

#include

#include

using namespace std;

struct G

{

double v;

double w;

double x=0;

int flag=0;

}good[100];

bool cmp1(G a, G b)//按照性价比降序排序

returna.v/a.w>b.v/b.w;

}

bool cmp2(G a, G b)//按照序号升序排序

{

returna.flag

}

int main()

{

inti, n, C;

doublemaxValue=0;

printf("请输入物品种类：");

scanf("%d",&n);

printf("请输入背包重量：");

scanf("%d",&C);

printf("请输入重量矩阵：");

for(inti=0; i

{

scanf("%lf",&good[i].w);

good[i].flag=i;

}

printf("请输入价值矩阵：");

for(inti=0; i

scanf("%lf",&good[i].v);

sort(good, good+n, cmp1);

for(i=0; good[i].w<=C; i++)

{

good[i].x=1;

maxValue+=good[i].v;

C-=good[i].w;

}

good[i].x=(double)C/good[i].w;

maxValue+=good[i].x*good[i].v;

printf("背包的最大价值为:%.2f\n",maxValue); sort(good, good+n, cmp2);

printf("问题的最优解向量为：");

for(inti=0; i

{

printf("%.1f ",good[i].x);

}

printf("\n");

return 0;

}

【运行结果】

【TSP源程序】

#include

//#define LOCAL

int arc[10][10];

int n;//城市个数

int w;//起点城市

int TSP(int n, int w)

{

intedgeCount = 0, TSPLength = 0;

int min = 100, u, v;

int flag[10]={0};//可以对于flag数组中所有元素清零； u=w; flag[w]=1;

while(edgeCount< n-1)

{

min = 100;

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

{

if(flag[j]==0 && arc[u][j]

{

v=j;

min=arc[u][j];

}

}

TSPLength+=arc[u][v];

flag[v]=1;edgeCount++;

printf("%d-->", u);

u=v;

}

printf("%d-->%d\n", v, w);

return (TSPLength+arc[u][w]);

}

int main()

{

#ifdef LOCAL

freopen("data.in", "r", stdin); freopen("data.out", "w", stdout); #endif // LOCAL

printf("请输入城市个数:");

scanf("%d",&n);

printf("请输入代价矩阵:\n");

for(inti=1; i<=n; i++)

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

{

scanf("%d",&arc[i][j]);

}

printf("请输入起点城市:");

scanf("%d",&w);

printf("最短路径为：");

printf("最小代价为:%d", TSP(n, w)); return 0;

}

【运行结果】

【分析总结】

通过这次试验，我更好地掌握了贪心法的设计思想。运用贪心法时，主要有以下步骤：

1.建立数学模型来描述问题

2.把求解的问题分成若干个子问题。

3.对每一子问题求解，得到子问题的局部最优解。

4.把子问题的解局部最优解合成原来解问题的一个解。

实现该算法的过程：

从问题的某一初始解出发；

while 能朝给定总目标前进一步

do

求出可行解的一个解元素；

由所有解元素组合成问题的一个可行解。

实验四

【实验学时】

6学时

【实验目的】

掌握回溯法的设计思想；掌握解空间树的构造方法，以及在求解过程中如何存储求解路径；考察回溯法求解问题的有效程度。

【问题描述】

给定n种物品和一背包。物品i的重量是wi>0，其价值为vi>0，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

TSP问题是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。

【0/1背包源程序】

#include

using namespace std;

intn,c,bestp;

//物品的个数，背包的容量，最大价值

int p[100],w[100],x[100],bestx[100];

//物品的价值，物品的重量，x[i]暂存物品的选中情况,物品的选中情况

void Backtrack(inti,intcp,intcw)

//cw当前包内物品重量，cp当前包内物品价值

{

int j;

if(i>n)

//结束回溯

{

if(cp>bestp)

{

bestp=cp;

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

bestx[i]=x[i];

}

}

else

for(j=0;j<=1;j++)

{

x[i]=j;

if(cw+x[i]*w[i]<=c)

{

cw+=w[i]*x[i]; //每个解向量的分量的c与当前的w[i]和前一个解向量分量的cw有关

cp+=p[i]*x[i];

Backtrack(i+1,cp,cw); //递归调用

}

}

}

int main()

{

cout<

cout<

inti;

bestp=0;

cout<<"输入物品个数:"<

cin>>n;

cout<<"输入背包最大容量:"<

cin>>c;

cout<<"依次输入物品的重量:"<

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

cin>>w[i];

cout<<"请依次输入物品的价值:"<

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

cin>>p[i];

Backtrack(1,0,0);

cout<<"最大价值为:"<

cout<<"物品的选中情况依次为（0表示没有被选中，1表示被选中）"<

cout<

cout<

return 0;

}

【运行结果】

【分析总结】

1、重温了算法课程里面学过的回溯法，强化了这种编程思想。

2、深刻理解了递归调用的思想。

3、通过这次实验对回溯算法有了进一步的了解，把理论知识应用于实验中。

4、回溯算法的主要思想：在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

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

《算法分析与设计》实验指导书本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。 上机实验一般应包括以下几个步骤： （1）、准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。（2）、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题，最好独立解决。 （3）、上机结束后，整理出实验报告。 实验报告应包括： 1）问题分析 2）算法描述 3）运行结果、 4）算法性能分析。 实验一 实验名称：贪心算法应用及设计 实验学时：6学时 实验类型：验证 实验目的： 1.理解贪心算法的基本思想 2.掌握利用贪心算法求解问题的求解步骤 实验容 1.活动选择问题（2学时） 问题描述： 设有11个会议等待安排，用贪心法找出满足目标要求的会议集合，这些会议按结束时间的非减序排列如下表。 实验实现提示： １)数据结构设计： 将会议开始时间存储在数组B中，结束时间存储在数组E中，数组下标为会议的代码。结果存储在数组A中，其元素A[i]==true，表示会议i被选中。 ２）算法： void GreedySelect(int n, struct time B[], struct time E[], bool A[]) { int i,j;

A[1]=true; j=1; i=2; while( i<=n) if (B[i]>=E[j]) { A[i]=true; j=i;} else A[i]=false; } 思考题：证明所得的解是最优解？ 2.单源点最短路径问题。（2学时） 问题描述 如图所示的有向带权图中，求源点0到其余顶点的最短路径及最短路径长度。并对算法进行性能分析。 实现提示 1）数据结构设计： 将图存储在邻接矩阵C中，结点个数为n，源点编号为u, 源点u到其余顶点的最短路径长度存储在dist[],最短路径存储在p[]。 2) 算法 void Dijkstra(int C[n][n], int n,int u,float dist[],int p[]) { bool s[n]; for( int i=1; i<=n; i++) { dist[i]=C[u][i]; s[i]=false; if (dist[i]=∞) p[i]=-1; else p[i]=u; } p[u]=-1; s[u]=true; for( i=1; i<=n; i++) { int temp= ∞; int t=u; for( int j=1;j<=n;j++)

河北工业大学数电期中考试试卷

河北工业大学城市学院期中模拟试卷 2016年(春)季学期 (a) (b) （c） 7、使用TTL与非门时下列做法中错误的是 A.输入端并联作非门使用； B.输出端并联作线与； 共 5 页第 1 页

2016年(春)季学期 学院名称：班级：姓名：学号：适用专业：课程名称：电子技术基础A 共 5 页第 2 页

2016 年(春)季学期 学院名称： 班级： 姓名： 学号： 适用专业： 课程名称： 电子技术基础A 电平有效；图5（b ）所示是各输入信号波形。试画出输出端F 的波形。 A B C (a) （b ） 4、试设计一个判别8421BCD 码中奇数的电路，其中十以上的二进制码为无关项。要求： （1）列出状态表； （2）画出卡诺图；（3）写出最简与或表达式；（4）用与非门实现之，画出逻辑电路图。 5、某自动车床上共有4台电动机，A 为润滑油泵电机，B 为主轴电机，C 为X 坐标进给电机，D 为Y 坐标进给电机。控制要求在下列工况之一时绿色指示灯亮，否则红色指示灯亮： （1）在任何工况下油泵必须工作； （2）主轴不开机时：①调整刀架X 坐标位置，②调整刀架Y 坐标位置，③X,Y 坐标同时调整； （3）主轴开机时：①X ，Y 坐标静止等待，②X 坐标单独进给加工，③Y 坐标单独进给加工，④两坐标同时进给加工。 试列出状态真值表，写出逻辑表达式，化简成最简与或表达式，变换成与非形式，画出逻辑图。 共 5 页 第 3 页

2016年(春)季学期 学院名称：班级：姓名：学号：适用专业：课程名称：电子技术基础A 共 5 页第 4 页

算法分析与设计实验报告

算法设计与分析 学院：计算机科学与技术 学号：129074106 姓名：张淼淼 2014 11 14

1、 当问题规模100 N 时，快速排序和插入排序各需多少时间？写清机器配置，列出五种 快速排序所需时间(ms) 插入排序所需时间（ms ） 两者相差多少 N=100 0.00600 0.019000 -0.013000 N=1000 0.074000 0.724000 -0.650000 N=10000 0.032000 64.657000 -64.625000 N=100000 13.300000 50.900000 -37.600000 N=1000000 53.500000 117.700000 -64.200000 Window 7 32位 Cpu ：Inter(R) Core(TM) i3-2120 cpu@3.30GHz AMD Radeon HD 6450 Graphics

程序： #include #include #include #include int a[1000000];

int b[1000000]; void QuickSort(int low ,int high) { long i,j; int x; i=low; j=high; x=a[i]; while(i=x&&i(j+1)) QuickSort(j+1,high); } void BinaryInsertSort(int length) { int low,high,mid; int i,j,m;//m为保存待插入的元素 for(i=1;i=b[mid]) low=mid+1; else high=mid-1; } for(j=i-1;j>=high+1;j--)//high为插入位置 b[j+1]=b[j];//后移元素，留出插入的空位b[high+1]=m;//将元素插入正确的位置 }

算法设计与分析实验报告贪心算法

算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include float small1,small2; int flag1,flag2,count; typedefstructHuffmanTree { float weight; intlchild,rchild,parent; }huffman; huffmanhuffmantree[100]; void CreatHuffmanTree(intn,int m) { inti; void select(); printf("请输入%d个节点的权值:",n); for(i=0;i

printf("\n"); for(i=0;i

算法设计与分析实验报告

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

课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号 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

计算机算法设计与分析

算法设计与分析 实 验 报 告 班级： 姓名： 学号： (备注：共给出5个参考实验案例，根据学号尾数做对应的实验，即如尾号为1，则模仿案例实验123；尾号2，则模仿案例实验234；尾号3，即345；尾号4，同1.)

目录 实验一分治与递归 (1) 1、基本递归算法 (1) 2、棋盘覆盖问题 (2) 3、二分搜索 (3) 4、实验小结 (5) 实验二动态规划算法 (5) 1、最长公共子序列问题 (5) 2、最大子段和问题 (7) 3、实验小结 (8) 实验三贪心算法 (8) 1、多机调度问题 (8) 2、用贪心算法求解最小生成树 (10) 3、实验小结 (12) 实验四回溯算法和分支限界法 (12) 1、符号三角形问题 (12) 2、0—1背包问题 (14) 3、实验小结 (18) 实验五多种排序算法效率比较 1、算法：起泡排序、选择排序、插入排序、shell排序，归并排序、快速排序等 (19) 2、实验小结 (18)

P art1：课程设计过程 设计选题--→题目分析---→系统设计--→系统实现--→结果分析---→撰写报告 P art2：课程设计撰写的主要规范 1.题目分析：主要阐述学生对题目的分析结果，包括题目描述、 分析得出的有关模型、相关定义及假设； 2.总体设计：系统的基本组成部分，各部分所完成的功能及相互 关系； 3.数据结构设计：主要功能模块所需的数据结构，集中在逻辑设 计上； 4.算法设计：在数据结构基础上，完成算法设计； 5.物理实现：主要有数据结构的物理存储，算法的物理实现，系 统相关的实现。具体在重要结果的截图，测试案例的结果数据，核心算法的实现结果等； 6.结果分析：对第五步的分析，包括定性分析和定量分析，正确 性分析，功能结构分析，复杂性分析等； 7.结论：学生需对自己的课程设计进行总结，给出评价，并写出 设计体会； 8.附录：带有注释的源代码，系统使用说明等； 9.参考文献：列出在撰写过程中所需要用到的参考文献。

河北工业大学年高考本科招生章程招生简章招生计划联系方式高考.doc

河北工业大学2016年高考本科招生章程招生简章招生计 划联系方式_高考 2河北工业大学为公办普通高校，上级主管部门为河北省教育厅，办学层次：本科，学校代码：10080。 3河北工业大学是国家“211工程”重点建设的大学，具备学士、硕士、博士、博士后完整的人才培养体系。学生毕业，颁发教育部统一印制的河北工业大学学历证书和学位证书。 二、学校原则 4学校录取新生的原则：以全国普通高等学校招生考试成绩为主要依据，德、智、体全面衡量，择优录取。 5应当符合教育部制定的《普通高等学校招生体检工作指导意见》的身体健康条件。 6对于实行平行投档的省份或批次，学校按平行志愿政策录取;对于非平行志愿投档的省份或批次，学校录取时按照考生报考学校志愿先后录取，即先录取学校第一志愿的考生，若第一志愿不满时，再录取第二志愿考生。 对于江苏省考生，录取原则是：先分数后等级，学业水平测试等级要求选测科目等级在2B及以上;必测科目在4C及以上，技术合格。

7对于艺术类，录取原则是：对于河北、天津的考生，高考文化课成绩必须达到考生所在省市划定的艺术类专业本科相应批次录取控制分数线且省艺术统考成绩达到本科报考资格，根据省市艺术统考成绩由高到低择优录取;对于其他省市的考生，高考文化课成绩必须达到考生所在省市划定的艺术类专业本科相应批次录取控制分数线且省艺术统考成绩达到本科报考资格，校考成绩合格，按综合成绩(综合成绩=校考专业成绩×70%+高考文化成绩×30%)由高分到低分择优录取。 8对于进档考生安排专业，以分数优先为原则安排考生专业志愿。第一专业志愿不能满足的考生，按其第二专业志愿投档，以此类推。当某考生所有专业志愿均不能满足，服从专业调剂的考生，将调剂到录取计划未满的专业，不服从专业调剂的考生，予以退档。 在内蒙古自治区实行“专业志愿清”录取原则。 三、部分专业具体要求 9建筑学、城乡规划专业的考生要求有徒手绘画基础;工业设计专业的考生要求有美术基础;计算机与技术、软件工程、网络工程、物联网工程、经济学、金融学、工业工程、工商管理、会计学、工程管理专业考生入学后外语教学为英语。 10计算机类(中外合作办学)计算机科学与技术专业为我校与法国SUPINFO国际信息技术大学(原法国巴黎高等计算机学院)合作专业，采用本硕连读学习模式;环境科学与工程类(中外合作办学)环境工程专业为我校与德国北

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

《计算机算法设计与分析》实验指导书（第一版）

前言 计算机算法分析与设计是面向设计的，它是计算机科学的核心。无论是计算机系统、系统软件和解决计算机的各种应用问题都可归结为算法的设计。通过本课程的学习，使学生掌握计算机领域中许多常用的非数值的算法描述：分治法、贪心法、动态规划、回溯法、分枝限界等算法，并掌握算法分析的方法，从而把学生的分析问题和解决问题能力提高到理论的高度。 前期课程为程序设计语言、数据结构、高等数学，即学生应该具备一门高级语言程序设计编程基础，学习基本的数据结构知识，还要求学生掌握较好的数学基础。 开发环境不限，本书采用C/C++语言的集成开发环境等。 实验完成后书写实验报告，包含实验问题、基本思想、关键算法流程图、测试数据及运行结果（截图）、调试心得和源程序。 总实验学时为16学时。

目录 预备实验验证算法的方法 (4) 实验目的： (4) 实验课时： (4) 实验原理： (4) 实验题目： (6) 基本题： (6) 提高题： (6) 实验一递归与分治 (7) 实验目的： (7) 实验课时： (7) 实验原理： (7) 实验题目： (7) 基本题： (7) 提高题： (8) 思考问题： (8) 实验二动态规划算法 (9) 实验目的： (9) 实验课时： (9) 实验原理： (9) 实验题目： (9) 基本题： (9) 提高题： (10) 思考问题： (10) 实验三贪心选择算法 (11) 实验目的： (11) 实验课时： (11) 实验原理： (11) 实验题目： (11) 基本题： (11) 提高题： (12) 思考问题： (12) 实验四回溯算法 (13) 实验目的： (13) 实验课时： (13) 实验原理： (13) 实验题目： (14) 基本题： (14) 提高题： (14) 思考问题： (14)

河北工业大学毕业论文

河北工业大学毕业论文

————————————————————————————————作者：————————————————————————————————日期：

河北工业大学成人高等教育毕业论文 关于可控励磁发电系统综合性实验的设计 摘要 现代电力系统的发展，对同步发电机励磁控制提出了更高要求。发电机在正常工作情况下，负载总在不断地变化着。而不同容量的负载，以及负载的不同功率因数，对同步发电机励磁磁场的反映作用是不同的，要维持同步发电机端电压为一定水平，就必须根据负载的大小及负载的性质随时调节同步发电机的励磁。在各类电站中，励磁系统是保证同步发电机正常工作，提高电网稳定水平的关键设备。同步发电机励磁的自动控制在保证电能质量、无功功率的合理分配和提高电力系统运行的可靠性方面都起着十分重要的意义。 本文主要对可控励磁发电系统进行了实验设计，首先对可控励磁发电系统做了相关简介并探讨了可控励磁发电系统的国内外未来发展形势。本文着重在可控励磁系统中的过励限制方面作了重点分析，并设计了相关的一个过励限制特性试验，对过励限制系统加深了了解。 关键词电力系统；励磁控制系统；过励限制

目录 第1章绪论 (1) 1.1 发电机励磁控制系统简介 (1) 1.2励磁控制系统的作用 (2) 1.2.1维持发电机端电压在给定水平 (2) 1.2.2提高电力系统的静态稳定性 (2) 1.2.3改善电力系统的暂态稳定性 (3) 1.2.4改善电力系统的动态稳定性 (4) 1.2.5在并列运行的发电机间合理分配无功功率 (4) 1.3自动励磁调节器的组成及功能 (4) 1.3.1基本工作电路 (4) 1.3.2辅助工作电路 (5) 1.4同步发电机励磁控制方式研究现状 (5) 1.4.1基于单变量控制方式 (5) 1.4.2基于现代控制理论的多变量控制方式 (5) 1.4.3非线性多变量励磁控制方式 (6) 1.4.4智能控制方法 (7) 1.5国外研究及发展状况 (8) 第2章励磁系统的过励限制 (11) 2.1 过励限制的主要特性 (11) 2.2限制过程 (11) 2.3级差 (12) 2.4以励磁机磁场电流作为过励限制控制量的过励限制整定 (12) 2.5无发电机转子过负荷保护的处理 (13) 2.6过热量的释放和再次过励的条件 (13) 2.7过励保护 (13) 2.7.1顶值电流保护 (13) 2.7.2过励反时限保护 (13) 2.7.3过励报警信号 (13) 第3章可控励磁发电系统实验装置操作及维护 (14) 3.1 实验装置操作说明 (14) 3.2实验的基本要求 (15) 3.3可控励磁发电系统操作运行及检测维护 (16) 3.3.1可控励磁自动调节系统的投入运行的操作步骤 (16) 3.3.2自动—手动控制切换操作要点 (16) 3.3.3可控励磁自动调节系统的正常运行要点 (16) 3.3.4励磁调节装置的退出及停机操作要点 (17) 3.3.5可控励磁自动调节装置的检查与维护 (18) 3.4控励磁发电系统常见故障及处理方法 (19) 3.4.1灭磁开关QFG的常见故障及处理方法 (19) 3.4.2调试中常见故障及处理方法 (19)

算法分析与设计实验报告

实验一、归并排序及各种排序算法性能比较 一、实验实习目的及要求 了解归并排序等各种排序算法，并能独立在计算机上实现，同时并能够计算它们的时间复杂度，并用计算机来验证。 二、实验实习设备（环境）及要求（软硬件条件） 计算机eclipse软件，执行环境JavaSE-1.8. 三、实验实习项目、内容与步骤(注意是主要关键步骤，适当文字+代码+截图说明) 项目：对10 4 6 3 8 2 5 7进行从小到大排序，采用几种排序方法，并统计这几种方法的运行时间，与归并排序比较。 内容及步骤： (1)归并排序：将序列每次分成两组，再进行合并，直到递归完成； 1、递归调用mergeSort对数组排序 2、merge将两个有序数组合并为一个有序数组

3、主函数调用mergeSort对数组排序 4、统计时间 (2) 选择排序：每次选择一个当前最小的并和当前的相对的第一个元素交换，直到最后 只有一个元素时结束；也可选择当前最大的并与当前的相对的最后一个 元素交换，直到最后只有一个元素时结束。

1、数组长度为n，需要选择n-1次；每次选择完成后，将数组中的最大值与最后一 个元素互换，调用java.util包中Arrays类。 2、主函数调用ChooseSort对数组排序。 3、统计运行时间。 (3)插入排序：从第二个元素开始，每次插入一个到当前有序序列中，使得有序，当 所有的元素插入完毕时，就排好序了； 1、从第二个元素开始，与之前序列比较，插入到合适的位置。

2、主函数调用sort对数组排序。 3、统计运行时间 (4) 快速排序：每次选择一个中间元素，并进行交换，使得中间元素的左边比它小，右 边比它大，然后对左右两边进行递归； 1、选取一个基准位，从右边向左边看，找比基准位小的元素，再从左边向右边看， 找比基准位大的元素，若两者均存在则交换；若两者相遇，则相遇元素与基准位元素交换，然后递归排序左右半数组。

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

《算法分析与设计》实验指导书 《算法分析与设计》课程是计算机专业的一门必修课程。开设算法分析与设计实验，目的就是为了使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。 《算法分析与设计》课程实验的目的：是为了使学生在课程学习的同时，通过实验环境中的实际操作，对部分算法的具体应用有一个初步的了解，使学生加深了解和更好地掌握《算法分析与设计》课程教学大纲要求的内容。 《算法分析与设计》课程实验的注意事项：在《算法分析与设计》的课程实验过程中，要求学生做到： (1)预习实验指导书有关部分，认真做好实验内容的准备，就实验可能出 现的情况提前作出思考和分析。 (2)认真书写实验报告。实验报告包括实验目的和要求，实验情况及其分 析。 (3)遵守机房纪律，服从辅导教师指挥，爱护实验设备。 (4)实验课程不迟到。如有事不能出席，所缺实验一般不补。 《算法分析与设计》课程实验的验收：实验的验收将分为两个部分。第一部分是上机操作，包括检查程序运行和即时提问。第二部分是提交电子的实验报告。

实验一算法实现一 一、实验目的与要求 熟悉C/C++语言的集成开发环境； 通过本实验加深对分治法、贪心算法的理解。 二、实验内容: 掌握分治法、贪心算法的概念和基本思想，并结合具体的问题学习如何用相应策略进行求解的方法。 三、实验题 1. 【伪造硬币问题】给你一个装有n个硬币的袋子。n个硬币中有一个是伪造的。你的 任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。试用分治法的思想写出解决问题的算法，并计算其时间复杂度。 2.【找零钱问题】一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。售 货员希望用数目最少的硬币找给小孩。假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。给出一种找零钱的贪心算法。 a)实验步骤 理解算法思想和问题要求； 编程实现题目要求； 上机输入和调试自己所编的程序； 验证分析实验结果； 整理出实验报告。 四、实验程序 五、实验结果 六、实验分析

河北工业大学 实验报告——自来水pH和微量Cl-

河北工业大学实验报告 课程：分析化学实验 班级：应化091姓名：刘菁组别：同组人：孙禹日期：2011-4-13 实验：自来水pH测定及直接电位法测微量Cl－ 一、实验目的： 1、了解pH S－2型酸度计的结构、原理和使用方法。 2、掌握用电位法测pH值的原理和方法。 3、掌握测定氯离子含量的标准曲线法和标准加入法。 二、实验原理： 1、TISAB的原理： 用测定离子的纯物质配制一系列不同浓度的标准溶液，并用总离子强度调节缓冲溶液（Totle Ionic Strength Adjustment Buffer简称TISAB）保持溶液的离子强度相对稳定，分别测定个溶液的电位值，并绘制E- lg c i关系曲线。 注意：离子活度系数保持不变时，膜电位才与lg c i 呈线性关系。 总离子强度调节缓冲溶液TISAB的作用： ①保持较大且相对稳定的离子强度，是活度系数恒定； ②维持溶液在适宜的pH范围内，满足离子电极的要求； ③掩蔽干扰离子。 2、水样pH值的测定： 测量溶液的pH值时，一般以玻璃电极为指示电极，饱和甘汞电极为参比电极。它们与被测溶液一起，组成原电池。通过测定该原电池的电动势来决定溶液的pH值。 在一定条件下，电池电动势E与pH呈线性关系 E=K`+(2.303RT/F)×pH 式中，K`是常数，其大小由内外参比电极的电位、不对称电位、液接电位等决定。实际上，K`不易求得。因此常用已知pH值的缓冲溶液来校正酸度计（称定位）——pHs（已知缓冲液pH值）应与被测物的估计pH值相近，以减少误差。一般用两种不同的pH值的标准缓冲溶液进行定位，，在用一种标准缓冲溶液定位后，测另一种标准缓冲溶液的pH值时，误差应小于0.05pH。 3、用氯离子选择性电极测微量Cl－含量： 用直接电位法测量溶液中氯离子浓度时，以氯离子选择性电极作指示电极，双液接甘汞电极（内液是饱和KCl溶液，外液是0.1MKNO3溶液）作参比电极，，与待测溶液组成原电池。在一定条件下，电池电动势E与氯离子活度的对数呈线性关系 E=K-(2.303RT/F)×lgαCl－ 因α=γ·c，所以上是可以写成 E=K-(2.303RT/F)×lgγ·c Cl－

算法分析与设计 实验二 哈夫曼编码

昆明理工大学信息工程与自动化学院学生实验报告 （201 —201 学年第一学期） 课程名称：算法设计与分析开课实验室：年月日 一、上机目的及内容 1.上机内容 设需要编码的字符集为{d1, d2, …, dn}，它们出现的频率为{w1, w2, …, wn}，应用哈夫曼树构造最短的不等长编码方案。 2.上机目的 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）证明哈夫曼树满足最优子结构性质； （2）设计贪心算法求解哈夫曼编码方案； （3）设计测试数据，写出程序文档。 数据结构与算法: typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码 typedef struct { unsigned int weight; //用来存放各个结点的权值 unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针 } HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树

程序流程图：

三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件 四、实验方法、步骤（或：程序代码或操作过程） 程序代码： #include #include #include typedef struct { unsigned int weight; unsigned int parent,LChild,RChild; } HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树 typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码 void Select(HuffmanTree *ht,int n,int *s1,int *s2) { int i,min; for(i=1; i<=n; i++) { if((*ht)[i].parent==0) { min=i; break; } } for(i=1; i<=n; i++) { if((*ht)[i].parent==0) { if((*ht)[i].weight<(*ht)[min].weight) min=i; } } *s1=min; for(i=1; i<=n; i++) { if((*ht)[i].parent==0 && i!=(*s1)) { min=i; break; }

算法设计与分析实验报告

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

实验一：串匹配问题 实验目的：(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

河北工业大学毕业设计说明书格式模版1306485519456

毕业设计说明书格式样板（A4纸型） 河北工业大学 毕业设计说明书 作者：学号： 学院： 系(专业)： 题目： 指导者： (姓名) (专业技术职务) 评阅者： (姓名) (专业技术职务) 年月日

（空2行） 目次（4号黑体，居中） 1引言（或绪论）（作为正文第1章，小4号宋体，行距18磅，下同） (1) 2××××××（正文第2章）……………………………………………………Y 2.1 ××××××（正文第2章第1条）…………………………………………Y 2.2 ××××××（正文第2章第2条）………………………………………… Y 2.X ××××××（正文第2章第X条）………………………………………… Y 3 ×××××（正文第3章）……………………………………………… Y ………………………………………（略） X ×××××（正文第X章）……………………………………………………… Y 结论…………………………………………………………………………………… Y 参考文献……………………………………………………………………………… Y 致谢………………………………………………………………………………Y 附录A ××××（必要时）………………………………………………………… Y 附录B ××××（必要时）………………………………………………………… Y 图1 ×××××（必要时）………………………………………………………… Y 图2×××××（必要时）………………………………………………………… Y 表1 ×××××（必要时）………………………………………………………… Y 表2 ×××××（必要时）………………………………………………………… Y 注：1. 目次中的内容一般列出“章”、“条”二级标题即可； 2．X、Y表示具体的数字。

算法分析与设计实验报告 (2)

算法分析与设计上机实验报告 课程名称：算法分析与设计班级：实验日期: 姓名：学号：指导教师：许晓华实验名称：最优二叉搜索树实验地点：主楼1114实验成绩：一、实验目的及要求 1．进一步掌握最优二叉树的含义。 2．掌握最优二叉树的结构特征。 3．认真阅读和掌握动态规划法秋最有搜索二叉树实验的程序。 4．上机运行本程序。 5．保存和打印出程序的运行结果，并结合程序进行分析。 6．按照你二叉树的操作需要，可重新改写主程序并运行，请上交文件清单和运行结果 二、实验环境及设备 微机一台：Intel 酷睿2双核 操作系统：Microsoft Windows XP Professional 工具软件：Microsoft Visual C++ 6.0 三、实验内容及实验步骤 动态规划——最优二叉查找树 1，问题描述：给定一个有序序列K={k1

算法分析与设计实验报告

计算机算法设计与分析实验报告

目录 实验一 (1) [实验题目] (1) [问题描述] (1) [算法设计] (1) [算法分析] (1) [源代码] (1) [运行结果] (2) 实验二 (2) [实验题目] (2) [问题描述] (2) [算法设计] (2) [算法分析] (2) [源代码] (2) [运行结果] (4) 实验三 (5) [实验题目] (5) [问题描述] (5) [算法设计] (5) [算法分析] (5) [源代码] (5) [运行结果] (6)

实验一 [实验题目] 2-7集合划分问题 [问题描述] n个元素的集合{1，2，…，n}可以划分为若干非空子集。例如，当n=4时，集合{1，2，3，4}可以划分为15个不同的非空子集。 [算法设计] 给定正整数n，计算出n个元素的集合{1，2，…，n}可以划分为多少个不同的非空子集。 [算法分析] 本算法实现采用分治法思想，F(n,m)=F(n-1,m-1)+m*F(n-1,m)。假设将m个元素分解到n 个集合中，首先考虑将(m – (n - 1))个元素分到第一个集合中，将余下的(n - 1)个元素分别分配到余下的(n - 1)个集合中，然后再考虑将(m – (n - 2))个元素分配到第一个集合中，将余下的(n - 2)个元素分别分配到余下的(n - 1)集合中，依此类推，直到后面的有一个集合中的元素个数比第一个集合中的元素个数多为止。 [源代码] #include using namespace std; int compute_bell(int row,int position) { if(row==1) return 1; if(row == 2 && position ==1) return 1; else { if(position == 1) return compute_bell(row-1,row-1); else return compute_bell(row,position-1)+ compute_bell(row-1,position-1); } } int main(){ int n=0; int m; cout<<"please input a number."<>n; m=compute_bell(n,n); cout<<"the resule is "<

河北工业大学毕业设计(论文)要求及模板(新)

毕业设计(论文)打印格式样板(供理工类专业用) （A4纸型）工业大学成人高等教育毕业设计说明书(论文) 姓名：学号： 教学管理单位： 专业： 题目： 指导者： (姓名) (专业技术职务) 评阅者： (姓名) (专业技术职务) 年月日

毕业设计(论文)打印格式样板(供管理、文法专业用) （A4纸型）工业大学成人高等教育 毕业论文 姓名：学号： 教学管理单位： 专业： 题目： 指导者： (姓名) (专业技术职务) 评阅者： (姓名) (专业技术职务) 年月日

毕业设计（论文）摘要

（空2行） 目录（4号黑体，居中） 1 引言（或绪论）（作为正文第1章，小4号宋体，行距18磅，下同） (1) 2××××××（正文第2章）……………………………………………………Y 2.1 ××××××（正文第2章第1条）…………………………………………Y 2.2 ××××××（正文第2章第2条）…………………………………………Y 2.X××××××（正文第2章第X条）…………………………………………Y 3×××××（正文第3章）………………………………………………Y ………………………………………（略） X×××××（正文第X章）………………………………………………………Y 结论……………………………………………………………………………………Y 致……………………………………………………………………………………Y 参考文献………………………………………………………………………………Y 附录A××××（必要时）…………………………………………………………Y 附录B××××（必要时）…………………………………………………………Y 图1×××××（必要时）…………………………………………………………Y 图2×××××（必要时）…………………………………………………………Y

河北工业大学电气工程入学复试安排

2016年电气工程学院硕士研究生入学复试安排 一、复试资格审查和笔试科目确认 时间：2015年3月23日（周三）下午14：00-17：00，地点：河北工业大学东院电气学院楼一楼大厅（天津市红桥区光荣道8号，北洋桥旁）。 届时需考生提供以下材料： 1.准考证原件； 2.应届生提供大学成绩单原件、往届生提供大学成绩单复印件（须加盖档案管理部门公章）； 3.政审表原件； 4.身份证原件及复印件； 5.应届生提供学生证原件、复印件及具有12位验证码的《教育部学籍在线验证报告》；往届生提供毕业证和学位证原件、复印件及具有12位验证码的《教育部学历证书电子备案表》。 经复试资格审查符合教育部规定要求的考生，对其发放“复试通知书”。 通过资格审查的考生需确认复试科目，不确认者不得参加专业课笔试。 二、考生体检 考生体检必须在河北工业大学校医院进行，电气工程学院的考生们须在2016年3月24日（周四）上午，持复试通知书自行到校医院（丁字沽一号路，河北工业大学北院斜对面）体检，未体检或体检不

合格者取消其录取资格。（校医院接待全校考生，请同学们早去排队，务必在当天上午完成体检）。 三、英语听力测试 时间：2016年3月24日（周四）下午，地点：河北工业大学东院七教。 四、专业课笔试 时间：2016年3月24日（周四）下午，地点：河北工业大学东院七教。 五、专业综合面试和英语口语测试（交替进行） （一）电气工程专业考生，时间：2016年3月25日（周五）8：00-19：00，地点：河北工业大学东院电气工程学院楼。 （二）生物医学工程专业考生，面试时间为2016年3月25日（周五）8：30- 地点：在河北工业大学东院电气工程学院楼。 六、注意事项 考生在复试资格审查现场可查阅英语听力、口语测试和专业综合面试的详细安排，3月24日（周四）11:00之后可在电气学院楼一楼大厅查阅专业课笔试的详细安排。请各位考生同学及时关注。

算法分析与设计实验二：动态规划法

题目：用动态规划法实现求两序列的最长公共子序列。 程序代码 #include #include //memset需要用到这个库 #include using namespace std; int const MaxLen = 50; class LCS { public: LCS(int nx, int ny, char *x, char *y) //对数据成员m、n、a、b、c、s初始化{ m = nx; //对m和n赋值 n = ny; a = new char[m + 2]; //考虑下标为0的元素和字符串结束标记 b = new char[n + 2]; memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); for(int i = 0; i < nx + 2; i++) //将x和y中的字符写入一维数组a和b中a[i + 1] = x[i]; for(int i = 0; i < ny + 2; i++) b[i + 1] = y[i]; c = new int[MaxLen][MaxLen]; //MaxLen为某个常量值 s = new int[MaxLen][MaxLen]; memset(c, 0, sizeof(c)); //对二维数组c和s中元素进行初始化 memset(s, 0, sizeof(s)); } int LCSLength(); //求最优解值（最长公共子序列长度） void CLCS() //构造最优解（最长公共子序列） { CLCS(m, n); //调用私有成员函数CLCS(int,int) } private: void CLCS(int i, int j); int (*c)[MaxLen], (*s)[MaxLen]; int m, n;