AA-chapter 3-02-蛮力法

算法设计与分析实验报告

本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼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．代码设计：

算法实验报告

华北电力大学 实验报告| | 实验名称算法设计与分析综合实验 课程名称算法设计与分析 | | 专业班级软件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;

分别用蛮力法、分治法、减治法实现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="<

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

题目描述：设计蛮力算法求解小规模的线性规划问题，假设约束条件为： （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

用蛮力法、动态规划法和贪心法求解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）

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

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

本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号实验项目类型设计实验地点机房 学生学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间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

算法设计与分析实验报告

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

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

【一】实验目的（小四黑体） 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）

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

分金块问题的解决思想和算法设计王雕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

蛮力法解决串匹配问题

算法分析实验报告 蛮力法-串匹配问题 学生姓名： 专业： 班级： 学号: 指导教师： 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<

蛮力法实验报告

数学与计算机学院实验报告 一、实验项目信息 项目名称：蛮力法实验 实验时间： 2016/03/16 实验学时： 03 学时实验地点：工科楼503 二、实验目的及要求 掌握蛮力法的设计思想， 掌握蛮力法的求解步骤 写程序代码，运行得到正确结果 三、实验环境 实验中主要使用的仪器、设备：计算机 实验材料：VC6.0 四、实验内容及实验步骤 实验内容或原理：重复元素删除问题与荷兰国旗问题。 实验步骤：(1)录入程序代码；(2)调试程序；(3)算法正确性测试；(4)撰写实验报告重复元素删除问题： 使用蛮力法求解： 找出解空间：每个元素都有可能重复所以可以说解空间是数组中的每个元素遍历解空间：把每个元素和其余元素进行比较如果有重复删除 程序代码： #include #define N 100 void deleteDuplicate(int a[]) { int i,j,m; i=0; while(a[i]!=0)//遇到0的时候意味着到数组尾 { j=i+1; while(a[j]!=0) { if(a[i]==a[j]) { printf("found duplicate\n");//若找到重复元素打印出提示 m=j; while(a[m]!=0)//移动后面的数组覆盖重复元素 { a[m]=a[m+1]; m++; } } else j++; } i++; } i=0; while(a[i]!=0)//打印出删除后的数组 { printf("%d ",a[i]); i++; } } void main() { int a[N]; int i=0; printf("Please input the number (0 to end your input!):"); a[0]=10; while(i

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

武汉工程大学计算机科学与工程学院 《算法设计与分析》实验报告

实验内容 （2）猴子吃桃子问题，猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了两个，第二天早上又将剩下的桃子吃掉一半，又多吃了两个，以后每天早上都吃了前一天剩下的一半零两个，到了第10天早上想再吃时，就只剩下两个桃子了，问第一天猴子摘了多少桃子？代码： #include void main() { int a=2,i; for(i=8;i>=0;i--) a=(a+2)*2; printf("第一天猴子摘下%d个桃子\n",a); } 测试： （3）54张扑克牌，两个人轮流拿牌，每人每次最少取一张牌最多取4张牌，谁拿最后一张谁输。编写模拟计算机先拿牌且必胜的算法。 代码： #include void main() { int a,b,c,d,e,f; for(a=1;a<=9;a++) for(b=0;b<=9;b++) if(b!=a) for(c=0;c<=9;c++) if(c!=a&&c!=b) for(d=0;d<=9;d++)

if(d!=a&& d!=b && d!=c) { e=a*1000+b*100+c*10+d; f=(a+b+c+d)*(a+b+c+d); if(e%f==0) printf("%d%d%d%d\t",a,b,c,d); } printf("\n"); } 测试： （8）寻找满足下列条件的四位数字：1.无重复数字；2.千位数字非零；3.能整除它的各个位数字和的平方。 代码: #include void main() { int i,c; printf("游戏开始，计算机先拿牌!\n"); c=51; printf("计算机拿3张!还剩%d张\n",c); while(c>1) { printf("请你拿牌，选择拿牌的张数（1-4张）\n"); scanf("%d",&i); c=c-5; printf("计算机拿了%d张，还剩%d张\n",5-i,c); } printf("你拿最后一张，计算机赢了！\n"); } 测试：

实验二蛮力法

南华大学 实验名称：算法的时间复杂度 学院：计算机学院 专业班级：本2010 电气信息类03班 学号：20104030342 姓名：谢志兴 指导教师：余颖 日期：2012 年 3 月27 日

实验二蛮力法 一、实验目的与要求 熟悉C/C++语言的集成开发环境； 通过本实验加深对蛮力法的理解。 二、实验内容: 掌握蛮力法的概念和基本思想，并结合具体的问题学习如何用相应策略进行求解的方法。 三、实验题 1. 某地刑侦大队对涉及六个嫌疑人的一桩疑案进行分析：（1）A、B至少有一人作案； （2）A、E、F三人中至少有两人参与作案；（3）A、D不可能是同案犯；（4）B、C或同时作案，或与本案无关；（5）C、D中有且仅有一人作案；（6）如果D没有参与作案，则E也不可能参与作案。试设计算法将作案人找出来。 2.将1,2...9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:2:3的 比例,试求出所有满足条件的三个三位数。 四、实验步骤 理解算法思想和问题要求； 编程实现题目要求； 上机输入和调试自己所编的程序； 验证分析实验结果； 整理出实验报告。 五、实验程序 /*1题程序*/ #include using namespace std;

int main() { int A,B,C,D,E,F; //每个罪犯只有01两种情况，1是罪犯0清白for(A=0;A<2;A++) //A for(B=0;B<2;B++) //B for(C=0;C<2;C++) //C for(D=0;D<2;D++) //D for(E=0;E<2;E++) //E for(F=0;F<2;F++) //F { if((A+B>0) //AB至少一人作案 &&(A+E+F>1) //AEF至少两人作案 &&(A+D==1) //AD不可能是同案犯 &&(B+C!=1) //BC或同案或与本案无关 &&(C+D==1) //CD只有一人作案 &&(!(!D&&E)))//如果D没有参与作案，则E也不可能参与作案 { cout<<"A:"; if(A==1) cout<<"作案"<

蛮力法、分治法和动态规划法设计最大子段和问题的算法

算法设计与分析实验报告 实验题目 给定由n个整数组成的序列(a1, a2, …, a n)，求该序列形如的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。 实验目的 （1）深刻掌握动态规划法的设计思想并能熟练运用； （2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。 实验要求 （1）分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法； （2）比较不同算法的时间性能； （3）给出测试数据，写出程序文档。 实验内容（包括代码和对应的执行结果截图） #include int x,y,z; int ml(int d[])//蛮力法 { int a=0,i,j,f; for(j=0;j<5;j++) {

f=0; for(i=j;i<5;i++) { f=f+d[i]; if(a0) sum=a[left]; else sum=0; y++; } else { center=(left+right)/2; //划分 leftsum=MaxSum(a, left, center); //对应情况①，递归求解rightsum=MaxSum(a, center+1, right); //对应情况②，递归求解s1=0; lefts=0; //以下对应情况③，先求解s1 for (i=center; i>=left; i--) { lefts+=a[i]; if (lefts>s1) s1=lefts; y++; } s2=0; rights=0; //再求解s2 for (j=center+1; j<=right; j++) { rights+=a[j]; if (rights>s2) s2=rights; y++; } sum=s1+s2; //计算情况③的最大子段和