《算法分析与设计》实验指导书(学时)

数理学院

算法分析与设计实验报告

姓名：

学号：

班级：

目录

实验一分治策略排序 (3)

实验二减治策略查找顺序表 (5)

实验三动态规划求解0/1背包问题 (8)

实验四贪心算法求解最短路径问题 (10)

实验一分治策略排序

实验目的

1）以排序问题为例，掌握分治法的基本设计策略；

2）熟练掌握合并排序算法的实现；

3）熟练掌握快速排序算法的实现；

4) 理解常见的算法经验分析方法。

实验环境

计算机、C语言程序设计环境

实验学时

2学时

实验内容与步骤

1.准备实验数据

要求：编写一个函数data-generate，生成2000个在区间[1,10000]上的随机整数，并将这些数输出到外部文件data.txt中。这些数作为本算法实验的输入数据。

2.实现合并排序算法

要求：实现mergesort算法。

输入：待排数据文件data.txt；

输出：有序数据文件resultsMS.txt（注：建议将此排好序的数据作为实验二的算法输入）；程序运行时间TimeMS。

合并排序算法（类C语言）：

/* 数组A[] 中包含待排元素；array B[] is a work array */

TopDownMergeSort(A[], B[], n)

{

TopDownSplitMerge(A, 0, n, B);

}

// iBegin is inclusive; iEnd is exclusive (即：A[iEnd]不是待排元素)

TopDownSplitMerge(A[], iBegin, iEnd, B[])

{

if(iEnd - iBegin < 2) // 如果只有1个待排元素，返回。

return;

// recursively split runs into two halves until run size == 1,

// then merge them

iMiddle = (iEnd + iBegin) / 2; // 划分

TopDownSplitMerge(A, iBegin, iMiddle, B);

TopDownSplitMerge(A, iMiddle, iEnd, B);

TopDownMerge(A, iBegin, iMiddle, iEnd, B); // 合并；元素放到数组B中。

CopyArray(B, iBegin, iEnd, A); // copy the merged runs back to A }

// left half is A[iBegin : iMiddle-1]

// right half is A[iMiddle : iEnd-1]

TopDownMerge(A[], iBegin, iMiddle, iEnd, B[])

{

i0 = iBegin, i1 = iMiddle;

// While there are elements in the left or right runs

for (j = iBegin; j < iEnd; j++) {

// If left run head exists and is <= existing right run head.

if (i0 < iMiddle && (i1 >= iEnd || A[i0] <= A[i1])) {

B[j] = A[i0];

i0 = i0 + 1;

} else {

B[j] = A[i1];

i1 = i1 + 1;

}

}

}

CopyArray(B[], iBegin, iEnd, A[])

{

for(k = iBegin; k < iEnd; k++)

A[k] = B[k];

}

3.实现快速排序算法

要求：实现QuickSort算法。

输入：待排数据文件data.txt；

输出：有序数据文件resultsQS.txt（注：建议将此排好序的数据作为实验二的算法输入）；程序运行时间TimeQS。

快速排序算法（伪码）：

Procedure QuickSort(p, q)

integer p, q；global n, A(1:n)

if p< q then

j ← q+1

Partition(p, j); //用元素A(p)划分元素表A[p : j-1]；划分后，划分元素下

标由参数j带出。

QuickSort (p, j-1);

QuickSort(j+1, q);

end if

end QuickSort

用元素A(m)划分元素表A[m : p-1]：

Procedure partition(m, p)

integer m, p, I; global A(m:p-1)

v=A(m); I=m;

loop

loop I=I+1 until A(I)>=v repeat

loop p=p-1 until A(p)<=v repeat

if I

then A(i) A(p)

else exit

end if

repeat

A(m)=A(p); A(p)=v;

end partition

实验报告：

实验报告应包括以下内容：

（1）题目；

（2）2个算法的基本思想描述；

（3）程序流程图；

（4）给出data.txt、resultsMS.txt、resultsQS.txt三个数据文件；给出TimeMS、TimeQS的数值结果；

（5）实验分析；以表或者图的形式给出这两个算法效率的经验分析结果；

并和理论分析结论进行对比。

（6）说明本次实验的心得体会、经验等。如果程序未通过，应分析其原因。

实验二减治策略查找顺序表

实验目的

1）以顺序表查找问题为例，掌握减治法的基本设计策略；

2）熟练掌握折半查找算法的实现；

3）掌握插值查找算法的实现；

4) 分析实验结果。

实验环境

计算机、C语言程序设计环境

实验学时

2学时

实验内容与步骤

1.准备实验数据

通过实验一获得的排好序的数据可作为本算法实验的输入数据。

2.实现折半查找算法

要求：实现binary_search算法。

输入：已排序数据序列A、待查找的数据元素key；

输出：数据元素key在数据序列A中的位置。

折半查找算法（类C语言）：

int binary_search(int A[], int key, int imin, int imax)

{

while (imin <= imax)

{

int imid = midpoint(imin, imax); // 找中点

if(A[imid] == key)

return imid;

else if (A[imid] < key)

imin = imid + 1;

else

imax = imid - 1;

}

// 没找到

return NOT_FOUND;

}

3.实现插值查找算法

要求：实现interp_search算法。

输入：已排序数据序列A、待查找的数据元素key；

输出：数据元素key在数据序列A中的位置。

插值查找算法（类C语言）：

int interpolation_search(int A[], int size, int key)

{

int low = 0;

int high = size - 1 ;

int mid ;

while (A[high] != A[low] && key >= A[low] && key <= A[high]) {

mid = low + (high - low) * ((key - A[low]) / ( A[high] - A[low])) ;

if (A[mid] < key)

low = mid + 1 ;

else if (key < A[mid])

high = mid - 1;

else

return mid;

}

if (key == A[low])

return low ;

else

return -1;

}

实验报告：

实验报告应包括以下内容：

（1）题目；

（2）2个算法的基本思想描述；

（3）程序流程图；

（4）程序输入和输出结果；

（5）实验分析；以表或者图的形式给出这两个算法效率的经验分析结果；

并和理论分析结论进行对比。

（6）说明本次实验的心得体会、经验等。如果程序未通过，应分析其原因。

实验三动态规划求解0/1背包问题

实验目的

1）以0/1背包问题为例，掌握动态规划算法的基本设计策略；

2）掌握并实现求解0/1背包问题的动态规划算法；

3) 分析实验结果。

实验环境

计算机、C语言程序设计环境

实验学时

2学时

实验内容与步骤

1.理解0/1背包问题

0/1背包问题的描述：已知有n个物品和一个承重为M的背包，物品i的重量为w i、价值为p i。现在的问题是：如果一个物品不能被分割以后部分放进背包，那么该如何装包，才能使背包中物品的价值之和为最大？这个问题可形式化地表述如下：

极大化目标函数∑

≤

≤n

i

i

x

p 1

i

约束条件：

M

x

w

n

i

i

≤

∑

≤

≤1

i

n

i

w

p

x

i

i

i

≤

≤

>

>

∈1

,0

,0

},

1,0{

2.准备实验数据

确定物品数目n的值，确定各物品的重量（取正整数）和价值；

确定背包的承重值M（取正整数）。

3.实现动态规划算法

要求：实现MFKnapsack算法。

输入：参数i（初次调用时为物品总数n），j（初次调用时为空包承重M）；

全局变量：物品重量Weights[1..n]，价值Values[1..n]；

输出：这i个物品的最优子集的价值。

算法MFKnapsack(i, j)（伪码）：

// 另有全局变量V[0..n, 0..M]存放已经解决的子问题的结果；V初始化：V[0,*]=0、V[*,0]=0，其他元素值初始化为负数。

if V[i,j] < 0 // 此问题还没有解

if j < Weights[i]

value ← MFKnapsack(i-1, j)

else

value ←max{MFKnapsack(i-1, j), Value[i]+MFKnapsack(i-1,

j-Weights[i])}

V[i,j] ← value

return V[i,j]

4.修改以上算法，以输出最大装包价值对应的那些装包物品。

实验报告：

实验报告应包括以下内容：

（1）题目；

（2）算法的基本思想描述；

（3）程序流程图；

（4）给出实验内容4所要求的算法伪码或程序清单；

（5）实验分析：分析算法效率；

（6）说明本次调试实验的心得体会、经验等。如果程序未通过，应分析其原因。

选做实验动态规划求解最短路径问题

实验目的：

1）以解决最短路径问题为例，掌握动态规划的基本设计策略；

2）掌握Floyd动态规划算法求解完全最短路径问题并实现；

3）分析实验结果。

实验环境

计算机、C语言程序设计环境

实验学时

2学时

实验内容与步骤

1.准备实验数据

假设算法要处理下图，需要把图数据组织存放到相应的数据结构中，如：权值矩阵float graph[maxsize][maxsize]。

2．实现Floyd算法

用Floyd算法求一个图中所有点对之间的最短距离。

输入：存储图数据的权值矩阵float graph[maxsize][maxsize]；

输出：保存到文件floyd-output1.txt。

Floyd算法（类C语言）：

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

{ // graph[i][j] = min {graph[i][j]}, graph[i][k] + graph[k][j]

for (i = 0; i < n; i ++) //每次找到最优的路径代替原来的路径

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

if (graph[i][j] > graph[i][k] + graph[k][j])

{

graph[i][j] = graph[i][k] + graph[k][j];

}

}

实验报告

实验报告应包括以下内容：

（1）题目；

（2）写出算法设计思想；

（3）程序清单；

（4）输入和输出结果；

（5）对运行情况所作的分析以及本次调试程序所取的经验。如果程序未通过，应分析其原因。

实验四贪心算法求解最短路径问题

实验目的：

1）以解决最短路径问题为例，掌握贪心算法的基本设计策略；

2）掌握Dijkstra贪心法求解单源点最短路径问题并实现；

3）分析实验结果。

实验环境

计算机、C语言程序设计环境

实验学时

2学时

实验内容与步骤

1.准备实验数据

假设算法要处理下图，需要把图数据组织存放到相应的数据结构中，如：权值矩阵float graph[maxsize][maxsize]。

2.实现Dijkstra算法

以上图作为输入，利用Dijkstra贪心算法获取由结点1到其余各顶点的最短路径及长度。

输入：存储图数据的权值矩阵float graph[maxsize][maxsize]；

输出：保存到文件dijkstra-output1.txt。

Dijkstra算法（类C语言）：

void dijkstra()

{

initialize();

int count=0;

int i;

int u;

while (count < num_of_vertices)

{

u = minimum();

set[++count] = u; // u进入单源点最小生成树的顶点集

mark[u] = 1;

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

{

if (graph[u][i] > 0 && mark[i] != 1)

{ // 顶点u到i有弧相连并且顶点i到源点的最短路径还没有确定

if(pathestimate[i] > pathestimate[u]+graph[u][i])

{

pathestimate[i] = pathestimate[u]+graph[u][i];

predecessor[i] = u;

}

}

}

}

}

3. 改写你的程序，求图中所有点对之间的最短距离；输出保存到文件dijkstra-output2.txt。

实验报告

实验报告应包括以下内容：

（1）题目；

（2）写出算法设计思想；

（3）程序清单；

（4）输入和输出结果；

（5）对运行情况所作的分析以及本次调试程序所取的经验。如果程序未通过，应分析其原因。

选做实验贪心算法求解背包问题

实验目的

1）以背包问题为例，掌握贪心法的基本设计策略；

2）熟练掌握各种贪心策略情况下的背包问题的算法并实现；其中：量度标准分别取：效益增量p、物品重量w、p/w比值；

3) 分析实验结果来验证理解贪心法中目标函数设计的重要性。

实验环境

计算机、C语言程序设计环境

实验学时

2学时

实验内容与步骤

1.理解需要求解背包问题

（1）背包问题的描述：已知有n个物品和一个承重为M的背包，物品i的重量为w i、价值为p i。如果将物品i的一部分x i（0 ≤x i ≤1）放入背包会有p i x i 的效益。由于背包承重为M，所以要求装入背包的物品的总重量不得超过M。

假如这n件物品的总重量不超过M，则可将所有物品装入背包并获得最大效益。但在这些物品重量的和大于M的情况下，该如何装包，才能得到最大的效益值？这个问题可形式化地表述如下：

极大化目标函数∑

≤

≤n

i

i

x

p 1

i

约束条件：

M

x

w

n

i

i

≤

∑

≤

≤1

i

n

i

w

p

x

i

i

i

≤

≤

>

>

≤

≤1

,0

,0

,1

（2）用贪心策略求解背包问题

首先需确定最优的量度标准。这里考虑三种策略：

策略1：按物品价值p降序装包，

策略2：按物品重w升序装包

策略3：按物品价值与重量比值p/w的降序装包（3）分别以上面三种策略分别求以下情况背包问题的解：n=7，M=15，

（p1 , … , p7）=（10，5，15，7，6，18，3）

（w1 , … , w7）=（2，3，5，7，1，4，1）。

以策略3为例的背包问题的贪心算法描述：

procedure GREEDY-KNAPSACK(P,W,M,X,n)

// P（1：n）和W（1：n）分别含有按P（i）/W（i）≥P（i+1）/ W （i+1）排序的n件物品的效益值和重量。M是背包的容量，而X（1：n）是解

向量。//

real P(1：n)，W（1：n）,X（1：n），M，cu；

integer i，n;

X←0 //将解向量初始化为零

cu←M //cu是背包剩余容量

for i←1 to n do

if W(i)>cu then exit endif

X(i) ←1

cu←cu-W(i)

repeat

if i≤n

then X(i) ←cu/W(i)

endif

end GREEDY-KNAPSACK

5.以策略1作为量度标准求解要求问题，记录解向量为X1、目标函数的值fp1

（即最后装好包后背包的效益值∑

≤

≤n

i

i x p

1i

）、背包的重量fw1；

6.以策略2作为量度标准求解要求问题，记录解向量为X21、目标函数的值fp2

（即最后装好包后背包的效益值∑

≤

≤n

i

i x p

1i

）、背包的重量fw2；

7.以策略3作为量度标准求解要求问题，记录解向量为X3、目标函数的值fp3

即最后装好包后背包的效益值∑

≤

≤n

i

i x p

1i

）、背包的重量fw3。

实验报告：

实验报告应包括以下内容：

（1）题目；

（2）算法的基本思想描述；

（3）程序流程图；

（4）给出3个程序任意之一的程序清单；

（5）实验分析；通过实验结果对比分析说明哪种策略好。

（6）说明本次调试实验的心得体会、经验等。如果程序未通过，应分析其原因。

Tips：

1. 解向量的表示。需要注意：因为算法中涉及到排序，如何保证各种物品的原

始命名（如果以第几种，即序号，来命名物品）关系需要考虑。

#define MAX 200

typedef struct Solution //定义的解向量

{

int x[MAX]; 表示该号物品放了多少在背包里，这里i 0x 1≤≤ int order[MAX]; 表示物品的序号，相当于其名字

}Solution;

Solution X;

所以，初始化时，为：

for (i=0; i

{

X.order[i]=i;

X.x[i]=0;

}

2. 主要函数：

void GreedyKnapsack(float profit[],float weight[],float x[],int m, int n) {

float cu;

int i;

cu=float(m);

for(i=0;i

{

x[i]=0;

}

for(i=0;i

{

if(weight[i]>cu)

break;

x[i]=1;

cu=cu-weight[i];

}

if(i

{ x[i]=cu/weight[i];

} }

选做实验回溯法求解N皇后问题

实验目的：

1）以N-皇后问题为例，掌握回溯法的基本设计策略；

2）掌握回溯法解决N-皇后问题的算法并实现；

3）分析实验结果。

实验环境

计算机、C语言程序设计环境

实验学时

2学时

实验内容与步骤

1.用回溯法求解N-Queen，参考教材算法思想，并实现你的算法。

要求：用键盘输入N；输出此时解的个数，并统计运算时间。

2.给出N=4, 5, 6时，N-Queen解的个数。

3.尝试增大N，观察运行情况；并理解该算法的时间复杂度。

实验报告

实验报告应包括以下内容：

（1）题目；

（2）写出算法设计思想；

（3）运行的结果；

（4）对运行情况所作的分析以及本次调试程序所取的经验。

（5）如果程序未通过，应分析其原因。

Tips: 主要函数等

while (k>0) // 对所有行执行以下语句

{

X[k] = X[k]+1; // 移到下一列

while(X[k]<=n && !PLACE(k) )

{

X[k] = X[k]+1; // 移到下一列，再判断

}

if (X[k] <= n) // 找到一个位置

{

if (k==n) // 一个完整的解

{

// print

printf("the soution is:\n");

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

printf("%3d",X[t]);

printf("\n");

count +=1 ;

}

else

{k=k+1; X[k]=0;} // 转向下一行}

else

k=k-1; // 回溯

}

printf("\n the number of the solutions is %d \n", count);

bool PLACE (int k)

{

i=1;

while(i

{

if (X[i]==X[k] || abs(X[i]-X[k])==abs(i-k) )

return false;

i=i+1;

}

return true;

}

算法分析与设计复习题及参考答案

网络教育课程考试复习题及参考答案算法分析与设计一、名词解释：1.算法 2.程序 3.递归函数 4.子问题的重叠性质 5.队列式分支限界法 6.多机调度问题7.最小生成树二、简答题： 1.备忘录方法和动态规划算法相 比有何异同？简述之。 2.简述回溯法解题的主要步骤。 3.简述动态规划算法求解的基本要素。 4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 6.简要分析分支限界法与回溯法的异同。7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？8.贪心算法求解的问题主要具有哪些性质？简述之。9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。10.简述分析贪心算法与动态规划 算法的异同。三、算法编写及算法应用分析题： 1.已知有3个物品： (w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。 2.按要求完成以下关于排序和查找的问题。①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。③给出上述算法的递归算法。④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。已知，=1，2，3，4，5，6，=5，=10，=3，=12，=5，=50，=6，kijr*r1234567ii1求矩阵链积A×A×A×A×A×A的最佳求积顺序（要求给出计算步骤）。1234564.根据分枝限界算法基本过程,求解0-1背包问题。已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。 5.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。6.试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：①删除一个字符。②插入一个字符。③将一个字符改为另一个字符。请写出该算法。7.对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。be2g212ad323182cf2h 8.试写出用分治法对数组A[n]实现快速排序的算法。9.有n个活动争用一个活动室。已知活动i占用的时间区域为[s，f ]，活动i,j相容的条件是：sj≥f ii，问题的解表示为(x| x =1，2…，n,)，x表示顺序为i的活动编号活动，求一个相容的活动子集，iiii且安排的活动数目最多。xxx10.设、、是一个三角形的三条边，而且x+x+x=14。请问有多少种不同的三角形？给出解答过程。12312311.

算法分析与设计总结

第一章算法概述 1.算法：解决问题的一种方法或过程；由若干条指令组成的有穷指令。 2.算法的性质： 1)输入：有零个或多个输入 2)输出：有至少一个输出 3)确定性：每条指令是清晰的、无歧义的 4)有限性：每条指令的执行次数和时间都是有限的 3.算法与程序的区别 程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的有限性 4.算法复杂性分析 1)算法的复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复 杂性，需要空间资源的量称为空间复杂性 2)三种时间复杂性：最坏情况、最好情况、平均情况 3)可操作性最好且最有实际价值的是最坏情况下的时间复杂性 第二章递归与分支策略 1.递归概念：直接或间接调用自身的算法 2.递归函数：用函数自身给出定义的函数 3.递归要素：边界条件、递归方程 4.递归的应用 ?汉诺塔问题 void Hanuo(int n,int a,int b,int c) { if(n==1) return; Hanuo(n-1,a,c,b); move(a,b) Hanuo(n-1,c,b,a); } ?全排列问题 void Perm(Type list[],int k,int m) { //产生list[k,m]的所有排列 if(k == m) { for(int i = 0;I <= m;i++) cout<

测试技术实验指导书及实验报告2006级用汇总

矿压测试技术实验指导书 学号： 班级： 姓名： 安徽理工大学 能源与安全学院采矿工程实验室

实验一常用矿山压力仪器原理及使用方法 第一部分观测岩层移动的部分仪器 ☆深基点钻孔多点位移计 一、结构简介 深基点钻孔多点位移计是监测巷道在掘进和受采动影响的整个服务期间，围岩内部变形随时间变化情况的一种仪器。 深基点钻孔多点位移包括孔内固定装置、孔中连接钢丝绳、孔口测读装置组成。每套位移计内有5~6个测点。其结构及其安装如图1所示。 二、安装方法 1.在巷道两帮及顶板各钻出φ32的钻孔。 2.将带有连接钢丝绳的孔内固定装置，由远及近分别用安装圆管将其推至所要求的深度。(每个钻孔布置5~6个测点，分别为；6m、5m、4m、3m、2m、lm或12m、10m、8m、6m、4m、2m)。 3.将孔口测读装置，用水泥药圈或木条固定在孔口。 4。拉紧每个测点的钢丝绳，将孔口测读装置上的测尺推至l00mm左右的位置后，由螺丝将钢丝绳与测尺固定在一起。 三、测试方法 安装后先读出每个测点的初读数，以后每次读得的数值与初读数之差，即为测点的位移值。当读数将到零刻度时，松开螺丝，使测尺再回到l00mm左右的位置，重新读出初读数。 ☆顶板离层指示仪 一、结构简介： 顶板离层指示仪是监测顶板锚杆范围内及锚固范围外离层值大小的一种监测仪器，在顶板钻孔中布置两个测点，一个在围岩深部稳定处，一个在锚杆端部围岩中。离层值就是围岩中两测点之间以及锚杆端部围岩与巷道顶板表面间的相对位移值。顶板离层指示仪由孔内固定装置、测量钢丝绳及孔口显示装置组成如图1所示。

二、安装方法： 1.在巷道顶板钻出φ32的钻孔，孔深由要求而定。 2.将带有长钢丝绳的孔内固定装置用安装杆推到所要求的位置；抽出安装杆后再将带有短钢丝绳的孔内固定装置推到所要求的位置。 3.将孔口显示装置用木条固定在孔口(在显示装置与钻孔间要留有钢丝绳运动的间隙)。 4.将钢丝绳拉紧后，用螺丝将其分别与孔口显示装置中的圆管相连接，且使其显示读数超过零刻度线。 三、测读方法： 孔口测读装置上所显示的颜色，反映出顶板离层的范围及所处状态，显示数值表示顶板的离层量。☆DY—82型顶板动态仪 一、用途 DY-82型顶板动态仪是一种机械式高灵敏位移计。用于监测顶底板移近量、移近速度，进行采场“初次来压”和“周期来压”的预报，探测超前支撑压力高 峰位置，监测顶板活动及其它相对位移的测量。 二、技术特征 (1)灵敏度(mm) 0.01 (2)精度(％) 粗读±1,微读±2.5 (3)量程(mm) 0～200 (4)使用高度(mm) 1000～3000 三、原理、结构 其结构和安装见图。仪器的核心部件是齿条6、指针8 以及与指针相连的齿轮、微读数刻线盘9、齿条下端带有读 数横刻线的游标和粗读数刻度管11。 当动态仪安装在顶底板之间时，依靠压力弹簧7产生的 弹力而站立。安好后记下读数(初读数)并由手表读出时间。 粗读数由游标10的横刻线在刻度管11上的位置读出，每小 格2毫米，每大格(标有“1”、“22'’等)为10毫米，微读数 由指针8在刻线盘9的位置读出，每小格为0.01毫米(共200 小格，对应2毫米)。粗读数加微读数即为此时刻的读数。当 顶底板移近时，通过压杆3压缩压力弹簧7，推动齿条6下 移，带动齿轮，齿轮带动指针8顺时针方向旋转，顶底板每 移近0.01毫米，指针转过1小格；同时齿条下端游标随齿条 下移，读数增大。后次读数减去前次读数，即为这段时间内的顶底板移近量。除以经过的时间，即得

算法设计与分析复习题目及答案

一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ）

混凝土结构实验指导书及实验报告(学生用)

土木工程学院 《混凝土结构设计基本原理》实验指导书 及实验报告 适用专业：土木工程周淼 编 班级：：学 号： 理工大学 2018 年9 月

实验一钢筋混凝土梁受弯性能试验 一、实验目的 1.了解适筋梁的受力过程和破坏特征； 2.验证钢筋混凝土受弯构件正截面强度理论和计算公式； 3.掌握钢筋混凝土受弯构件的实验方法及荷载、应变、挠度、裂缝宽度等数据的测试技术 和有关仪器的使用方法； 4.培养学生对钢筋混凝土基本构件的初步实验分析能力。 二、基本原理当梁中纵向受力钢筋的配筋率适中时，梁正截面受弯破坏过程表现为典型的三个阶段：第一阶段——弹性阶段（I阶段）：当荷载较小时，混凝土梁如同两种弹性材料组成的组合梁，梁截面的应力呈线性分布，卸载后几乎无残余变形。当梁受拉区混凝土的最大拉应力达到混凝土的抗拉强度，且最大的混凝土拉应变超过混凝土的极限受拉应变时，在纯弯段某一薄弱截面出现首条垂直裂缝。梁开裂标志着第一阶段的结束。此时，梁纯弯段截面承担的弯矩M cr称为开裂弯矩。第二阶段——带裂缝工作阶段（II阶段）：梁开裂后，裂缝处混凝土退出工作，钢筋应力急增，且通过粘结力向未开裂的混凝土传递拉应力，使得梁中继续出现拉裂缝。压区混凝土中压应力也由线性分布转化为非线性分布。当受拉钢筋屈服时标志着第二阶段的结束。此时梁纯弯段截面承担的弯矩M y称为屈服弯矩。第三阶段——破坏阶段（III阶段）：钢筋屈服后，在很小的荷载增量下，梁会产生很大的变形。裂缝的高度和宽度进一步发展，中和轴不断上移，压区混凝土应力分布曲线渐趋丰满。当受压区混凝土的最大压应变达到混凝土的极限压应变时，压区混凝土压碎，梁正截面受弯破坏。此时，梁承担的弯矩M u 称为极限弯矩。适筋梁的破坏始于纵筋屈服，终于混凝土压碎。整个过程要经历相当大的变形，破坏前有明显的预兆。这种破坏称为适筋破坏，属于延性破坏。 三、试验装置

算法设计与分析书中程序

【程序5-1】分治法 SolutionType DandC(ProblemType P) { ProblemType P1，P2， ，P k。 if (Small(P)) return S(P)。//子问题P足够小，用S(P)直接求解 else { Divide(P，P1，P2， ，P k)。//将问题P分解成子问题P1, P2, …,P k Return Combine(DandC(P1)，DandC(P2)，…，DandC(P k))。//求解子问题，并合并解 } } 【程序5-2】一分为二的分治法 SolutionType DandC(int left，int right) { if (Small(left，right)) return S(left，right)。 else { int m=Divide(left，right)。//以m为界将问题分解成两个子问题Return Combine(DandC(left，m)，DandC(m+1，right))。//分别求解子问题，并合并解 } } 【程序5-3】可排序表类 template struct E { //可排序表中元素的类型 operator K()const { return key。} //重载类型转换运算符 K key。//关键字可以比较大小 D data。//其他数据 }。 template class SortableList { //可排序表类 public: SortableList(int mSize) //构造函数 { maxSize=mSize。 l=new T[maxSize]。 n=0。

算法分析与设计

专业： 班级： 学号： 姓名： 日期： 2014年 11月 10日

48476Λn n 111+++=。 2、q(n ，m)=q(n ，n)，m>=n 。 最大加数n1实际上不能大于n ，因此，q(1，m)=1。 3、q(n ，n)=1+q(n ，n-1)。 正整数n 的划分由n1=n 的划分和n1<=n-1的划分组成。 4、q(n ，m)= q(n ，m-1)+q(n-m ，m)，n>m>1。 正整数n 的最大加数n1不大于m 的划分由n1=m 的划分和n1<=m-1的划分组成。 （2）、算法描述 public class 张萌 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub System.out .println(q (2,2)); } public static int q(int n,int m) { if ((n<1)||(m<1)) return 0; if ((n==1)||(m==1)) return 1; if (n

土工实验指导书及实验报告

土工实验指导书及实验报告编写毕守一 安徽水利水电职业技术学院 二OO九年五月

目录 实验一试样制备 实验二含水率试验 实验三密度试验 实验四液限和塑限试验 实验五颗粒分析试验 实验六固结试验 实验七直接剪切试验 实验八击实试验 土工试验复习题

实验一试样制备 一、概述 试样的制备是获得正确的试验成果的前提，为保证试验成果的可靠性以及试验数据的可比性，应具备一个统一的试样制备方法和程序。 试样的制备可分为原状土的试样制备和扰动土的试样制备。对于原状土的试样制备主要包括土样的开启、描述、切取等程序；而扰动土的制备程序则主要包括风干、碾散、过筛、分样和贮存等预备程序以及击实等制备程序，这些程序步骤的正确与否，都会直接影响到试验成果的可靠性，因此，试样的制备是土工试验工作的首要质量要素。 二、仪器设备 试样制备所需的主要仪器设备，包括： （1）孔径0.5mm、2mm和5mm的细筛； （2）孔径0.075mm的洗筛； （3）称量10kg、最小分度值5g的台秤； （4）称量5000g、最小分度值1g和称量200g、最小分度值0.01g的天平；

（5）不锈钢环刀（内径61.8mm、高20mm；内径79.8mm、高20mm或内径61.8mm、高40mm）； （6）击样器：包括活塞、导筒和环刀； （7）其他：切土刀、钢丝锯、碎土工具、烘箱、保湿器、喷水设备、凡士林等。 三、试样制备 （一）原状土试样的制备步骤 1、将土样筒按标明的上下方向放置，剥去蜡封和胶带，开启土样筒取土样。 2、检查土样结构，若土样已扰动，则不应作为制备力学性质试验的试样。 3、根据试验要求确定环刀尺寸，并在环刀内壁涂一薄层凡士林，然后刃口向下放在土样上，将环刀垂直下压，同时用切土刀沿环刀外侧切削土样，边压边削直至土样高出环刀，制样时不得扰动土样。 4、采用钢丝锯或切土刀平整环刀两端土样，然后擦净环刀外壁，称环刀和土的总质量。 5、切削试样时，应对土样的层次、气味、颜色、夹杂物、裂缝和均匀性进行描述。 6、从切削的余土中取代表性试样，供测定含水率以及颗粒分析、界限含水率等试验之用。

算法分析与设计

第一章 什么是算法 算法是解决一个计算问题的一系列计算步骤有序、合理的排列。对一个具体问题（有确定的输入数据）依次执行一个正确的算法中的各操作步骤，最终将得到该问题的解（正确的输出数据）。 算法的三个要素 1).数据: 运算序列中作为运算对象和结果的数据. 2).运算: 运算序列中的各种运算:赋值,算术和逻辑运算 3).控制和转移: 运算序列中的控制和转移. 算法分类 从解法上：数值型算法:算法中的基本运算为算术运算；非数值型算法:算法中的基本运算为逻辑运算. 从处理方式上：串行算法:串行计算机上执行的算法；并行算法:并行计算机上执行的算法 算法的五个重要的特性 （1） 有穷性：在有穷步之后结束。 （2） 确定性：无二义性。 （3） 可行性：可通过基本运算有限次执行来实现。 （4） 有输入 表示存在数据处理 （5） 有输出 伪代码 程序设计语言（PDL ），也称为结构化英语或者伪代码，它是一种混合语言，它采用一种语言（例如英语）的词汇同时采用类似另外一种语言（例如，结构化程序语言）的语法。 特点：1)使用一些固定关键词的语法结构表达了结构化构造、数据描述、模块的特征； 2)以自然语言的自由语法描述了处理过程；3)数据声明应该既包括简单的也包括复杂的数据结构；4)使用支持各种模式的接口描述的子程序定义或者调用技术。 求两个n 阶方阵的相加C=A+B 的算法如下，分析其时间复杂度。 #define MAX 20 ∑∑∑∑-=-=-=-=====102101010*11n i n i n i n j n n n n n n n n )O()1O(1O(11i i j i j ==∑∑==）)O(N )21O()O()O(21N 1=+=∑=∑==)(N N i i N i i 赋值，比较，算术运算，逻辑运算，读写单个变量（常量）只需1单位时间 2). 执行条件语句 if c then S1 else S2 的时间为TC +max(TS1,TS2). 3). 选择语句 case A of a1: s1；a2: s2；...； am: sm 需要的时间为 max （TS1,TS2 ,..., TSm ）. 4). 访问数组的单个分量或纪录的单个域需要一个单位时间. 5). 执行for 循环语句的时间=执行循环体时间*循环次数. 6). while c do s (repeat s until c)语句时间=(Tc+Ts)*循环次数. 7). 用goto 从循环体内跳到循环体末或循环后面的语句时,不需额外时间 8). 过程或函数调用语句：对非递归调用，根据调用层次由里向外用规则1-7进行分析； 对递归调用，可建立关于T(n)的递归方程,求解该方程得到T(n).

CAD上机实验指导书及实验报告

北京邮电大学世纪学院 实验、实习、课程设计报告撰写格式与要求 （试行） 一、实验报告格式要求 1、有实验教学手册，按手册要求填写，若无则采用统一实验报告封面。 2、报告一律用钢笔书写或打印，打印要求用A4纸；页边距要求如下：页边距上下各为2.5厘米，左右边距各为2.5厘米；行间距取固定值（设置值为20磅）；字符间距为默认值（缩放100%，间距：标准）。 3、统一采用国家标准所规定的单位与符号，要求文字书写工整，不得潦草；作图规范，不得随手勾画。 4、实验报告中的实验原始记录，须经实验指导教师签字或登记。 二、实习报告、课程设计报告格式要求 1、采用统一的封面。 2、根据教学大纲的要求手写或打印，手写一律用钢笔书写，统一采用国家标准所规定的单位与符号，要求文字书写工整，不得潦草；作图规范，不得随手勾画。打印要求用A4纸；页边距要求如下：页边距上下各为2.5厘米，左右边距各为2.5厘米；行间距取固定值（设置值为20磅）；字符间距为默认值（缩放100%，间距：标准）。 三、报告内容要求 1、实验报告内容包括：实验目的、实验原理、实验仪器设备、实验操作过程、原始数据、实验结果分析、实验心得等方面内容。 2、实习报告内容包括：实习题目、实习任务与要求、实习具体实施情况（附上图表、原始数据等）、实习个人总结等内容。 3、课程设计报告或说明书内容包括：课程设计任务与要求、总体方案、方案设计与分析、所需仪器设备与元器件、设计实现与调试、收获体会、参考资料等方面内容。 北京邮电大学世纪学院 教务处 2009-8

实验报告 课程名称计算机绘图（CAD） 实验项目AutoCAD二维绘图实验 专业班级 姓名学号 指导教师实验成绩 2016年11月日

算法设计与分析所有程序

目录 第二章递归与分治 (3) 1、用递归思想求N! (3) 2、用递归思想求Fibonacci数列 (3) 3、用递归思想求排列问题 (4) 4、用递归思想求整数划分问题 (5) 5、用递归思想求汉诺塔问题 (6) 6、用递归思想实现插入排序 (7) 7、用分治思想实现二分查找 (8) 8、用分治法求两个大整数的乘法 (9) 9、用分治思想求一个数组的最大值与最小值 (10) 10、用分法思想实现合并排序 (12) 11、用分治思想实现快速排序 (13) 12、用分治法实现线性时间选择问题 (15) 13、用分法思想实现残缺棋盘问题 (15) 第三章动态规划法 (18) 1、矩阵连乘问题 (18) 2、最长公子序列 (20) 3、最大子段和问题 (23) 4、图像压缩问题 (28) 5、电路布线问题 (31) 6、最 (31) 7、最 (31) 第四章贪心算法 (32) 1、哈夫曼编码 (32) 4、Kruskal算法求最小生成树 (35) 5、集装箱问题 (38) 6、活动安排问题 (40) 第五章回溯法 (42) 1、用回溯法求0－1背包问题 (42)

2、用回溯法求N皇后问题 (45) 3、用回溯法求旅行售货员问题 (46) 4、用回溯法求圆排列问题 (48) 5、用回溯法求符号三角形问题 (50) 6、用回溯法求批处理作业调度问题 (52) 7、用回溯法求连续邮资问题 (54) 8、用回溯法求图的m着色问题 (57) 9、用回溯法求最大团问题 (59) 第六章回溯法 (62) 1、用分支限界法求0－1背包问题 (62)

第二章递归与分治1、用递归思想求N! 王晓东版——《计算机算法设计与分析（第四版）》P11页，例2－1 2、用递归思想求Fibonacci数列 王晓东版——《计算机算法设计与分析（第四版）》P12页，例2－2

算法分析与设计习题集整理

算法分析与设计习题集整理 第一章算法引论 一、填空题： 1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。 2、多项式10()m m A n a n a n a =+++L 的上界为O(n m )。 3、算法的基本特征：输入、输出、确定性、有限性 、可行性 。 4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。 5、计算下面算法的时间复杂度记为： O(n 3) 。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; } 6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。 7、算法设计的基本要求：正确性 和 可读性。 8、计算下面算法的时间复杂度记为： O(n 2) 。 for （i ＝1；i

《流体力学》课程实验(上机)指导书及实验报告格式

《流体力学》课程实验指导书袁守利编 汽车工程学院 2005年9月

前言 1.实验总体目标、任务与要求 1)学生在学习了《流体力学》基本理论的基础上，通过伯努利方程实验、动量方程实 验，实现对基本理论的验证。 2）通过实验，使学生对水柱（水银柱）、U型压差计、毕托管、孔板流量计、文丘里流量计等流体力学常用的测压、测流量装置的结构、原理和使用有基本认识。 2.适用专业 热能与动力工程 3.先修课程 《流体力学》相关章节。 4.实验项目与学时分配 5. 实验改革与特色 根据实验内容和现有实验条件，在实验过程中，采取学生自己动手和教师演示相结合的方法，力求达到较好的实验效果。

实验一伯努利方程实验 1．观察流体流经实验管段时的能量转化关系，了解特定截面上的总水头、测压管水头、压强水头、速度水头和位置水头间的关系，从而加深对伯努利方程的理解和认识。 2．掌握各种水头的测试方法和压强的测试方法。 3．掌握流量、流速的测量方法，了解毕托管测速的原理。 二、实验条件 伯努利方程实验仪 三、实验原理 1．实验装置： 图一伯努利方程实验台 1.水箱及潜水泵 2.上水管 3.电源 4.溢流管 5.整流栅 6.溢流板 7.定压水箱 8.实验 细管9. 实验粗管10.测压管11.调节阀12.接水箱13.量杯14回水管15.实验桌 2.工作原理 定压水箱7靠溢流来维持其恒定的水位，在水箱下部装接水平放置的实验细管8，水经实验细管以恒定流流出，并通过调节阀11调节其出水流量。通过布置在实验管四个截面上的四组测压孔及测压管，可以测量到相应截面上的各种水头的大小，从而可以分析管路中恒定流动的各种能量形式、大小及相互转化关系。各个测量截面上的一组测压管都相当于一组毕托管，所以也可以用来测管中某点的流速。 电测流量装置由回水箱、计量水箱和电测流量装置（由浮子、光栅计量尺和光电子

算法设计与分析基础课后习题答案

Program算法设计与分析基础中文版答案 习题 5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint: 根据除法的定义不难证明: 如果d整除u和v, 那么d一定能整除u±v; 如果d整除u,那么d也能够整除u的任何整数倍ku. 对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。 数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint: 对于任何形如0<=m

设sqrt(x)是求平方根的函数) 算法Quadratic(a,b,c) 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述 解答： a.将十进制整数转换为二进制整数的算法 输入：一个正整数n 输出：正整数n相应的二进制数 第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n 第二步：如果n=0，则到第三步，否则重复第一步 第三步：将Ki按照i从高到低的顺序输出 b.伪代码 算法 DectoBin(n) .n]中 i=1 while n!=0 do { Bin[i]=n%2; n=(int)n/2; i++; } while i!=0 do{ print Bin[i]; i--; } 9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进. 算法 MinDistance(A[0..n-1])

算法分析与设计-课程设计报告

XXXX大学 算法设计与分析课程设计报告 院（系）： 年级： 姓名： 专业：计算机科学与技术 研究方向：互联网与网络技术 指导教师： XXXX 大学

目录 题目1 电梯调度 (1) 1.1 题目描述 (1) 1.2 算法文字描述 (1) 1.3 算法程序流程 (4) 1.4 算法的程序实现代码 (10) 题目2 切割木材 (12) 2.1题目描述 (12) 2.2算法文字描述 (12) 2.3算法程序流程 (13) 2.4算法的程序实现代码 (18) 题目3 设计题 (20) 3.1题目描述 (20) 3.2 输入要求 (20) 3.3输出要求 (20) 3.4样例输入 (20) 3.5样例输出 (20) 3.6测试样例输入 (21) 3.7测试样例输出 (21) 3.8算法实现的文字描述 (21) 3.9算法程序流程 (22) 3.10算法的程序实现代码 (23) 算法分析与设计课程总结 (26) 参考文献 (27)

题目1电梯调度 1.1 题目描述 一栋高达31层的写字楼只有一部电梯，其中电梯每走一层需花费4秒，并且在每一层楼停靠的时间为10秒，乘客上下一楼需要20秒，在此求解最后一位乘客到达目的楼层的最短时间以及具体的停靠计划。例如：此刻电梯停靠需求为4 5 10（有三位乘客，他们分别想去4楼、5楼和10楼），如果在每一层楼都停靠则三位乘客到达办公室所需要的时间为3*4=12秒、4*4+10=26秒、4*9+2*10=56秒，则最后一位乘客到达办公室的时间为56秒，相应的停靠计划为4 5 10均停靠。对于此测试用例电梯停靠计划方案：4 10，这样到第4楼的乘客所需时间为3*4=12秒，到第5楼的乘客所需时间为3*4+20=32秒，到第10楼的乘客所需时间为9*4+10=46秒，即最后到达目的楼层的顾客所需时间为46秒。 输入要求： 输入的第1行为整数n f1 f2 … fn，其中n表示有n层楼需要停靠，n=0表示没有更多的测试用例，程序终止运行。f1 f2 … fn表示需要停靠的楼层（n<=30，2<=f1

电磁场实验指导书及实验报告

CENTRAL SOUTH UNIVERSITY 题目利用Matlab模拟点电荷电场的分布姓名xxxx 学号xxxxxxxxxx 班级电气xxxx班 任课老师xxxx 实验日期2010-10

电磁场理论 实验一 ——利用Matlab 模拟点电荷电场的分布 一．实验目的： 1．熟悉单个点电荷及一对点电荷的电场分布情况； 2．学会使用Matlab 进行数值计算，并绘出相应的图形； 二．实验原理： 根据库伦定律：在真空中，两个静止点电荷之间的作用力与这两个电荷的电量乘积成正比，与它们之间距离的平方成反比，作用力的方向在两个电荷的连线上，两电荷同号为斥力，异号为吸力，它们之间的力F 满足： R R Q Q k F ? 212 = (式1) 由电场强度E 的定义可知： R R kQ E ? 2 = (式2) 对于点电荷，根据场论基础中的定义，有势场E 的势函数为 R kQ U = (式3) 而 U E -?= (式4) 在Matlab 中，由以上公式算出各点的电势U ，电场强度E 后，可以用Matlab 自带的库函数绘出相应电荷的电场分布情况。 三．实验内容： 1. 单个点电荷 点电荷的平面电力线和等势线 真空中点电荷的场强大小是E=kq /r^2 ,其中k 为静电力恒量, q 为电量, r 为点电荷到场点P(x,y)的距离。电场呈球对称分布, 取电量q> 0, 电力线是以电荷为起点的射线簇。以无穷远处为零势点, 点电荷的电势为U=kq /r,当U 取

常数时, 此式就是等势面方程.等势面是以电荷为中心以r 为半径的球面。 平面电力线的画法 在平面上, 电力线是等角分布的射线簇, 用MATLAB 画射线簇很简单。取射线的半径为( 都取国际制单位) r0=, 不同的角度用向量表示( 单位为弧度) th=linspace(0,2*pi,13)。射线簇的终点的直角坐标为: [x,y]=pol2cart(th,r0)。插入x 的起始坐标x=[x; *x].同样插入y 的起始坐标, y=[y; *y], x 和y 都是二维数组, 每一列是一条射线的起始和终止坐标。用二维画线命令plot(x,y)就画出所有电力线。 平面等势线的画法 在过电荷的截面上, 等势线就是以电荷为中心的圆簇, 用MATLAB 画等势 线更加简单。静电力常量为k=9e9, 电量可取为q=1e- 9; 最大的等势线的半径应该比射线的半径小一点 r0=。其电势为u0=k8q /r0。如果从外到里取7 条等势线, 最里面的等势线的电势是最外面的3 倍, 那么各条线的电势用向量表示为: u=linspace(1,3,7)*u0。从- r0 到r0 取偶数个点, 例如100 个点, 使最中心点的坐标绕过0, 各点的坐标可用向量表示: x=linspace(- r0,r0,100), 在直角坐标系中可形成网格坐标: [X,Y]=meshgrid(x)。各点到原点的距离为: r=sqrt(X.^2+Y.^2), 在乘方时, 乘方号前面要加点, 表示对变量中的元素进行乘方计算。各点的电势为U=k8q. /r, 在进行除法运算时, 除号前面也要加点, 同样表示对变量中的元素进行除法运算。用等高线命令即可画出等势线 contour(X,Y,U,u), 在画等势线后一般会把电力线擦除, 在画等势线之前插入如下命令hold on 就行了。平面电力线和等势线如图1, 其中插入了标题等等。越靠近点电荷的中心, 电势越高, 电场强度越大, 电力线和等势线也越密。

解析算法和程序实现教学设计Word版

解析算法及程序实现教学设计 一、设计思想 根据《新课标》的要求，本课“解析算法”的学习目的是使学生进一步体验算法设计思想。为了让学生更易理解其算法的思想：用解析法找出数学表达式，用它来描述问题的原始数据与结果之间的关系。本堂课的设计思路：通过一元二次方程求解实例引入主题——认知主题——实践体验主题——扩展与提高这几个阶段层层深入的递进式方法使学生充分掌握解析算法。从而使学生形成解析算法的科学逻辑结构。 二、教材分析 本课的课程标准内容： 结合实例，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程，认识算法和程序设计在其中的地位和作用。掌握使用解析算法设计程序解决问题的方法基本要求：1.初步掌握解析算法。2.初步掌握解析算法的程序实现。 教材中很多例子，但是考虑到课时，具体采用了“计算1900年开始的任意一天是星期几”的问题。 三、学情分析 学生对程序的3种基本模式已有一个了解的基础，对于简单的程序段也有一定的认知意识。并且已学习了枚举算法，这对本节课的教学产生积极的作用。但学生还是会觉得算法设计比较难掌握，困难之处在于，如何将题目的设计思想转化为流程图，根据流程图写出相应的代码并通过自己编制程序上机实践来体验。因此在课堂分析过程中，学生应当从听课认识——分析理解——实践探究这些过程中全面掌握解析算法的设计思想，并能用此算法来解决日常生活问题及与其他学科有所关联的一些简单问题。 四、教学目标 知识与技能：理解解析算法的概念和特点，通过分析了解解析算法的解题结构，初步掌握对解析算法的程序实现。 过程与方法：通过具体问题分析，归纳解析算法的基本思想和方法，确定解题步骤。让学生理解如何用3步法来解决实际问题（提出问题——分析问题——解决问题）； 情感态度与价值观：通过小组合作，增进学生间的学习交流，培养合作能力，激发学生学习能动性；感受解析算法的魅力，养成始终坚持、不断积累才能获得成功的意志品质。 五、重点与难点 重点：通过计算1900年开始的任意一天是星期几，让学生理解解析算法的思想，初步

算法分析与设计复习题及答案

算法分析与设计复习题及答案一、单选题 1．D 2．B 3．C 4．D 5．D 6．D 7．C 8．D 9．B 10．C 11．D 12．B 13．D 14．C 15．C 16．D 17．D 18．D 19．D 20．C 1．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 2．根据执行算法的计算机指令体系结构，算法可以分为（）。 Ａ精确算法与近似算法Ｂ串行算法语并行算法 Ｃ稳定算法与不稳定算法Ｄ３２位算法与６４位算法 3．具有１0个节点的完全二叉树的高度是（）。 Ａ６Ｂ５Ｃ3Ｄ 2 4．下列函数关系随着输入量增大增加最快的是（）。 Ａlog2n B n2 C 2n D n! 5．下列程序段的S执行的次数为( )。 for i ←0 to n-1 do for j ←0 to i-1 do s //某种基本操作 A.n2 B n2/2 C n*(n+1) D n(n+1)/2 6．Fibonacci数列的第十项为( )。 A 3 B 13 C 21 D 34 7．4个盘子的汉诺塔，至少要执行移动操作的次数为( )。 A 11次 B 13次 C 15次 D 17次 8．下列序列不是堆的是（）。 A 99，85，98，77，80，60，82，40，22，10，66 B 99，98，85，82，80，77，66，60，40，22，10 C 10，22，40，60，66，77，80，82，85，98，99 D 99，85，40，77，80，60，66，98，82，10，22 9．Strassen矩阵乘法的算法复杂度为（）。 ＡΘ(n3)ＢΘ(n2.807) ＣΘ(n2) ＤΘ(n) 10．集合A的幂集是（）。 A．A中所有元素的集合 B. A的子集合 C． A 的所有子集合的集合 D. 空集 11．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 12．从排序过程是否完全在内存中显示，排序问题可以分为（）。 Ａ稳定排序与不稳定排序Ｂ内排序与外排序 Ｃ直接排序与间接排序Ｄ主排序与辅助排序 13．下列（）不是衡量算法的标准。 Ａ时间效率Ｂ空间效率 Ｃ问题难度Ｄ适应能力 14．对于根树，出度为零的节点为（）。 Ａ０节点Ｂ根节点Ｃ叶节点Ｄ分支节点 15．对完全二叉树自顶向下，从左向右给节点编号，节点编号为１0的父节点编号为（）。 Ａ０Ｂ２Ｃ４Ｄ６ 16．下列程序段的算法时间的复杂度为（）。 for i ←0 to n do for j ←0 to m do

算法分析与设计

《算法分析与设计》2020年03月考试考前练习题 一、简答题 附：参考答案 1. 何谓P、NP、NPC问题。 解答: P（Polynomial问题）：也即是多项式复杂程度的问题。 NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。 NPC（NP Complete）问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。 2. 动态规划算法的基本思想是什么？它和分治法有什么区别和联系？ 解答: 动态规划算法的基本思想为：该方法的思路也是将待求解的大问题分成规模较小的子问题，但所得的各子问题之间有重复子问题，为了避免子问题的重复计算，可依自底向上的方式计算最优值，并根据子问题的最优值合并得到更大问题的最优值，进而可构造出所求问题的最优解。 分治法也是将待求解的大问题分成若干个规模较小的相同子问题，即该问题具有最优子结构性质。规模缩小到一定的程度就可以容易地解决。所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题；利用该问题分解出的子问题的解可以合并为该问题的解。 3. 贪心算法和动态规划算法都要求问题具有共同的性质是？ 解答: 最优子结构性质。 4. 为什么用分治法设计的算法一般有递归调用？ 解答: 子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。 5. 简述分治法所能解决的问题一般应具有的特征。 解答: 1）该问题的规模缩小到一定的程度就可以容易地解决； 2）该问题具有最优子结构性质； 3）利用该问题分解出的子问题的解可以合并为该问题的解； 4）该问题所分解出的各个子问题是相互独立的。 6. 在回溯法中，为了避免无效的搜索，通常采用哪两种剪枝策略？ 解答: 约束剪枝，限界剪枝。 7. 给定如下二分搜索算法，请分析算法的复杂性。 int BinarySearch(Type a[], const Type& x, int l, int r){ while (r >= l){ int m = (l+r)/2; if (x == a[m]) return m; if (x < a[m]) r = m-1; else l = m+1; }