算法分析与设计方案实验研究报告Word文档格式.docx
《算法分析与设计方案实验研究报告Word文档格式.docx》由会员分享，可在线阅读，更多相关《算法分析与设计方案实验研究报告Word文档格式.docx（16页珍藏版）》请在冰点文库上搜索。
9elsemid←［（i+j）/2］
10REC-MAXMIN（i，mid，gmax，gmin）
11REC-MAXMIN（mid+1，j，hmax，hmin）
12fmax←max{gmax，hmax}
13fmin←min{gmin，hmin}
4、程序清单
#include<
iostream.h>
voidFZFa（inti,intj,int&
max,int&
min,inta[]）
{
if（i==j）
{
max=a[i]。
min=a[j]。
}
elseif（i==（j-1））
if（a[i]>
a[j]）
{
max=a[i]。
min=a[j]。
}
else
max=a[j]。
min=a[i]。
else
intmidd=（i+j）/2。
intmax1=0,min1=0,max2=0,min2=0。
FZFa（i,midd,max1,min1,a）。
FZFa（midd+1,j,max2,min2,a）。
if（max1>
max2）
max=max1。
max=max2。
if（min1<
min2）
min=min1。
min=min2。
}
intmain（）
intt[]={2,4}。
intmax,min。
FZFa（0,1,max,min,t）。
cout<
<
"
最大值：
max<
endl。
最小值：
min<
return0。
5、实验结果（可用文字描述和贴图等方式表现实验结果）
2
动态规划法实验
最长公共子序列
1、方法思想
动态规划算法与分治法类似，其基本思想也是将待求解问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适用于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。
在分治法求解时，有些子问题被重复计算了许多次。
如果能够保存已解决的子问题的答案，而再需要时再找出已求的答案，就可以避免大量重复计算，从而得到多项式时间算法。
为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案。
不过孩子问题以后是否被用到，只要它被计算过，就将其结果填入表中。
这就是动态规划的基本思想。
最长公共子序列为题：
给定两个序列X={x1,x2,x3……xm}和Y={y1,y2,y3……yn},找出X和Y的最长公共子序列。
LCSLENGTH（X,Y）
1m←length［X］
2n←length［Y］
3fori←1tom
4dol［i,0］←0
5forj←1ton
6dol［0,j］←0
7fori←1tom
8doforj←1ton
9doifxi=yj
10thenl［i,j］←l［i-1,j-1］+1
b［i,j］←1
12elseifl［i-1,j］←l［i,j-1］
13thenl［i,j］←l［i-1,j］
14b［i,j］←2
15elsel［i,j］←l［i,j-1］
16b［i,j］←3
17returnlandb
intlcsleng（charx[],chary[],inta[10][10],intn,intm）
intc[10][10]。
inti,j。
for（i=1。
i<
=m。
i++）
c[i][0]=0。
=n。
c[0][i]。
for（j=1。
j<
j++）
if（x[i]==y[j]）
{
c[i][j]=c[i-1][j-1]+1。
a[i][j]=1。
}
elseif（c[i-1][j]>
=c[i][j-1]）
c[i][j]=c[i-1][j]。
a[i][j]=2。
else
c[i][j]=c[i][j-1]。
a[i][j]=3。
returnc[n][m]。
voidlcs（inti,intj,charx[],inta[10][10]）
if（i==0||j==0）
return。
if（a[i][j]==1）
lcs（i-1,j-1,x,a）。
x[i]<
elseif（a[i][j]==2）
lcs（i-1,j,x,a）。
lcs（i,j-1,x,a）。
chara[]="
kagajsj"
。
charb[]="
asjofgo"
intt[10][10]。
intc=lcsleng（a,b,t,7,7）。
c<
lcs（7,7,a,t）。
5、实验结果
3
贪心法
活动选择问题
贪心算法总是做出再当前看来最好的选择，也就是说贪心算法并不是从整体最优考虑，它所做出的选择只是在某种意义上看的局部最优选择。
活动选择问题（activity-selectionproblem）即若干个具有竞争性的活动要求互斥使用某一公共资源，目标是选择最大的相容活动集合。
假定集合S={a1,a2,…,an}中含有n个希望使用某一资源的活动，这样的资源有教室、某一设备等，它们一次只能由一个活动使用。
每个活动ai有开始时间（starttime）si和完成时间（finishtime）fi，其中，0≤si<
fi<
∞。
如果某个活动ai被选中使用资源，则该活动在半开区间（si，fi］这段时间占据资源。
如果活动ai和aj在时间区间（si，fi］和（sj，fj］上不重叠，则称它们是相容的（compatible），即如果si≥fj或者sj≥fj，活动ai和aj是相容的。
活动选择问题是选择最大的相容活动集合。
RECUR-ACTIVITY-SELECT（s,f,i,j）
1m←i+1
2whilem<
jandsm<
fi//找Sij中第一个活动
3dom←m+1
4ifm<
j//找到满足条件的活动m
5thenreturn{am}∪RECUR-ACTIVITY-SELECT（s,f,m,j）
//将m加入集合
6elsereturn￠
intrecuractivityselect（ints[],intf[],inti,intj）
intm=i+1,k=0。
while（m<
j&
&
s[m]<
f[i]）
m=m+1。
if（m<
j）
cout<
m<
"
k=1+recuractivityselect（s,f,m,j）。
returnk。
intbudigui（ints[],intf[],intk[],intn）
k[1]=1。
inti=1,m,t=2,w=1。
for（m=2。
n。
m++）
if（s[m]>
=f[i]）
k[t]=m。
t++。
w++。
i=m。
returnw。
inta[]={0,1,2,3,4,5,6,7,8,9,10,11}。
intp[]={0,1,2,0,5,3,5,6,8,8,2,12}。
intq[]={0,4,5,6,7,8,9,10,11,12,13,14}。
intt[12]={0}。
inti,f。
活动名称"
for（i=0。
11。
a[i]<
活动开始时间"
p[i]<
活动结束时间"
q[i]<
最大相容活动序列是:
f=recuractivityselect（p,q,0,12）。
安排活动个数:
f<
f=budigui（p,q,t,12）。
/*for（i=0。
12。
t[i]<
*/
4
回溯法---
n皇后问题
回溯法是一个既带有系统性又带有跳跃性的搜索算法。
它在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。
算法搜索至解空间树的任何一结点时，先判断该结点是否包含问题的解。
如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；
否则进入该子树，继续按深度优先策略搜索。
我们给棋盘上的行和列从1到8编号，同时也给皇后从1到8编号。
由于每一个皇后应放在不同的行上，不失一般性，假设皇后i放在第i行上，因此8皇后问题可以表示成8元组（x1,x2,…,x8），其中xi（i=1,2,…,8）表示皇后i所放置的列号。
这种表示法的显式约束条件是Si={1,2,3,4,5,6,7,8}，i=1,2,…,8。
在这种情况下，解空间为88个8元组组成，而隐式约束条件是没有两个xi相同（即所有皇后必须在不同列上），且满足不存在两个皇后在同一条对角线上。
加上隐式约束条件，问题的解空间可进一步减小。
此时，解空间大小为8!
，因为所有解都是8元组的一个置换。
图5-4表示了8皇后问题的一个解。
N-QUEEN（n）
1x1←0//第1个皇后的列位置初始化
2k←1//当前行
3whilek>
0do
4x［k］←x［k］+1
//到下一列
5whilex［k］≤n&
notPLACE（k）do
6x［k］←x［k］+1
7ifx［k］≤n
//找到一个位置
8thenifk=n
//测试是否为问题的解
9thenoutput（X）
//输出解
10elsek←k+1
//转下一行，即给下一个皇后找位置
11x［k］←0
//初始化当前皇后列取值
12elsek←k-1
//回溯
13return
PLACE（k）
1i←1
2whilei<
kdo
3if（x［i］=x［k］orabs（x［i］-x［k］）=abs（i-k）
//同一列或同一对角线有两个皇后
4thenreturn（false）
5i←i+1
6return（true）
math.h>
boolplace（intk,intx[]）
intj。
for（j=1。
k。
if（（abs（k-j）==abs（x[j]-x[k]））||（x[j]==x[k]））
returnfalse。
returntrue。
voidbacktrack（intx[],int&
sum,intn）
x[1]=0。
intk=1。
while（k>
0）{
x[k]+=1。
while（（x[k]<
=n）&
（!
place（k,x）））
x[k]+=1。
if（x[k]<
=n）
if（k==n）
for（inti=1。
{
for（intj=1。
{
if（j==x[i]）
cout<
○"
else
□"
}
cout<
}
sum++。
else{
k++。
x[k]=0。
elsek--。
intn=4,m,i,sum=0。
intx[5]。
x[i]=0。
backtrack（x,sum,n）。
sum<
升级会员 