算法设计与分析实验报告Word文档下载推荐.docx
《算法设计与分析实验报告Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《算法设计与分析实验报告Word文档下载推荐.docx（25页珍藏版）》请在冰点文库上搜索。
inti;
for（i=1;
t;
m=m*10;
a[t]=t*m;
}
intzero=1;
l;
{zero*=10;
}//求出输入数为10的n次方
intyushu=n%zero;
//求出最高位以后的数
intzuigao=n/zero;
//求出最高位zuigao
for（i=0;
zuigao;
{s[i]+=zero;
}//求出0~zuigao-1位的数的出现次数
10;
{s[i]+=zuigao*a[l];
}//求出与余数位数相同的0~zuigao-1位中0~9出现的次数
//如果余数是0,则程序可结束,不为0则补上所缺的0数,和最高位对应所缺的数
if（yushu==0）//补上所缺的0数,并且最高位加1
{s[zuigao]++;
s[0]+=l;
else
{i=0;
while（（zero/=10）>
yushu）
{i++;
s[0]+=i*（yushu+1）;
//补回因作模操作丢失的0
s[zuigao]+=（yushu+1）;
//补回最高位丢失的数目
sum（yushu,l-i-1,m+1）;
//处理余位数
}}
voidmain（）
{inti,m,n,N,l;
cout<
<
"
输入数字要查询的数字:
;
cin>
>
N;
'
\n'
n=N;
n>
=10;
{n/=10;
}//求出N的位数n-1
l=i;
sum（N,l,1）;
i<
{cout<
"
数字"
出现了:
s[i]<
次"
}}
五.程序调试中的问题
调试过程，页码出现报错。
六.实验结果
算法设计与分析实验报告二
实验名称分治法实现归并排序算法评分
实验日期2012年11月26日指导教师刘长松
姓名专业班级学号
1.了解用分治法求解的问题：
当要求解一个输入规模为n，且n的取值相当大的问题时，
如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1<
k≤n，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。
那末，对于这类问题分治法是十分有效的。
2.掌握分治法的一般控制流程。
DanC（p,q）
globaln，A[1:
n];
integerm,p,q;
//1pqn
ifSmall（p,q）thenreturnG（p,q）;
elsem=Divide（p,q）;
//pm<
q
returnCombine（DanC（p,m）,DanC（m+1,q））;
endif
endDanC
3．实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。
1.编程实现归并排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。
2.输入10组相同的数据，验证排序结果和完成排序的比较次数。
3.与复杂性函数所计算的比较次数比较。
4.用表格列出比较结果。
5.给出文字分析。
1.归并排序算法
procedureMERGESORT（low，high）
//A（low；
high）是一个全程数组，它含
有high-low+1≥0个待排序的元素//
integerlow，high；
iflow<
high；
thenmid←，//求这个集合的分割点//
callMERGESORT（low，mid）//将一个子集合排序//
callMERGESORT（mid+1，high）//将另一个子集合排序
callMERGE（low，mid，high）//归并两个已排序的子集合//
endMERGESORT
归并两个已排序的集合
procedureMERGE（low，mid，high）
//A（low：
high）是一个全程数组//
//辅助数组B（low；
high）//
integerh，i，j，k；
h←low；
i←low；
j←mid+1；
whileh≤midandj≤highdo//当两个集合都没取尽时//
ifA（h）≤A（j）thenB（i）←A（h）；
h←h+1
elseB（i）←A（j）；
j←j+1
i←i+1
repeat
ifh>
midthen
fork←jtohighdo//处理剩余的元素//
B（i）←A（k）；
i←i+1
elsefork←htomiddo
将已归并的集合复制到A
endMERGE
2.快速排序算法
QuickSort（p,q）
//将数组A[1:
n]中的元素
A[p],A[p+1],,A[q]按不降次序排列，
并假定A[n+1]是一个确定的、且大于
A[1:
n]中所有的数。
//
intp,q;
globaln,A[1:
ifp<
qthen
j=Partition（p,q+1）;
//划分后j成为划分元素的位置
QuickSort（p,j-1）;
QuickSort（j+1,q）;
endQuickSort
procedurePARTITION（m，p）
//退出过程时，p带着划分元素所在的下标位置。
integerm，p，i；
globalA（m：
p-1）
v←A（m）；
i←m//A（m）是划分元素//
loop
loopi←i+1untilA（i）≥vrepeat//i由左向右移//
loopp←p-1untilA（p）≤vrepeat//p由右向左移//
ifi<
p
thencallINTERCHANGE（A（i），A（p））//A（i）和A（p）换位//
elseexit
A（m）←A（p）；
A（p）←v//划分元素在位置p//
EndPARTITION
1.归并排序
iomanip.h>
stdlib.h>
time.h>
#defineM11
typedefintKeyType;
typedefintElemType;
structrec{
KeyTypekey;
ElemTypedata;
};
typedefrecsqlist[M];
classguibing{
public:
guibing（sqlistb）
{for（inti=0;
M;
r[i]=b[i];
voidoutput（sqlistr,intn）
n;
cout<
setw（4）<
r[i].key;
cout<
endl;
}
voidxuanze（sqlistb,intm,intn）
{inti,j,k;
for（i=m;
n-1;
{k=i;
for（j=i;
j<
j++）
if（b[k].key>
b[j].key）k=j;
if（k!
=i）
{rectemp=b[k];
b[k]=b[i];
b[i]=temp;
}
}}
voidmerge（intl,intm,inth,sqlistr2）
{xuanze（r,l,m）;
xuanze（r,m,h）;
output（r,M）;
inti,j,k;
k=i=l;
for（j=m;
m&
&
h;
k++）
{if（r[i].key<
=r[j].key）
{r2[k]=r[i];
i++;
}
else
{r2[k]=r[j];
j++;
output（r2,M）;
}
while（j<
h）
{r2[k]=r[j];
j++;
k++;
while（i<
=m）
{r2[k]=r[i];
i++;
output（r2,M）;
private:
sqlistr;
voidmain（）
guibingfa1运行结果:
\n"
sqlista,b;
inti,j=0,k=M/2,n=M;
srand（time（0））;
for（i=0;
{a[i].key=rand（）%80;
b[i].key=0;
guibinggx（a）;
cout<
排序前数组:
gx.output（a,M）;
数组排序过程演示:
gx.merge（j,k,n,b）;
排序后数组:
gx.output（b,M）;
cin.get（）;
2.快速排序
#defineMAXI10
typedefrecsqlist[MAXI];
classkuaisu
{public:
kuaisu（sqlista,intm）:
n（m）
{for（inti=0;
i++）b[i]=a[i];
voidquicksort（ints,intt）
{inti;
if（s<
t）{
i=part（s,t）;
quicksort（s,i-1）;
quicksort（i+1,t）;
elsereturn;
intpart（ints,intt）
{inti,j;
recp;
i=s;
j=t;
p=b[s];
while（i<
j）
{while（i<
j&
b[j].key>
=p.key）j--;
b[i]=b[j];
b[i].key<
=p.key）i++;
b[j]=b[i];
b[i]=p;
output（）;
returni;
voidoutput（）
b[i].key;
sqlistb;
intn;
};
{cout<
kuaisu1.cpp运行结果:
sqlista1;
inti,n=MAXI,low=0,high=9;
srand（time（0））;
a1[i].key=rand（）%80;
kuaisupx（a1,n）;
cout<
px.quicksort（low,high）;
px.output（）;
cin.get（）;
调试过程中，在排序方面有问题。
算法设计与分析实验报告三
实验名称动态规划算法实现多段图的最短路径问题评分
1.理解最优子结构的问题
有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程如何达到这种状态的方式无关。
最优子结构性质：
原问题的最优解包含了其子问题的最优解。
子问题重叠性质：
每次产生的子问题并不总是新问题，有些子问题被反复计算多次。
问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。
2.理解分段决策Bellman方程。
每一点最优都是上一点最优加上这段长度。
即当前最优只与上一步有关。
Us初始值，uj第j段的最优值。
3.一般方法
1）找出最优解的性质，并刻画其结构特征；
2）递归地定义最优值（写出动态规划方程）；
3）以自底向上的方式计算出最优值；
4）根据计算最优值时得到的信息，构造一个最优解。
1.编程实现多段图的最短路径问题的动态规划算法。
2.图的数据结构采用邻接表。
3.要求用文件装入5个多段图数据，编写从文件到邻接表的函数。
4.验证算法的时间复杂性。
多段图算法：
ProcedureFGRAPH（E,k,n,P）
//输入是按段的顺序给结点编号的，有n个结点的k段图。
E是边集，c（i，j）是边<
i，j>
的成本。
P（1：
k）是最小成本路径。
realCOST（n）,integer（n-1）,P（k）,r,j,k,n
COST（n）<
-0
forj<
-n-1to1by-1do//计算COST（j）//
设r是一个这样的结点，（j，r）
E且使c（j，r）+COST（r）取最小值
COST（j）<
-c（j，r）+COST（r）;
D（j）<
-r;
Repeat//向前对j-1进行决策//
P
（1）<
-1;
P（k）<
-n;
-2tok-1do//找路径上的第j个节点//
P（j）<
-D（P（j-1））;
repeat;
endFGRAPH
#include<
stdio.h>
conio.h>
#defineMAX100
#definen12/*顶点数*/
#definek5/*段数*/
intc[n][n];
voidinit（intcost[]）//初始化图
{inti,j;
13;
{for（j=0;
{c[i][j]=MAX;
}}
c[1][2]=9;
c[1][3]=7;
c[1][4]=3;
c[1][5]=2;
c[2][6]=4;
c[2][7]=2;
c[2][8]=1;
c[3][6]=2;
c[3][7]=7;
c[4][8]=11;
c[5][7]=11;
c[5][8]=8;
c[6][9]=6;
c[6][10]=5;
c[7][9]=4;
c[7][10]=3;
c[8][10]=5;
c[8][11]=6;
c[9][12]=4;
c[10][12]=2;
c[11][12]=5;
voidfgraph（intcost[],intpath[],intd[]）//使用向前递推算法求多段图的最短路径
{intr,j,temp,min;
for（j=0;
cost[j]=0;
for（j=n-1;
j>
=1;
j--）
{temp=0;
min=c[j][temp]+cost[temp];
//初始化最小值
for（r=0;
r<
r++）
{if（c[j][r]!
=MAX）
{if（（c[j][r]+cost[r]）<
min）//找到最小的r
{min=c[j][r]+cost[r];
temp=r;
}}
cost[j]=c[j][temp]+cost[temp];
d[j]=temp;
path[1]=1;
path[k]=n;
for（j=2;
k;
path[j]=d[path[j-1]];
voidbgraph（intbcost[],intpath1[],intd[]）//使用向后递推算法求多段图的最短路径
bcost[j]=0;
{temp=12;
min=c[temp][j]+bcost[temp];
{if（c[r][j]!
{if（（c[r][j]+bcost[r]）<
{min=c[r][j]+bcost[r];
}}}
bcost[j]=c[temp][j]+bcost[temp];
path1[1]=1;
path1[k]=n;
for（inti=4;
i>
=2;
i--）
{path1[i]=d[path1[i+1]];
{intcur=-1;
intcost[13],d[12],bcost[13];
intpath[k];
intpath1[k];
\t\t\t动态规划解多段图问题"
\n\n"
init（cost）;
fgraph（cost,path,d）;
输出使用向前递推算法后的最短路径:
for（inti=1;
=5;
path[i]<
endl<
最短路径为长度:
cost[1]<
\n输出使用向后递推算法后的最短路径:
bgraph（bcost,path1,d）;
for（i=1;
path1[i]<
bcost[12]<
动态规划的思想很容易理解，但当用程序代码实现起来的时候又觉得有点困难，经过我反复的调试操作，发现对于邻接表的程序表达不是很好。
算法设计与分析实验报告四
实验名称贪心算法实现背包问题评分
1.优化问题
有n个输入，而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组
成，而把满足约束条件的子集称为该问题的可行解。
可行解一般来说是不唯一的。
那些使目标函数取极值（极大或极小）的可行解，称为最优解。
2.贪心法求优化问题
算法思想：
在贪心算法中采用逐步构造最优解的方法。
在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。
决策一旦作出，就不可再更改。
作出贪心决策的依据称为贪心准则（greedycriterion）。
1）根据题意，选取一种量度标准。
2）按这种量度标准对这n个输入排序
3）依次选择输入量加入部分解中。
如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。
procedureGREEDY（A，n）/*贪心法一般控制流程*/
//A（1：
n）包含n个输入//
solutions←φ//将解向量solution初始化为空／
fori←1tondo
x←SELECT（A）
ifFEASIBLE（solution，x）
thensolutions←UNION（solution，x）
return（solution）
endGREEDY
4.实现典型的贪心算法的编程与上机实验，验证算法的时间复杂性函数。
1.编程实现背包问题贪心算
升级会员 