计算机软件程序算法论文.docx
《计算机软件程序算法论文.docx》由会员分享，可在线阅读，更多相关《计算机软件程序算法论文.docx（35页珍藏版）》请在冰点文库上搜索。
计算机软件程序算法论文
《算法设计与分析》
上机实验报告
专业：
计算机科学与技术
班级：
软件07-4班
姓名：
22号
学号：
XX
说明
算法设计与分析上机实验是充分掌握理论知识的重要环节，也是锻炼实际操作能力的重要过程和手段，因此，对学生上机实验有以下几点要求：
1、上机前做好充分的预习和准备，认真复习每章重点内容，熟悉所使用的硬件和软件环境。
2、实验前，预习好每次实验内容并预先给出相应的结果和算法，以达到上机检验的目的。
3、注意调试过程及运行结果，不断积累程序编写和程序调试经验。
4、实验结束后，认真完成每次实验报告，包括程序书写格式和结果的正确性。
另外，上机实验成绩的给定主要包括三部分，即上机实验课的出勤，实验的完成情况和实验报告的总结书写情况。
序号
实验题目
成绩
批阅教师签字
1
实验一递归与分治之归并排序和快速排序问题
2
实验二动态规划之多段图问题
3
实验三动态规划之矩阵连乘问题和最长公共子序列问题
4
实验四贪心法之单源最短路径问题
5
实验五回溯法之N皇后问题和图的m着色问题
总成绩
实验一递归与分治之归并排序和快速排序问题
上机实验日期：
2010-3-26上机指导教师：
刘文强
一、实验目的
1．掌握递归与分治策略的基本思想；
2．掌握用递归与分治策略来设计算法的基本方法和步骤；
3．学会使用递归与分治策略来解决一些实际问题；
4．进一步加强分析问题、解决问题的能力；
二、实验要求
1．实验前做好充分准备，事先预习好本次实验内容。
2．实验时记录实验结果，按要求完成实验内容。
3．实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。
三、实验原理
1．递归与分治策略的基本思想
将一个复杂问题分解成若干较小问题进行求解是一个好主意。
可以将一个难以求解的复杂问题分解成若干较小规模、相互独立，但类型相同的子问题，然后求解这些子问题；如果子问题还比较复杂而不能直接求解，还可以继续细分，直到子问题足够小，能够直接求解为止；此外，为了得到原始问题的解，必须找到一种途径能将各子问题的解组合正原始问题的一个完整答案，这种问题求解策略称为分治法。
分治法顾名思义就是分而治之。
一个问题能够用分治法求解的要素是：
第一，问题能够按照某种方式分解成若干个规模较小、相互独立且与原问题类型相同的子问题；
第二，子问题足够小时可以直接求解；
第三，能够将子问题的解组合成原问题的解；
由于分治法要求分解成同类子问题，并允许不断分解，使问题规模不断减小，最终可用已知的方法求解足够小的问题，因此，分治法求解很自然导致一个递归算法。
2．分治法的算法设计模式
divide-and-conquer（p）
{
if（|p|<=n0）
adhoc（p）;
dividepintosmallersubinstancesp1,p2,…pk;
for（i=1;i<=k;i++）
yi=divide-and-conquer（pi）;
returnmerge（y1,y2,…yk）;
}
其中|p|表示问题p的规模。
n0为一阈值，表示当问题p的规模不超过n0时，问题已容易解出，不必再继续分解。
adhoc（p）是该分治法中的基本子算法，用于直接解小规模的问题p。
当问题p的规模不超过n0时，直接用算法adhoc（p）求解。
算法merge（y1,y2,…yk）是该分治法中的合并子算法，用于将p的子问题p1,p2,…pk的解y1,y2,…yk合并为p的解。
四、实验内容
1．请编程实现找最大最小元素问题的分治算法
算法如下：
voidMaxMin（inti,intj,intmax,intmin）
{if（i==j）max=min=a[i];
elseif（i==j-1）
{if（a[i]>a[j]）
{max=a[i];min=a[j];}
else
{max=a[j];min=a[i];}
}
else
{intmid=（i+j）/2;intmax1,min1;
MaxMin（i,mid,max,min）;
MaxMin（mid+1,j,max1,min1）;
if（maxmax=max1;
if（min>min1）
min=min1;
}
请给出实现该算法的主程序和输入输出数据。
●主程序
voidmain（）
{intn,max,min;
scanf（"%d",&n）;
for（inti=1;i<=n;i++）
scanf（"%d",&a[i]）;
MaxMin（1,n,max,min）;
printf（"MAX：
%d\n",max）;
printf（"MIN：
%d\n",min）;
}
●输入与输出
2．请编程实现归并排序算法
算法如下：
voidmerge（intlow，intmid，inthigh）
{inth=low,i=low,j=mid+1,k;
while（（h<=mid）&&（j<=high））
{if（a[h]<=a[j]）
{b[i]=a[h];h++;}
else
{b[i]=a[j];j++;}
i++;}
if（h>mid）
for（k=j;k<=high;k++）
{b[i]=a[k];i++;}
else
for（k=h;k<=mid;k++）
{b[i]=a[k];i++;}
for（k=low;k<=high;k++）
a[k]=b[k];
}
voidmergesort（intlow，inthigh）
{
if（low{
intmid=（low+high）/2;
mergesort（low,mid）;
mergesort（mid+1,high）;
merge（low,mid,high）;
}
}
请给出实现该算法的主程序和输入输出数据。
●主程序
intmain（）
{
intn,i;
while（scanf（"%d",&n））
{
for（i=0;iscanf（"%d",&a[i]）;
mergesort（0,n-1）;
for（i=0;iprintf（"%d",a[i]）;
printf（"\n"）;
}
return0;
}
●输入与输出
3．请编程实现快速排序算法
算法如下：
intpartition（inta[],intm,intp）
{
intt=a[m],i=m,j=p,x;
do{
doi++;
while（a[i]doj--;
while（a[j]>t）;
if（i}while（ia[m]=a[j];
a[j]=t;
returnj;
}
voidquicksort（intp，intq）
{
if（p{
intj=partition（a,p,q+1）;
quicksort（p,j-1）;
quicksort（j+1,q）;
}
}
请给出实现该算法的主程序和输入输出数据。
●主程序
intmain（）
{
inta[100],i;
while（scanf（"%d",a））
{
for（i=1;i<=a[0];i++）
scanf（"%d",&a[i]）;
qsort（a,1,a[0]）;
for（i=1;i<=a[0];i++）
printf（"%d",a[i]）;
printf（"\n"）;
}
}
●输入与输出
五、实验记事与总结
本次实验中，我了解了递归和分治两种方法的区别及其优劣性；递归与分治算法就像一对孪生兄弟。
分治法是由于要解决的问题较为复杂，显示出N的特性，于是采取一种分治的办法，将其难度逐步降低，降成能容易解决的程序。
而解决之。
如果可以将问题分治成K个相同的小问题。
那么就可以使用递归的办法。
递归就是直接或者间接调用自身的算法。
递归优点：
结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。
缺点：
递归算法的运行效率较低，无论是耗费计算时间还是占用的存储空间都比非递归算法要多。
六、实验成绩
实验二动态规划之多段图问题
上机实验日期：
2010-4-2上机指导教师：
刘文强
一、实验目的
1．掌握动态规划的基本思想；
2．掌握用动态规划方法来设计算法的基本方法和步骤；
3．学会使用动态规划策略来解决一些实际问题；
4．进一步加强分析问题、解决问题的能力；
5.注意区分动态规划方法与分治法的主要区别。
二、实验要求
1．实验前做好充分准备，事先预习好本次实验内容。
2．实验时记录实验结果，按要求完成实验内容。
3．实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。
三、实验原理
1．动态规划的基本思想
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是适合于用动态规划法求解的问题，经分解得道的子问题往往不是相互独立的。
在用分治法求解时，有些子问题被重复计算了许多次。
如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量的重复计算。
为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案。
不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。
这就是动态规划的基本思想，具体的动态规划算法是多种多样的，但它们具有相同的填表格式。
2.动态规划算法的设计步骤
动态规划算法适用于解最优化问题，通常可以按以下步骤设计动态规划算法：
（1）找出最优解的性质，并刻画其结构特征；
（2）递归的定义最优值；
（3）以自底向上的方式计算出最优值；
（4）根据计算最优值时得到的信息，构造最优解。
步骤
（1）-（3）是动态规划算法的基本步骤。
在只需要求出最优值时的情形，步骤（4）可以省略。
若需要求出问题的最优解，则必须执行步骤（4）。
此时，在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速构造出最优解。
四、实验内容
1．请编程实现基于邻接矩阵存储结构所描述的多段图算法
要求调用该算法求出下面所示的多段图中从顶点1（即源点）到顶点12（即汇点）的最短路径长度，并输出这条最短路径。
该多段图的邻接矩阵如下所示。
采用邻接矩阵存储结构所描述的多段图的动态规划算法如下：
#definemax999
intcost[101],path[101],route[101];
intg[101][101];
intmultigraph（intk,intn）
{inti,j;
for（i=1;i<=n;i++）
{cost[i]=max;
path[i]=-1;}
for（i=1;i<=k;i++）
route[i]=0;
cost[n]=0;
for（i=n-1;i>=1;i--）
for（j=1;j<=n;j++）
if（g[i][j]{cost[i]=g[i][j]+cost[j];
path[i]=j;}
route[1]=1;
route[k]=n;
for（j=2;j<=k-1;j++）
route[j]=path[route[j-1]];
returncost[1];
}
请给出实现该算法的主程序和输入输出数据。
●主程序
intmain（）
{
intn,k,result,i;
while（scanf（"%d%d",&n,&k）!
=EOF）
{
for（i=1;i<=n;i++）
for（intj=1;j<=n;j++）
scanf（"%d",&g[i][j]）;
result=multigraph（k,n）;
printf（"%d\n",result）;
for（i=1;iprintf（"%d->",route[i]）;
printf（"%d\n",route[k]）;
}
return0;
}
●输入与输出
2．请编程实现基于邻接表存储结构所描述的多段图算法
仍以前面所给的那个5段图为具体实例。
（1）多段图的邻接表类型定义
structarcnode
{intadjvex;
intw;
structarcnode*nextarc;
};
structvnode
{intdata;
structarcnode*firstarc;
};
typedefstruct
{structvnodevertices[101];
intvexnum,arcnum,k;
}ALGraph;
（2）多段图的创建算法
#include
voidcreategraph（ALGraph&G）
{inti,j,u,v,x;
structarcnode*p;
printf（“pleaseinputvexnumandarcnumandk:
”）;
scanf（“%d%d%d”,&G.vexnum,&G.arcnum,&G.k）;
for（i=1;i<=G.vexnum;i++）
{G.vertices[i].data=i;
G.vertices[i].firstarc=NULL;}
for（j=1;j<=G.arcnum;j++）
{printf（“请输入第%d条边的两个顶点及其边上的权值:
”,j）;
scanf（“%d%d%d”,&u,&v,&x）;
p=（structarcnode*）malloc（sizeof（structarcnode））;
p->adjvex=v;
p->w=x;
p->nextarc=G.vertices[u].firstarc;
G.vertices[u].firstarc=p;
}
（3）基于邻接表存储结构描述的多段图算法
#definemax999
intcost[101],path[101],routep[101];
intmultigragh（ALGraphG）
{inti,j;
structarcnode*p;
for（i=1;i<=G.vexnum;i++）
{cost[i]=max;path[i]=-1;}
for（j=1;j<=G.k;j++）
route[j]=0;
cost[G.vexnum]=0;
for（i=G.vexnum-1;i>=1;i--）
{p=G.vertices[i].firstarc;
while（p!
=null）
{if（p->w+cost[p->adjvex]{cost[i]=p->w+cost[p->adjvex];
path[i]=p->adjvex;}
p=p->nextarc;
}
}
route[1]=1;
route[G.k]=n;
for（j=2;j<=G.k-1;j++）
route[j]=path[route[j-1]];
returncost[1];
}
请给出实现该算法的主程序和输入输出数据。
●主程序
intmain（）
{
intresult,i;
ALGraphg;
creategraph（g）;
result=multigragh（g）;
printf（"%d\n",result）;
for（i=1;iprintf（"%d->",route[i]）;
printf（"%d\n",route[g.k]）;
return0;
}
●输入与输出
五、实验记事与总结
在本次实验中，让我了解了一个新的思想，那就是动态规划。
动态规划适用于解那些可以被划分为多个子问题且子问题不是独立的情况的问题，更确切的说动态规划所解的问题的各子问题包含公共子问题（重叠子问题）。
多段图问题也了解了一些原理：
从终点n开始，直到顶点1，对每个点：
遍历其所能达到的各个结点，判断通过该结点访问终点的路径是否小于当前能找到的最短距离，是则更新，否则不变。
最后，顶点1找到的最短距离必然是该点到达终点n的最短距离。
六、实验成绩
实验三动态规划之矩阵连乘问题和最长公共子序列问题
上机实验日期：
2010-4-9上机指导教师：
刘文强
一、实验目的
1．掌握动态规划的基本思想；
2．深刻掌握动态规划法来设计算法的思想并能熟练运用；
3．进一步加强使用动态规划策略来解决一些实际问题的能力；
4．进一步加强分析问题、解决问题的能力；
5.进一步区分动态规划算法与分治法的主要区别
二、实验要求
1．实验前做好充分准备，事先预习好本次实验内容。
2．实验时记录实验结果，按要求完成实验内容。
3．实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。
三、实验原理
1．动态规划的基本思想
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是适合于用动态规划法求解的问题，经分解得道的子问题往往不是相互独立的。
在用分治法求解时，有些子问题被重复计算了许多次。
如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量的重复计算。
为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案。
不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。
这就是动态规划的基本思想，具体的动态规划算法是多种多样的，但它们具有相同的填表格式。
2.动态规划算法的设计步骤
动态规划算法适用于解最优化问题，通常可以按以下步骤设计动态规划算法：
（1）找出最优解的性质，并刻画其结构特征；
（2）递归的定义最优值；
（3）以自底向上的方式计算出最优值；
（4）根据计算最优值时得到的信息，构造最优解。
步骤
（1）-（3）是动态规划算法的基本步骤。
在只需要求出最优值时的情形，步骤（4）可以省略。
若需要求出问题的最优解，则必须执行步骤（4）。
此时，在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速构造出最优解。
四、实验内容
1．请编程实现求解矩阵连乘问题最优值的动态规划算法
算法如下：
intn;
intp[100],m[100][100],s[100][100];
voidMatrixChain（）
{for（inti=1;i<=n;i++）
m[i][i]=0;
for（intr=2;r<=n;r++）
for（inti=1;i<=n-r+1;i++）
{intj=i+r-1;
m[i][j]=m[i+1][j]+p[i]*p[i+1]*p[j+1];
s[i][j]=i;
for（intk=i+1;k{intt=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];
if（t{m[i][j]=t;
s[i][j]=k;}
}
}
}
在上述算法中，数组p用来存放n个矩阵的n+1个不同的维数。
请给出实现该算法的主程序和输入输出数据。
●主程序
intmain（）
{
while（scanf（"%d",&n）!
=EOF）
{
for（inti=1;i<=n+1;i++）
scanf（"%d",&p[i]）;
MatrixChain（）;
printf（"%d\n",m[1][n]）;
}
}
●输入与输出
2．请编程实现求解最长公共子序列问题最优值的动态规划算法
算法如下：
charx[100],y[100];
intc[100][100],b[100][100];
voidLCSLength（intm,intn）
{
inti,j;
for（i=0;ifor（i=0;ifor（i=0;ifor（j=0;j{if（x[i]==y[j]）
{c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;}
elseif（c[i-1][j]>=c[i][j-1]）
{c[i][j]=c[i-1][j];
b[i][j]=2;}
else{c[i][j]=c[i][j-1];
b[i][j]=3;}
}
}
请给出实现该算法的主程序和输入输出数据。
●主程序
intmain（）
{
while（scanf（"%s%s",x,y）!
=EOF）
{
LCSLength（strlen（x）,strlen（y））;
printf（"%d\n",c[strlen（x）-1][strlen（y）-1]）;
}
}
●输入与输出
●
五、实验记事与总结
在本次实验中，又一次接触了动态规划，并对它更深一层的进行了了解。
在运用动态规划解问题时,总是假设已经可以以一种方式最优划分子问题（当然并不能立刻得到这种划分方式,而是通过递归的回传而得到）.正是有了最优子结构以及重叠子问题,才使得动态规划在解此类问题时往往有着无与伦比的优越性.当然动态规划是一种思想,而不是具体某个算法,所以在运用时通常不可能写一个程序而放之四海皆准（正如比快速排序算法可以排序一切可比较数列,而矩阵连乘算法则只能用于解矩阵连乘问题）.而且由于动态规划使用的是自底向上的,不太符合我们的正常的思维次序,所以算法通常会比运用其它算法（如分治算法、贪心算法）解同等问题更加难以理解。
最长公共子序列问题的关键在于确定谁是公共子序列。
并且在检查过程中找出最长的公共子序列。
六、实验成绩
实验四贪心法之单源最短路径问题
上机实验日期：
2010-4-16上机指导教师：
刘文强
一、实
升级会员 