蛮力法

算法设计与分析实验报告

本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼110 专业班级：物联网1601 学号：2016002105 学生姓名：俞梦真 指导教师：郝晓丽

2018年05月04 日 实验一递归与分治算法 1.1 实验目的与要求 1．进一步熟悉C/C++语言的集成开发环境； 2．通过本实验加深对递归与分治策略的理解和运用。 1.2 实验课时 2学时 1.3 实验原理 分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。 需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。 1.4 实验题目 1．上机题目：格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。 对于给定的正整数n，格雷码为满足如下条件的一个编码序列。 （1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。 （2）序列中无相同的编码。 （3）序列中位置相邻的两个编码恰有一位不同。 2．设计思想：

根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。 3．代码设计：

分别用蛮力法、分治法、减治法实现a的N次方

《算法设计与分析》实验报告一 学号：姓名： 日期： 2012.11.5 得分： 一、实验内容： 分别用蛮力法、分治法、减治法实现a^n。 二、实验要求： 完成试验报告、给出对此结果。 为防止大数溢出，可以用1^n来测试在n比较大是的三种算法运行情况。 四、源程序及注释： #include #include using namespace std; //蛮力法求a的n次方 int Power1(int a,int n) { int as=1; for(int i=0;i

} int main() { int a=1; int n=10000; LARGE_INTEGER start1,end1,start2,end2,start3,end3,f; QueryPerformanceFrequency(&f); QueryPerformanceCounter(&start1) ; int p1=Power1(a,n); QueryPerformanceCounter(&end1); QueryPerformanceCounter(&start2) ; int p2=Power2(a,n); QueryPerformanceCounter(&end2); QueryPerformanceCounter(&start3) ; int p3=Power3(a,n); QueryPerformanceCounter(&end3); cout<<"a="<

算法实验报告

华北电力大学 实验报告| | 实验名称算法设计与分析综合实验 课程名称算法设计与分析 | | 专业班级软件12 学生姓名： 学号：成绩： 指导教师：胡朝举实验日期：

实验一分治策略—归并排序 一、实验要求 （1）编写一个模板函数：template ，MergeSort(T *a, int n); 以及相应的一系列函数，采用分治策略，对任意具有:bool operator<(const T&x,const T&y);比较运算符的类型进行排序。 （2）与STL库中的函数std::sort(..)进行运行时间上的比较，给出比较结果,如：动态生成100万个随机生成的附点数序列的排序列问题, 给出所用的时间比较。 二、实验代码 #include <> #include <> #include <> #include <> #define MAX 50 typedef struct { int arr[MAX+1]; int length; }SortArr; SortArr *CreateSortArr() { int i = 0; char buf[4*MAX] = ""; char *ptr = NULL; SortArr *sortArr = (SortArr *)malloc(sizeof(SortArr)); memset(sortArr, 0, sizeof(SortArr)); printf("请输入待排序数据，以逗号分隔，以分号结束\n" "input:"); scanf("%s", buf); ptr = buf; sortArr->arr[i] = 0; i = 1; while(*ptr != ';') { sortArr->arr[i] = atoi(ptr); i++; ptr = strstr(ptr, ","); if(!ptr) { break; } ptr++; } sortArr->length = (i - 1); return sortArr; } int merge(int arr[], int p, int q, int r) { int i = 0; int j = 0; int k = 0; int n1 = 0; int n2 = 0; int *leftArr = NULL; int *rightArr = NULL; n1 = q - p + 1; n2 = r - q;

算法分析与设计第三章课后练习题

题目描述：设计蛮力算法求解小规模的线性规划问题，假设约束条件为： （1）x+y<=4;(2)x+3y<=6;(3)x>+0;y>=0，使目标函数3x+5y取得最大值 */ /* 思路：用两个for遍历用一个if比较找出最大的。 */ #include using namespace std; int main() { int i,x,y,s,temp = 0; for(y = 0;y <= 6;y++) for(x = 0;x <= 6;x++) if(((x +y) <= 4)&&((x + 3 * y) <= 6)) { s = 3*x + 5*y; if(s > temp) temp = s; } cout< #include using namespace std; int main() { long int a,b,c,d;//因为这4件商品的价格肯定存在不是整数的，所以可以将其扩大100倍进行处理 for(a=1;a<711;a++) for(b=1;b<=a;b++) for(c=1;c<=b;c++) { d=711-a-b-c; if(a*b*c*d==711*1000000)//4个数相乘就要扩大10的8次方倍 cout<

算法设计与分析实验报告

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

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

蛮力法分治法求最近对

实验题目 设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。 实验目的 （1）进一步掌握递归算法的设计思想以及递归程序的调试技术；（2）理解这样一个观点：分治与递归经常同时应用在算法设计之中。 实验内容（包括代码和对应的执行结果截图） #include #include #include using namespace std; typedef struct Node {//定义一个点的结构，用于表示一个点 int x; int y; }Node; typedef struct NList {//定义一个表示点的集合的结构 Node* data; int count; }NList; typedef struct CloseNode {//用于保存最近两个点以及这两个点之间的距离 Node a; Node b; double space; }CloseNode; int max; void create(NList & L) { cout<<"请输入平面上点的数目:\n"; cin>>max;

L.count=max; L.data = new Node[L.count];//====================动态空间分配 cout<<"输入"<>L.data[i].x>>L.data[i].y; } //求距离平方的函数 double Distinguish2(Node a,Node b) { return ((a.x-b.x)*(a.x-b.x))+((a.y-b.y)*(a.y-b.y)); } //蛮力法求最近对 void BruteForce(const NList & L,CloseNode & cnode,int begin,int end) { for(int i=begin;i<=end;i++) for(int j=i+1;j<=end;j++) { double space = Distinguish2(L.data[i],L.data[j]); if(space

《算法设计与分析》实验报告

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

本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号实验项目类型设计实验地点机房 学生学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间2012年3月1 日～6月30日温度24℃ 1.实验目的和要求： 熟悉蛮力法的设计思想。 2.实验原理和主要容： 实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验容：以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序，实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人 H.E.Dudeney(1857-1930)给出的： S END +MORE MONEY . 这里有两个前提假设： 第一，字母和十进制数字之间一一对应，也就是每个字母只代表一个数字，而且不同的字母代表不同的数字；第二，数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意，解可能并不是唯一的，不同人的解可能并不相同。3.实验结果及分析： （将程序和实验结果粘贴，程序能够注释清楚更好。）

该算法程序代码如下： #include "stdafx.h" #include "time.h" 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

用蛮力法、动态规划法和贪心法求解01背包问题

算法设计与分析 项目名称：用蛮力法、动态规划法和贪心法求解0/1背包问题 作者姓名：余武丹 李红波 刘红梅 完成日期：2013年9月20日

目录 第一章：简介（Introduction） 第二章：算法定义（Algorithm Specification） 第三章：测试结果（Testing Results） 第四章：分析和讨论

第一章：简介（Introduction ） 0/1背包问题是给定n 个重量为{w 1, w 2, … ,wn }、价值为{v 1, v 2, … ,vn }的物品和一个容量为C 的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。 在0/1背包问题中，物品i 或者被装入背包，或者不被装入背包，设xi 表示物品i 装入背包的情况，则当xi =0时，表示物品i 没有被装入背包，xi =1时，表示物品i 被装入背包。根据问题的要求，有如下约束条件和目标函数： 于是，问题归结为寻找一个满足约束条件式1，并使目标函数式2达到最大的解向量X =(x 1, x 2, …, xn )。 背包的数据结构的设计： typedef struct object { int n;//物品的编号 int w;//物品的重量 int v;//物品的价值 }wup; wup wp[N];//物品的数组，N 为物品的个数 int c;//背包的总重量 第二章：算法定义（Algorithm Specification ） 1、蛮力法 蛮力法是一种简单直接的解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。蛮力法的关键是依次处理所有的元素。 用蛮力法解决0/1背包问题，需要考虑给定n 个物品集合的所有子集，找出所有可能的子集（总重量不超过背包容量的子集），计算每个子集的总价值，然后在他们中找到价值最大的子集。 所以蛮力法解0/1背包问题的关键是如何求n 个物品集合的所有子集，n 个物品的子集有2的n 次方个，用一个2的n 次方行n 列的数组保存生成的子集，以下是生成子集的算法： void force(int a[][4])//蛮力法产生4个物品的子集 { int i,j; int n=16; int m,t; for(i=0;i<16;i++) ????? ≤≤∈≤∑=) 1(}1,0{1 n i x C x w i n i i i （式1） ∑=n i i i x v 1 max （式2）

算法设计与分析实验报告

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

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

《算法设计与分析基础(第3版)》部分习题答案

作业一 学号：______ 姓名：________ P135 2. a.为一个分治算法编写伪代码，该算法同时求出一个元素数组的最大元素和 最小元素的值。 解：算法：EXTREMUM(A[],EXTREMUM_MAX, EXTREMUM_MIN) //递归调用EXTREMUM函数来找出数组A[]的最大元素和 最小元素。 //输入：数值数组A[] //输出：最大值EXTREMUM_MAX和最小值EXTREMUM_MIN if() //只有一个元素 EXTREMUM_MAX A[]; EXTREMUM_MIN A[]; else if //有两个元素 if EXTREMUM_MAX; EXTREMUM_MIN; else EXTREMUM_MAX; EXTREMUM_MIN; else EXTREMUM(,EXTREMUM_MAX_01, EXTREMUM_MIN_01); EXTREMUM(,EXTREMUM_MAX_02, EXTREMUM_MIN_02); if EXTREMUM_MAX_01 EXTREMUM_MAX_02 EXTREMUM_MAX = EXTREMUM_MAX_02; If EXTREMUM_MIN_02 EXTREMUM_MIN_01 EXTREMUM_MIN = EXTREMUM_MIN_02;

b. 假设,为该算法的键值比较次数建立递推关系式并求解。 解： c.将该算法与解决同样问题的蛮力法做一个比较 蛮力法时间时间复杂度为2n-2，分治算法的为3n/2-2,虽然都属于Θ(n)级别，但是分治算法速度要比蛮力算法快。 5.1.3 a.为一个分治算法编写伪代码，该算法用来计算指数函数a n的值，其中a>0, n 是一个正整数。 //该算法使用分治法来计算a n Pow(a,n) If n = 1 return a else p←pow(a,n/2); If n mod 2 = 1 return p*p*a; else return p*p; b.建立该算法执行的乘法次数的递推关系式并求解 c.将该算法与解决同样问题的蛮力法做一个比较 蛮力法时间复杂度为n，分治法为,分治法速度明显要 高于蛮力法。

算法分析实验3蛮力法排序

【一】实验目的（小四黑体） 1．采用蛮力法实现序列排序； 2．分析各种方法的优缺点。 【二】实验内容（小四黑体） 1．采用蛮力排序算法对序列排序； 2．编程实现选择排序与冒泡排序； 3．分析比较2种算法的时间复杂度； 4．试着改进冒泡排序，使算法在序列达到有序状态时停止运行。【三】实验步骤（代码、结果）（小四黑体） #include <> #include <> #include <> void SelectionSort(int a[],int n) { int i,j,t,temp; for(i=0; i<=n-2; i++) { t=i; for(j=i+1; j<=n-1; j++) { if(a[j]

{ temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } } void BubbleSort1(int a[],int n) { int falg=1; int i,temp; while(falg) { falg=0; for(i=0;i

实验项目三 用蛮力法、动态规划法和贪心法求解背包问题

实验项目三 用蛮力法、动态规划法和贪心法求解0/1 背包问题 实验目的 1、学会背包的数据结构的设计，针对不同的问题涉及到的对象的数据结构的设计也不同； 2、对0-1背包问题的算法设计策略对比与分析。 实验内容： 0/1背包问题是给定n 个重量为{w 1, w 2, … ,wn }、价值为{v 1, v 2, … ,vn }的物品和一个容量为C 的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。 在0/1背包问题中，物品i 或者被装入背包，或者不被装入背包，设xi 表示物品i 装入背包的情况，则当xi =0时，表示物品i 没有被装入背包，xi =1时，表示物品i 被装入背包。根据问题的要求，有如下约束条件和目标函数： 于是，问题归结为寻找一个满足约束条件式1，并使目标函数式2达到最大的解向量X =(x 1, x 2, …, xn )。 背包的数据结构的设计： typedef struct object { int n;//物品的编号 int w;//物品的重量 int v;//物品的价值 }wup; wup wp[N];//物品的数组，N 为物品的个数 int c;//背包的总重量 1、蛮力法 蛮力法是一种简单直接的解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。蛮力法的关键是依次处理所有的元素。 用蛮力法解决0/1背包问题，需要考虑给定n 个物品集合的所有子集，找出所有可能的子集（总重量不超过背包容量的子集），计算每个子集的总价值，然后在他们中找到价值最大的子集。 所以蛮力法解0/1背包问题的关键是如何求n 个物品集合的所有子集，n 个物品的子集有2的n 次方个，用一个2的n 次方行n 列的数组保存生成的子集，以下是生成子集的算法： ?????≤≤∈≤∑=)1(}1,0{1n i x C x w i n i i i （式1） ∑=n i i i x v 1max （式2）

【IT专家】蛮力算法： 选择排序 冒泡排序(详解)

蛮力算法：选择排序冒泡排序（详解） 2015/10/26 1 蛮力法：蛮力法(brute force)是一种简单直接地解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。虽然巧妙而高效的算法很少来自于蛮力法，但它还是具有重要地位。因为它能解决几乎任何问题，如果要解决的问题的规模不大，或者对性能没有很高的要求，那么花大工夫涉及复杂的算法显然是不值得的。下面就来介绍一下2大蛮力排序算法，然后是它们的分析。 ?框架介绍：在介绍算法之前，有必要介绍一些以后会用到的方法。使用前2个方法，我们就可以生成随机数组，然后方便地判断数列是否被正确排序了，以此验证排序算法的正确性。第3个方法从标准输入中读取数据（通过重定向），进行大规模排序，以此比较不同算法的性能。 ?/** * 生成一个长度为0~600的数组，每个元素的值为0~99999的整数。* * @return */ public static Integer[] randomArray() { Integer[] r = new Integer[(int) (600 * Math.random())]; for (int i = 0; i r.length; i++) r[i] = (int) (99999 * Math.random()); return r; } /** * 返回一个数组是否是有序的。* @param r * @return */ public static boolean isSorted(Integer[] r) { for (int i = 1; i r.length; i++) if (r[i]pareTo(r[i - 1]) 0) return false; return true; } /** * 从标准输入中读取1000000个整数的数组。* @return */ public static Integer[] arrayIn(){ Scanner in = new Scanner(System.in); Integer[] r = new Integer[1000000]; for(int i=0;i 1000000;i++) r[i] = in.nextInt(); return r; }选择排序：选择排序开始的时候，我们扫描整个列表，找到它的最小元素，然后和第一个元素交换（如果第一个元素就是最小元素，那么它就和自己交换。）。再次，在剩下的元素中找到最小元素，将它和数组的第二个元素交换位置，以此往复，直到整个数组有序。这种算法叫做选择排序，因为它每次都选择剩余元素之中最小的元素放在正确位置。 public static void selection(Integer[] r) { int N = r.length; for (int i = 0; i N - 1; i++) { int min = i;//已知最小元素的索引for (int j = i + 1; j j++) if (r[min] r[j])//如果找到更小的元素，更新索引min = j; int temp = r[i];//交换位置r[i] = r[min]; r[min] = temp; } }

分金块问题的两种算法实验报告

分金块问题的解决思想和算法设计王雕40912127 2009级计算机科学与技术三班 摘要：在日常生活中，分金块问题是一个常见的问题，人们总是会面临怎样比较大小。本文给出了较为常用的两种算法—蛮力法和分治法。 关键词：分金块问题；蛮力法(非递归)；分治法； 1 问题概述 老板有n个金块，希望最优秀的雇员得到其中最重要的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，如何用最少的比较次数找出最重和最轻的金块？ 2 理解金块问题：以9以内的实例理解问题 金块示例

问题：1.最重的是那块？用max标记 2.最轻的是那块？用max标记 3 求解金块问题的常用算法一蛮力法 蛮力法的设计思想：蛮力法，也称穷举法，是一种简单而直接地解决问题的方法，常常直接基于问题的描述，因此，也是最容易应用的方法。但是，用蛮力法设计的算法其时间性能往往是最低的，典型的指数时间算法一般都是通过蛮力搜索而得到的。即从第一块开始查找，查找哪块最重，哪块最轻。 a[0] a[1] a[2] a[3] max 4算法设计： Maxmin(float a[],int n) {max=a[1];min=a[1]; for(i=2;i<=n;i=i+1) {if(max

max=a[i] else if(min>a[i]) min=a[i] } Return(max, min) } Step1 将所有金块重量存于数组 Step2 将第一个金块同时标记为最重和最轻的金块 Step3 将第一个与后一个进行重量的比较，将更重的标记为max，同时如果现阶段最轻的比后者轻，那么将后者标记为min。 Step4 依次进行比较，最重得到最重的和最轻的max min. 5算法分析：(1)时间复杂性和空间复杂性。 分析该算法可以看出，比较操作max

算法设计与分析部分算法伪代码

第三章蛮力法 1.选择排序 ?SelectionSort(A[0..n-1]) for i=0 to n-2 do min=i for j=i+1 to n-1 do if A[j]

4.顺序查找算法 算法SwquentialSearch2(A[0...n],k) //顺序查找算法的实现，它用了查找键来作限位器 //输入：一个n个元素的数组A和一个查找键K //输出：第一个值等于K的元素的位置，如果找不到这样的元素就返回-1 A[n]<--k i<--0 while A[i]!=K do i<--i+1 if i

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

实验一——串匹配问题 1．实验题目 给定一个文本，在该文本中查找并定位任意给定字符串。 2．实验目的 ⑴ 深刻理解并掌握蛮力法的设计思想； ⑵ 提高应用蛮力法设计算法的技能； ⑶ 理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。 3．实验要求 ⑴ 实现BF 算法； ⑵ 实现BF 算法的改进算法：KMP 算法和BM 算法； ⑶ 对上述三个算法进行时间复杂性分析，并设计实验程序验证分析结果。 4．实现提示 BF 算法、KMP 算法和BM 算法都是串匹配问题中的经典算法，BF 算法和KMP 算法请参见本章第2节。下面介绍BM 算法。 BM （Boyer -Moore ）算法是Boyer 和Moore 共同设计的快速串匹配算法。BM 算法与KMP 算法的主要区别是匹配操作的方向不同。虽然BM 算法仅把匹配操作的字符比较顺序改为从右向左，但匹配发生失败时，模式T 右移的计算方法却发生了较大的变化。 为了方便讨论，假设字符表∑＝{a , b , …, y , z }，BM 算法的关键是，对给定的模式T ="t 1t 2 … t m "，定义一个从字符到正整数的映射： dist : c →{1, 2,… , m } （c ∈∑） 函数dist 称为滑动距离函数，它给出了正文中可能出现的任意字符在模式中的位置。函数dist 定义如下： ?? ?=-≤≤==-=c t c m m j c t j j j m c dist m j 不出现在模式中或 若且}11|max{)( 例如，T ＝"pattern "，则dist (p )=6，dist (a )=5，dist (t )=3，dist (e )=2，dist (r )=1，dist (n )=7，字符表∑中的其他字符ch 的dist (ch )=7。 BM 算法的基本思想是：假设将主串中自位置i 起往左的一个子串与模式进行从右到左的匹配过程中，若发现不匹配，则下次应从主串的i +dist (s i )位置开始重新进行新一轮的匹配，其效果相当于把模式和主串均向右滑过一段距离dist (s i )，即跳过dist (s i )个字符而无需进行比较。 例如，给定主串S ="ababcabcacbab "，模式T ="abcac "，则dist (a )=1，dist (b )=3，dist (c )=5，BM 算法的匹配过程如图3.19所示。

用蛮力法和分治法解决最近对问题

算法分析与复杂型设计作业 学院计算机与控制工程学院 专业计算机软件与理论 班级 Y130701 学生姓名郑晓璐 流水号 20130789 2014年4月

问题： 设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。 蛮力算法描述： int ClosestPoints(int n, int x[ ], int y[ ]){ minDist=Double.POSITIVE_INFINITY;; for (i=1; i< n; i++) for (j=i+1; j<=n; j++) { d=(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; } } return minDist; } 程序： import java.util.*; public class ClosestPair1{ public static void main(String[] args) { /** *输入需要比较的点的对数存在变量n中 */ Scanner in=new Scanner(System.in); System.out.println("How many pairs of points to compare?(有多少对点需要比较?)"); int n=in.nextInt(); int[] x=new int[n]; int[] y=new int[n]; /** *输入这些点的横坐标和纵坐标分别存储在x[n]和y[n] */ System.out.println("Please enter these points,X-coordinate(请输入这些点,横坐标):"); for(int i=0;i< n;i++) { x[i]=in.nextInt(); }

蛮力法解决串匹配问题

算法分析实验报告 蛮力法-串匹配问题 学生姓名： 专业： 班级： 学号: 指导教师： 2017年6月12日

目录 一、实验题目 (2) 二、实验目的 (2) 三、实验要求 (2) 四、实现过程 (3) 1、实验设计： (3) 2、调试分析： (9) 3、运行结果：..... 错误！未定义书签。 4、实验总结： (9) 五、参考文献 (10)

一、实验题目 蛮力法-串匹配问题 二、实验目的 (1)深刻理解并掌握蛮力法的设计思想； (2)提高应用蛮力法设计算法的技能； (3)理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。 三、实验要求 1.[问题描述]： 给定两个字符串S和T，在主串S中查找子串T的过程称为串匹配，T 称为模式。 设主串S=“abcabcacb”,模式=“abcac”。 2.[算法]： 蛮力法：蛮力法（也称穷举法或枚举法）是一种简单直接的解决问题的方法，常常直接基于问题的描述，所以，蛮力法也是最容易应用的方法，例如，对于给定的整数a和非负整数n，计算a n的值，最直接最简单的方法就是把1和a相乘n次，即：a n=a*a*a*···*a。 蛮力法所依赖的基本技术是遍历（也称扫描），即采用一定的策略依次处理待求解问题的所有元素，从而找出问题的解。依次处理所

有元素是蛮力法的关键，为了避免陷入重复试探，应保证处理过的元素不再被处理。用蛮力法设计的算法，一般来说，都可以对算法的第一个版本进行一定程度的改进，提高其时间性能，但只能减少系数，而数量级不会改变。 四、实现过程 1、实验设计： ●想法一：BF算法 1 在串S中和串T中设比较的下标i=1和j=1; 2 循环直到S中所剩字符个数小于T的长度或T中所有字符均比较完 2.1 k=i 2.2 如果S[i]=T[j],则比较S和T的下一字符,否则 2.2 将i和j回溯(i=k+1; j=1) 3 如果T中所有字符均比较完,则匹配成功,返回k，否则匹配失败,返回0 时间复杂度：设匹配成功发生在si处，则在i-1趟不成功的匹配中比较了（i-1）*m次，第i趟成功匹配共比较了m次，所以总共比较了i*m次，因此平均比较次数是： 一般情况下，m<