算法分析大作业Word文件下载.docx
《算法分析大作业Word文件下载.docx》由会员分享，可在线阅读，更多相关《算法分析大作业Word文件下载.docx（19页珍藏版）》请在冰点文库上搜索。
ki到j
result[i][n][a]。
中的某一个字符，于
k从
i
到
j
：
result[i][j][a]+=result[i][k][a]*result[k+1][j][c]+result[i][k][b]*result[k+1][j][c]+result[i][k][c]*result[k+1][j][a];
result[i][j][b]+=result[i][k][a]*result[k+1][j][a]+result[i][k][a]*result[k+1][j][b]+result[i][k][b]*result[k+1][j][b];
result[i][j][c]+=result[i][k][b]*result[k+1][j][a]+result[i][k][c]*result[k+1][j][b]+result[i][k][c]*result[k+1][j][c];
输入：
输入一个以a,b,c组成的任意一个字符串。
输出：
计算出的加括号方式数。
1.3设计方法
乘法表问题直观理解就是通过加括号使得最终运算结果为a，该问题与矩阵连乘问题类似，矩阵连乘是每一次加括号选择运算量最小的，写成数学表达式有：
而乘法表问题那么是计算所有加括号运算结果为
a的情况数，并不要求输
出加括号方式。
那么可以从乘法的最小单元两个符号相乘的所有可能开始，
接着在两个符号相乘的根底上计算三个符号相乘的所有可能。
直到计算N长
度的符号1-N的所有可能。
可以定义一个三维数组
a[n][n][3],n
为输入字
符串的长度，a[i][j][0]
为从字符串中第i个元素到第j个元素的子串表达
式值为a的加括号方式数，a[i][j][1]
为从字符串中第i个元素到第j
个元
素的子串表达式值为b的加括号方式数，a[i][j][2]
为从字符串中第i
素到第j个元素的子串表达式值为
c的加括号方式数。
由乘法表的定义那么可知啊a[i][j][0]=
〔对k求和，k从i
到j-1
〕a[i][k]
[0]*a[i][k+1][2]+a[i][k][1]*a[i][k+1][2]+a[i][k][2]*a[i][k+1]
[1];
同理可得到a[i][j][1]
和a[i][j][2]
。
同时由上面的表达式可知，要计算a[i][j][],
需先计算a[i][k][]
和a[i][k
+1][]，这里k从i到j-1，故a[i][j][]可采取如下的计算次序
1.4源代码
#include"
iostream"
algorithm"
fstream"
usingnamespacestd;
/*
f[i][j][0]表示在ch[i]~ch[j]之间以某种方式加括号后，结果为a
f[i][j][1]表示在ch[i]~ch[j]之间以某种方式加括号后，结果为b
f[i][j][2]表示在ch[i]~ch[j]之间以某种方式加括号后，结果为c
a=a*c||b*c||c*a
b=a*a||a*b||b*b
c=b*a||c*b||c*c*/
intf[50][50][3];
charchars[3]={'
a'
'
b'
c'
};
intmul（intn,charch[]）
{
for（inti=0;
i<
n;
i++）
for（intk=0;
k<
3;
k++）
f[i][i][k]=（ch[i]==chars[k]?
1:
0）;
c=b*a||c*b||c*c
*/
for（intr=1;
r<
r++）//规模
for（i=0;
n-r;
i++）//区间左端点
intj=i+r;
//区间右端点
for（intk=i;
j;
k++）//断点
f[i][j][0]+=f[i][k][0]*f[k+1][j][2]+
f[i][k][1]*f[k+1][j][2]+f[i][k][2]*f[k+1][j][0];
f[i][j][1]+=f[i][k][0]*f[k+1][j][0]+
f[i][k][0]*f[k+1][j][1]+f[i][k][1]*f[k+1][j][1];
f[i][j][2]+=f[i][k][1]*f[k+1][j][0]+
f[i][k][2]*f[k+1][j][1]+f[i][k][2]*f[k+1][j][2];
}
returnf[0][n-1][0];
intmain（）
ifstreamfin（"
mul.txt"
）;
cout<
<
"
输入字符串：
;
charch[100];
fin>
>
ch;
cout<
intn=strlen（ch）;
\n结果为a的加括号方式为：
<
mul（n,ch）<
endl;
fin.close（）;
return0;
1.5最终结果
2.动态规划解决汽车加油行驶问题
2.1问题描述
给定一个N*N的方形网络，设其左上角为起点○，坐标为（1，1），X轴向右为正，Y轴向下为正，每个方格边长为1。
一辆汽车从起点○出发驶向
右下角终点，其坐标为〔M，N〕。
在假设干网格交叉点处，设置了油库，可供汽车在行驶途中，可供汽车在行驶途中加油。
汽车在行驶过程中应遵守如下规那么：
〔1〕汽车只能沿网格边行驶，装满油后能行驶K条网格边。
出发时汽车已
装满油，在起点与终点处不设油库。
〔2〕当汽车行驶经过一条网格边时，假设其X坐标或Y坐标减小，那么应付费
用B，否那么免付费用。
〔3〕汽车在行驶过程中遇油库那么应加满油并付加油费用A。
〔4〕在需要时可在网格点处增设油库，并付增设油库费用〔C不含加油费A〕。
〔5〕〔1〕~〔4〕中的各数N，K，A，B，C均为正整数。
2.2算法设计思想
这个题目,应该说是刚开始的时候被他给吓到了，只是想着如何去把所有
的条件构造起来，然后使用网络流的方式来解决问题！
但是，如果真的是很
冷静下来好好地思考这道题目，就会发现如果没有那些限制条件，就是一个
求解最长路的题目，这样就可以直接使用ＳＰＦＡ来解决这个问题！
关键就
是在于这个每次最多只能走Ｋ个网格边，这样就是限制了活动的范围，使得
有的边无法扩展！
因此可以考虑使用这个分层思想的最短路问题！
就是通过
将每一个点进行拆分，这样，就是相当于一种分类讨论的方式！
而分类讨论
了之后，就知道哪些边是可以扩展的，哪些边是不能扩展的！
关键点就是在
于该如何选取变量来分层，这就是因情况而异了！
像这道题目之中，就是通
过油量的多少来扩展边的！
分层思想，说穿了其实就是相当于这个动态规划
之中的增加变量的方式来确定状态一样，他们的实质其实都是一样的！
2.3设计方法
采用的是动态规划的思想来解题,用备忘录的方法进行递归,递归的式子后面写出.
不能直接以汽车行驶的费用为目标来进行动态规划,因为最优子结构性质得不到证明.
所以必须把油量和费用一起考虑,作为动态规划的对象,此时就有了最优子结构性质.
最优子结构性质的证明
证明:
假设路径M是从起点◎到终点▲的一条最小费用路径,P（x,y）是M经过的一个点（非加油站）,且油量和费用为（g,c）,现假设有一条新路径Q从起点◎到点P（x,y）,使得其在P（x,y）点的油量和费用为（g,c'
）,其中c'
备忘录递归
刚开始的时候为每个网格点P（x,y）建立一个记录,初始化时,为该记录
存入一个特殊值W,表示汽车未行驶过.那么在汽车行驶过程中,对每个待求
的汽车最小费用值COST,先查看其相应的记录项C,如果存储的是初始值W,
那么表示这个点P（x,y）是第一次遇到,此时计算出该点的最小费用值,并保
存在其相应的记录项中,以备以后查看.假设记录项C中存储的不是初始值W,
那么表示该问题已经求解过了,其相应的记录项中存储的就是该点的最小费
用值COST,此时要取出记录项C的值跟最新的计算出的COST进行比拟,取其
最小的那个数存入到C中.依此建立记录项C的值,当程序递归完成时,我们
也得到了汽车行驶到（n,n）的最小费用值COST.
2.4源代码
#defineINF10000
f[i][j][0]表示汽车从网格点（1,1）行驶至网格点（i,j）所需的最少费用
f[i][j][1]表示汽车行驶至网格点（i,j）还能行驶的网格边数
s[i][0]表示x轴方向
s[i][1]表示y轴方向
s[i][2]表示行驶费用
f[i][j][0]=min{f[i+s[k][0]][[j+s[k][1]][0]+s[k][2]}
f[i][j][1]=f[i+s[k][0]][[j+s[k][1]][1]-1;
f[1][1][0]=0
f[1][1][1]=K
f[i][j][0]=f[i][j][0]+A,f[i][j][1]=K如果（i,j）是油库
f[i][j][0]=f[i][j][0]+C+A,f[i][j][1]=K（i,j）不是油库，
且f[i][j][1]=0
intN;
//
方形网络规模
intA;
汽车在行驶过程中遇到油库应加满油并付加油费A
intC;
在需要时可在网格点处增设油库，并付增设油库费用
C〔不含加
油费A〕
intB;
当汽车行驶经过一条网格边时，如果其
x坐标或y坐标减少，应
付费用B
intK;
装满油后，还能行驶K条边
intf[50][50][2];
ints[4][3]={{-1,0,0},{0,-1,0},{1,0,B},{0,1,B}};
inta[50][50];
//方形网络
intdyna（）
inti,j,k;
for（i=1;
i<
=N;
i++）
for（j=1;
j<
j++）
f[i][j][0]=INF;
f[i][j][1]=K;
f[1][1][0]=0;
f[1][1][1]=K;
intcount=1;
inttx,ty;
while（count）
count=0;
for（i=1;
for（intj=1;
j<
j++）
if（i==1&
&
j==1）
continue;
intminStep=INF;
intminDstep;
intstep,dstep;
for（k=0;
4;
k++）//
可走的四个方向
tx=i+s[k][0];
ty=j+s[k][1];
if（tx<
1||ty<
1||tx>
N||ty>
N）//
如果出界
step=f[tx][ty][0]+s[k][2];
dstep=f[tx][ty][1]-1;
if（a[i][j]==1）//
如果是油库
step+=A;
dstep=K;
if（a[i][j]==0
dstep
==0&
（i!
=N||j!
=N））//
如果不是油库
且油已经用完
step+=A+C;
if（step<
minStep）//
可以走
minStep=step;
minDstep=dstep;
if（f[i][j][0]>
如果有更优解
count++;
f[i][j][0]=minStep;
f[i][j][1]=minDstep;
returnf[N][N][0];
car.txt"
输入方格规模：
N;
\n输入装满油后能行驶的网格边数：
fin>
K;
\n输入加油费：
A;
\n输入坐标减少时应付的费用：
B;
s[2][2]=s[3][2]=B;
\n输入增设油库费用：
C;
\n输入方形网络：
\n"
for（inti=1;
a[i][j];
a[i][j]<
最优行驶路线所需的费用为：
dyna（）<
2.5最终结果
动态规划〔DynamicProgramming，DP〕思想启发于分治算法的思想，也是将复杂问题化解假设干子问题，先求解小问题，再根据小问题的解得到原问题的解。
但是DP与分治算法不同的是，DP分解的假设干子问题，往往是互相不独立的，这时如果用分治算法求解，那么会对重叠子问题重复进行求解，从而使得浪费大量的时间。
那么如果我们保存已经计算过的子问题的解，这样当再次计算该子问题时，可以直接使用，这样可以节约大量的时间。
设计动态规划的四个步骤：
1、刻画一个最优解的结构特征。
2、递归地定义最优解的值。
3、计算最优解的
值，通常采用自底向上的方法。
4、利用计算出的信息构造一个最优解。
升级会员 