《算法设计与分析》实验报告实验一递归与分治策略应用基础
学号：
姓名：
班级：
一、实验目的
1、熟悉递归的概念和分治法。
2、对递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法。递归与分治策略的问题类型，并能设计相应的分治策略算法。
二、实验内容
任务：以下题目要求应用递归与分治策略设计解决方案，本次实验成绩按百分制计，完成各小题的得分如下，每小题要求算法描述准确且程序运行正确。
1、求n个元素的全排。（30分）
算法分析：用递归的方法，先将n个数分成两个部分，然后将两个部分交换位子，然后再将这两个部分继续再分成四个部分，然后再将每个部分进行交换，然后就重复刚才的过程，直到不能再分为止，在这个过程中所产生的所有结果就是我们要求的全排列。
代码实现：
#include
int n = 0;
void swap(int *a, int *b)
{
int m;
m = *a;
*a = *b;
*b = m;
}
void perm(int list[], int k, int m) {
int i;
if(k > 2)
{
for(i = 0; i <= 2; i++)
printf("%d ", list[i]);
printf("\n");
n++;
}
else
{
for(i = k; i <= 2; i++)
{
swap(&list[k], &list[i]);
perm(list, k + 1, 4);
swap(&list[k], &list[i]); }
}
}
int main()
{
int list[] = {1, 2, 3,4};
perm(list, 0, 2);
printf("total:%d\n", n);
return 0;
}
2、解决一个2k*2k的特殊棋牌上的L型骨牌覆盖问题。（30分）算法分析：用分治策略，将大的棋盘分割为下一级的棋盘，直到不能再分为止，然后再将每一个小的棋盘填满，接着将一个一个小的棋盘再又合并成一个大的棋盘。
代码实现：
#include "iostream"
using namespace std;
int board[1025][1025];
int tile = 1;
//tr,tc棋盘左上角方格坐标， dr, dc特殊方格所在坐标， size 为行数
void ChessBoard(int tr, int tc, int dr, int dc, int size) {
if(size == 1)
return;
int t = tile++; // L型骨牌号
int s = size / 2;
//覆盖左上角子棋盘
if(dr < tr + s && dc < tc + s)
//特殊方格在此棋盘中
ChessBoard(tr, tc, dr, dc, s);
else{
//此棋盘无特殊方格，用 t 号 L 型骨牌覆盖右下角
board[tr + s - 1][tc + s - 1] = t;
//覆盖其余方格
ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
}
//覆盖右上角子棋盘
if(dr < tr + s && dc >= tc + s)
//特殊方格在此棋盘中
ChessBoard(tr, tc + s, dr, dc, s);
else{
board[tr + s - 1][tc + s] = t;
ChessBoard(tr, tc + s, tr + s - 1, tc + s, s); }
//覆盖左下角子棋盘
if(dr >= tr + s && dc < tc + s)
ChessBoard(tr + s, tc, dr, dc, s);
else{
board[tr + s][tc + s - 1] = t;
ChessBoard(tr + s, tc, tr + s, tc + s - 1, s); }
//覆盖右下角子棋盘
if(dr >= tr + s && dc >= tc + s)
ChessBoard(tr + s, tc + s, dr, dc, s);
else{
board[tr + s][tc + s] = t;
ChessBoard(tr + s, tc + s, tr + s, tc + s, s); }
}
int main(){
int k, x, y, i, j;
while(cin>>k)
{
tile = 1;
cin>>x>>y;
int size = 1< board[x][y] = 0; ChessBoard(0, 0, x, y, size); for(i = 0; i < size; i++) { for(j = 0; j < size; j++) cout< cout< } } return 0; } 3、设有n=2k个运动员要进行网球循环赛。设计一个满足要求 的比赛日程表。（40分） #include #include #include void Table(double k, int **a) { int i, j, s, t, n = pow(2, k); for (i = 1; i <= n; i++) a[1][i] = i; int m = 1; for (s = 1; s <= k; s++) { n /= 2; for (t = 1; t <= n; t++) for (i = m + 1; i <= 2 * m; i++) for (j = m + 1; j <= 2 * m; j++) { a[i][j+(t-1)*m*2] = a[i-m][j+(t-1)*m*2-m]; a[i][j+(t-1)*m*2-m] = a[i-m][j+(t-1)*m*2]; } m *= 2; } } printf(int **a, int n) { for(int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) printf(" %d ",a[i][j]); printf("\n"); } } void main() { printf("输入人数:"); int n,r; scanf("%d",&n); printf("比赛时间:"); scanf("%d",&r); int **a = new int*[n+1]; for (int i = 0; i <= n; i++) a[i] = new int[n+1]; int k = log10(n)/log10(2); printf("日程表:\n"); int *b; b=new int[n+1]; b[0]=0; printf(" "); for(int l=1;l { b[1]=r++; printf(" %d日",b[1]); } printf("\n"); Table(k, a); printf(a, n); } 提交结果：算法设计分析思路、源代码及其分析说明和测试运行报告。 三、实验总结与体会 体会：我们需要多多熟悉书上的知识。虽然这些题在书上有类似的题，但真正做起来还是有一定的难度。我们基础需要打好，使得在今后的学习中更得心应手。 实验报告分治与递归 中国矿业大学计算机科学与技术学院孟靖宇 一、实验目的与要求 1、熟悉C/C++语言的集成开发环境； 2、通过本实验加深对递归过程的理解 二、实验内容： 掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。 三、实验题 任意输入一个整数，输出结果能够用递归方法实现整数的划分。 四、算法思想 对于数据n,递归计算最大加数等于x 的划分个数+最大加数不大于x-1的划分个数。最大加数x 从n 开始，逐步变小为n-1, (1) 考虑增加一个自变量：对于数据n,最大加数n1不大于m 的划分个数记作),(m n q 。则有： ???????>>=<==-+--+=1 1,1),()1,()1,(1),(1),(m n m n m n m n m m n q m n q n n q n n q m n q 五、代码实现 #include "stdafx.h" #include return 0; } int q(intn,int m){ if((n<1)||(m<1)) return 0; if((n==1)||(m==1)) return 1; if(n 分治算法 一、分治算法 分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。 分治法解题的一般步骤： （1）分解，将要解决的问题划分成若干规模较小的同类问题； （2）求解，当子问题划分得足够小时，用较简单的方法解决； （3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。 当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。下面通过实例加以说明。 【例1】[找出伪币] 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。 另外一种方法就是利用分而治之方法。假如把1 6硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把1 6个硬币的问题分成两个8硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这1 6个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。 《算法设计与分析》实验报告 分治策略 姓名：XXX 专业班级：XXX 学号：XXX 指导教师：XXX 完成日期：XXX 一、试验名称：分治策略 （1）写出源程序，并编译运行 （2）详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序，实现归并排序。 (2)编写一段程序，实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序，实现归并排序。 将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行 排序，最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序，实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有 数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数 据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割， 直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序，实现归并排序。 #include 递归与分治实验报告 班级：计科1102 姓名：赵春晓学号：2011310200631 实验目的：进一步掌握递归与分治算法的设计思想，通过实际问题来应用递归与分治设计算法。 实际问题：1集合划分问题，2输油管道问题，3邮局选址问题，4整数因子分解问题，5众数问题。 问题1：集合划分 算法思想：对于n个元素的集合，可以划分为由m个子集构成的集合，例如{{1,2}{3,4}}就是由2个子集构成的非空子集。假设f（n，m）表示将n个元素划分成由m个子集构成的集合的个数。那么1）若m == 1 ，则f（n，m）= 1 ；2）若n == m ，则f（n，m）= 1 ；3）若不是上面两种情况则有下面两种情况构成：3.1）向n-1个元素划分成的m个集合里面添加一个新的元素，则有m*f(n-1,m)种方法；3.2）向n-1个元素划分成的m-1个集合里添加一个由一个元素形成的独立的集合，则有f(n-1,m-1)种方法。 实验代码： #include 算法分析(第二章)：递归与分治法 一、递归的概念 知识再现：等比数列求和公式： 1、定义：直接或间接地调用自身的算法称为递归算法。 用函数自身给出定义的函数称为递归函数。 2、与分治法的关系： 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归经常同时应用在算法设计之中，并由此产生许多高效算法。 3、递推方程： (1)定义：设序列01,....n a a a简记为{ n a}，把n a与某些个() i a i n <联系起来的等式叫做关于该序列的递推方程。 (2)求解：给定关于序列{n a}的递推方程和若干初值，计算n a。 4、应用：阶乘函数、Fibonacci数列、Hanoi塔问题、插入排序 5、优缺点： 优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 二、递归算法改进： 1、迭代法： (1)不断用递推方程的右部替代左部 (2)每一次替换，随着n的降低在和式中多出一项 (3)直到出现初值以后停止迭代 (4)将初值代入并对和式求和 (5)可用数学归纳法验证解的正确性 2、举例： -----------Hanoi塔算法----------- ---------------插入排序算法----------- ()2(1)1 (1)1 T n T n T =?+ = ()(1)1 W n W n n W =?+? （1）=0 实验一递归与分治策略 实验目的 1.了解并掌握递归的概念，递归算法的基本思想； 2.掌握分治法的基本思想方法； 3.了解适用于用分治法求解的问题类型，并能用递归或非递归的方式设计相应的分治法算法； 4.掌握分治法复杂性分析方法，比较同一个问题的递归算法与循环迭代算法的效率。预习与实验要求 1.预习实验指导书及教材的有关内容，掌握分治法的基本思想； 2.严格按照实验内容进行实验，培养良好的算法设计和编程的习惯； 3.认真听讲，服从安排，独立思考并完成实验。 实验原理 简单说来，当一个函数用它自己来定义时就称为递归。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。因此，在考虑使用递归算法编写程序时，应满足两点：1）该问题能够被递归形式描述；2）存在递归结束的边界条件。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。一般说来，一个递归算法可以转换称为一个与之等效的非递归算法，但转换后的非递归算法代码将成倍地增加。 分治是一种被广泛应用的有效方法，它的基本思想是把最初的问题分解成若干子问题，然后在逐个解决各个子问题的基础上得到原始问题的解。所谓分治就是“分而治之”的意思。由于分解出的每个子问题总是要比最初的问题容易些，因而分治策略往往能够降低原始问题的难度，或者提高解决原始问题的效率。 根据如何由分解出的子问题求出原始问题的解，分治策略又可分为两种情形：第一，原始问题的解只存在于分解出的某一个子问题中，则只需要在原始问题的一个划分中求解即可；第二，原始问题的解需要由各个子问题的解再经过综合处理得到。无论是哪一种情况，分治策略可以较快地缩小问题的求解范围，从而加快问题求解的速度。 分治策略运用于计算机算法是，往往会出现分解出来的子问题与原始问题类型相同的现象，而与原问题相比，各个子问题的规模变小了，这刚好符合递归的特征。因此分治策略往往是和递归联系在一起的。 应用数学学院信息安全专业班学号姓名 实验题目递归与分治法 综合实验评分表 实验报告 一、实验目的与要求 1.掌握递归算法的设计思想 2.掌握分治法设计算法的一般过程 3.理解并掌握算法渐近时间复杂度的分析方法 二、实验内容 1、折半查找的递归算法 （1）源程序代码 #include if(-1 != addr) cout << endl << n << "是上述整数中的第" << addr << "个数" << endl; else cout << endl << n << "不在上述的整数中" << endl << endl; getchar(); return 0; } （2）运行界面 ①查找成功 ②查找失败 第2章递归与分治策略 实验2 分治算法的递归程序实现与时间复杂度测试 1. 实验目的 编程实现合并排序和快速排序算法，理解分治算法设计的基本思想、递归程序实现的基本方法，加深对分治算法设计与分析思想的理解。通过程序的执行时间测试结果，与理论上的时间复杂度结论进行对比、分析和验证。 2. 原理解析 分治算法的基本思想 分治算法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。分治算法设计的一般步骤包括： (1) 分解，将要解决的问题划分成若干规模较小的同类问题； (2) 求解，当子问题划分得足够小时，用较简单的方法解决； (3) 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。 分治法的基本设计范式如下： DivideAndConquer(data,n,solution) if(n≤SizeLimit) then DirectSolution(data,n,solution) else DivideInput(data,n,smallerSets,smallerSizes,numberSmaller) for i=1 to numberSmaller do DivideAndConquer(smallerSets[i],smallerSizes[i],smallerSol ution[i]) end for CombineSolutions(smallerSolution,numberSmaller,solution) end if 测试算法 不同问题的分治算法在分解与合并步骤可能有所不同，例如合并排序和快速排序这两个有代表性的分治算法中，合并排序算法没有分解、只有合并，快速排序算法没有合并、只有分解；这两个算法的计算时间分别取决于合并与分解步骤。这两个算法分别如下： 1、MergeSort(list, first, last) if first 《算法设计与分析》 课程设计报告 题目：循环赛日程表 院（系）：信息科学与工程学院 专业班级：软工 学生姓名： 学号： 指导教师： 2018 年 1 月 8 日至 2018 年 1 月 19 日 算法设计与分析课程设计任务书 目录 1 常用算法 (1) 1.1分治算法 (1) 基本概念: (1) 1.2递推算法 (2) 2 问题分析及算法设计 (5) 2.1分治策略递归算法的设计 (5) 2.2 分治策略非递归算法的设计 (7) 2.3 递推策略算法的设计 (8) 3 算法实现 (9) 3.1分治策略递归算法的实现 (9) 3.2 分治策略非递归算法的实现 (10) 3.3 递推策略算法的实现 (12) 4 测试和分析 (15) 4.1分治策略递归算法测试 (15) 4.2分治策略递归算法时间复杂度的分析 (16) 4.3 分治策略非递归算法测试 (16) 4.4分治策略非递归算法时间复杂度的分析 (17) 时间复杂度为：O(5^(n-1)) (17) 4.5 递推策略算法测试 (17) 4.6 递推策略算法时间复杂度的分析 (18) 时间复杂度为：O(5^(n-1)) (18) 4.7 三种算法的比较 (18) 5 总结 (19) 参考文献 (20) 1 常用算法 1.1分治算法 基本概念: 在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)…… 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。 基本思想及策略: 分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。 如果原问题可分割成k个子问题，1 算法分析与设计实验报告第四次附加实验 while (a[--j]>x); if (i>=j) { break; } Swap(a[i],a[j]); } a[p] = a[j]; //将基准元素放在合适的位置 a[j] = x; return j; } //通过RandomizedPartition函数来产生随机的划分 template vclass Type> int RandomizedPartition(Type a[], int p, int r) { int i = Random(p,r); Swap(a[i],a[p]); return Partition(a,p,r); } 较小个数排序序列的结果: 测试结果 较大个数排序序列的结果: 实验心得 快速排序在之前的数据结构中也是学过的，在几大排序算法中，快速排序和归并排序尤其是 重中之重，之前的快速排序都是给定确定的轴值，所以存在一些极端的情况使得时间复杂度 很高，排序的效果并不是很好，现在学习的一种利用随机化的快速排序算法，通过随机的确 定轴值，从而可以期望划分是较对称 的，减少了出现极端情况的次数，使得排序的效率挺高了很多， 化算法想呼应，而且关键的是对于随机生成函数，通过这一次的 学习终于弄明白是怎么回事了，不错。 与后面的随机实 验和自己的 实验得分助教签名 附录： 完整代码(分治法) //随机后标记元素后的快速排序 #i nclude 分治策略 姓名：XXX 专业班级：XXX 学号：XXX 指导教师：XXX 完成日期：XXX 一、试验名称：分治策略 （1）写出源程序，并编译运行 （2）详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序，实现归并排序。 (2)编写一段程序，实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序，实现归并排序。 将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行 排序，最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序，实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有 数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数 据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割， 直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序，实现归并排序。 #include 实验一分治与递归算法的应用一、实验目的 1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。 2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。 3．学会利用分治算法解决实际问题。 二、算法问题要求 老板有一袋金块（共n块，n是2的幂（n≥2））,最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。并对自己的程序进行复杂性分析。 三、算法设计 在n个元素的集合中寻找最大和最小值元素。(1)将集合一分为二，变为两个集合，目的是在较小的两个集合中分别找最大、最小元素。(2)递归分解较小集合，直到每个集合中的元素个数≤2，然后找出小集合的最大、最小元素。（3）合并（回溯）：自低向上把子问题的解合并，大元素中取最大者，小元素中取最小者，最后得到元问题的解。 四、验证分析实验结果 图1.1 运行界面 图1.2 运行结果五、程序 #include fmax=a[i]; fmin=a[i]; } else if (i==(j-1)){ if (a[i] 华北水利水电学院算法分析与设计实验报告 20010～2011学年第二学期2008级计算机科学与技术专业 班级：2008109 学号：200810906 姓名：刘景超 实验一递归与分治算法的设计与实现 一、实验目的： 1、了解递归、分治算法的设计思路与设计技巧，理解递归的概念，掌握设计有效算法的 分治策略。 2、通过实际案例，领会算法的执行效率 二、试验内容： 棋盘覆盖、最接近点对、排序算法、矩阵乘法等，（也可选作其它问题）； 三、核心程序源代码： #include 五、小结 本想用MFC采用图形的方式展示移动的过程，可惜水平有限，实在是写不出来，只好采用控制台程序了。采用控制台程序表述还是很简单的，算法也不复杂。这次实验让我认识到我在MFC方面基础还很薄弱，还需要多多练习，慢慢提升自己。 淮海工学院计算机工程学院实验报告书 课程名：《算法分析与设计》 题目：实验1 递归与分治算法 班级： 学号： 姓名： 实验1 递归与分治算法 实验目的和要求 （1）进一步掌握递归算法的设计思想以及递归程序的调试技术； （2）理解这样一个观点：分治与递归经常同时应用在算法设计之中。 （3）分别用蛮力法和分治法求解最近对问题； （4）分析算法的时间性能，设计实验程序验证分析结论。 实验内容 设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。 实验环境 Turbo C 或VC++ 实验学时 2学时，必做实验 数据结构与算法 核心源代码 蛮力法： #include { scanf("%d",&y[i]); } ClosestPoints(x,y,4); return 0; } int ClosestPoints(int x[ ], int y[ ], int n) { int index1, index2; //记载最近点对的下标 int d, minDist = 1000; //假设最大距离不超过1000 for (int i = 0; i < n - 1; i++) for (int j = i + 1; j < n; j++) //只考虑i＜j的点对 { d =sqrt ((x[i]-x[j])* (x[i]-x[j]) + (y[i]-y[j])* (y[i]-y[j])); if (d < minDist) { minDist = d; index1 = i; index2 = j; } } cout<<"最近的点对是："< 实验一 递归与分治策略 一、实验目的 （1）理解递归与分治策略算法设计思想和方法； （2）培养学生的动手能力。 二、实验工具 （1）JDK1.8 （2）Eclipse IDE for Java EE Developers 三、实验题： 1、设n 个不同的整数排好序后存于T[0:n-1]中。若存在下标i ，n i <≤0，使得T[i]=i ，设计一个有效算法找到这个下标。要求算法在最坏情况下的计算时间为)(log n O 。 2、设子数组]1-:0[k a 和]1:[-n k a 已排好序10-≤≤n k 。试设计一个合并这两个子数组为排好序的数组]1:0[-n a 的算法，要求算法在最坏情况下的计算时间为)(n O ，且只用到)1(O 的辅助空间。 三、实验提示： 1、由于n 个整数是不同的，因此对任意0≤i ＜n-1 有T[i]≤T[i+1]-1。 (1) 对于0＜i ＜n ，当T[i]>i 时，对任意的i ≤j ≤n-2 有T[j]≥T[i]+j-i>i+j-i=j 。 (2) 对于0＜i ＜n,当T[i]＜i 时，对任意的0≤j ≤i 有T[j]≤T[i] -i+j ＜i-i +j =j 。 由①和②可知，用二分搜索算法可以在)(log n O 时间内找到所要求的下标，伪代码如下： SEARCH(A,n) low <-- 0 high <-- n-1 while low < high do if A[middle] = middle then return middle if A[middle] < middle then low <-- middle + 1 else high <-- middle - 1 算法分析与设计实验报告 第 1 次实验 附录：完整代码 SelectMaxMin.cpp: #include else min=minj; return; } } intmain() { clock_tstart,end,over; start=clock(); end=clock(); over=end-start; start=clock(); //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int m; cout<<"Please input the number : "; cin>> m; int a[m]; srand((unsigned int)time(NULL)); cout<< "随机产生的数据(0-100)："; for(inti=0; i 《算法设计与分析》实验报告实验一递归与分治策略应用基础 学号： 姓名： 班级： 一、实验目的 1、熟悉递归的概念和分治法。 2、对递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法。递归与分治策略的问题类型，并能设计相应的分治策略算法。 二、实验内容 任务：以下题目要求应用递归与分治策略设计解决方案，本次实验成绩按百分制计，完成各小题的得分如下，每小题要求算法描述准确且程序运行正确。 1、求n个元素的全排。（30分） 算法分析：用递归的方法，先将n个数分成两个部分，然后将两个部分交换位子，然后再将这两个部分继续再分成四个部分，然后再将每个部分进行交换，然后就重复刚才的过程，直到不能再分为止，在这个过程中所产生的所有结果就是我们要求的全排列。 代码实现： #include *b = m; } void perm(int list[], int k, int m) { int i; if(k > 2) { for(i = 0; i <= 2; i++) printf("%d ", list[i]); printf("\n"); n++; } else { for(i = k; i <= 2; i++) { swap(&list[k], &list[i]); perm(list, k + 1, 4); swap(&list[k], &list[i]); } } } int main() { int list[] = {1, 2, 3,4}; perm(list, 0, 2); printf("total:%d\n", n); return 0; } 2、解决一个2k*2k的特殊棋牌上的L型骨牌覆盖问题。（30分）算法分析：用分治策略，将大的棋盘分割为下一级的棋盘，直到不能再分为止，然后再将每一个小的棋盘填满，接着将一个一个小的棋盘再又合并成一个大的棋盘。 代码实现： #include "iostream" using namespace std; int board[1025][1025]; int tile = 1; //tr,tc棋盘左上角方格坐标， dr, dc特殊方格所在坐标， size 为行数 算法分析与设计实验报告第一次实验 else Max=max2; //分别保存在Max与Min if(min1<=min2) Min=min1; else Min=min2; } else //当数组中元素个数少于2时，直接赋值处理 { Max=compmax(a,left,right); Min=compmin(a,left,right); } } 测试结果 利用分治法（递归实现）：非递归实现： 实验心得通过这次实验，加深了我对分治法的理解，明白了分治法到底是怎样的一个过程，在代码实现分治法的时候，也使我加深了对于自己构造函数的理解，明白了分治法利用代码是怎样实现的，以及构造函数的传参与返回值等等地方需要注意的东西，是我认识到我的编程能力的不足，更加加深了我要好好学习，多做练习的想法，总体收获很大。 附录： 完整代码（分治法） #include实验报告 分治与递归
递归与分治
算法分析实验报告--分治策略
递归与分治实验报告
算法之2章递归与分治
算法分析与设计实验一递归与分治策略
算法设计与分析：递归与分治法-实验报告
递归与分治策略
使用分治策略递归和非递归和递推算法解决循环赛日程表课程设计报告
分治算法实验(用分治法实现快速排序算法)
算法分析实验报告--分治策略
实验一分治与递归算法报告
实验一 递归与分治策略算法设计与实现实验报告
实验1++递归与分治算法
实验一 递归与分治策略
分治算法实验报告
递归与分治策略应用基础
分治算法实验(用分治法查找数组元素的最大值和最小值)
相关主题
文本预览