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

《算法设计与分析》实验指导书目录实验一单链表的建立插入及删除 (3)实验二多项式加法 (5)实验三集合的表示与操作算法设计 (7)实验四迷宫问题求解 (8)实验五树的建立及遍历 (11)实验六图的遍历的演示 (12)实验七哈希表的设计 (15)实验八Kruskal算法的设计 (17)实验九归并排序的分治策略设计 (19)实验十哈夫曼编码的贪心算法设计 (21)实验十一递归与迭代程序设计 (22)实验十二多段图问题的动态规划算法设计 (24)实验十三作业调度问题 (26)实验十四回溯算法设计 (28)实验十五搜索顺序的选择 (29)实验十六蛇和梯子 (31)实验十七游戏中寻址算法的设计 (34)实验十八旅行商问题 (36)实验十九骑士游历算法设计 (38)实验二十输油管道问题的设计与实现 (40)实验二十一邮局选址问题的设计与实现 (42)实验二十二会场安排问题的设计与实现 (44)实验二十三目录树打印程序的设计 (46)实验二十四最少演员问题 (48)附：实验（设计）报告参考格式 (50)实验一单链表的建立插入及删除[实验目的]1．掌握单链表的建立插入及删除的算法；2．进一步熟悉指针的用法；[预习要求]1.认真阅读教材或参考书, 掌握线性表算法的基本思想；2.写出求解本实验的程序；3.设计好相应的测试用例。

[类型定义]typedef struct Lnode{int data;struct Lnode *next;}Lnode,*linklist;[实验提示]void create(link *h,int n){//创建单链表link p,q;int i;p=(link)malloc(sizeof(node));p->next=null;*h=p;q=p;for(i=1;i<=n;++i){p=(link)malloc(sizeof(node));scanf("%d",&p->data);p->next=null;q->next=p;q=p;}}void print(link h){//输出单链表link p;p=h->next;while(p){printf("%d ",p->data);p=p->next;}}void insertlist(linklist *L,int i,int e){//在单链表的第i个元素之前插入元素值为e的结点}void dellist(linklist *L,int i,int *e){//删除单链表的第i个结点，被删结点通过 e返回}[实验步骤]1.先用插表头或插表尾的方法建立单链表并输出，并测试你的程序，直至正确为止；2.再进行插入和删除程序的设计；3.将你的程序和实录的界面存盘备用。

《算法分析与设计》实验指导书《算法分析与设计》课程是计算机专业的一门必修课程。

开设算法分析与设计实验，目的就是为了使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。

《算法分析与设计》课程实验的目的：是为了使学生在课程学习的同时，通过实验环境中的实际操作，对部分算法的具体应用有一个初步的了解，使学生加深了解和更好地掌握《算法分析与设计》课程教学大纲要求的内容。

《算法分析与设计》课程实验的注意事项：在《算法分析与设计》的课程实验过程中，要求学生做到：(1)预习实验指导书有关部分，认真做好实验内容的准备，就实验可能出现的情况提前作出思考和分析。

(2)认真书写实验报告。

实验报告包括实验目的和要求，实验情况及其分析。

(3)遵守机房纪律，服从辅导教师指挥，爱护实验设备。

(4)实验课程不迟到。

如有事不能出席，所缺实验一般不补。

《算法分析与设计》课程实验的验收：实验的验收将分为两个部分。

第一部分是上机操作，包括检查程序运行和即时提问。

第二部分是提交电子的实验报告。

实验一算法实现一一、实验目的与要求熟悉C/C++语言的集成开发环境；通过本实验加深对分治法、贪心算法的理解。

二、实验内容:掌握分治法、贪心算法的概念和基本思想，并结合具体的问题学习如何用相应策略进行求解的方法。

三、实验题1. 【伪造硬币问题】给你一个装有n个硬币的袋子。

n个硬币中有一个是伪造的。

你的任务是找出这个伪造的硬币。

为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。

试用分治法的思想写出解决问题的算法，并计算其时间复杂度。

2.【找零钱问题】一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。

售货员希望用数目最少的硬币找给小孩。

假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。

算法设计与分析实验指导书. . .. . .算法设计与分析实验指导书东北大学软件学院2012年.. .专业. .目录算法设计与分析 (1)实验指导书 (1)前言 (3)实验要求 (4)实验1 分治法的应用（2学时） (5)1.实验目的 (5)2.实验类型 (5)3.预习要求 (5)4.实验基本要求 (5)5.实验基本步骤 (7)实验2动态规划（2学时） (9)1.实验目的 (9)2.实验类型 (9)3.预习要求 (9)4.实验基本要求 (9)5.实验基本步骤 (10)实验3 回溯法（4学时） (12)1.实验目的 (12)2.实验类型 (12)3.预习要求 (12)4.实验基本要求 (12)5.实验基本步骤 (13)前言《算法设计与分析》是一门面向设计，处于计算机科学与技术学科核心地位的教育课程。

通过对计算机算法系统的学习，使学生理解和掌握计算机算法的通用设计方法，培养对算法的计算复杂性正确分析的能力，为独立设计算法和对算法进行复杂性分析奠定基础。

要求掌握算法复杂度分析、分治法、动态规划法、贪心法、回溯法、分支限界法等算法的设计方法及其分析方法。

能将这些方法灵活的应用到相应的问题中，并且能够用C++实现所涉及的算法，并尽量做到低复杂度，高效率。

通过本课程的实验，使学生加深对课程容的理解，培养学生严密的思维能力，运用所学知识结合具体问题设计适用的算法的能力；培养学生良好的设计风格，激励学生创造新算法和改进旧算法的愿望和热情。

希望同学们能够充分利用实验条件，认真完成实验，从实验中得到应有的锻炼和培养。

希望同学们在使用本实验指导书及进行实验的过程中，能够帮助我们不断地发现问题，并提出建议，使《算法设计与分析》课程成为对大家有益的课程。

实验要求《算法设计与分析》课程实验的目的是为了使学生在课堂学习的同时，通过一系列的实验，使学生加深理解和更好地掌握《算法设计与分析》课程教学大纲要求的容。

在《算法设计与分析》的课程实验过程中，要求学生做到：（1）仔细观察调试程序过程中出现的各种问题，记录主要问题，做出必要说明和分析。

计算机科学与技术学院算法分析与设计实验指导书2011年8月于洪编写2015年9月周应华修订目录实验一分治策略排序 (3)实验二减治策略查找顺序表 (5)实验三动态规划求解0/1背包问题 (8)实验四贪心算法求解最短路径问题 (10)附录1 关于文件的操作 (12)附录2 关于如何统计运算时间 (13)实验一分治策略排序实验目的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 themiMiddle = (iEnd + iBegin) / 2; // 划分TopDownSplitMerge(A, iBegin, iMiddle, B);TopDownSplitMerge(A, iMiddle, iEnd, B);TopDownMerge(A, iBegin, iMiddle, iEnd, B); // 合并；元素放到数组B中。

《算法设计与分析》实验指导《算法分析与设计》实验指导 .1 实验一锦标赛问题 [实验目的] 1. 基本掌握分治算法的原理. 2. 能用程序设计语言求解锦标赛等问题的算法; [预习要求] 1. 认真阅读数据结构教材和算法设计教材,了解分治算法原理; 2. 设计用分治算法求解背包问题的数据结构与程序代码. [实验题] 【问题描述】设有 n=2 k 个运动员要进行网球循环赛。

现要设计一个满足以下要求的比赛日程表：（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 2 3 4 5 6 7 8 2 1 4 3 6 7 8 5 3 4 1 2 7 8 5 6 1 2 3 4 3 2 1 8 5 6 7 1 2 3 4 5 6 7 8 1 4 3 2 1 2 1 4 3 6 5 8 7 2 1 4 3 1 2 3 4 1 2 7 8 5 6 3 2 1 4 2 1 4 3 2 1 8 7 6 5 4 3 2 1 （1）（2）（3）图 1 2 个、4 个和 8 个选手的比赛日程表图 1 所列出的正方形表（3）是 8 个选手的比赛日程表。

其中左上角与左下角的两小块分别为选手 1 至选手 4 和选手 5 至选手 8 前 3 天的比赛日程。

据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这2 样我们就分别安排好了选手 1 至选手 4 和选手 5 至选手 8 在后 4 天的比赛日程。

实验一串匹配程序设计（2学时）一、实验目的(1). 熟练掌握串匹配的含义(2). 掌握BF算法匹配的过程并编程实现(3). 熟悉C++编译环境的基本操作二、实验内容给定两个字符串S和T，用BF算法，在主串S中查找字串T，输出结果，输出时要求有文字说明。

请编写程序。

三、实验要求(1)、熟悉C++编译环境的基本操作(2)、考虑各种可能的情况（匹配成功或不成功）(3)、写出完整的程序四、实验结果实验二排序问题程序设计（2学时）一、实验目的(1). 掌握选择排序和起泡排序的基本思想(2). 掌握两种排序方法的具体实现过程(3). 在掌握的基础上编程实现两种排序方法二、实验内容输入一个待排序的序列，分别用选择排序和起泡排序两种排序方法将其变换成有序的序列，输出结果，输出时要求有文字说明。

请编写程序。

三、实验要求(1)、熟悉C++编译环境的基本操作(2)、考虑各种可能的情况（序列本身已是有序序列，序列不是有序序列）(3)、写出完整程序四、实验结果实验三数字旋转方阵程序设计（2学时）一、实验目的(1). 掌握分治法的设计思想(2). 掌握数字旋转方阵的具体实现过程(3). 熟练掌握二维数组的使用方法(4). 在掌握的基础上编程实现数字旋转方阵的实现过程二、实验内容给出一个初始数据，在此数据的基础上由外层向里层填写数据，完成一个数字旋转方阵，输出结果，输出时要求有文字说明。

请编写程序。

三、实验要求(1)、熟悉C++编译环境的基本操作(2)、考虑各种可能的情况（方阵有一层，两层或更多层）(3)、写出完整程序四、实验结果实验四排序中分治法的程序设计（2学时）一、实验目的(1). 掌握归并排序和快速排序的划分方法(2). 掌握归并排序和快速排序的具体分治策略(3). 在掌握的基础上编程两种排序方法的实现过程二、实验内容给出一个初始序列，分别用归并排序和快速排序两种分治法将所给序列变换为有序序列，输出结果，输出时要求有文字说明。

《算法设计与分析》课程实验指南(适合于非计算机科学与技术专业)实验项目1 串匹配问题1．实验题目给定一个文本，在该文本中查找并定位任意给定字符串。

2.学时安排2个学时。

3.实验目的(1)深刻理解并掌握蛮力法的设计思想；(2)提高应用蛮力法设计的技能；(3)理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。

4.实验要求(1)实现BF算法；(2)实现BF算法的改进算法：KMP算法；(3)对上述2个算法进行时间复杂性分析，并设计实验程序验证分析结果。

实验项目2 最近对问题1.实验题目设p1=(x1,y1)，p2=(x2,y2)，…，pn=(xn,yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近点对。

2.学时安排2个学时。

3.实验目的(1)进一步掌握递归算法的设计思想以及递归程序的调试技术；(2)理解这样一个观点：分治与递归经常同时应用在算法设计之中。

4.实验要求（1）分别用蛮力法和分治法求解最近对问题；（2）分析算法的时间性能，设计实验程序验证分析结论。

实验项目3 八枚硬币问题1.实验题目在8枚外观相同的硬币中，有一枚是人民币假币，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是较重。

可以通过一架天平来任意比较两组硬币，设计一个高效的算法来测出这枚假币。

2.学时安排2个学时。

3.实验目的(1)深刻理解并掌握减治法的设计思想；(2)提高应用减治设计算法的技能；(3)理解这样一个观点：建立正确的模型对于问题的求解是非常重要的。

4.实验要求(1)设计减治算法实现8枚硬币问题；(2)设计测试数据，写出程序文档。

实验项目4 0/1背包问题1.实验题目给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，0/1背包问题是如何选择装入背包的物品(物品不可分割)，使得装入背包中物品总价值最大。

2.学时安排2个学时。

<<算法设计与分析>>实验指导书实验一、回溯法一、实验目的掌握回溯法求解问题的思想，学会利用其原理求解相关问题。

二、实验内容及要求1、八皇后问题八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。

该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

高斯认为有76种方案。

1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。

要求对用C实现的回溯法进行验证，并使其能扩展到任意的皇后数的情况，同时对源程序给出详细的注释。

三、实验步骤1. 理解算法思想和问题要求；2. 编程实现题目要求；3. 上机输入和调试自己所编的程序；4. 验证分析实验结果；5. 整理出实验报告。

四、实验源代码1、八皇后问题（回溯法实现）#define QUEENNO 8#define MAXNO 32#include <stdio.h>#include <stdlib.h>int X[MAXNO];char D[MAXNO][MAXNO];int count=0;void initiate(int n);void nqueen(int n);void display(int n);main(){int queenno=QUEENNO;initiate(queenno);nqueen(queenno);printf("共有%d个解,解已经保存在D盘文件result.txt中\n",count); }void initiate(int n){int i;for(i=0;i<n;i++)X[i]=-1;return;}void nqueen(int n){ int k;X[0]=0;k=0;while(k>=0){X[k]++;while(X[k]<=n&&!place(k)){X[k]++;}if(X[k]<=n){ if(k==n-1) display(n);else {k++;X[k]=0;}}else{ k--;}}}int place(int k){int i;i=0;while(i<k){if((X[i]==X[k])||(abs(X[i]-X[k])==abs(i-k)))return 0;i++;}return 1;}void display(int n){FILE *fw;int i,j;count++;fw=fopen("D:\\result.txt","a");for(i=0;i<n;i++)for(j=0;j<n;j++)D[i][j]='o';for(i=0;i<n;i++)D[i][X[i]-1]='*';fprintf(fw,"%d\n",count);fprintf(fw,"-------------------------\n");for(i=0;i<n;i++)for(j=0;j<n;j++){if(j==n-1)fprintf(fw,"%c \n",D[i][j]);else fprintf(fw,"%c ",D[i][j]); }fprintf(fw,"-------------------------\n");fclose(fw);return;}实验二：分治法（2学时）问题陈述:对所给元素存储于数组中和存储于链表中两中情况，写出自然合并排序算法.解题思路:将待排序元素分成大小大相同的两个集合,分别对两个集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合.自然排序是通过一次扫描待排元素中自然排好序的子数组,再进行子数组的合并排序.程序代码:#include <iostream.h>const int N=100;void ScanTarget(int target[], int n, int head[], int tail[]);int CountHead(int head[]);void MergeSort(int a[], int head[], int tail[], int m);void MergePass(int x[], int y[], int s, int a[], int b[], int m);void Merge(int c[], int d[], int l, int m, int r);void main(){char a;do{int target[N],head[N],tail[N];int i=0,n,m;for(; i<N; i++){head[i]=-1;tail[i]=-1;}cout<<"请输入要排序的总数:"<<endl;cin>>n;cout<<"请输入要排序的数列:" <<endl;for(i=0; i<n; i++)cin>>target[i];ScanTarget(target,n,head,tail);m=CountHead(head);MergeSort(target,head,tail,m);cout<<"排序后:"<<endl;for(i=0; i<n; i++)cout<<target[i]<<" ";cout<<endl;cout<<"是否继续(y/n):"<<endl;cin>>a;}while(a!='n' && a!='N');}void ScanTarget(int target[], int n, int head[], int tail[])//扫描待排数组；{int i,j=0,k=0;head[k]=0;k++;for(i=1;i<n;i++){if(target[i-1]>target[i]){tail[j++]=i-1;head[k++]=i;}}tail[j]=n-1;}int CountHead(int head[])//求长度；{int i(0);while(head[i]!=-1){i++;}return i;}void MergeSort(int a[], int head[], int tail[], int m){int b[N];int s=1;while(s<m){MergePass(a,b,s,head,tail,m);s+=s;MergePass(b,a,s,head,tail,m);s+=s;}}void MergePass(int x[], int y[], int s, int a[], int b[], int m){int i=0;while(i <= m-2*s){Merge(x,y,a[i],b[i+s-1],b[i+2*s-1]);i=i+2*s;}if(i+s < m){Merge(x,y,a[i],b[i+s-1],b[m-1]);}else{for(int j=i; j<m; j++)for(int k=a[j]; k<=b[j]; k++)y[k]=x[k];}}void Merge(int c[], int d[], int l, int m, int r){int i,j,k;i=l;j=m+1;k=l;while((i<=m) && (j<=r)){if( c[i] <= c[j] )d[k++]=c[i++];else d[k++]=c[j++];}if( i>m ){for(int q=j; q<=r; q++)d[k++]=c[q];}else{for(int q=i; q<=m; q++)d[k++]=c[q];}}时间复杂度:通常情况下用自然合并排序所需要的合并次数较少。

《算法分析与设计》实验指导与报告书实验目录实验1 求最大公约数 (1)实验2 斐波那契数列 (3)实验3 最近对问题 (6)实验4 堆排序 (7)实验5 霍纳法则和二进制幂 (8)实验6 字符串匹配问题 (9)实验7 Warshall算法和Floyd算法 (10)实验8 最优二叉查找树 (11)实验9 Huffman编码* (12)实验10 求解非线性方程* (13)实验11 投资问题* (14)注：（1）实验4和实验5为变治法应用，二选一；（2）实验7和实验8为动态规划法应用，二选一；（3）带*号的实验为选做实验，根据课时及学生实验完成情况机动安排。

实验1 求最大公约数{c = a;a = b;b = c;}while(a % b != 0){c = a % b;a = b;b = c;}printf("%d", b);return 0;}连续整数检测算法最大公约数算法：#include <stdio.h>int main(){int a,b,t;printf("Please input two integers: ");scanf("%d %d",&a,&b);if(a<b)t=a;elset=b;while(t>=1){if((a%t==0)&&(b%t==0))break;t--;}printf("%d",t);return 0;}相减循环：#include<stdio.h>int main(){int m,n;printf("Please input two integers: ");scanf("%d%d",&m,&n);while(m!=n)if(m>n) m=m-n;else n=n-m;printf("%d",m);return 0;}教师评分实验2 斐波那契数列实验目的（1）求斐波那契数列；（2）区分递归和递推思想。

《算法设计与分析》实验指导书《算法设计与分析》实验指导书本文档主要用于《算法设计与分析》课程的实验指导。

《算法设计与分析》旨在教会学生处理各种问题的方法，通过实验，使学生能够把所学的方法用于具体的问题，并对所用算法进行比较分析，从而提高学生分析问题、解决问题的能力。

通过该课程的实验，使学生对课堂中所讲述的内容有一个直观的认识，更好地掌握所学的知识，培养学生的实际动手能力，加强学生创新思维能力的培养。

本课程设计了7个设计型实验。

实验内容包括用分治法、动态规划、贪心法、回溯法以及分支限界法求解问题。

一、实验内容安排二、实验基本要求实验前要求学生一定要先了解实验目的、内容、要求以及注意事项，要求学生熟悉实验对象，设计并编写相应的算法。

学生应独立完成所布置实验内容，编写代码，运行程序，记录结果并撰写实验报告。

三、实验报告要求实验结束后，应及时整理出实验报告，实验报告提交书面文档。

四、考核方式理论考试（60％）＋实验（30％）+作业（10%）五、实验内容与指导实验一快速排序问题1．实验目的(1) 用分治法求解该问题。

2．实验环境PC机，要求安装Eclipse软件或VC++软件供学生实验。

3．实验内容有n个无序的数值数据，现要求将其排列成一个有序的序列。

4. 实验步骤(1) 输入实现该问题的源代码；(2) 输入测试数据，验证代码的正确性。

5.实验要求(1)做好实验预习，熟悉本实验中所使用的开发环境。

(2)写出实验报告①实验目的②实验内容③出错信息及处理方法④实验结果实验二最少硬币问题1．实验目的(1) 用动态规划求解该问题。

2．实验环境PC机，要求安装Eclipse软件或VC++软件供学生实验。

3．实验内容有n种不同面值的硬币，各硬币面值存于数组T[1:n]；现用这些面值的钱来找钱；各面值的个数存在数组Num[1:n]中。

对于给定的1≤n≤10，硬币面值数组、各面值的个数及钱数m，0<=m<=2001，设计一个算法，计算找钱m的最少硬币数。

《算法分析与设计》实验指导本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使用学生对算法的分析与设计有更深刻的认识。

上机实验一般应包括以下几个步骤：1、准备好上机所需的程序，手编程序应书写整齐，并经人工检查无误后才能上机。

2、上机输入和调试自己所编的程序。

一人一组，独立上机调试，上机时出现的问题，最好独立解决。

3、上机结束后，整理出实验报告。

实验报告应包括：题目，程序清单，运行结果，对运行情况所作的分析。

本书共分阶段4个实验，每个实验有基本题和提高题。

基本题必须完成，提高题根据自己实际情况进行取舍。

题目不限定如下题目，可根据自己兴趣爱好做一些与实验内容相关的其它题目，如动态规划法中的图象压缩，回溯法中的人机对弈等。

其具体内容如下：实验一分治与递归（4学时）基本题一：基本递归算法一一、实验目的与要求1、熟悉C/C++语言的集成开发环境；2、通过本实验加深对递归过程的理解；二、实验内容掌握递归算法的概念和基本思想，分析结果能够用递归方法实现整数的划分。

三、实验题：任意输入一个整数，输出结果能够用递归方法实现整数的划分。

四、四实验步骤1、理解算法思想和问题要求；2、编程实现题目要求；3、上机输入和调试自己所编写的程序；4、验证分析实验结果；5、整理实验报告。

基本题二：棋盘覆盖问题一、实验目的与要求1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法。

二、实验题目棋盘覆盖问题在一个2k*2k方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一个特殊棋盘。

在棋盘覆盖问题中，要用图标4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

提高题一：二分搜索一、实验目的与要求1、熟悉二分搜索算法；2、初步掌握分治算法。

二、实验题1、高a【0：n-1】是一个已排好的数组。

《算法设计与分析课程设计》指导书《算法设计与分析课程设计》实习指导书一、课程设计目的本课程设计是在学生学习《算法设计与分析》课程后，进行的一次针对具体问题进行算法设计与分析的综合训练，其目的在于加深算法设计分析的理解，掌握算法分析设计方法。

二、算法设计与分析课程设计要求1.学生必须仔细阅读《算法设计与分析课程设计》实习方案，认真主动完成课设的要求。

有问题及时主动通过各种方式与教师联系沟通。

2.学生要发挥自主学习的能力，充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时向教师汇报。

3.课程设计按照教学要求需要一周（5天）时间完成。

三、实验所用仪器及实验环境PC机，Codeblocks软件环境。

四、实习基本内容本次课程设计要求在（一）、（二）、（三）、（四）组中每组选择至少一个题目完成。

（一）分治策略1、输油管道问题【题目描述】某石油公司计划建造一条由西向东的主输油管道，该管道要穿过一个有n口油井的油田。

从每口油田都要有一条输油管道沿最短路径（或南或北）与主管道相连。

如果给定n口油井的位置，即它们的x坐标（东西向）和y坐标（南北向），应如何确定主管道的最优位置，即使各油井到主管道之间的输油管长度总和最小的位置？【输入】第一行是一个整数n，表示油井数量（1-1000之间），接下来n行是油井的位置，每行两个整数x和y。

【输出】各油井到主管道之间的输油管道最小长度总和。

【输入样例】51 22 21 33 -23 3【输出样例】62、船的价值问题描述：大橙子最近在玩《艦これ》，因此大橙子收集了很多很多的船(这里我们假设大橙子氪了很多金，开了无数个船位)。

去除掉重复的船之后，还剩下N(1≤N≤1,000,000)种不同的船。

每一艘船有一个稀有值，任意两艘船的稀有值都不相同，稀有值越小的船越稀有，价值也就越高。

Nettle现在通过大建又造出了一艘船，他想知道这艘船是不是重复的。

《算法设计与分析》实验指导书实验一递归与分治1、实验目的（1）掌握设计有效算法的分治策略；（2）通过合并排序和快速排序两个示例学习分治策略设计技巧。

2、实验要求（1）熟练掌握分治法的基本思想及其应用实现；（2）理解所给出的算法，并对其加以改进。

3、实验内容（1）分治法基本思想如果原问题可分割成k个子问题，1<k≤n ，且这些子问题都可解，并可利用这些子问题的解求出原问题的解。

由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。

在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。

（2）分治法--算法设计模式如下：Divide-and-Conquer(P)1) if |P|≤n02) then return(ADHOC(P))3) 将P分解为较小的子问题P1 ,P2 ,...,Pk4) for i←1 to k5) 5. do yi ← Divide-and-Conquer(Pi) △递归解决Pi6) 6. T ← MERGE(y1,y2,...,yk)△合并子问题7) return(T)4、实验方法1）合并排序：将待排序元素分成个数大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合并成为所要求的排序集合。

2）快速排序：对于输入的子序列L[p..r]，如果规模足够小则直接进行排序，否则分三步处理：①分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。

②递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。

③合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。

常熟理工学院
《算法设计与分析》实验指导与报告书
______学年第____ 学期
专业：___________________________________________ 学号：___________________________________________ 姓名：___________________________________________ 实验地点：___________________________________________ 指导教师：___________________________________________
计算机科学与工程学院
2012
实验目录
实验一求最大公约数 (4)
实验二串匹配问题 (7)
实验三斐波那契数列 (10)
实验四堆的创建与堆排序 (13)
实验五霍纳法则 (16)
实验六Warshall算法和Floyed算法 (19)
实验七最优二叉查找树 (22)
实验八解非线性方程的算法 (25)
实验一求最大公约数
实验二串匹配问题
实验三斐波那契数列
实验四堆的创建与堆排序
实验五霍纳法则
实验六Warshall算法和Floyed算法
实验七最优二叉查找树
实验八解非线性方程的算法。

《算法设计与分析》实验指导书曹严元计算机与信息科学学院2007年5月目录实验一递归算法与非递归算法 (2)实验二分治算法 ................................................... 错误！未定义书签。

实验三贪心算法 (3)实验四动态规划 (2)实验五回溯法 (3)实验六分枝—限界算法 (4)实验七课程设计 (4)实验一递归与分治算法实验目的1.了解并掌握递归的概念，掌握递归算法的基本思想；2.掌握分治法的基本思想方法；3.了解适用于用递归与分治求解的问题类型，并能设计相应递归与分治算法；4.掌握递归与分治算法复杂性分析方法，比较同一个问题的递归算法与循环迭代算法的效率。

实验二动态规划实验目的1.掌握动态规划的基本思想方法；2.了解适用于用动态规划方法求解的问题类型，并能设计相应动态规划算法；3.掌握动态规划算法复杂性分析方法。

实验三贪心算法实验目的1.掌握贪心法的基本思想方法；2.了解适用于用贪心法求解的问题类型，并能设计相应贪心法算法；3.掌握贪心算法复杂性分析方法分析问题复杂性。

实验五回溯法实验目的1.掌握回溯法的基本思想方法；2.了解适用于用回溯法求解的问题类型，并能设计相应回溯法算法；3.掌握回溯法算法复杂性分析方法，分析问题复杂性。

实验六 分枝—限界算法实验目的1. 掌握分枝—限界的基本思想方法；2. 了解适用于用分枝—限界方法求解的问题类型，并能设计相应动态规划算法；3. 掌握分枝—限界算法复杂性分析方法，分析问题复杂性。

实验七 课程设计实验目的1. 在已学的算法基本设计方法的基础上，理解算法设计的基本思想方法；2. 掌握对写出的算法的复杂性分析的方法，理解算法效率的重要性；3. 能运用所学的基本算法设计方法对问题设计相应算法，分析其效率，并建立对算法进行改进，提高效率的思想意识。

预习与实验要求1. 预习实验指导书及教材的有关内容，回顾所学过的算法的基本思想；2. 严格按照实验内容进行实验，培养良好的算法设计和编程的习惯；3. 认真听讲，服从安排，独立思考并完成实验。

算法分析与设计本书是为配合《计算机算法分析与设计》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授内容的理解，增强算法分析与设计实践动手能力。

上机实验注意事项如下：（1）课前认真做好预习，准备好实验工具，熟悉实验流程和手段。

（3）课中根据实验指导书，结合课本实例进行编程实验。

实验时，一人一组，独立上机调试，上机时出现疑问，可以举手询问实验指导老师，或者与周边同学小声讨论，鼓励独立解决问题。

（4）课后按时按质按量整理出实验报告。

实验报告应独立完成，拒绝抄袭。

实验内容覆盖：递归与分治策略、动态规划、贪心算法、回溯法、分支限界法等。

实验一递归与分治策略一．实验目的与要求（1）理解和掌握递归与分治策略的基本原理。

（2）理解课本中的示例代码。

（3）调试代码通过。

二．递归与分治的基本思想（1）递归与分治方法。

递归与分治方法的基本思想是：将一个难以解决的大问题，分割成一些规模较小的、相同的子问题，以便各个击破，分而治之。

（2）递归。

递归问题分析时，要把握如下两个要素：●递归出口。

●递归公式。

其中：●递归出口给出了最简单情况下问题的解。

●递归公式则给出了一般意义下大问题（原问题）和小问题（子问题）之间的递归关系。

通过递归公式，一个难以解决的大问题会随着递归不断分解为多个小问题，小问题继续递归变为更小的小问题，直到最后到达递归出口得到解。

三．实验代码分析和说明本部分实验，需完成“棋盘覆盖”（课本P20）和“快速排序”（课本P22）两个问题。

3.1棋盘覆盖1. 棋盘覆盖问题的思路：（1）首先，将原始的棋盘覆盖问题看作最初的大问题。

（2）然后，将棋盘的行、列一分为二，从而将原始的大棋盘分为四个同样大小的小棋盘。

（3）接着，采用P21的图2-5中合适的L型骨牌，覆盖原始大棋盘的中心位置，将四个同样大小的小棋盘都转化为特殊棋盘。

（4）最后，对四个特殊小棋盘进行递归处理即可。

以上步骤（2）和步骤（3）合起来，完成了将大问题划分为小问题的过程，特别需要注意的是：小问题必须要和大问题相同或相似，否则无法递归。