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

一、实验目的1. 理解分金块问题的背景和意义；2. 掌握分治法的基本思想及其在解决分金块问题中的应用；3. 比较不同算法在解决分金块问题时的性能；4. 提高编程能力和算法设计能力。

二、实验内容1. 问题概述分金块问题是一个经典的算法问题。

问题描述如下：老板有n个金块，希望最优秀的雇员得到其中最重要的一块，最差的雇员得到其中最轻的一块。

假设有一台比较重量轻重的天平，要求设计一个算法，在尽可能少的比较次数内，将金块分为三组，使得最优秀的雇员得到最重的金块，最差的雇员得到最轻的金块。

2. 算法分析针对分金块问题，我们可以采用以下两种算法：（1）蛮力法（非递归）蛮力法的基本思想是：遍历所有可能的分组方式，找出最优解。

具体步骤如下：① 将n个金块依次编号为1至n；② 遍历所有可能的分组方式，即从第一个金块开始，将其与其他金块进行分组，然后继续对剩余的金块进行分组，直到分组完毕；③ 对于每一种分组方式，分别找出最重的金块和最轻的金块，并比较其重量；④ 找出所有分组方式中最优的分组方式，即最重的金块和最轻的金块的重量差最小。

（2）分治法分治法的基本思想是将大问题分解为若干个小问题，递归地解决这些小问题，然后合并其结果。

具体步骤如下：① 当n=1时，直接返回该金块；② 将n个金块随机分为两组，分别编号为A和B；③ 分别对A组和B组递归调用分治法，找出每组中的最重金块和最轻金块；④ 比较A组最重金块和A组最轻金块的重量差，以及B组最重金块和B组最轻金块的重量差；⑤ 根据比较结果，确定最终的最重金块和最轻金块。

三、实验步骤1. 实验环境：Python 3.72. 实验数据：随机生成100个金块，重量在1至1000之间。

3. 实验代码（1）蛮力法实现```pythondef brute_force(n):# 初始化金块重量列表weights = [i for i in range(1, n+1)]# 遍历所有可能的分组方式for i in range(1, n//2+1):for j in range(i+1, n-i+1):for k in range(j+1, n-j+1):# 计算分组方式下的最重金块和最轻金块的重量差diff_a = max(weights[i-1:k]) - min(weights[i-1:k])diff_b = max(weights[k:n]) - min(weights[k:n])# 更新最优解if diff_a < diff_b:best_a = max(weights[i-1:k])best_b = min(weights[i-1:k]) else:best_a = max(weights[k:n]) best_b = min(weights[k:n]) return best_a, best_b# 测试n = 100print(brute_force(n))```（2）分治法实现```pythondef divide_and_conquer(weights, left, right):# 当只剩一个金块时，返回该金块if left == right:return weights[left]# 将金块分为两组mid = (left + right) // 2max_a = max(weights[left:mid])min_a = min(weights[left:mid])max_b = max(weights[mid:right+1])min_b = min(weights[mid:right+1])# 比较两组金块的重量差if max_a - min_a < max_b - min_b:return max_a, min_aelse:return max_b, min_b# 测试n = 100weights = [i for i in range(1, n+1)]print(divide_and_conquer(weights, 0, n-1))```四、实验结果与分析1. 实验结果（1）蛮力法：当n=100时，运行时间约为0.6秒；（2）分治法：当n=100时，运行时间约为0.001秒。

实验报告实验名称：黄金分割法院（系）：机电学院专业班级：机械制造及其自动化姓名：学号：2013年5 月13 日实验一：黄金分割法实验日期：2013年5 月13 日一、实验目的了解MATLAB的基本运用了解MATLB在优化中的使用二、实验原理黄金分割法是用于一元函数f(x)在给定初始区间[a,b]内搜索极小点α*的一种方法。

其基本原理是：依照“去劣存优”原则、对称原则、以及等比收缩原则来逐步缩小搜索区间。

三、实验内容黄金分割法程序：function [xmin,fmin]=hjfg (f,a0,b0,epsilon)a=a0; %初始化b=b0;x1=b-0.618*(b-a);f1=f(x1);x2=a+0.618*(b-a);f2=f(x2);while abs(b-a)>=epsilon %迭代求解if f1<f2 %判断缩小方向b=x2;x2=x1;f2=f1; %缩小区间x1=b-0.618*(b-a);f1=f(x1);elsea=x1;x1=x2;f1=f2;x2=a+0.618*(b-a);f2=f(x2);endx=0.5*(a+b);endxmin=0.5*(a+b);%输出fmin=f(xmin);end函数程序：function [zhi]= fx2(x) %2²âÊÔº¯Êýzhi=2*x^2-3*x+1;end调用执行程序：[xmin2,fmin2]=hjfg (@fx2,-1,2,0.1) %2»Æ½ð·Ö¸î¼ÆËãÃüÁî执行结果：xmin2 =0.7583fmin2 =-0.1249四、实验小结通过本实验了解了了matlab的基本操作方法，了解黄金分割法法的原理与基本运用。

第九章分治策略当我们要求解一个数据规模为n且n取值又相当大的问题时，直接求解往往是非常困难的。

如果在将这n个输入分成k个不同子集合的情况下，能得到k个不同的可分别求解的子问题，其中1<k≤n，求出了这些子问题的解之后，还可找到适当的方法把它们合并成整个问题的解，那么，具备上述特性的问题可考虑使用分治策略求解。

第1课金块问题(gold)【问题描述】一个老板有一袋金块，里面有n块金子。

每个月，老板会从袋子中拿出两个金块奖励两名表现优秀的雇员。

按规矩，最优秀的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。

如果老板周期性地往袋中加入新的金块，那么每个月他都要找出最重和最轻的金块。

假设有一台比较质量的仪器，我们希望用尽量少的比较次数找出最重和最轻的金块。

【输入格式】第1行只有一个整数n(2≤n≤100000)。

第2行n个长整型范围内的整数，每个整数之间用一个空格隔开，表示每块金子的质量。

【输出格式】输出两个用空格分开的整数，表示最重和最轻的金块的质量。

【输入样例】8108245391【输出样例】101分析问题明显，金块问题就是在n个元素中求最大值和最小值的问题。

最直接的方法就是逐个地进行比较查找，如下面程序所示：vara:array[1..100000]of longint;i,n,max,min:longint;beginreadln(n);for i:=1to n do read(a[i]);max:=a[1];min:=a[1];for i:=2to n dobeginif a[i]>max then max:=a[i];if a[i]<min then min:=a[i];end;writeln(max,'',min);end.这种方法需要比较2n-2次。

也可以采用另一种方法，先比较n-1次求出最重的金块，再从剩下的n-1个金块中比较n-2次得到最轻的，这样总的比较次数为2n-3次（程序如下），相差只有一次。

matlab实验黄金分割法黄金分割法（Golden Section Method）是一种用于解决最优化问题的数值计算方法。

在数学上，最优化问题可以表述为寻找某个函数的最小值或最大值。

而黄金分割法是一种无约束优化算法，常被用于一维函数的最优化问题。

在本文中，我们将介绍黄金分割法的原理，并通过Matlab实验来演示其应用。

黄金分割法的原理基于黄金分割比，即1：0.618。

黄金分割法通过将搜索区间不断缩小，直到满足指定的精度要求，最终找到函数的极值点。

下面我们将逐步介绍黄金分割法的步骤：1. 初始化：给定初始搜索区间[a, b]，以及所需的精度要求ε。

2. 计算区间长度：计算区间长度L = b - a。

3. 计算划分点：计算第一个划分点x1 = a + 0.382L，以及第二个划分点x2 = a + 0.618L。

4. 计算函数值：计算在划分点x1和x2处的函数值f(x1)和f(x2)。

5. 更新搜索区间：比较f(x1)和f(x2)的大小关系，若f(x1) < f(x2)，则新的搜索区间为[a, x2]，否则为[x1, b]。

6. 判断收敛：如果L < ε，算法收敛，停止迭代；否则，返回步骤2。

接下来，我们将通过一个实例来演示黄金分割法在Matlab中的应用。

假设我们要优化以下函数：```matlabf(x) = x^2 + 5*sin(x)```首先，我们需要在Matlab中定义这个函数。

在命令窗口中输入以下代码：```matlabf = @(x) x^2 + 5*sin(x);```接下来，我们可以采用黄金分割法来最小化这个函数。

以下是Matlab代码的大致框架：```matlaba = 0;b = 10;epsilon = 0.001;L = b - a;x1 = a + 0.382*L;x2 = a + 0.618*L;while L >= epsilonf1 = f(x1);f2 = f(x2);if f1 < f2b = x2;elsea = x1;endL = b - a;x1 = a + 0.382*L;x2 = a + 0.618*L;end```以上代码中，我们使用了一个while循环来不断更新搜索区间和划分点，直到满足指定的精度要求。

算法实验报告一分治法实验金块问题问题描述：有一个老板有一袋金块。

每个月将有两名雇员会因其优异的表现分别被奖励一个金块。

按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。

根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。

如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。

假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块算法思想：分而治之方法与软件设计的模块化方法非常相似。

为了解决一个大的问题，可以：1) 把它分成两个或多个更小的问题；2) 分别解决每个小问题；3) 把各小问题的解答组合起来，即可得到原问题的解答。

小问题通常与原问题相似，可以递归地使用分而治之策略来解决。

问题分析:一般思路：假设袋中有n 个金块。

可以用函数M a x（程序1 - 3 1）通过n-1次比较找到最重的金块。

找到最重的金块后，可以从余下的n-1个金块中用类似的方法通过n-2次比较找出最轻的金块。

这样，比较的总次数为2n-3。

分治法：当n很小时，比如说，n≤2，识别出最重和最轻的金块，一次比较就足够了。

当n 较大时（n＞2），第一步，把这袋金块平分成两个小袋A和B。

第二步，分别找出在A和B中最重和最轻的金块。

设A中最重和最轻的金块分别为HA 与LA，以此类推，B中最重和最轻的金块分别为HB 和LB。

第三步，通过比较HA 和HB，可以找到所有金块中最重的；通过比较LA 和LB，可以找到所有金块中最轻的。

在第二步中，若n＞2，则递归地应用分而治之方法程序设计据上述步骤，可以得出程序1 4 - 1的非递归代码。

该程序用于寻找到数组w [ 0 : n - 1 ]中的最小数和最大数，若n < 1，则程序返回f a l s e，否则返回t r u e。

当n≥1时，程序1 4 - 1给M i n和M a x置初值以使w [ M i n ]是最小的重量，w [ M a x ]为最大的重量。

黄金分割法及程序求解第5题：对函数f(x)=（x^2-1）^2+(x-1)^2+3,当给定搜索区-10≤x≤10使用黄金分割法求极小点α*。

解：显然，此时的a=-10,b=10。

首先插入两个点a1和a2,由黄金分割点法得：a1=b-γ(b-a)=10-0.618×(10-(-10))=-2.36a2=a+γ(b-a)=-10+0.618×20=2.36再计算相应插图点的函数值，得y1=f(a1)=35.171y2=f(a2)=25.731因为y1>y2，所以，消去区间〔-10，-2.36〕,则新的搜索区间〔a，b〕为〔-2.36，10〕。

第一次迭代：此时插入点a1=b-γ(b-a)=10-0.618×[10-(-2.36)]=2.362a2=a+γ(b-a)=-2.36+0.618×[10-(-2.36)]=5.279相应插入点的函数值为：y1=25.823y2=743.191由于y2>y1，同理，得新的搜索区间为〔-2.36，5.279〕.如此继续迭代下去，列出前六次迭代的结果：y2迭代序号a a1a2b y1比较0-10-2.36 2.361035.171＞25.7311-2.36 2.362 5.2791025.832＜743.1912-2.360.558 2.361 5.279 3.669＜25.7773-2.36-0.5570.558 2.361 5.900＞ 3.6694-0.5570.558 1.246 2.361 3.669＞ 3.36650.558 1.247 1.443 2.361 3.369＜ 4.36860.5580.896 1.105 1.443假定，经过前六次迭代后已满足收敛精度要求，则得α*=(a+b)/2=（0.558+1.443）/2=1.0005相应的函数极值:f（α*）=3.000001运用MATLB程序求解:建立m文件：function[x,minf]=minHJ(f,a,b,k) format long;if nargin==3eps=0.000001;enda1=b-0.618*(b-a);a2=a+0.618*(b-a);k=1;tol=b-a;while tol>eps&&k<100000fa1=subs(f,findsym(f),a1);fa2=subs(f,findsym(f),a2);if fa1>fa2a=a1;a1=a2;a2=a+0.618*(b-a);else b=a2;a2=a1;a1=b-0.618*(b-a);endk=k+1;tol=abs(b-a);endif k==100000disp('找不到最小值');x=NaN;minf=NaN;return;endkx=(a+b)/2minf=subs(f,findsym(f),x)format short函数文件：syms x;f=(x^2-1)^2+(x-1)^2+3;[x,minf]=minHJ(f,-10,10);运行结果:k=36k=36x=1.000004289112507 minf=3.000000000091983。

分金块问题的解决思想和算法设计王雕40912127 2009级计算机科学与技术三班摘要：在日常生活中，分金块问题是一个常见的问题，人们总是会面临怎样比较大小。

本文给出了较为常用的两种算法—蛮力法和分治法。

关键词：分金块问题；蛮力法(非递归)；分治法；1 问题概述老板有n个金块，希望最优秀的雇员得到其中最重要的一块，最差的雇员得到其中最轻的一块。

假设有一台比较重量的仪器，如何用最少的比较次数找出最重和最轻的金块？2 理解金块问题：以9以内的实例理解问题金块示例问题：1.最重的是那块？用max标记2.最轻的是那块？用max标记3 求解金块问题的常用算法一蛮力法蛮力法的设计思想：蛮力法，也称穷举法，是一种简单而直接地解决问题的方法，常常直接基于问题的描述，因此，也是最容易应用的方法。

但是，用蛮力法设计的算法其时间性能往往是最低的，典型的指数时间算法一般都是通过蛮力搜索而得到的。

即从第一块开始查找，查找哪块最重，哪块最轻。

a[0] a[1] a[2] a[3]max4算法设计：Maxmin(float a[],int n){max=a[1];min=a[1];for(i=2;i<=n;i=i+1){if(max<a[i])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<a[i]和mix<a[i]是执行频次最高的关键语句。

因此以这两个语句执行的总次数作为该算法执行所需要的时间。

最好情况下，金块由轻到重排列，不需要进行min<a[i]比较，而max<a[i]比较共需进行n-1次,即可得到max和min; 最坏情况下，金块由重到轻排列，还需要进行n-1次min<a[i]比较，才能得到最终的min，因此共进行2(n-1)次比较。