通过学习“算法设计与分析”课程,我想对于那些经典的算法,除了在理论上“认识”他们外,最主要是在思想上学会他们,接受他们,这样不知不觉地培养了我们一种严密的思维能力,并且运用所学知识结合具体问题设计适用的算法的能力。而且那些经典算法也有很多复杂的应用领域,但是对于没有涉足这方面的人来说,由“认识”他们再上升到算法思想上的掌握也是很有必要的。
下面介绍的几个应用例子都是相对来说不是很难的,主要是先有一种感性的认识。
分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题,可以: 1) 把它分成两个或多个更小的问题;
2) 分别解决每个小问题;
3) 把各小问题的解答组合起来,即可得到原问题的解答。
小问题通常与原问题相似,可以递归地使用分而治之策略来解决。
中位数问题
问题的提出
对于两个长度均为n的已排序的序列,确定这两个序列的2n个元素的中位数
解决此问题的算法思想
设两个长度为n的数列分别为x[ 0 : n -1]和y[ 0 : n -1],分别找出这两个数列的中位数x[i]和
y[ j ],二者进行比较,根据比较结果可以在每个数列中减少一半的搜索范围,然后再分别取
两个子数列的中位数再比较,再减少搜索范围,继续下去直到找到最后结果
求解过程
查找范围确定:
-
当n为奇数时,令n=2m +1,则两个数列的中位数分别为x[ m ]和 y[ m ],则:
x[0:m-1]<x[m]<x[m+1:2m]和
y[0:m-1]<y[m]<y[m+1:2m]
若 x[m]<y[m]
若整体中位数x[k]在x[0:m-1]中,则
x[k]<x[m]<x[m+1:2m]且 x[k]<y[m]<y[m+1:2m]
则x[k]至少小于2m+2即n+1个数,而整体的中位数应该是第n个数,它小于n个数,所以整体中位数不在x的前半部分,同样不会在y的后半部分。
x[m]至少小于n个数,y[m]至少大于n个数,所以这两个局部中位数都有可能成为整体中位数.
所以再次查找范围为x[m:2m]和y[0:m]
-
当n为偶数时,令n=2m ,则两个数列的中位数分别为x[ m-1 ]和 y[ m-1 ],则:
x[0:m-2]<x[m-1]<x[m:2m-1]和
y[0:m-2]<y[m-1]<y[m:2m-1]
若 x[m-1]<y[m-1]
若整体中位数x[k]在x[0:m-2]中,则
x[k]<x[m-1]<x[m:2m-1]且 x[k]<y[m-1]<y[m:2m-1]
则x[k]至少小于2m+1即n+1个数,而整体的中位数应该是第n个数,它小于n个数,所以整体中位数不在x的前半部分,同样不会在y的后半部分。
x[m-1]至少小于n+1个数,所以其不会成为整体中位数,y[m-1]至少大于n-1个数,所以它有可能成为整体中位数
所以再次查找范围为x[m:2m-1]和y[0:m-2]
举个例子:
x={10, 15, 16, 19, 24}
y={11, 17, 18, 20, 23}
x1={16, 19, 24} y1= {11, 17, 18 }
x2={16,19} y2={17,18}
x2={19} y2={17} ————出口,应单独处理
x={10, 15, 16, 19}
y={11, 17, 18, 20}
x1={16, 19} y1= {11, 17}
x2={16} y2={17}
mid=16
数据输入
由文件input.txt提供输入数据。文件的第1行中有1个正整数n(n<=200),表示每个数组有n个数。接下来的两行分别是X,Y数组的元素。
输入文件示例
|
输出文件示例
|
input.txt
|
output.txt
|
3
5 15 18
3 14 21
|
14
|
C++实现:
#include<iostream>
#include<fstream>
usingnamespacestd;
intfindMedian(int*,int*,int);
intmain()
...{
ifstreamin("in.txt");
ofstreamout("d://out.txt");
intn;
int*x,*y;
in>>n;
x=newint[n];
y=newint[n];
for(inti=0;i<n;i++)
in>>x[i];
for(i=0;i<n;i++)
in>>y[i];
intmedian=findMedian(x,y,n);
cout<<median<<endl;
out<<median;
in.close();
out.close();
return1;
}
intfindMedian(int*x,int*y,intn)
...{
if(n==1)
return*x<=*y?*x:*y;
intm=(n-1)/2;//中位数位置
intp=m+1;//中位数小者子数字起始位置
if(n%2!=0)//n为奇数
p--;
if(*(x+m)==*(y+m))
return*(x+m);
elseif(*(x+m)(y+<*m))
returnfindMedian(x+p,y,m+1);
else
returnfindMedian(x,y+p,m+1);
}
Gray码问题
Gray码是一个长度为2n的序列。序列中无相同的元素,每个 元素长度都为n位的串,相邻元素恰好之有一位不同,对任意的n位如何构造相应的Gray码。
对于n=4的Gray码,如下图所。
上图 第1列从最左边算起
实现这个问题的方法是,递归上半部分,下半部分对称复制上半分部即可
由文件input.txt提供输入数据n。
用C++ 实现:
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<math.h>
usingnamespacestd;
voidGraycode(inta,intb,int**arr)
...{
//递归出口
if(a==1)
return;
//处理当前列
for(inti=0;i<a/2;i++)
...{
arr[i][b-1]=0;//上半部分赋值为0
arr[a-i-1][b-1]=1;//下半部分赋值为1
}
//处理子问题
Graycode(a/2,b-1,arr);//递归调用子问题,生成列数为b-1的Gray码,填写高半部分
for(intk=a/2;k<a;k++)//将(n-1)位的Gray码逆序后,填入目标码字/的低半部分
for(intj=0;j<b-1;j++)
arr[k][j]=arr[a-k-1][j];
}
intmain()
...{
intn;
ifstreamin("in.txt");
ofstreamout("d://out.txt");
in>>n;
introw=pow(2,n);
int**arr=newint*[row];
for(intm=0;m<row;m++)...{
arr[m]=newint[n];
}
Graycode(row,n,arr);
for(inti=0;i<row;i++)
...{
for(intj=0;j<n;j++)
cout<<arr[i][j];
cout<<endl;
}
in.close();
out.close();
return1;
}
零钱问题
设有n种不同面值的硬币,各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱,可以实用的各种面值的硬币个数不限。当只用硬币面值T[1],T[2],…,T[i]时,可找出钱数j的最少硬币个数记为C(i,j)。若只用这些硬币面值,找不出钱数j时,记C(i,j)=∞:<shapetype id="_x0000_t75" stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" o:preferrelative="t" o:spt="75" coordsize="21600,21600"></shapetype><shape id="_x0000_i1025" style="WIDTH: 415.5pt; HEIGHT: 231pt" type="#_x0000_t75"><imagedata src="file:///E:%5CDOCUME~1%5CADMINI~1%5CLOCALS~1%5CTemp%5Cmsohtml1%5C08%5Cclip_image001.jpg" o:title="666"></imagedata></shape>
<stroke joinstyle="miter"></stroke><formulas><f eqn="if lineDrawn pixelLineWidth 0"></f><f eqn="sum @0 1 0"></f><f eqn="sum 0 0 @1"></f><f eqn="prod @2 1 2"></f><f eqn="prod @3 21600 pixelWidth"></f><f eqn="prod @3 21600 pixelHeight"></f><f eqn="sum @0 0 1"></f><f eqn="prod @6 1 2"></f><f eqn="prod @7 21600 pixelWidth"></f><f eqn="sum @8 21600 0"></f><f eqn="prod @7 21600 pixelHeight"></f><f eqn="sum @10 21600 0"></f></formulas><lock aspectratio="t" v:ext="edit"></lock>
« 数据输入
由文件input.txt提供输入数据。文件的第1行中有1个正整数n(n<=13),表示有n种硬币可选。接下来的一行是每种硬币的面值。由用户输入待找钱数j。
使用C++语言实现
相关推荐
分治法-中位数 第一行: n,为x和y数组的元素个数 第二行: x数组的n个数,用空格分隔 第三行: y数组的n个数,用空格分隔
算法设计与分析中最大子段和问题的蛮力法、分治法和动态规划法
算法设计 蛮力法 分治法 动态规划 贪心算法 分支限界法 回溯法 近似算法 减制法
/*蛮力法 n^2 对于数组a[n],其连续的子段有 以a[0]开始的 , { a[0] }, { a[0],a[1] },{ a[0],a[1],a[2] }.....共n 个 以a[1]开始的, { a[1] }, { a[1],a[2] },{ a[1],a[2],a[3] }.....共n-1个 ... 以a[n]开始的,...
蛮力法、分治法和动态规划法设计最大子段和问题的算法,一、试分别利用蛮力法、分治法和动态规划法求解最大子段和问题,要求写出C/C++程序实现和算法的效率分析。程序运行结果要同时给出最大子段和的值以及由哪个子段...
递归与分治策略及其应用 一个求解Gray码的分治策略
蛮力法分治法动态规划法求最大子段和,已测试通过
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干子问题,先求解子问题,然后从这些子问题的解求得原问题的解。与分治法不同的是,适合于动态规划法求解的问题,经分解求得的子问题往往不是互相独立...
1.暴力算法 2.分治法 1.暴力算法 2.分治法 1.暴力算法 2.分治法 1.准确性分析 2.性能分析 1.分治法的设计思想是,将一个难以直接解决的大问题,
Gray码是一个长度为2的N次幂的序列,序列中无相同元素,每个元素都是长度为N位的(0,1)串,相邻元素恰好只有一位不同,用分置策略设计一个算法对任意的N构造相应的Gray码。
c语言分治法求众数重数-五大常见算法策略之——递归与分治策略,算法数据结构 五大常用算法
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 与分治法不同的是,适合于用动态规划法求解的问题,经分解得到的子问题往往不是独立...
动态规划法与分治法的区别 动态规划法与贪心法的区别 分枝限界法与回溯法的异同 等自己的总结
用动态规划法和分治法 自己写的 可以运行
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
2)格雷码问题。即利用分治法产生n位的格雷码,n由系统给出,n小于10.
最近对问题 最大子段和(分治法) 最长公共子序列问题 最大子段和(动态规划)
贪心算法和动态规划以及分治法的区别? (1) 贪心算法和动态规划.pdf
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
(1)设X[0:n-1]和Y[0:n-1]为两个数组,每个数组中含有n个已排好序的数,设计一个算法复杂度为O(logn)的分治算法,找出X和Y中2n个数中的中位数。(中位数:个数为奇数:中间位置上的数;个数为偶数,中间两个数的...